Я ученик средней школы, пишущий статью о RSA, и я делаю пример с очень маленькими простыми числами. Я понимаю, как работает система, но я не могу на всю жизнь вычислить закрытый ключ с использованием расширенного евклидова алгоритма.
Вот что я сделал до сих пор:
- Я выбрал простые числа p = 37 и q = 89 и рассчитано N = 3293
- Я вычислил (p-1) (q-1) = 3168
- Я выбрал число e так, чтобы e и 3168 были взаимно простыми. Я проверяю это на стандартный алгоритм евклидова, и это работает очень хорошо. Мой e = 25
Теперь мне просто нужно вычислить закрытый ключ d, который должен удовлетворять ed = 1 (mod 3168)
Используя Extended Euclidean Algorithm, чтобы найти d таких, что de + tN = 1, я получаю -887 • 25 + 7 • 3168 = 1. Я бросаю 7 и получаю d = -887. Однако, пытаясь расшифровать сообщение, это не сработает.
Я знаю из своей книги, что d должно быть 2281, и это работает, но я не могу понять, как они достигают этого числа.
Может ли кто-нибудь помочь? Я пробовал решить эту проблему в течение последних 4 часов и искал ответ повсюду. Я выполняю расширенный алгоритм Евклида вручную, но поскольку результат работает, мои вычисления должны быть правильными.
Спасибо заранее,
Мадс
