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

Самым известным роторным устройство является Энигма (Enigma). Энигма использовалась немцами во Второй мировой войне. Сама идея пришла в голову Артуру Шербиусу (Arthur Scherbius) и Арвиду Герхарду Дамму (Arvid Gerhard Damm) в Европе. В Соединенных Штатах она была запатентована Артуром Шербиусом [1383]. Немцы значительно усовершенствовали базовый проект для использования во время войны .

У немецкой Энигмы было три ротора, котроые можно было выбрать из пяти возможных, коммутатор, кот о-рый слегка тасовал открытый текст, и отражающий ротор, который заставлял каждый ротор обрабатывать о т-крытый текст каждого письма дважды . Несмотря на сложность Энигмы, она была взломана в течение Второй мировой войны. Сначала группа польских криптографов взломала немецкую Энигму и объяснила раскрытый алгоритм англичанам. В ходе войны немцы модифицировали Энигму, а англичане продолжали криптоанализ новых версий. Объяснение работы роторных шифров и способов их раскрытия можно найти в [794, 86, 448, 498, 446, 880, 1315, 1587, 690]. В двух следующих отчетах увлекательно рассказывается о взломе Энигмы [735,

Для дальнейшего чтения

Данная книга не является книгой по классической криптографии, поэтому далее я не буду подробно остана вливаться на этих предметах. Прекрасными книгами по докомпьютерной криптологии являются [587, 1475]. [448] содержит современный криптоанализ шифровальных машин . Дороти Деннинг (Dorothy Denning) рассматривает многие из этих шифров в [456], а [880] содержит беспристрастный сложный математический анализ тех же самых шифров. Другим описанием старой криптографии, описывающим аналоговую криптографию, являе т-ся [99]. Прекрасный обзор выполнен в статье [579]. Великолепны также книги по исторической криптографии

Дэвида Кана [794, 795, 796].

1.4 Простое XOR

XOR представляет собой операцию "исключающее или": ,Л в языке C или Q в математической нотации. Это обычная операция над битами:

0 © 0 = 0

0© 1 = 1

1© 0 = 1 1 © 1 = 0

Также заметим, что:

a © a = 0 a © b © b = a

Казалось бы, запутанный алгоритм простого XOR по сути является ничем иным, как полиалфавитным ши ф-ром Вигенера. Здесь он упоминается только из-за распространенности в коммерческих программных продуктах, по крайней мере в мире MS-DOS и Macintosh [1502, 1387]. К сожалению, если о программе компьютерной безопасности заявляется, что это "патентованный" алгоритм шифрования, значительно более быстрый, чем DES, то скорее всего используется какой-то вариант следующего .

/* Использование: crypto key input file output file */

void main (int argc, char *argv[])

FILE *fl, *fo; char *cp; int c;

if ((cp = argv[l]) && *cp!= \0) {

if ((fi = fopen(argvl[2], "rb")) != NULL) {

if ((fo = fopen(argv[3], "wb")) != NULL) { while ((c = getc(fi)) != EOF) { if (!*cp) cp = argv[1]; cA= *(cp++); putc(c,fo);

fclose(fo);

fclose(fi);

Это симметричный алгоритм. Открытый текст подвергается операции "исключающее или" вместе с ключ е-вым текстом для получения шифротекста. Так как повторное применение операции 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 нет другой возможности удалить информацию кроме как физически разрушить весь диск . Гораздо больше подходит цифровая лента.

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

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