1.2 Стеганография

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

Ближе к сегодняшнему дню люди начали прятать секреты в графических изображениях, заменяя младший значащий бит изображения битом сообщения. Графическое изображение при этом менялось совсем незаметно - большинство графических стандартов определяют больше цветовых градаций, чем способен различить человеческий глаз - и сообщение извлекалось на противоположном конце. Так в черно-белой картинке 1024x1024 пиксела можно спрятать сообщение в 64 Кбайт. Многие общедоступные программы могут проделывать подобный фокус.

Имитационные функции Питера Уэйнера (Peter Wayner) маскируют сообщения. Эти функции изменяют сообщение так, что его статистический профиль становится похожим на что-нибудь еще: раздел The New York Times, а пьесу Шекспира или телеконференцию в Internet [1584,1585]. Этот тип стеганографии не одурачит человека, но может обмануть большой компьютер, ищущий нужную информацию в Internet.

Лекция 2. Докомпьютерные шифры

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

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

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

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

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

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

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

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

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

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

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

P = ROT13(ROT13(P))

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

Простые подстановочные шифры легко раскрываются, так как шифр не прячет частоты использования различных символов в открытом тексте. Чтобы восстановить открытый текст, хорошему криптоаналитику требуется только знать 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 позиций и выполняет простую подстановку. Например, ротор может быть использован для замены "А" на " F", "В" на "U", "С" на "I" и так далее. Выходные штыри одного ротора соединены с входными штырями следующего ротора.

Открытый текст: COMPUTER GRAPHICS MAY BE SLOW BUT AT LEAST IT'S EXPENSIVE.

COMPUTERGR

APHICSMAYB

ESLOWBUTAT

LEASTITSEX

PENSIVE

Шифротекст: CAELP OPSEE MHLAN PIOSS UCWTI TSBIV EMUTE RATS GYAE RBTX

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

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

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

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

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

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

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