Times, a пьесу Шекспира или телеконференцию в Internet [1584,1585]. Этот тип стеганографии не одурачит человека, но может обмануть большой компьютер, ищущий нужную информацию в Internet.

1.3 Подстановочные и перестановочные шифры

До появления компьютеров криптография состояла из алгоритмов на символьной основе . Различные криптографические алгоритмы либо заменяли одни символы другими, либо переставляли символы. Лучшие алгоритмы делали и то, и другое, и по много раз.

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

Подстановочные шифры

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

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

- Однозвучный подстановочный шифр похож на простую подстановочную криптосистему за исключ е-нием того, что один символ открытого текста отображается на несколько символов шифротекста . Например, "A" может соответствовать 5, 13, 25 или 56, "B" - 7, 19, 31 или 42 и так далее.

- Полиграмный подстановочный шифр - это шифр, который блоки символов шифрует по группам . Например, "ABA" может соответствовать "RTQ", "ABB" может соответствовать "SLL" и так далее.

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

Знаменитый шифр Цезаря, в котором каждый символ открытого текста заменяется символом, находящег о-ся тремя символами правее по модулю 26 ("A" заменяется на "D," "B" - на "E", ... "W" - на " Z ", "X" - на "A", "Y" - на "B", "Z" - на "C"), представляет собой простой подстановочный фильтр . Он действительно очень прост, так как алфавит шифротекста представляет собой смещенный, а не случайно распределенный алфавит открыт ого текста.

ROTI3 - это простая шифровальная программа, обычно поставляемая с системами UNIX. Она также является простым подстановочным шифром. В этом шифре "A" заменяется на "N," "B" - на "O" и так далее. Каждая буква смещается на 13 мест. Шифрование файла программой ROTI3 дважды восстанавливает первоначальный файл.

P = ROT13 (ROT13 (P))

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

Простые подстановочные шифры легко раскрываются, так как шифр не прячет частоты использования ра з-личных символов в открытом тексте . Чтобы восстановить открытый текст, хорошему криптоаналитику требуе т-ся только знать 26 символов английского алфавита [1434]. Алгоритм вскрытия таких шифров можно найти в [578, 587, 1600, 78, 1475, 1236, 880]. Хороший компьютерный алгоритм приведен в [703].

Однозвучные подстановочные шифры использовались уже в 1401 году в герцогстве Мантуа [794]. Они более сложны для вскрытия, чем простые подстановочные шифры, хотя и они не скрывают всех статистических свойств языка открытого текста. При помощи вскрытия с известным открытым текстом эти шифры раскрыв а-ются тривиально. Вскрытие с использованием только шифротекста более трудоемко, но и оно занимает на ко м-пьютере лишь несколько секунд. Подробности приведены в [1261].

Полиграмные подстановочные шифры - это шифры, которые кодируют сразу группы символов . Шифр Play-fair ("Честная игра"), изобретенный в 1854 году, использовался англичанами в Первой мировой войне [794]. Он шифрует пары символов, и его криптоанализ обсуждается в [587,1475,880]. Другим примером полиграмного подстановочного шифра является шифр Хилла (Hill) [732]. Иногда можно видеть как вместо шифра используется кодирование по Хаффману (Huffman), это небезопасный полиграмный подстановочный шифр .

Полиалфавитные подстановочные шифры были изобретены Лином Баттистой ( Lean Battista) в 1568 году

[794]. Они использовались армией Соединенных Штатов в ходе Гражданской войны в Америке . Несмотря на то, что они легко могут быть взломаны [819, 577, 587, 794] (особенно с помощью компьютеров), многие коммерческие продукты компьютерной безопасности используют такие шифры [1387,1390, 1502]. (Подробности того, как вскрыть эту схему шифрования, используемую программой WordPerfect, можно найти в [135,139].) Шифр Вигенера (Vigenere), впервые опубликованный в 1586 году, и шифр Бофора (Beaufort) также являются примерами полиалфавитных подстановочных шифров.

У полиалфавитных подстановочных шифров множественные однобуквенные ключи, каждый из которых и с-пользуется для шифрования одного символа открытого текста. Первым ключом шифруется первый символ о т-крытого текста, вторым ключом - второй символ, и так далее. После использования всех ключей они повтор я-ются циклически. Если применяется 20 однобуквенных ключей, то каждая двадцатая буква шифруется тем же ключом. Этот параметр называется периодом шифра. В классической криптографии шифры с длинным периодом было труднее раскрыть, чем шифры с коротким периодом. Использование компьютеров позволяет легко раскрыть подстановочные шифры с очень длинным периодом .

Шифр с бегущим ключом (иногда называемый книжным шифром), использующий один текст для шифр о-вания другого текста, представляет собой другой пример подобного шифра . И хотя период этого шифра равен длине текста, он также может быть легко взломан [576,794].

Перестановочные шифры

В перестановочном шифре меняется не открытый текст, а порядок символов. В простом столбцовом перестановочном шифре открытый текст пишется горизонтально на разграфленном листе бумаги фиксирова н-ной ширины, а шифротекст считывается по вертикали (см. -3-й). Дешифрирование представляет собой запись шифротекста вертикально на листе разграфленной бумаги фиксированной ширины и затем считывание откр ы-того текста горизонтально.

Криптоанализ этих шифров обсуждается в [587,1475]. Так как символы шифротекста те же, что и в открытом тексте, частотный анализ шифротекста покажет, что каждая буква встречается приблизительно с той же частотой, что и обычно. Это даст криптоаналитику возможность применить различные методы, определяя пр а-вильный порядок символов для получения открытого текста . Применение к шифротексту второго перестаново ч-ного фильтра значительно повысит безопасность. Существуют и еще более сложные перестановочные фильтры, но компьютеры могут раскрыть почти все из них .

Немецкий шифр ADFCVX, использованный в ходе Первой мировой войны , представлял собой перестановочный фильтр в сочетании с простой подстановкой . Этот для своего времени очень сложный алгоритм был раскрыт Жоржем Пенвэном (Georges Painvin), французским криптоаналитиком [794].

Хотя многие современные алгоритмы используют перестановку, с этим связана проблема использования большого объема памяти, а также иногда требуется работа с сообщениями определенного размера . Подстановка более обычна.

Роторные машины

В 1920-х годах для автоматизации процесса шифрования были изобретены различные механические устро й-ства. Большинство использовало понятие ротора, механического колеса, используемого для выполнения по д-становки.

Роторная машина, включающая клавиатуру и набор роторов, реализует вариант шифра Вигенера. Каждый ротор представляет собой произвольное размещение алфавита, имеет 26 позиций и выполняет простую подст а-новку. Например, ротор может быть использован для замены "A" на " F", "B" на "U", "C" на "I" и так далее. Выходные штыри одного ротора соединены с входными штырями следующего ротора.

Открытый TеKCT:COMPUTER graphics may be slow but at least ITS EXPENSIVE.

COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVE

Шифротекст:cAELP opsee mhlan pioss ucwti tcbiv emute ratsg yaerb tx

Рис. 1-4. Столбцовый перестановочный фильтр.

Например, в четырехроторной машине первый ротор может заменять "A" на " F", второй - "F" на "Y", третий - "Y" на "E" и четвертый - "E" на "C", "C" и будет конечным шифротекстом. Затем некоторые роторы смещаются, и в следующий раз подстановки будут другими .

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

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

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

796].

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

Данная книга не является книгой по классической криптографии, поэтому далее я не буду подробно остана вливаться на этих предметах. Прекрасными книгами по докомпьютерной криптологии являются [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]; c= *(cp++); putc(c,fo);

fclose(fo);

fclose(fi);