RSA: вычисление частных ключей с расширенным евклидовым алгоритмом

Я ученик средней школы, пишущий статью о 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 часов и искал ответ повсюду. Я выполняю расширенный алгоритм Евклида вручную, но поскольку результат работает, мои вычисления должны быть правильными.

Спасибо заранее,

Мадс

Ответы

Ответ 1

Ты так близко, что будешь пинать себя.

3168-887 = 2281.

В частности, если у вас есть mod x, то A должен удовлетворять 0<=a<x. Если это не так, добавьте или вычтите x столько раз, сколько необходимо, пока вы не попадете в этот диапазон. Это называется модульной арифметикой.

Возможно, вы захотите ознакомиться с линейными конгруэнциями и теорией чисел. Эти темы - математика уровня в Великобритании (что бы вы назвали колледжом, я думаю), так что не волнуйтесь, если это кажется немного странным. Линейная конгруэнция просто говорит, что -887 mod 3168 и 2281 mod 3168 на самом деле одно и то же, потому что они являются частью одного и того же класса, класс, который оказывается в 2281 mod 3168 в требуемом диапазоне. 2281+3168 mod 3168 также будет в этом классе.

Удачи!

P.S. PARI/GP - теоретик полезности, используемый для расчетов. Возможно, стоит посмотреть.