(е и (р- 1) х (q — 1) должны быть взаимно простыми[39], но это — техническая сторона дела).
(3) Алиса может теперь опубликовать е и N в чем-то сродни телефонному справочнику. Поскольку эти два числа необходимы для зашифровывания, они должны быть доступны всем, кто захочет зашифровать сообщение для Алисы. Вместе эти числа называются открытым ключом. (Это число е может являться частью открытого ключа не только Алисы, но и любого другого человека. Однако у всех остальных должны быть иные значения N, которые зависят от выбора р и q.)
(4) Перед тем как приступить к зашифровыванию сообщения, оно должно быть вначале преобразовано в число М. Например, слово заменяется на двоичные цифры ASCII-кода, а эти двоичные цифры могут рассматриваться как десятичное число. После этого М зашифровывается, образуя шифртекст С, по формуле:
С= Me(mod N)
(5) Представьте, что Боб хочет послать Алисе простой поцелуй — всего лишь букву X. В ASCII-коде она представляется числом 1011000, которое эквивалентно 88 в десятичном виде. Поэтому М — 88.
(6) Чтобы зашифровать это сообщение, Боб начинает разыскивать открытый ключ Алисы и находит, что N= 187, а е = 7. Это дает ему формулу шифрования, необходимую, чтобы зашифровывать сообщения для Алисы. При М= 88 формула имеет вид:
С = 887 (mod 187)
(7) Вычислить ее на калькуляторе непросто, поскольку дисплей не способен справиться с такими огромными числами. В модулярной арифметике есть, однако, способ вычисления экпоненциальных функций. Мы знаем, что, поскольку 7 = 4 + 2+ 1, то:
887 (mod 187) = [884 (mod 187) х 882 (mod 187) х 881] (mod 187)] (mod 187) 881 = 88 = 88 (mod 187)
882 = 7744 = 77 (mod 187)
884 = 59969536 = 132 (mod 187)
887 = 881 х 882 х 884 = 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)
М= 1123 (mod 187)
M = [111(mod 187) х 112(mod 187) х 114(m od 187) х 1116(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].
Длина ключа — при компьютерном шифровании используются ключи, которые являются числами. Длина ключа относится к количеству цифр или битов в ключе и, таким образом, указывает самое большое число, которое может быть использовано в качестве ключа, задавая тем самым число возможных ключей. Чем больше длина ключа (или чем больше число возможных ключей), тем больше времени потребуется криптоаналитику, чтобы проверить все ключи.
Закодировать — преобразовать исходное сообщение в закодированное.
Зашифровать — преобразовать исходное сообщение в зашифрованное.
Квантовый компьютер — чрезвычайно мощный компьютер, который использует квантовую теорию, в частности, теорию, что объект может одновременно находиться во многих состояниях (суперпозиция), или теорию, что объект может одновременно находиться во многих мирах. Если бы ученые смогли создать квантовый компьютер, это поставило бы под угрозу стойкость всех нынешних шифров, за исключением шифра одноразового шифрблокнота.
Квантовая криптография — нераскрываемая форма криптографии, в которой применяется квантовая теория, в частности, принцип неопределенности, который гласит, что нельзя измерить все параметры объекта с абсолютной точностью. Квантовая криптография гарантирует безопасный обмен случайной последовательностью битов, которая затем используется в качестве основы для шифра одноразового шифрблокнота.
Ключ — элемент, который преобразует общий алгоритм шифрования в конкретный способ шифрования. Вообще говоря, противник может знать алгоритм шифрования, используемый отправителем и получателем, но следует приложить все силы, чтобы он не узнал ключ.
Код — система, предназначенная для скрытия содержания сообщения путем замены каждого слова или фразы в исходном сообщении другим символом или набором символов. Таблица замен содержится в кодовой книге. (Другое определение кода: это любая форма шифрования, которая не обладает внутренней гибкостью, то есть существует только один ключ — кодовая книга.)
Кодовая книга — таблица замен слов или фраз в исходном сообщении.
Криптоанализ — наука получения открытого текста из шифртекста без знания ключа.
Криптография — наука зашифровывания сообщения или наука скрытия содержания сообщения. Иногда этот термин используется в более широком смысле для обозначения науки, так или иначе связанной с шифрами, и является другим названием криптологии.
Криптография с асимметричным ключом — вид криптографии, в которой ключ, необходимый для зашифровывания, не совпадает с ключом, требующимся для расшифровывания. Описывает системы шифрования с открытым ключом, такие как RSA.
Криптография с симметричным ключом — вид криптографии, в которой ключ, необходимый для зашифровывания, совпадает с ключом, необходимым для расшифровывания. Данным термином описываются все традиционные виды шифрования, то есть те, которые использовались до 70-х годов.
