Хорст Файстель. Криптография и компьютерная безопасность. Перевод А.Винокурова. Часть 3.

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

Независимо от того, закодировано ли сообщение с использованием истинно случайных цифр или псевдослучайной последовательности цифр, в подобном побитовом зашифровании одиночная ошибка, возникшая при передаче сообщения, остается в рамках одной цифровой позиции; ошибка не "размножается", не распространяется на остаток сообщения. Этот шифр не вносит межсимвольных зависимостей. Когда сообщение написано на естественном языке, таком, как английский, контекст естественной избыточности позволяет человеку, читающему текст, легко обнаруживать случайные ошибки. Так, если некоторые из 5 бит, представляющих букву  E, оказались искаженными таким образом, что соответствующая группа битов стала представлением буквы F (так например, что слово SECRET превратилось в SECRFT), то читатель-человек немедленно обнаружил бы ошибку.

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

Мы будем называть любой шифр, который преобразует n цифр сообщения в n цифр шифрограммы блочным шифром. Например, блочным будет такой шифр, который преобразует код 00000, представляющий по нашему соглашению букву A в открытом тексте, в, скажем, 11001, эквивалент A для шифртекста, по некоторому ключу перестановки, в точности, как это задает таблица подстановок. Чтобы увидеть, как такое двоичное преобразование выполняется электронным устройством, давайте рассматривать подстановки только в группах из трех двоичных цифр, как это показано на следующем ниже рисунке.

Вход Выход 000 011 001 111 010 000 011 110 100 010 101 100 110 101 111 001

Блок подстановок, в отличие от потоковых устройств, имеет более общий характер и включает как линейные, так и нелинейные преобразования: он не просто прибавляет нули и единицы к цифрам входа, но может заменить любой входной блок цифр на любой выходной блок. Реально он состоит из двух коммутаторов - один преобразует двоичное число из n цифр в одну цифру по основанию 2ⁿ, другой выполняет обратное преобразование. Блок, таким образом, содержит 2ⁿ внутренних соединений коммутаторов, которые могут быть выполнены 2ⁿ! различными способами. Это означает, что в случае изображенного на данном рисунке блока с n = 3 существует 40320 различных вариантов разводки или таблиц, подобных той, что изображена на рисунке. Блок такого типа с n = 128 сделал бы анализ практически неосуществимым, однако его технологически невозможно создать.

С помощью трех двоичных цифр можно представить восемь элементов: 2³ равно восьми. Устройство, выполняющее подстановку, состоит из двух коммутаторов. Первый преобразует последовательность из трех двоичных цифр в соответствующее восьмеричное значение, подавая сигнал ровно на одну из восьми выходных линий. Эти восемь выходов могут быть соединены с восемью входами второго переключателя любым из 8! или 40320 способов. Мы вольны выбирать, который из 40320 различных вариантов соединения или коммутации проводов между первым и вторым переключателем использовать. Роль второго переключателя - преобразовать вход, представленный одной цифрой по основанию 8, обратно в трехцифровой двоичных выход.

Если бы устройство подстановки было построено для обработки пятицифрового двоичного входа, оно могло бы быть использовано для зашифрования алфавита из 32 символов. Количество возможных соединений двух переключателей было бы тогда 32!. Это могло бы показаться невероятно большим количеством ключей, но к созданному таким образом шифру все же необходимо относиться как к очень слабому: он не может противостоять частотному анализу. Эта слабость не является его неотъемлемым свойством; описанное устройство с математической точки зрения определяет наиболее общее возможное преобразование. Оно включает для любого заданного размера входа-выхода любой возможный обратимый шифр, который когда-либо был, или даже просто мог бы быть изобретен; математики могли бы сказать, что он представляет полную симметричную группу. Он полностью "несистематический": одно соединение переключателей ничего не говорит оппоненту относительно всех других соединений. Слабость не является внутренне присущим данному шифру свойством, она обусловлена выбранным размером блока. Несмотря на большое количество ключей "каталог" возможных входов или выходов очень мал: в нем всего лишь 32 элемента. Здесь необходим, такой большой каталог, чтобы для любого оппонента было практически невозможно записать его. Если бы у нас, например, был блок со 128 входами и выходами, аналитику было бы необходимо одолеть 2¹²⁸ (или больше 10³⁸) возможных блоков цифр - настолько огромное число, что частотный анализ здесь просто неосуществим. К несчастью, устройство подстановок со 128 входами также потребовало бы 2¹²⁸ внутренних соединений между первым и вторым переключателями, что технологически нереализуемо. Это фундаментальная дилемма криптографии. Мы знаем, что является идеалом, но мы не можем достичь его на практике.

Однако существует преобразование, которое легко реализовать для большого набора входов. Практически возможно, например, построить блок со, скажем, 128 входными и выходными выводами, которые внутри соединены обычными проводами, как показано на следующем ниже рисунке. Для такого "блока перестановок" с n выходами имеется n! возможных вариантов коммутации проводов, каждый из которых определяется отдельным ключом. Он легко может быть построен для  n = 128. Хотя это обеспечит нам большое количество возможных ключей (128!), что весьма полезно, мы теперь столкнемся с новой трудностью. Путем использования набора специально сконструированных сообщений можно целиком определить ключ такой системы всего за n-1 (в данном случае 127) попыток. Этот прием заключается в том, чтобы использовать серию сообщений, содержащих одну единственную единицу в  n-1 различных позициях; позиция единицы в выходном блоке "выдаст" использованное в устройстве подключение провода. Слабость простого блока перестановок заключается в том, что он опять является линейной системой.

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

Нам необходим компромисс, который бы, как минимум, приближался по характеристикам к общей системе. Мы пришли к идее составного шифра, в котором два или более шифра скомбинированы таким образом, что результирующая система обладает большей стойкостью, чем каждая из составляющих ее систем в отдельности. Как раз перед первой мировой войной исследовались различные громоздкие шифры, использующие несколько этапов шифрования. Первым действительно успешным образцом была, вероятно, система, изобретенная немцами, известная как ADFCVX-система. Нам необходимо здесь отметить только, что она соединяла "дробления" с "перестановками". В этой процедуре сообщение разбивалось на сегменты и эти сегменты переставлялись на другие места. Важный факт, на который следует обратить внимание, заключается в том, что составной шифр, составленный из блочных шифров, опять является блочным шифром; цель здесь, конечно, состоит в том, чтобы шифр вел себя, насколько это возможно, подобно общему шифру замен.

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

Современный интерес к составным шифрам возник благодаря статье Клода Шеннона, озаглавленной "Теория связи в секретных системах", которая была опубликована в техническом журнале корпорации Bell (Bell System Technical Journal) в 1949 году. В разделе, посвященном практической разработке шифров, Шеннон ввел в рассмотрение понятие "перемешивающего преобразования", которое предполагает особый способ использования результатов преобразования. В добавок к изложению интуитивных принципов, ведущих, как он полагал, к созданию стойких шифров, он ввел в обиход понятия "перемешивания" и "рассеивания". Его статья открыла практически неограниченные возможности по разработке и исследованию шифров.

Способ, которым следует сочетать принципы перемешивания и рассеивания для получения криптографической стойкости, можно описать следующим образом: Мы видели, что перестановки общего вида не могут быть реализованы для больших значений n, скажем, для n = 128, и поэтому мы должны ограничиться схемами подстановки, имеющими практический размер. В системе, разработанной в IBM и названной "Люцифер" мы выбрали для блоков подстановки n = 4. Хотя это может показаться слишком маленьким числом, такая подстановка может оказаться вполне эффективной, если ключ подстановки, или схема коммутации проводников, выбрана верно. В Люцифере нелинейная подстановка эффективно обеспечивает определенную степень перемешивания.

Мы также видели, что линейный блок перестановок легко построить даже для n = 128. Число входных и выходных клемм равно n. Будучи "тасователем" цифр в чистом виде, устройством, которое просто перемещает цифры с места на место без изменения количества единиц и нулей, блок перестановок является естественным распределителем перемешивания, таким образом, он может обеспечить оптимальное рассеивание.

[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 23.12.00. (c) 1998-2000 Андрей Винокуров.