Приложение J Математика RSA

Ниже в несложном виде дается математическое описание принципа шифрования и дешифрования с помощью RSA.

(1) Алиса выбирает два гигантских простых числа p и q. Простые числа должны быть громадными, но мы, для простоты, предположим, что Алиса выбрала числа p = 17, q = 11. Она должна хранить эти числа в секрете.

(2) Алиса перемножает их и получает число N. В нашем случае N = 187. Теперь она выбирает еще одно число — e; в нашем случае она выбрала e = 7.

(e и (p - 1) x (q — 1) должны быть взаимно простыми[39], но это — техническая сторона дела).

(3) Алиса может теперь опубликовать e и N в чем-то сродни телефонному справочнику. Поскольку эти два числа необходимы для зашифровывания, они должны быть доступны всем, кто захочет зашифровать сообщение для Алисы. Вместе эти числа называются открытым ключом. (Это число e может являться частью открытого ключа не только Алисы, но и любого другого человека. Однако у всех остальных должны быть иные значения N, которые зависят от выбора p и q.)

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

С= M^e(mod N)

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

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

С = 88⁷ (mod 187)

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

88⁷ (mod 187) = [88⁴ (mod 187) x 88² (mod 187) x 88¹] (mod 187)] (mod 187) 88¹ = 88 = 88 (mod 187)

88² = 7744 = 77 (mod 187)

88⁴ = 59969536 = 132 (mod 187)

88⁷ = 88¹ x 88² x 88⁴ = 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 = C^d (mod 187)

M = 11²³ (mod 187)

M = [11¹(mod 187) x 11²(mod 187) x 11⁴(m od 187) x 11¹⁶(mod 187)] (mod 187)

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

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

Ривест, Шамир и Адлеман создали специальную одностороннюю функцию — функцию, которая может быть обращена только тем человеком, который имеет доступ x сугубо конфиденциальной информации, то есть к значениям чисел p и q. Каждая функция может быть индивидуализирована путем выбора р и q, которые перемножаются для получения N. Эта функция позволяет всем зашифровывать сообщения для конкретного лица, используя для этого полученное им число N, но только тот, кому предназначено это сообщение, сможет расшифровать его, поскольку только он знает p и q, следовательно, только он знает ключ для расшифровывания d.