Криптосистема RSA

Question

Привет, я пытаюсь настроить криптосистему RSA, у меня есть все значения, кроме d выбранных простых чисел: p=1889, q=2003, n=3783667, phi=3779776, e= 61

я застрял в поиске d, может ли кто-нибудь помочь мне разобраться в этом?

Настройка криптосистемы RSA

• Два больших различных простых числа p и q выбираются, и n = pq и Φ(n) = (p − 1)(q − 1) рассчитываются.

• Целое число e выбирается таким образом , чтобы gcd(Φ(n), e) = 1 и мультипликативный обратный d = e^(−1) в ZΦ(n) вычисляется, т. е.

  ed ≈ 1 (mod Φ(n)).

• Цифры p, q, и Φ(n), затем отбрасываются.

• Пара (e, n) публикуется как открытый ключ шифрования
• Число d является секретным ключом дешифрования.

Answer 1

Вот алгоритм, шаг за шагом, включая поиск d.
m из статьи следует, что ваш Φ(n).
Теперь вы пытаетесь найти d = (1 + нм) / e, работая через значения n до тех пор, пока не будет получено целочисленное решение для e найден.

Редактировать:Здесь вы найдете более подробное объяснение всего алгоритма.