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

Что такое RSA?

RSA — это аббревиатура, которая расшифровывается как Rivest, Shamir, Adleman. Эти люди создали криптографический алгоритм, который и получил это название. Несмотря на то, что алгоритм был создан в 1976 году, он до сих пор остаётся популярным.

Как работает RSA

RSA работает следующим образом. Создаются два ключа — открытый и закрытый. Закрытый ключ владелец должен держать у себя и хранить в тайне, открытый же может распространять всем желающим. Допустим, 2 человека хотят вести тайную переписку. Пускай одного из них зовут Владимир Владимирович, а другого Дмитрий Анатольевич. При этом есть третий участник процесса — Борис Абрамович, которому очень интересно прочитать их переписку. Тогда ВВ и ДА создают каждый по паре ключей, обмениваются по электронной почте открытыми ключами. БА, при этом перехватывает открытый ключ каждого, но это ему, как мы увидим дальше, не сильно поможет. Далее, ВВ шифрует своё послание открытым ключом ДА и посылает второму зашифрованное сообщение. БА опять-таки его перехватывает, но ничего поделать не может, т.к. для прочтения ключа ему нужен закрытый ключ ДА, а ДА в свою очередь расшифровывает полученное сообщение, используя свой закрытый ключ, и только он и ВВ знают, что именно написано в этом сообщении.

Математическая сторона вопроса

Для более пытливых читателей, рассмотрим сам алгоритм шифрования и дешифрования. Пусть у нас есть пара ключей <P, S> ( Public — открытый; Secret — закрытый). Покажем как они формируются.

Выберем два простых числа p и q.

N=p*q

T = (p-1)(q-1)

Теперь выберем за E число, не имеющее общих простых делителей с T; выберем такое D что D*E = 1, по модулю T. То есть

D*E = 1 mod T. mod — означает взятие остатка от деления по модулю T, то есть 5 mod 3 = 3*1 + 2 mod 3 = 2. Для удобства, я буду писать mod не в каждой выкладке, а только в тех, где mod будет использоваться для осуществления перехода или же в конце формулы, чтобы подчеркнуть, что мы работали в mod N или mod T.

Шифрование происходит следующим образом: сообщение M шифруется открытым ключом P( M ) = M^E mod N = C ( Ciphertext — зашифрованное сообщение ), а дешифруется закрытым ключом

S( C ) = C^D = (M^E)^D = M^E*D mod N = M¹ = M.

Теперь следует пояснить математический смысл этих шаманских действий.

Первый логичный вопрос — зачем было выбирать именно два простых числа, когда сделать вычисление по mod можно сделать и без этого. Суть в том, что за T на самом деле стоит ф( N ) — функция Эйлера, и благодаря её свойствам этот алгоритм оказался таким хорошим.

ф( n ) ставит натуральному числу n в соответствие количество чисел, взаимно простых с ним, и не превышающих n.

Введём ещё одно понятие — Z_L. Это группа целых чисел, в которых математические операции выполняются по mod L.

Почему мы выбираем E взаимно простым с T? Мы делаем это для того, чтобы уравнение E*D = 1 mod T имело решение. Более того, оно будет единственным.

Пускай, E не взаимно просто с T и имеет с T общий делитель Q. Тогда

E*X = 1 mod T <=> E*X = A*T + 1 = Q*B, где B — целое число. Но т.к. T делится на Q, то и 1 делится на Q, что невозможно, т.к. в Z_T 1*B = 0 <=> B делится на T.

По теореме Эйлера

a^{ф( N )} = 1

для всех a из Z_N.

Применим эту теорему для нашего случая

E*D = 1 mod T <=> E*D = 1 + k(p-1)(q-1), где k — некоторое целое число.
M^E*D=M^{1 + k(p-1)(q-1)}=M*M^k(p-1)(q-1)
Покажем, что M^E*D = M mod p

M*M^k(p-1)(q-1) = M*(M^(p-1))^k(q-1) mod p = M*(1)^k(q-1) = M

Здесь теорема Эйлера скрывается в переходе M^(p-1) = 1 mod p. Внимательный читатель мог легко заметить, что ф(p) = p-1 для простого числа p. Действительно, все числа до p, за исключением 1 взаимно просты с ним.

Аналогично M^E*D = M mod q. Таким образом, M^E*D = M mod pq

Итак, мы показали, что алгоритм RSA корректен. Но очевидно же, что p, q, D можно подобрать брутфорсным методом! Фактически, в открытом ключе уже лежит пара E, N. Но тут опять в игру вступает математика — если p и q достаточно большие числа, то с разложением E на множители суперкомпьютер будет справляться очень долго. В разных статьях и книжках можно найти цифры от 100 лет, до возраста вселенной. Эти цифры зависят от величины p и q.

Цифровые подписи

Опять вернёмся к практической стороне вопроса. В нашем примере, Борис Абрамович перехватил открытые ключи и может посылать Владимиру Владимировичу и Дмитрию Анатольевичу всякие непотребные письма от чужого имени, например содержащие вирусы. Из предыдущего раздела ясно, что если открытый и закрытый ключ поменять местами, то работа алгоритма по сути не изменится. То есть

P( S( M ) ) = S( P( M ) ) = M.

На этой идее и основывается цифровая подпись с использованием RSA. Текст M' Шифруется закрытым ключом и ВВ посылает ДА пару ( M', S( M' ) ) — ДА может проверить эту пару на соответствие, а БА не может подсунуть ДА такую пару, т.к. у него нет закрытого ключа ВВ.

В следующих постах я планирую рассказать о применении RSA в почтовых клиентах Thunderbird и The Bat, а также подробнее написать про цифровую подпись.