Книга шифров

(4) Перед тем как приступить к зашифровыванию сообщения, оно должно быть вначале преобразовано в число M. Например, слово заменяется на двоичные цифры ASCII-кода, а эти двоичные цифры могут рассматриваться как десятичное число. После этого M зашифровывается, образуя шифртекст С, по формуле:

С= Me (mod N)

(5) Представьте, что Боб хочет послать Алисе простой поцелуй — всего лишь букву X . В ASCII-коде она представляется числом 1011000, которое эквивалентно 88 в десятичном виде. Поэтому M — 88.

(6) Чтобы зашифровать это сообщение, Боб начинает разыскивать открытый ключ Алисы и находит, что N = 187, а e = 7. Это дает ему формулу шифрования, необходимую, чтобы зашифровывать сообщения для Алисы. При M = 88 формула имеет вид:

С = 887 (mod 187)

(7) Вычислить ее на калькуляторе непросто, поскольку дисплей не способен справиться с такими огромными числами. В модулярной арифметике есть, однако, способ вычисления экпоненциальных функций. Мы знаем, что, поскольку 7 = 4 + 2 + 1, то:

887 (mod 187) = [884 (mod 187) x 882 (mod 187) x 881] (mod 187)] (mod 187) 881 = 88 = 88 (mod 187)

882 = 7744 = 77 (mod 187)

884 = 59969536 = 132 (mod 187)

887 = 881 x 882 x 884 = 88 x 77 x 132 = 894432 = 11 (mod 187)

Теперь Боб отправляет Алисе зашифрованный текст: С = 11.

(8) Мы знаем, что экпоненциальные функции в модулярной арифметике являются односторонними функциями, поэтому двигаться в обратном направлении и восстановить из С = 11 исходное сообщение M исключительно сложно. Так что Ева дешифровать сообщение не сможет.

(9) Алиса, однако, способна расшифровать его, поскольку у нее есть определенная специальная информация: ей известны значения p и q. Она вычисляет особое число d — ключ для расшифровывания, иначе известный как ее секретный ключ. Число d рассчитывается по следующей формуле:

e x d = 1 (mod (p - 1) $x (q — 1))

7 x d (mod 16 $x 10)

7 x d = 1 (mod 160)

d = 23

(Вычислить значение d не просто, но с помощью метода, известного как алгоритм Евклида, Алиса сможет быстро и без труда найти d.)

(10) Чтобы расшифровать сообщение, Алиса просто воспользуется следующей формулой:

M = Cd (mod 187)

M = 1123 (mod 187)

M = [111(mod 187) x 112(mod 187) x 114(m od 187) x 1116(mod 187)] (mod 187)

M = 11 x 121 x 55 x 154 (mod 187)

M = 88 = X в виде ASCII-кода