RSA: вычисление закрытого ключа с помощью расширенного алгоритма Евклида

Я учусь в старшей школе и пишу статью об RSA, и я делаю пример с очень маленькими простыми числами. Я понимаю, как работает система, но я не могу вычислить закрытый ключ, используя расширенный алгоритм Евклида.

Вот что я сделал до сих пор:

  • Я выбрал простые числа p=37 и q=89 и вычислил N=3293.
  • Я вычислил (p-1)(q-1)=3168
  • Я выбрал число e так, чтобы e и 3168 были относительно простыми. Я проверяю это с помощью стандартного алгоритма Евклида, и он работает очень хорошо. мой е=25

Теперь мне просто нужно вычислить закрытый ключ d, который должен удовлетворять ed=1 (mod 3168)

Используя расширенный алгоритм Евклида, чтобы найти такое d, что de+tN=1, я получаю -887•25+7•3168=1. Я отбрасываю 7 и получаю d=-887. Однако попытка расшифровать сообщение не работает.

Я знаю из своей книги, что d должно быть 2281, и это работает, но я не могу понять, как они получают это число.

Кто-нибудь может помочь? Я пытался решить эту проблему в течение последних 4 часов и везде искал ответ. Я выполняю расширенный алгоритм Евклида вручную, но, поскольку результат работает, мои расчеты должны быть правильными.

Заранее спасибо,

Мадс


rsa private-key algorithm greatest-common-divisor
person mads    schedule 12.12.2010    source источник
comment
Как заметил Девятипалый, просто используйте положительный остаток. Эквивалентно, чтобы возвести что-то в отрицательную степень x, сначала вычислить обратное значение, а затем возвести его в степень (-x) (-x положительно, так как x отрицательно).   -  person President James K. Polk    schedule 13.12.2010
comment
Я запутался, как вы получаете de+tN=1 -887•25+7•3168=1. Я понимаю, что e = 25, но d, t и N не имеют смысла. Что означают d, t и N? И почему вам разрешено выбрасывать 7? Кейси   -  person    schedule 31.10.2011

Ответы (1)


arrow_upward
20
arrow_downward

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

3168-887=2281.

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

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

Повеселись!

P.S. PARI/GP — это число полезности, которое теоретики используют для расчетов. Может стоит посмотреть.

person Community    schedule 12.12.2010