Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
3—>4, 4—>1, 5—>2) на множестве из пяти элементов, примененная к открытому тексту «hello», дает слово «lolhe». Пусть секретным ключом будет именно эта перестановка, и предположим, что более длинный открытый текст шифруется с использованием одного из «режимов работы», которые описаны в § 5. Тогда такое шифрование, хотя и не окажет воздействия на частоту появления самих букв (и скорее, даже облегчит раскрытие самого шифра [181]), но зато скроет частоты появления биграмм, триграмм, и так далее.
Другой подход к рассеиванию заключается в том, чтобы сделать каждый символ (или бит) открытого текста зависимым от стольких его оставшихся символов (битов), от скольких это вообще возможно. Рассмотрим, например, открытый текст сообщения т = т\m2 . • • тп, где каждый символ ш,- выражается целым числом от 00 до 25. Пусть к = kik2--.ks для некоторого целого числа s является секретным ключом и имеет точно такое же представление, что и т. Для 0 ^ г < s положим гтг_,- = Агд. После этого для каждого г < п определим с,- как
дится в § 4.1) и рассмотрим шифртекст с = cic2...c„. Когда ключ известен, расшифровать такой шифртекст не составляет труда. Обратите внимание, что здесь каждый символ шифртекста с (кроме первых s) зависит от s + 1 символов открытого текста, и именно это обеспечивает рассеивание. Для осуществления
1В русской версии [324], опубликованной в книге К. ШЕННОН, Работы по теории информации и кибернетике, ИЛ, М, 1963, соответствующие термины «diffusion» и «confusion» переведены как «распыление» в «запутывание».
mod 26 (определение оператора mod приво-
34 Системы с секретным ключом
Глава 3
рассеивания очень хорошо подходят также некоторые из режимов работы при шифровании длинных открытых текстов, которые мы будем обсуждать в § 5.
Цель перемешивания состоит в том, чтобы зависимость между ключом и шифртекстом сделать настолько сложной, насколько это вообще возможно. Криптоаналитик, основываясь на результатах статистического анализа шифрованного текста, полученного в процессе перемешивания, не должен получить сколь-нибудь значительного количества полезной информации
о ключе шифрования криптосхемы. Обычно перемешивание осуществляется при помощи техники подстановок, которые используют для получения шифртекста из открытого текста перестановки символов алфавита сообщения. Использующий подстановку шифр простой замены не дает очень уж хорошего перемешивания потому, в частности, что самым повторяющимся символом любого шифртекста в этом случае почти наверняка будет пятая запись в его ключе шифрования (соответствующая букве «Е» открытого текста сообщения). Лучше использовать подстановку для блоков из нескольких символов, хотя она,и приводит к тому, что ключ становится намного длиннее (во всяком случае тогда, когда подстановка задается в виде таблицы). Альтернативный подход состоит в том, чтобы для каждой позиции в открытом тексте использовать свою собственную подстановку. Это может привести, с одной стороны, к совершенной секретности, как в одноразовом шифре, а с другой — к злополучной Энигме (Enigma) [187, 303].
Необходимо учитывать, что применяемые порознь ни рассеивание, ни перемешивание сами по себе не являются очень уж действенными методами, радикально затрудняющими статистический криптоанализ шифртекста (если только ключ не будет достаточно длинным — ведь, в конце концов, в одноразовых шифрах используется только перемешивание). Тем не менее, оказывается, что криптосистема, в которой оба этих метода используются совместно, становится намного более стойкой. Возможно, самый лучший пример подобного феномена — Стандарт шифрования данных (Data Encryption Standard, или, сокращенно, DES).
Стандарт шифрования данных (DES) 35
§ 4. Стандарт шифрования данных (DES)
Стандарт шифрования данных (DES) — это знаменитая криптографическая система с секретным ключом, которая была предложена Национальным бюро стандартов при Министерстве торговли США (National Bureau of Standarts, или сокращенно NBS) в 1977 году [277]. Она была разработана для использования на срок от десяти до пятнадцати лет «в интересах Федерального правительства [США] для криптографической защиты наиболее значимых, но не подлежащих категорированию компьютерных данных». Несмотря на то, что с недавнего времени эта криптосистема уже не имеет сертификата, она по-прежнему широко применяется и достойна изучения. Основным преимуществом DES является то, что ее использование позволяет достичь очень высокой скорости шифрования и дешифрования. История создания DES описана Хорстом Фейстелом в [175], ее «настоящее и будущее» — Майлсом Смидом и Деннисом Брэнстэдом в [337].
Мы не будем описывать здесь детально алгоритмм DES. Для этого обращайтесь к [277, 142, 337]. Отметим лишь, что в нем Шифруются 64-битовые блоки данных с использованием секретного ключа длиной в 64 бита. Однако, фактически секретными в нем являются только 56 бит, так как последние разряды байтов, составляющих ключ, т.е. его 8-ой, 16-ый, ..., 64-ый биты, отведены для контроля предшествующих разрядов соответствующих байтов по четности. Алгоритм DES предварительно преобразует секретную 56-битовую часть ключа посредством вполне определенного алгоритма формирования ключей, использующего перестановки и сдвиги, в шестнадцать 48-битовых частичных ключей, используя каждый из битов первичного ключа по нескольку раз. Затем после стандартной начальной перестановки над 64-битовым блоком данных открытого текста производится шестнадцать раундов некоего конкретного преобразования, в конце которого осуществляется инверсия начальной перестановки. При этом, следуя рекомендациям Шеннона, в каждом раунде выполняется один шаг перемешивания (с использованием соответствующего частичного ключа и так называемых S-боксов), за которым следует один шаг рассеивания. Примечательно, что процесс на этапе рассеивания не зависит от секретного ключа, так что стойкость достигается за счет комбинации перемешива-
