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

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

20 голосов
/ 12 декабря 2010

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

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

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

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

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

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

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

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

Мадс

1 Ответ

20 голосов
/ 12 декабря 2010

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

3168-887 = 2281.

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

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

Веселись!

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

...