Симметричные криптографические системы – ЧАСТЬ 1

С точки зрения теории информации задача шифрования интерпретируется как задача разрушения статистических связей в исходном сообщении. Состав­ные части этого сообщения (слова, знаки, буквы или цифры) преобразуются с целью приведения содержащихся в нем сведений к неявному виду. Все много­образие защитных преобразований в криптосистемах с секретным ключом по существу, основано на двух методах – методе перестановок и методе подстано­вок [61].

Суть первого ясна из его названия: входной поток исходного текста делится на блоки, в каждом из которых выполняют перестановку символов. Перестанов­ки обычно получают в результате записи исходного текста и чтения шифрованно­го текста по разным путям некой геометрической фигуры. Последовательность заполнения их вершин задается ключом. Совокупность фигур, обеспечивающих хорошую маскировку смыслового содержания блока (а этим свойством обладает не каждая перестановка) называется маршрутами Гамильтона.

Метод подстановок называют также методом замены. Символы исходного текста, записанные в одном алфавите, заменяются символами другого алфавита в соответствии с принятым ключом преобразования. Примером примитивного по меркам сегодняшнего дня подстановочного шифра является шифр, которым более 2000 лет назад Цезарь писал в Рим Цицерону. Буквы открытого текста он заменял третьей по счету (с учетом цикличности) буквой латинского алфавита. Так, из латинского Gaius Julius Caesar получался шифртекст JDLYV MYOLYV FDHVDU.

Более криптостойкой реализацией метода подстановок является схема на базе таблицы Вижинера. Вместо регулярных замен, применяемых в шифре Цезаря, здесь применяются рандомизированные подстановки. Современная ее реализация предполагает умножение псевдослучайной матрицы ключа на век­тор сообщения (блок открытого текста). Криптограмма (шифртекст) – результат умножения. При дешифровании операндами являются криптограмма и обрат­ная матрица ключа.

Еще один вариант подстановок – гаммирование, при котором шифрование осуществляется за счет сложения символов исходного текста и ключа по модулю, равному числу букв в алфавите (чаще используют двоичный алфавит и сложение по модулю 2). Роль ключа выполняет гамма шифра — псевдослучайная двоичная последовательность, вырабатываемая по некоторому правилу. Упоминавшаяся в подразделе 2.7.2 связь между стойкостью криптосистемы и длиной ключа при этом очень наглядна. Длина К ключа вида 101101111010110101…1011 экспоненци­ально связана с количеством 2К всевозможных равновероятных ключей. Их пере­бор (до тех пор, пока из шифртекста не получится осмысленный открытый текст) так или иначе характеризует вычислительную сложность задачи криптоанализа.

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

Заметим, что при простых подстановках сохраняется распределение частот символов в шифртексте. Это дает богатый материал криптоаналитику, как это и произошло в произведении Эдгара По «Золотой жук». Например, в русском язы­ке, анализируя статистику букв, встречающихся в шифртексте, можно сделать вывод о том, что наиболее часто встречающийся в нем символ соответствует букве «Е», а встречающийся наименее часто – букве «Ф», и так далее.

Из приведенного примера ясно, что большой объем ключа – необходимое, но не достаточное условие секретности. Стойкий шифр должен обеспечивать два принципа, сформулированных еще К. Шенноном: рассеивание и перемешивание. Под первым понимается распространение влияния одного знака открытого текста на множество знаков шифртекста, что позволяет скрыть статистические свойства открытого текста (и распространение влияния каждого знака ключа на многие знаки шифртекста, что препятствует восстановлению ключа по частям).

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

Многократное чередование простых перестановок и подстановок позволя­ет получить стойкий шифр с хорошим рассеиванием и перемешиванием. Не­которые из таких шифров оказались настолько удачными, что были приняты в качестве национальных стандартов. Одним из наиболее долговечных примеров оказался DES (Data Encryption Standard), созданный IBM и принятый в 1978 г. в качестве стандарта шифрования в США [62]. Он представлял собой суперпози­цию шифров из 16 последовательных «циклов», в каждом из которых простые перестановки сочетаются с подстановками в 4-битовых группах. Всякий раз ис­пользуются 48 битов ключа, выбираемые из 56-битового ключа случайным об­разом. Алгоритм DES полностью отвечал принципу Керкхоффа (возможности его опубликования без ущерба для криптостойкости) [61].

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

Самым распространенным способом задания блочных шифров являются сети Фейстеля [63] (Feistel), названные именем их автора Хорста Фейстеля. Это конструкции, представляющие собой преобразование нелинейной необратимой функции (называемой F-функцией) в перестановку на множестве шифруемых блоков, ^-функция – это некоторая последовательность замен, перестановок и сдвигов, зависящих от ключа. Сеть Фейстеля формируется последовательным набором итераций, число которых определяется требованиями к стойкости шифра (например, в DES их 16). Процедуру расшифровывания от шифрования отличает лишь обратный порядок применения ключей.

Акгуальным шифром на основе сети Фейстеля является алгоритм KASUMI, используемый в качестве криптографического ядра в системе мобильной связи третьего поколения UMTS.

Рост возможностей компьютерной техники за время, прошедшее с момента появления DES, привел к появлению новых, более мощных шифров. Так, в 2001 г. в США стандарт DES заменен новым стандартом симметричного шифрования Advanced Encryption Standard (AES) на основе алгоритма Rijndael, названного в честь его авторов (К Rijman и J. Daemeri). Это разновидность блочного шиф­ра, не использующего криптопреобразования типа сетей Фейстеля. Наиболее важными применениями AES в беспроводных сетях является его реализация в схеме безопасности систем WiMAX и cdma2000 (см. главы 5, 7).

Rijndael – это блочный шифр с переменными длинами ключа и шифруемо­го блока (выбираемыми из значений 128, 192 или 256 бит). В зависимости от длины ключа алгоритм предусматривает выполение 10, 12 или 14 шифрующих итераций над блоками, упакованными в двумерные массивы байтов размером 4×4, 4×6 или 4×8 (в зависимости от длины блока). Шифрование, выполняемое над столбцами, строками и отдельными байтами таких таблиц, включает сле­дующие типовые шифрующие преобразования (см. рис. 2.59) [64]:

–                табличные подстановки ByteSub (осуществляется нелинейная независимая подстановка каждого байта с использованием таблицы замен);

–                циклические сдвиги строк таблицы на различное число элементов (ShiftRow);

–                перемешивание элементов внутри столбцов подстановок (MixColumn). При этом каждый столбец интерпретируется как полином четвертой степени и умножается по модулю X4 + 1 на полином с(х) = 3х32 + х + 2в поле Галуа GF(28), что обеспечивает шифру необходимый эффект рассеивания;

–                т.н. процедуру добавления материала ключа AddRoundKey путем выполне­ния матричной операции XOR («исключающее ИЛИ»);

–                процедура KeyExpansion, позволяющая получить ключи для последующих итераций шифрования.

Рис. 2.59. Шифрующие преобразования криптоалгоритма AES-Rijndael

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

последовательности (ПСП) – на второй вход сумматора по модулю 2. Расшиф­ровывается криптограмма путем повторного суммирования по модулю два с би­тами этой же ПСП.

Криптостойкость схемы полностью определяется структурой генератора последовательности. Первый фактор, от которой она зависит напрямую – пе­риод ПСП. Применение бесконечной ПСП обеспечило бы этому шифру «абсо­лютную» стойкость. Поскольку это невозможно, второй фактор – степень «слу­чайности» последовательности. Рандомизированный старт генератора ПСП обеспечивается частой сменой ключа.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100