ца, ПЛ. Тимофеева, В.Ф. Шаньгина. Защита информации в компьютерных сис темах и сетях. Радио и связь, М., 1999, 328 стр. В отношении учебной литера туры по данному вопросу мы отмечаем: 1) прекрасное описание шифратора «Хагелин», данное А.'Соломаа в его книге «Криптография с открытым клю чом» и 2) изданные Московским Государственным инженерно-физическим ин ститутомучебные материалы по криптографии.
Следует отметить глубину математических исследований в области синтеза криптосхем Ю. С. Харина, В.И. Берника, Г.В. Матвеева в их книге «Математические основы криптологий», Минск, БГУ, 1999, стр. 319.
Много конкретных алгоритмов блочного шифрования приведено в книгах Молдовяна Н.А. (Н. А. Молдовян, «Проблемы и методы криптогра фии», С.-П. 1998; Н.А. Молдовян, «Скоростные блочные шифры», С.-П., 1998). В отношении поточных шифров мы рекомендуем читателю
(Ьйр:/п$.381.пеуа.ги/р5\у/с1ур1о/ро1ок/81;г-с1рЬ.Ь1т, 1997). Нельзя пройти мимо хо роших кнрг:
АА. Варфоломеев, А.Е. Жуков, М.А. Пудовкина. Поточные криптосхемы. Ос новные свойства и методы анализа стойкости. МГИФИ, 2000, 243 стр.; Грушо А.А., Тимонина Е.Е., Применко Э.А. «Анализ и синтез криптоалгорит мов», 2000, 108 стр.; АЛ. Чмора «Современная прикладная криптография». М., Гелиус АРВ, 2001, 244 стр.
Естественно, мы не касались здесь книг, посвященных главным образом -«криптографии с открытым ключом» и монографий по теоретическим пробле мам криптографии. /
Криптосхемы шифраторов, как и сами шифраторы, принято клас сифицировать на криптосхемы блочного шифрования и криптосхемы по точного шифрования.
Условно большую часть криптосхем поточного шифрования можно схематически представить в виде последовательного соединения двух блоков: управляющего блока (УБ) и шифрующего блока (ШБ).
11 Зак. 5
1
322
Управляющий блок предназначен для выработки управляющей после довательности шифрующего блока. Эта последовательность должна быть «псевдослучайной» последовательностью, то есть по своим статистическим характеристикам она должна быть «близка» к случайной и равновероятной по следовательности элементов некоторого алфавита. Нередко криптосхемы управляющих блоков шифраторов представляют собой последовательное со единение линейного регистра сдвига (ЛРС) с некоторым узлом усложнения, функционирование которого моделируется либо функцией, определенной на последовательных отрезках выходной последовательности ЛРС, либо более сложным устройством с памятью, моделируемым некоторым конечным авто матом, выходная последовательность которого и является управляющей после довательностью шифрующего блока. В ряде случаев вместо ЛРС используют параллельное соединение нескольких ЛРС. Для таких управляющих блоков центральными направлениями их синтеза (получения псевдослучайных после довательностей) являются решения следующих математических задач.
1)Построение статистических аналогов двоичных функций и ав томатов.
3)Построение автоматов с гарантированными периодами выход ных последовательеностей.
Основными элементами управляющих блоков криптосхем являются устройства, реализующие лийейные рекуррентные последовательности элемен тов конечного поля-или кольца вычетов по некоторому модулю, К-значные функции (в частности, двоичные функции), коммутаторы, регистры сдвига и ряд других устройств, функционирование которых моделируется конечными автоматами и многоосновными алгебрами.
Шифрующий блок предназначен для последовательного шифрования букв открытого текста с помощью управляющей последовательности. Многие шифрующие блоки, как сами шифраторы, делятся в основном на два класса-
шифрующие блоки гаммирования и блоки реализации замены.
В первом классе криптосхем управляющая проследовательность шиф рующего блока является, собственно, гаммой наложения шифра гаммирования. Второй класс криптохем - класс криптосхем шифров последовательной заме ны - таков, что шифрующий блок под воздействием управляющей последова тельности вырабатывает последовательность подстановок П=П| ,П2,... ,Г^,... алфавита открытого текста, при этом элемент П, этой после
довательности используется для зашифрования )-ой буквы аф открытого текс та, именно, )-ая шифрованная буква ЬО) является образом буквы а(]) для подстановки П,: Ь(0=Ща(1)). Процесс зашифрования в ряде случаев моделируется
323
функционированием некоторого перестановочного автомата (см. параграф 1.3) с множеством состояний, совпадающим с алфавитом открытого текста. В этом случае управляющая последовательность 3=й,12,... шифрующего блока пред ставляется конкатенацией 3=3(1),3(2),..., 3(к),... своих последовательных 11грамм
3 (к)=1(к-1 )Ь+1 >1(к-1 )Ь+2»• • -Й(к-1)Ь+Ь-
При начальном состоянии а(1) под воздействием входного слова 3(1) автомат переходит в состояние Ъ(1), второй знак Ъ(2) шифрованнгого текста является заключительным состоянием автомата при подаче входного слова 3(2) на автомат с начальным состоянием а(2) и т. д. В других случаях шифру ющие блоки реализуются на базе регистров сдвига или с помощью конструк ции Фейстеля. Центральными вопросами синтеза шифрующих блоков последо вательной замены являются известные математические задачи изучения строе ния групп подстановок, заданных своими образующими подстановками (см. литературу).
В параграфах 6.6, 6.7 этой главы приводятся основные результы по за дачам, поставленном выше для управляющих блоков шифраторов.
Параграф 6.6 Статистическая структура двоичной функции
В этом параграфе мы приводим ряд известных результатов по вопро сам построения линейных статистических аналогов двоичных функций.
Рассмотрим двоичную функцию У(хь...,х„): р" —> Р2, будем считать, что ее переменные являются независимыми случайными величинами с распре
делениями: р {х , = 1) = р (х , = 0) = , г = 1,п .
Тогда для любого набора а = (а, ,К ,а п) е Р" выполняется равенство
р((х, ,К , х я) = (а, ,К , а п)) = , кроме того
11/1
Ъ - т
р ( / ( х {,К ,х п) = !) = —
= — —2 п— , где х = (х,,К ,хи).
11*
324
Здесь через р | обозначен вес функции Г- число двоичных наборов, на, которых она принимает.значение, равное единице.
Определение. Двоичная функция §(х) называется статистическим ана
логом функцииДх), если р ( / ( х ) = ^(х)) > ^ . Здесь р ( / ( х ) = %(х)) - вероя
тность совпадения значений функций/ и § при случайном и равновероятном
выборе набора х е
.
Ь(х)
1
■
1 " "‘г
Очевидно свойство: если р ( / ( х ) = Л(х)) < ^~, то р(?(х) = Ь(х)) > —. Здесь 2 2
и далее Ь(х) =Ь(х) ® 1.
На использовании статистических аналогов двоичных функций основан целый ряд статистических методов анализа криптосхем. Основная идея этих методов заключается в замене «сложной» функции / (х ), используемой в исс ледуемой схеме, на один из ее статистических аналогов более простого вида,. причем этот аналог §(х) выбирают так, чтобы вероятность р ( / ( х ) —#(х)) , была максимальной. В этом случае функция §{х) будет нести информацию о многих свойствах исследуемой функции, однако за счет отличия значений фу* нкций / (х) и§(х) на некоторых наборах задача из детерминированной стано
вится вероятностной, для решения которой используются статистические мето ды.
Наиболее изученным классом двоичных функций, для которых имеют ся достаточно эффективные методы решения систем уравнений, является класс линейных функций. Поэтому при анализе зачастую используют линейные ста: тистические аналоги функций.
Из доказанного утверждения следует, что статистическую структуру функции / (х,,..., хя) можно вычислить по статистическим структурам ее по дфункций / 0(х2,...,х„) й / , ( х 2,...,хя) следующим образом:
^ Пусть (А{0 . о о , Д о ° . . о , , ••• >
= С 0 и ( А
д д д
, А о . 0 1 , ... , А[' .п) = С , , тог-
Д а ( А ( ю . . . о о > А00 0 | , . . . , А 01 м , А ]0 0 0 , А ,0 0 1 , . . . , А П
п )
= ( С0 + С , , С 0 — С , ) .
На этом основан индуктивный алгоритм поиска статистической струк
туры двоичной функции / ( х , х „
).
Сначала определяем статистические структуры всех подфункций / (а,,...,ая_,, хп), зависящих от одной переменной. Для этого удобно исполь зовать следующую таблицу:
Г
0 X
X 1
> о
1
0
0 - 1
А ,
0
1- вспомогательная таблица
-1
0
327
,
Затем, по доказанной формуле находим статистические структуры фун
кций /
( а , ап_2, дгл_1, хп) для всех наборов (а х ап_2) € Р2~2. Потом ищем
статистические структуры функций / ( а , ап_3, х п_2, хп_х, хп) и так далее, до
получения статистической структуры функции / (х1,...,хп) .
Схема алгоритма и пример его использования для функции от 4-х пере менных приведены ниже.
Оценим трудоемкость этого метода. Для его реализации необходимо проделать п этапов, на каждом из которых подсчитать 2" коэффициентов. По этому Т = 0(п • 2”).
Индуктивный метод поиска статистической структуры двоичной функций.
Случай функции от четырех переменных.
1(х ,,Х 2,
х3,х4)
Х,ХзХзХ4
0 0 0 0
/ооо(х4)
0 0 0
1
/ио(хз.х4)
0 0
1 0
)'о О ](х4)
0 0
1
1
/о(Х2,Х3,
Х4)
0
1 0 0
/ою (х4)
0
1 0 1
/ о1(х 3,х 4)
0
1 1 0
/оп (х4)
0
1 1 1
1 0 0 0
/ю о(х4)
1 0 0
1
Л о(х з .х 4)
1 0
1 0
1ю ](х4)
1 0
1 1
Л(Х2,Хз,
1
1 0 0
х 4)
/ио(х4 )
1 1 0
1
/п(хз,х4)
1 1 1 0
/ ш (х 4)
1 1 1 1
Аооо~
В оо -(А ооо+
Л 001~
А оо1, Аооо-Аоо0
( Ы
ш )
А 010~
( ^ 0|0Д
Ш0)
•Во1=(А оЮ+
^ 0 1 1 =
Аои, Аою -Аоп)
( 4 ° " Х ° " )
Амо=
В 10=(А 100+
А 101~
А юл А^оо-АюО
( 4 0,4 0')
Ацо=
В ц = (А ц о +
Ац1, А цогА щ )
А ш =
( 4 " 4 “)
С о= (В 00
+в 01,
Воо~В 01)
(С 0+ С 1, С 0-С 1)
С 1=(В ю
+В ц ,
Вю -В ц)
\
328
Получаем Г> (А000^, Ад^,, Дошо» Доои» ••• ’^пп)-
Пример, использования индуктивного метода поиска статистической структуры двоичной функции.
Х/Х2X3X4
0 0 0 0
0 0 0
1
0 0
1
0
0 0
1
1
0
1
0 0
0 10
1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0
1
10 10
10
11
1
1 0 0
1 1 0
1
1 1 1 0
/
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
1Аооо” (-1,0)
А001 =
X
(0,1)
0
II
О
О ^
XАои — (0, 1)
X
>
-8II
3
^ ^
X
Аю1 “
(0,-1)
X
А 1ю=
(0,1)
X
А|ц =
(0,-1)
Воо-
(-1, 1,-1,-1)
С0= (0 ,2 ,
0,-2,-2,0,
Во1 =
-2, 0)
(1,1, 1,-1)
Б = (0, 0,0,
С! = (0,-2,0,-2,-2,-2,-2,
Вю ==
0, 2, 0,-2,
0,4, 0,-4,-2,
2,-2,2)
0,-2)
(0,-2,0, 0)
В ц - (0, 0, 0, 2)
1 1 1 1
0
^ (^оооо»^ 0001»^оою’^оои’ч-" ’^пп)
0,-2,-2,-2,-2, 0, 4, 0,-4,-2, 2,-2,2)
Среди координат вектора О наибольшие по модулю значения (4 и -4)
имеют 10-я и 12-я соответственно, т.е. А ^ , = 4, а д{0|| = -4. Поэтому наилучшими линейными статистическими аналогоми функции/ являются фун-
При этом Р(/(л:) = Х1®Х4)=Р(/(дг)=л:1®Хз®;С4Ф 1)= — +
—— + — = —.
Параграф 6. 7 Математические основы синтеза булевых функций с
гарантированными криптографическими свойствами
Введение. При написании данного параграфа использована начальная часть работы В.Н. Сачкова, В.И. Солодовникова, М.В. Федюкина «Дискретные
329
функции, используемые в криптографи», М., 1998 г., любезно предоставленная ими авторам данной книги. Здесь рассматриваются основные свойства матриц Сильвестра-Адамара, с использованием которых вводятся преобразования Уо- лша-Адамара и Фурье булевых функций. Приводится схема Грина быстрых преобразований Уолша-Адамара и Фурье. Определяются критерии нелиней ности булевых функций, инвариантные относительно групп преобразований переменных, являющихся подгруппами группы всех аффинных преобразова ний. Вводятся понятие линейной структуры булевой функции и понятие расс тояние булевой функции до множества функций, имеющих линейные структу ры. Определяется порядок нелинейности булевой функции являющейся од ним из критериев нелинейности булевой функции. Булева функция, имеющая максимальное расстояние до линейных структур, называется совершенной не линейной функцией. Оказывается, что эти функции находятся также на макси мальном расстоянии и от аффинных функций. Класс совершенно нелинейных функций совпадает с классом так называемых «бент-функций», у которых мо дуль преобразования Уолша-Адамара, принимает единственное значение.
1. Матрицы Адамара и их свойства.
Определение. Матрица Н=(Ьу), у е {1,2,...,п} такая, что Ь„е {1,-1}, на зывается матрицей Адамара, если имеет место равентво
ННт=пЕ, где Нттранспонированная матрица Н и Е - единичная матрица.
Матрица Адамара обладает следующими свойствами.
1.<1е1(#) = п ^ .
2.ННТ = НТН . Имеем ННТ = Н 'ННтН=пЕ.
3.Если Нь...,Н„- строки, Н(1),...,Н(п) - столбцы матрицы Н, (Н^Н) и (Н^Н^) - скалярные произведения соответствующих векторов, то
пл = /
{о , , * ; •
п , 1 = ]
0 , 1 * у
Отметим, что каждое из четырех условий при Ьу=—•/ является характе ристическим, т. е. определяет все остальные свойства и, стало быть, рпределяет матрицу Адамара.
330
4.Перестановка строк или столбцов, умножение на -1 строк или столб цов переводят матрицу Адамара снова в матрицу Адамара.
5.Для существования матрицы Адамара порядка п, необходимо, чтобы
либо и = 1,2 , либо пх0(тос14).
При п=1 и п=2 матрицы Адамара существуют и имеют вид
Н х= (1),
' I 1 Л
Н 2
с т о ч н о с т ь ю д о п е р е с т а н о в к и с т р о к , с т о л б ц о в и у м н о ж е н и я и х н а - 1 .
Используя свойство 4, любую матрицу Адамара порядка п можно при вести к нормализованному виду, при котором матрица Адамара имеет первую строку и первый столбец, состоящие только из единиц. Рассмотрим первые три
строки матрицы Адамара Н , приведенной к нормализованному виду. Соот
ветствующая подматрица Зхп матрицы Н имеет столбцы вида
Г1! гп
'П
1 9 -1
1
5
- 1
Л , , 1 ,
- 1
;
, - 1 ,
х,у,2. Если число таких столбцов в подматрице Зх п равно соответственно \у, то
имеют место следующие соотношения х+у+2-Иу=п
Х+2=у+\У Х+у=2-ИУ
Х+\У =у+2 .
Первое равенство означает, что общее число столбцов равно п. После дующие равенства следуют из ортогональности 1 и 2 строк, 1 и 3 строк, 2 и 3 строк подматрицы Зхп. Нетрудно убедиться (например, приведением матрицы системы к треугольному виду методом Гаусса), что детерминант приведенной системы линейных уравнений относительно неизвестных х, у, 2, \\- отличен от
нуля и, стало быть, эта система имеет единственное решение: х=у=2=\у=п/4. Следовательно, п=0(тоё 4).
Кронекеровское произведение матриц А=(ау), у=1,2,...,п; В=(Ъу), у=1,2,...,т определяется равенством
