Это симметричный алгоритм. Открытый текст подвергается операции "исключающее или" вместе с ключ е-вым текстом для получения шифротекста. Так как повторное применение операции XOR восстанавливает оригинал для шифрования и дешифрирования используется одна и та же программа :

P ® K = C

C © K = P

Настоящей безопасности здесь никогда не было. Этот тип шифрования легко вскрывается, даже без компь ю-тера [587, 1475]. Его взлом на компьютере занимает несколько секунд .

Предположим, что открытый текст использует английский язык. Более того, пусть длина ключа любое н е-большое число байт. Ниже описано, как взломать этот шифр:

1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений [577]. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещ е-ниями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут др у-гими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа.

2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шиф-ротекстов. Результатом операции будет удаления ключа и получение открытого текста, подвергнутого операции XOR с самим собой, смещенным на длину ключа. Так как в английском языке на один байт приходится 1.3 бита действительной информации (см раздел 11.1), существующая значительная избыточность позволяет определить способ шифрования.

Несмотря на это, количество поставщиков программного обеспечения, навязывающих этот игрушечный а л-горитм в качестве "почти такого же безопасного как DES", впечатляет [1387]. Именно этот алгоритм (с 160-битным повторяющимся "ключом") NSA в конце концов разрешило использовать в цифровых телефонных сотовых сетях для закрытия голоса. XOR может защитить ваши файлы от младшей сестры, но настоящего криптоаналитика задержит лишь на считанные секунды.

1.5 Одноразовые блокноты

Поверите или нет, но идеальный способ шифрования существует. Он называется одноразовым блокнотом и был изобретен в 1917 году Мэйджором Джозефом Моборном ( Major Joseph Mauborgne) и Гилбертом Вернамом (Gilbert Vernam) из AT&T [794]. (Фактически одноразовый блокнот представляет собой особый случай пороговой схемы, см. раздел 3.7.) В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом, написанных на кусочках бумаги и приклеенных к листу блокнота. Первоначально это была одноразовая лента для телетайпов . Отправитель использовал каждый символ ключа блокнота для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю 26 символа открытого текста и символа ключа из одн о-разового блокнота.

Каждый символ ключа используется только единожды и для единственного сообщения . Отправитель шифрует сообщения и уничтожает использованные страницы блокнота или использованную часть ленты . Получатель, в свою очередь, используя точно такой же блокнот, дешифрирует каждый символ шифротекста . Расшифровав сообщение, получатель уничтожает соответствующие страницы блокнота или часть ленты . Новое сообщение -новые символы ключа. Например, если сообщением является:

ONETIMEPAD

а ключевая последовательность в блокноте:

TBFRGFARFM

то шифротекст будет выглядеть как:

IPKLPSFHGQ так как

Q + T mod 26 = I

N + B mod 26 = P

E + F mod 26 = K

и т.д.

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

Так как все ключевые последовательности совершенно одинаковы (помните, символы ключа генерируются случайным образом), у противника отсутствует информация, позволяющая подвергнуть шифротекст криптоан а-лизу. Кусочек шифротекста может быть похож на:

POYYAEAAZX

что дешифрируется как:

SALMONEGGS

или на:

BXEGBMTMXM

что дешифрируется как: GREENFLUID

Повторю еще раз: так как все открытые тексты равновероятны, у криптоаналитика нет возможности определить, какой из открытых текстов является правильным . Случайная ключевая последовательность, сложенная с неслучайным открытым текстом, дает совершенно случайный шифротекст, и никакие вычислительные мощн ости не смогут это изменить.

Необходимо напомнить, что символы ключа должны генерироваться случайным образом . Любые попытки вскрыть такую схему сталкиваются со способом, которым создается последовательность символов ключа . Использование генераторов псевдослучайных чисел не считается, у них всегда неслучайные свойства . Если вы используете действительно случайный источник - это намного труднее, чем кажется на первый взгляд, см. ра з-дел 17.14 - это совершенно безопасно.

Другой важный момент: ключевую последовательность никогда нельзя использовать второй раз. Даже если вы используете блокнот размером в несколько гигабайт, то если криптоаналитик получит несколько текстов с перекрывающимися ключами, он сможет восстановить открытый текст . Он сдвинет каждую пару шифротекстов относительно друг друга и подсчитает число совпадений в каждой позиции. Если шифротексты смещены пр а-вильно, соотношение совпадений резко возрастет - точное значение зависит от языка открытого текста . С этой точки зрения криптоанализ не представляет труда. Это похоже на показатель совпадений, но сравниваются два различных "периода" [904]. Не используйте ключевую последовательность повторно .

Идея одноразового блокнота легко расширяется на двоичные данные. Вместо одноразового блокнота, с о-стоящего из букв, используется одноразовый блокнот из битов . Вместо сложения открытого текста с ключом одноразового блокнота используйте XOR. Для дешифрирования примените XOR к шифротексту с тем же одноразовым блокнотом. Все остальное не меняется, и безопасность остается такой же совершенной .

Все это хорошо, но существует несколько проблем . Так как ключевые биты должны быть случайными и не могут использоваться снова, длина ключевой последовательности должна равняться длине сообщения . Одноразовый блокнот удобен для нескольких небольших сообщений, но его нельзя использовать для работы по каналу связи с пропускной способностью 1.544 Мбит/с. Вы можете хранить 650 Мбайт случайных данных на CD-ROM, но и тут есть проблемы. Во первых, вам нужно только две копии случайных битов, но CD-ROM экономичны только при больших тиражах. И во вторых, вам нужно уничтожать использованные биты. Для CD-ROM нет другой возможности удалить информацию кроме как физически разрушить весь диск . Гораздо больше подходит цифровая лента.

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

Одноразовые блокноты используются и сегодня, главным образом для сверхсекретных каналов связи с ни з-кой пропускной способностью. По слухам "горячая линия" между Соединенными Штатами и бывшим Советским Союзом (а действует ли она сейчас?) шифруется с помощью одноразового блокнота . Многие сообщения советских шпионов зашифрованы с использованием одноразовых блокнотов . Эти сообщения нераскрыты сегодня и навсегда останутся нераскрытыми. На этот факт не повлияет время работы суперкомпьютеров над этой

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

1.6 Компьютерные алгоритмы

Существует множество компьютерных алгоритмов. Следующие три используются чаще всего :

- DES (Data Encryption Standard, стандарт шифрования данных) - самый популярный компьютерный алгоритм шифрования, является американским и международным стандартом . Это симметричный алгоритм, один и тот же ключ используется для шифрования и дешифрирования .

- RSA (назван в честь создателей - Ривеста (Rivest), Шамира (Sharnir) и Эдлмана (Adleman)) - самый популярный алгоритм с открытым ключом. Используется и для шифрования, и для цифровой подписи .

- DSA (Digital Signature Algorithm, алгоритм цифровой подписи, используется как часть стандарта цифр о-вой подписи, Digital Signature Standard) - другой алгоритм с открытым ключом. Используется только для цифровой подписи, не может быть использован для шифрования .

Именно эти и подобные алгоритмы описываются в этой книге .

1.7 Большие числа

На протяжении всей книги я использую различные большие числа для описания различных вещей в крипт о-графии. Так как легко заблудиться в этих числах и их значениях, физические аналоги некоторых чисел прив едены в 0-й.

Эти числа оцениваются по порядку величины и были отобраны из различных источников. Многие астроф и-зические значения объясняются в работе Фримана Дайсона ( Freeman Dyson), "Время без конца: физика и биология в открытой Вселенной" ("Time Without End: Physics and Biology in an Open Universe") в Reviews of Modem Physics, v. 52, n. 3, July 1979, pp. 447-460. Смертность в результате автокатастроф рассчитана с помощью статистики Министерства транспорта (163 смерти миллион человек в 1993 году и для средней продолжительности жизни 69.7 года.

Табл. 1-1. Большие числа

Физический аналог

Вероятность быть убитым молнией (в течение дня)

Вероятность выиграть главный приз в государственной лотерее США

Вероятность выиграть главный приз в государственной лотерее США и быть убитым молнией в течение того же дня

Вероятность утонуть (в США в течение года)

Вероятность погибнуть в автокатастрофе (в США в году)

Вероятность погибнуть в автокатастрофе (в США в течение времени жизни)

Время до следующего оледенения

Время до превращения Солнца в сверхновую звезду

Возраст планеты

Возраст Вселенной

Число атомов планеты

Число атомов Солнца

Число атомов галактики

Число атомов Вселенной

Объем Вселенной

Число

1 из 9 миллиардов (233)

1 из 4000000 (222) 1 из261

1 из 59000 (216) 1 из 6100 (213) 1 из 88 (27) 14000 (214) лет 109 (230) лет 109 (230) лет 1010 (234) лет 1051 (2170) 1057 (2190) 1067 (2223) 1077 (2265) 1084 (2 280) см 3

Если Вселенная конечна: