4. Информационная дедукция. Криптоаналитик получил некоторую информацию о ключе или откр ы-том тексте. Такой информацией могут быть несколько бит ключа, сведения о форме открытого текста и так далее.

Алгоритм является безусловно безопасным, если, независимо от объема шифротекстов у криптоаналитика, информации для получения открытого текста недостаточно . По сути, только шифрование одноразовыми бло к-нотами (см. раздел 1.5) невозможно вскрыть при бесконечных ресурсах. Все остальные криптосистемы подвержены вскрытию с использованием только шифротекста простым перебором возможных ключей и прове р-кой осмысленности полученного открытого текста. Это называется вскрытием грубой силой (см. раздел 7.1).

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

1.Сложность данных. Объем данных, используемых на входе операции вскрытия .

2.Сложность обработки. Время, нужное для проведения вскрытия. Часто называется коэффициентом работы.

3.Требования к памяти. Объем памяти, необходимый для вскрытия.

В качестве эмпирического метода сложность вскрытия определяется по максимальному из этих трех коэфф и-циентов. Ряд операций вскрытия предполагают взаимосвязь коэффициентов : более быстрое вскрытие возможно за счет увеличения требований к памяти .

Сложность выражается порядком величины . Если сложность обработки для данного алгоритма составляет

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

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

Исторические термины

Исторически термин код относится к криптосистеме, связанной с лингвистическими единицами: словами, фразами, предложениями и так далее. Например, слово "ОЦЕЛОТ" может кодировать целую фразу "ПОВОРОТ НАЛЕВО НА 90 ГРАДУСОВ", слово "ЛЕДЕНЕЦ" - фразу "ПОВОРОТ НАПРАВО НА 90 ГРАДУСОВ", а слова "ПОДСТАВЬ УХО" могут кодировать слово "ГАУБИЦА". Коды такого типа не рассматриваются в данной кн иге, см. [794,795]. Коды полезны только при определенных обстоятельствах . Если у вас нет кода для "МУРАВЬЕДЫ", вы не сможете передать это понятие. А используя шифр можно сказать все.

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

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

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

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

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" и так далее. Выходные штыри одного ротора соединены с входными штырями следующего ротора.

Открытый текстхюмршт 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" на "Е" и четвертый - "Е" на "C", "C" и будет конечным шифротекстом. Затем некоторые роторы смещаются, и в следующий раз подстановки будут другими .