Саймон Сингх - Книга шифров .Тайная история шифров и их расшифровки

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

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

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

( е и (р- 1) х (q — 1) должны быть взаимно простыми [39] Числа называются взаимно простыми, если их наибольший делитель равен единице. — Прим. пер. , но это — техническая сторона дела).

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

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

С= M e (mod N)

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

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

С = 88 7(mod 187)

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

88 7(mod 187) = [88 4(mod 187) х 88 2(mod 187) х 88 1] (mod 187)] (mod 187) 88 1= 88 = 88 (mod 187)

88 2= 7744 = 77 (mod 187)

88 4= 59969536 = 132 (mod 187)

88 7= 88 1х 88 2х 88 4= 88 х 77 х 132 = 894432 = 11 (mod 187)

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

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

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

е х d = 1 (mod ( р- 1) $х (q — 1))

7 х d (mod 16 $x 10)

7 x d = 1 (mod 160)

d = 23

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

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

М= С d (mod 187)

М= 11 23(mod 187)

M = [11 1(mod 187) х 11 2(mod 187) х 11 4(m od 187) х 11 16(mod 187)] (mod 187)

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

М = 88 = Х в виде ASCII-кода

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

ASCII— американский стандартный код для обмена информацией; стандарт для перевода букв и других символов в числа.

DES— стандарт шифрования данных, разработан IBM и принят в качестве стандарта в 1976 году.

Pretty Good Privacy (PGP) («Вполне достаточная секретность») — алгоритм компьютерного шифрования, разработанный Филом Циммерманом на основе RSA.

RSA— первая система, которая удовлетворяла условиям шифрования с открытым ключом; была придумана Роном Ривестом, Ади Шамиром и Леонардом Адлеманом в 1977 году.

Агентство национальной безопасности (АНБ) — подразделение министерства обороны США, отвечающее за безопасность американских средств связи и за проникновение в линии связи других стран.

Алгоритм шифрования— любой общий процесс зашифровывания, который может быть строго определен выбором ключа.

Декодировать— преобразовать закодированное сообщение обратно в исходное.

Депонирование ключей— схема, когда пользователи отдают на хранение копии своих секретных ключей заслуживающему доверия третьему лицу, эскроу-агенту, который передает их сотрудникам правоприменяющих органов только в определенных ситуациях, например, по распоряжению суда.

Дешифровать— преобразовать зашифрованное сообщение обратно в исходное сообщение. Формально данный термин относится только к получателю данного сообщения, который знает ключ, необходимый для того, чтобы получить открытый текст, но в действительности также относится к криптоанализу, при котором дешифрование осуществляется противником, перехватившим сообщение [40] Как правило, данный термин употребляется, если ключ неизвестен; если же он известен, то вместо дешифровать, дешифрование используется расшифровать, расшифровывание. В этом смысле в названии книги следовало бы употребить более корректный, но менее расхожий термин, «дешифрование»: «Тайная история шифров и их дешифрования». — Прим. пер. .

Длина ключа— при компьютерном шифровании используются ключи, которые являются числами. Длина ключа относится к количеству цифр или битов в ключе и, таким образом, указывает самое большое число, которое может быть использовано в качестве ключа, задавая тем самым число возможных ключей. Чем больше длина ключа (или чем больше число возможных ключей), тем больше времени потребуется криптоаналитику, чтобы проверить все ключи.

Закодировать— преобразовать исходное сообщение в закодированное.