Я ученик средней школы, пишущий документ по RSA, и я делаю пример с очень маленькими простыми числами. Я понимаю, как работает система, но я не могу на всю жизнь вычислить закрытый ключ с использованием расширенного евклидова алгоритма.RSA: вычисление частных ключей с расширенным евклидовым алгоритмом
Вот что я сделал до сих пор:
- Я выбрал простые числа р = 37 и д = 89 и рассчитывается N = 3293
- Я вычислил (р-1) (д -1) = 3168
- Я выбрал число e, так что e и 3168 взаимно просты. Я проверяю это на стандартный алгоритм евклидова, и это работает очень хорошо. Мой е = 25
Теперь я просто вычислить закрытый ключ д, который должен удовлетворять Ed = 1 (по модулю 3168)
С помощью расширенного алгоритма Евклида найти д такое, что де + Tn = 1 Я получаю -887 • 25 + 7 • 3168 = 1. Я бросаю 7 и получаю d = -887. Однако, пытаясь расшифровать сообщение, это не сработает.
Я знаю из своей книги, что d должно быть 2281, и это работает, но я не могу понять, как они доходят до этого числа.
Может ли кто-нибудь помочь? Я пробовал решить эту проблему в течение последних 4 часов и искал ответ повсюду. Я выполняю расширенный алгоритм Евклида вручную, но поскольку результат работает, мои вычисления должны быть правильными.
Спасибо заранее,
Мадс
Как отмечают Девятимерные фигуры, используйте положительный остаток. Эквивалентно, чтобы поднять что-то к отрицательной силе 'x' сначала вычислить ее обратную, а затем поднять ее до (' -x') мощности ('-x' положительно, так как' x' отрицательно). –
Я смущен, как вы получаете «de + tN = 1» -887 • 25 + 7 • 3168 = 1. Я понимаю, что e = 25, но d, t и N не имеют смысла. Что означают d, t и N? И почему вы позволили выбросить 7? Casey –