автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Свойства программно реализуемых поточных шифров

На правах рукописи

Пудовкина Марина Александровна

СВОЙСТВА ПРОГРАММНО РЕАЛИЗУЕМЫХ ПОТОЧНЫХ ШИФРОВ (НА ПРИМЕРЕ RC4, GI, ВЕСТА)

Специальность: 05.13.19 - методы и системы защиты информации,

информационная безопасность

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Автор:_

Москва-2004

Работа выполнена в Московском государственном инженерно-физическом институте (государственном университете)

Научный руководитель:

Официальные оппоненты:

доктор физ.-мат. наук, профессор Борис Александрович Погорелов

доктор физ.-мат. наук, профессор Грушо Александр Александрович

кандидат физ.-мат. наук, доцент Велигура Александр Николаевич

Ведущая организация:

Московский государственный институт электроники и математики Министерства образования и науки Российской Федерации

Защита состоится »(Тц ^А 2004 г. в / ^ часов на

заседании диссертационного совета ДМ 212.130.08 в МИФИ по адресу: 115409, Москва, Каширское шоссе, д.31.

С диссертацией можно ознакомиться в библиотеке МИФИ. Автореферат разослан

Просим принять участие в работе совета или прислать отзыв в одном экземпляре, заверенный печатью организации.

Ученый секретарь диссертационного совет

к.т. н. Горбатов В. С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время в мире происходит активное развитие электронной коммерции. При разработке систем электронной коммерции фактор безопасности играет первостепенную роль. При этом типовой задачей является создание системы работы с партнерами, предоставляющей защищенный доступ к динамически обновляемой информации. В некоторых случаях система должна предоставлять возможность оформления заказа и резервирования товаров. Для этого она должна обеспечивать аутентификацию, невозможность отказа от авторства и конфиденциальность пользователя. Многие производители компьютеров, крупные компьютерные дистрибьюторы, а также многие из некомпьютерных международных корпораций уже используют системы с элементами обеспечения информационной безопасности в России. Одни системы разработаны специалистами самих фирм, другие используют стандартные решения.

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

Поскольку Интернет технологии требуют высоких скоростей, то одной из

актуальных задач в криптографии является разработка и реализация

высокоскоростных программно реализуемых поточных алгоритмов

шифрования, обеспечивающих высокую надежность защиты информации, с

хорошими техническими и эксплуатационными свойствами. К настоящему

I РОС. НАЦИОНАЛЬНАЯ 3 I БИБЛИОТЕКА 1 С. Петербург /га» л 1 О» X»

времени значительная часть предложенных в открытой литературе поточных шифров основана регистрах сдвига над полем GF(2).

В значительной степени это объясняется разработанной теорией и удобством при аппаратной реализации алгоритмов шифрования. Дня алгоритмов, основанных на регистрах сдвига над полем GF(2), достаточно хорошо разработаны методы синтеза и криптоанализа, в тоже время относительно мало изучены высокоскоростные программно реализуемые нерегистровые поточные алгоритмы и практически не развита теория их синтеза и методов криптоанализа, хотя при программной реализации они могут быть предпочтительнее.

Существенное повышение производительности микропроцессоров к 80-м годам вызвало в криптографии усиление интереса к программным методам

реализации алгоритмов шифрования как возможной альтернативе аппаратным схемам. Одним из самых первых подобных алгоритмов шифрования, получившим широкое распространение в электронной коммерции, стал алгоритм поточного шифрования RC4 (также известный как алгоритм ARCFOUR). Он, например, используется во многих платежных системах. В России, кроме RC4, программно реализуемыми алгоритмами поточного шифрования, используемыми в электронной коммерции, являются Веста-2, Веста-2М. Поэтому основное внимание в диссертации уделяется как программно реализуемым неригистровым алгоритмам: RC4, предложенному в диссертации его обобщению (включающему IA, IBAA, ISAAC), Solitaire, так и регистровым: Веста-2, Веста-2М. Рассмотренные алгоритмы шифрования включают большинство наиболее распространенных среди программно реализуемых алгоритмов поточного шифрования. Единство исследований достигается общей математической моделью, изложенной на теоретико-автоматном языке, едиными математическими методами.

Целью диссертационной работы является разработка общих математических моделей, включающих ряд алгоритмов шифрования и методов их криптоанализа; исследование криптографических свойств (теоретико-

автоматных, теоретико-групповых, теоретико-вероятностных) программно реализуемых алгоритмов поточного шифрования RC4 и различных его обобщений GI (IA, IBAA, ISAAC), Solitaire, Веста.

Для достижения поставленной цели, используя единую теоретико-автоматную модель, были решены следующие задачи:

• Проведен обзор современных программно реализуемых поточных алгоритмов и методов их криптоанализа в рамках этой модели;

• Введено в рамках теоретико-автоматной модели семейство алгоритмов поточного шифрования GI, обобщающее ряд известных алгоритмов шифрования (LA, IBAA, ISAAC), предложенных в открытой литературе, и получена верхняя оценка числа знаков гаммы, необходимых для восстановления начального состояния по гамме алгоритма GI;

• Описан ряд криптографических свойств алгоритмов RC4, GI, Solitaire, Веста;

• Разработаны методы восстановления начального состояния по гамме алгоритмов семейств GI и Веста, основанные на их алгебраических свойствах.

Методы исследования: теоретическая криптография, теория автоматов, комбинаторный анализ, теория вероятностей, математическая статистика, теория групп, полугрупп.

Научная новизна работы заключается в следующем:

1. Описан ряд классов слабых состояний алгоритмов RC4, GI, Веста-2, и подсчитана их мощность;

2. Получены распределения первого, второго знака и биграмм в гамме RC4 при предположении о равновероятности выбора начальной подстановки из множества всех подстановок. Построены критерии различения гаммы RC4 от случайной равновероятной последовательности;

3. Подсчитано число ключей алгоритма RC4, приводящих к начальным подстановкам с произвольной фиксированной цикловой структурой;

4. Введена теоретико-автоматная модель семейства алгоритмов поточного шифрования GI, обобщающая ряд известных алгоритмов шифрования (IA, IBAA, ISAAC), предложенных в открытой литературе. Найдена верхняя оценка числа знаков, необходимых для восстановления начального состояния по гамме;

5. Разработаны методы восстановления по гамме начального состояния алгоритмов GI и Веста;

6. Описаны групповые свойства преобразований, связанных с алгоритмами Solitaire и Веста.

Результаты, выносимые на защиту.

• Разработка модели семейства алгоритмов шифрования GI и описание ее свойств;

• Определение распределения первого, второго знаков и биграмм в гамме RC4 при предположении о равновероятности выбора начальной подстановки из множества всех подстановок;

• Определение числа ключей алгоритма шифрования RC4, приводящих к начальным подстановкам с произвольной фиксированной цикловой структурой;

• Определение вида и числа слабых состояний алгоритмов шифрования RC4, Веста-2 и GI;

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

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

Внедрение результатов исследований. Полученные свойства алгоритмов Веста-2, Веста-2М используются фирмой «ЛАН Крипто» при создании программно реализуемых шифров, предназначенных для электронной коммерции. Результаты исследований, связанные с анализом криптографических свойств поточных алгоритмов шифрования Solitaire, IA, IBAA, ISAAC внедрены в учебный процесс на факультете «Информационная безопасность» Московского государственного инженерно-физического института (государственного университета). Публикации и апробация работы.

Результаты диссертации изложены в 40 публикациях и докладывались на конференциях и семинарах различного уровня, в том числе:

• на международной конференции EUROCRYPT' 2001, EUROCRYPT'2002, EUROCRYPT2003 (rump sessions);

• в трудах международной конференции «First International IFIP ТС-11 WG 11.4 Working Conference on NETWORK SECURITY», Leuven (Belgium) 2001;

• в трудах международной конференции «International Workshop on Computer Science and Information Technologies», 2001-2003 гг.;

• в трудах международной конференции «Discrete Mathematics and Theoretical Computer Science», France, 2003;

• на международной конференции «РусКрипто» в 1999-2004 гг.;

• в трудах XXIII конференция молодых ученых мехмата МГУ, Москва, 2001;

• в трудах XLIV юбилейной научной конференции МФТИ, 2001;

• в сборнике тезисов Российской научно-технической конференции «Методы и технические средства обеспечения безопасности информации», Санкт-Петербург, (2000-2003 гг.);

• на Всероссийской научно-практической конференции «Проблемы информационной безопасности в системе высшей школы», Москва, (2000-2003 гг.);

• в трудах седьмого международного научного семинара «Дискретная математика и ее приложения», МГУ, 2001;

• на общероссийской конференции с международным участием «Математика и безопасность информационных технологий» (МаБИТ-03), Москва;

• в трудах семинара «Информационная безопасность-Юг России», 2001;

• на международной конференции «Computer data analysis and modeling», Minsk, 2004.

• на III Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT'04.

• написано 1 учебное пособие;

• на научных семинарах в ФАПСИ, ФСБ, ИКСИ, МИФИ, МГТУ. Структура и объем работы.

Диссертация состоит из введения, пяти глав, списка литературы из 100 наименований. Работа изложена на 150 страницах с рисунками и таблицами.

СОДЕРЖАНИЕ РАБОТЫ

Во введении показана актуальность темы диссертации, определены цели и задачи проведенных исследований, отражены научная новизна и практическая значимость полученных результатов.

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

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

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

Введем следующие обозначения. Пусть 2т={0,1,...,>я-1}-множество классов вычетов целых чисел по модулю т; 0,т —1=0, l,...,w-l; Sm — симметрическая группа подстановок множества

i[m—1]>— запись подстановки seSm; |х|— модуль числа х, или мощность множества х; s- изоморфные алгебраические структуры; Р-конечный алфавит, элементы которого являются знаками открытого текста; Y— конечный алфавит, элементы которого являются знаками шифртекста; К — конечное множество всех ключей; Z - конечный алфавит, элементы которого являются знаками гаммы; GF(q)- конечное поле из q элементов; V -множество состояний автомата; э.о.— элементарная операция.

Для описания функционирования дискретных устройств, реализующих отдельные блоки шифратора, часто применяется язык теории автоматов. Пусть F: Рх.К х V -> V, /: РхЛГх К->У-функции, где F((x,k), v)=/rk(x, v)= t)(v), Á(x, k), v)=/k(x, v)=/(k,v)(jc). Автомат A=(PxK, Y, V, F,f) называется шифрующим автоматом, если

1. автомат А регулярный, т.е. частичная функция F^ к): V-*V- биекция для любых пар (х, к)еРхК;

2. при фиксированном ключе кеК и состоянии ve V отображение f^:P—>Y является инъективным.

Алгоритм поточного шифрования моделируется шифрующим автоматом А„=(РхАТ, V, Y, F,f), работа которого описывается в i-м такте, />1, уравнениями:

v,+í=/r*(ví,x();

Условимся дальше под состоянием алгоритма шифрования понимать состояние автомата, моделирующего этот алгоритм.

Пусть Р=Z=Y и на Z задана групповая операциЙНасто, например, в шифрах гаммирования, fiív, ,х,) зависит от х, "линейно" относительно операции ® HaZ, т.е.

y,=xt®fk(v).

Последовательность {z,-f¡¡(s¡ ): Ï>1} называется гаммой.

В последние 10 лет активно исследовались следующие программно реализуемые поточные алгоритмы: Pike, Scop, Dagger, Sober, Sober -tl6, Bmgl, Sober-t32, RSC, Lili, Leviathan, RC4, Wake, Seal, Twoprime, ISAAC, IA, IBAA, Chameleon, Panama, Rabbit, Solitaire, Веста. Среди перечисленных алгоритмов только RC4, Wake, Веста используются практически. Алгоритмы шифрования RC4, IA, IBAA, ISAAC, Веста, Solitaire наиболее распространенные среди программно реализуемых поточных алгоритмов.

Поскольку RC4 один из наиболее применяемых в электронной коммерции алгоритмов, то основное внимание при обзоре алгоритмов поточного шифрования уделено результатам, полученным с 1993 по 2003 гг. по анализу алгоритма RC4 следующими авторами: Golic J., Shamir A., Knudsen L., Preneel В., Rijmen V., Fluhrer , McGrew D., Meier W., Verdoolaege S, Mantin I.. Отмечена связь их результатов с результатами диссертации.

Целью второй главы является исследование алгебраических и вероятностно-статистических свойств алгоритма поточного шифрования RC4. Алгоритм RC4 зависит от параметра т= 2", натуральное п>2, (для практических приложений выбирается ти=256). Алгоритм RC4 моделируется автономным автоматом A=(ZmxZmxSm, Zm, Z™ F, f), где F: ZraxZmx,S'm-»ZmxZmx(Sm, f. ZmxZmx5'm—^Z,,,. Состоянием алгоритма в такте t>\ является тройка vt=(/„ j„ ^ÊZmXZjnXiSn,, ключом длины L - слово где k^eZ^, L<m. Начальное

состояние - (io,jo> Jo,), где г0=0 и j0-0.

Функция р. Хт Б„ формирования начального состояния (подстановки) из ключа keZm> т.е. р(к)еБ„, задается следующим образом.

Пусть 5о' — тождественная подстановка, /<гУо=0. Для каждого /, 1=1, т,

Приведем описание /-го (/=1,2....) такта работы алгоритма.

Шифрование /-го знака открытого текста х(=СЧп-I, • • - А,о) е имеет вид с,=х,Фг„ где © — операция покоординатного сложения в поле Расшифрование /-го знака шифртекста определяется выражением х,=с, Фг,.

Будем придерживаться следующих обозначений. Пусть 5(а|,...,ат>-множество всех подстановок из 5т с цикловой структурой {1"'2"1...т'т}, где

1 • с?! +2• «2+.. -+т -а^т. Пусть подстановка 5 выбрана случайно равновероятно

Если распределение начальных подстановок £(к), генерируемых алгоритмом ЛС4, равномерно на то

Р{ДА)е5(а,.....ат)}=р^-

т т • а, !-а2 !...-<*„!

и среднее число ключей, приводящих к начальным подстановкам с фиксированной цикловой структурой, равно

Тп

ЛГю(аь...,аи)= ———--—-

1 '2 г..т " • а, Ьа2 !...•«„!

В §2.1.1 описаны все самые короткие циклы длины (/и(от-1)) графа Г функции переходов алгоритма ЯС4 и приведен метод восстановления по гамме состояний, порождающих эти циклы. Справедливы следующие утверждения.

Утверждение 1. Все состояния (¡о, <&о[0],...,зо[т-1]>) с $о[1о+1]—1, ("о алгоритма КС4 принадлежат циклам длины (т-1)-т. Число состояний с произвольной заданной парой координат (¡о, ¡о+1), принадлежащих фиксированному циклу, равно т-1.

Утверждение 2. Пусть 2/, 22, ....¿„(„-ц — гамма длины т(т—1). Если Уо~(0, 1, <50[0], 1, ¡0[2], ...,$о[т-1]>)~ начальное состояние алгоритма ЯС4, то: О 0]+к+1]к=\,т;

2) существует единственное ге{\,т} такое, что гг-(т-1)=и при этом

Яо[0]=т-г, $0[к]=2(г+к.0<т-0, к=\,т-\.

Из утверждения 2 следует способ восстановления начального состояния алгоритма ЯС4. Для этого среди знаков гаммы г^), г2(т-1).....гт(т-1) находится

элемент затем полагают^о[0]=от—г,(от_1), к=\,т-\.

В §2.1.2 построен изоморфизм (изоморфизм циклов понимается, как изоморфизм графов) между циклами в графе Г и показано, что число изоморфных циклов является делителем числа т.

Рассмотрим биективное преобразование <р : (/', /, $')=(/+1,у+1,

<у[/я—1], $[0],...,л[/п-2]>). Группа <<р>, порожденная преобразованием <р, является циклической порядка т.

Пусть у<г>- орбита, содержащая состояние у=({, у, л). Будем говорить, что состояния у=(|,7, 5) и V]\ л) алгоритма ЯС4 ^связны, если они лежат на одной орбите группы <</>. Рассмотрим произвольное состояние у. На одной с ним орбите лежат состояния <р(у),...,д?(у),...,<рт~1(у), которые, очевидно,

все различны. Следовательно, |v<iS>|=w, поэтому, число орбит равно т\-т. Справедлива следующая теорема.

Теорема 3. Если в графе Г существует цикл, которому принадлежат ровно к состояний из множества v*^, то к\т и существует L—mfk изоморфных циклов £2j, 02, Q,..., Qi. Каждому из этих циклов принадлежит ровно к состояний из множества v<<IU>.

Утверждение 4. Пусть Q=£21u...uQl - множество состояний алгоритма RC4, лежащих на изоморфных циклах Qh П2,—, графа Г и veil Тогда орбитой, содержащей состояние v в группе <q>, F>, является множество О, т.е. v<v~ ^=12 При ограничении действия группы <(р, F> на множество £2блоками импримитивности являются: Q\, /2?,.... QL.

Следствие 1. Если т-простое число, то состояния из множества v<qi>

flv^l =т) либо принадлежат все одному циклу, либо имеется т изоморфных

циклов, каждому из которых принадлежит только одно состояние из <а>

множества v .

Следствие 2. Если m=pip2, где р/, рг- простые числа, то состояния из множества v<0>, либо принадлежат все одному циклу, либо имеется р/ изоморфных циклов, каждому из которых принадлежит р2 состояний из множества v<(tf>, либо имеется изоморфных циклов, каждому из которых принадлежит р/ состояний из множества v<<r>.

В §2.2 получены распределения частот ¿-грамм (¿=1, 2) в гамме алгоритма RC4. Данный параграф является обобщением и усилением результатов, полученных A. Shamir, I. Mantin и S. Fluhrer, D. McGrew.

Теорема 5. Пусть начальная подстановка so выбирается случайно и равновероятно из Sn jo^Zm — произвольные фиксированные числа. Тогда при т—*со справедливы асимптотические равенства: I.

a) P{z2=0}=—+ 0(\) при i2=j0=0, т т

b) P{z2~k}-— + 0(-Хг) при i2=jo=0. k*0. m m

a) P{z2=0}=- + npujo-O, i2*0,

m m

b) P{z2=k}=— + 0(\) npuj0=0, i2*0, k*0.

m m

В остальных случаяхP{z2-k}=—+ O(-^-r), k=0,m-\.

m m

Отметим, что первый частный случай (P{z-£=Q}=— при Уо='о=0> тогда

¿2=/"о+2=2) теоремы 5 был получен A. Shamir, I. Mantin. Также найдено распределение биграмм (zi, zj) при предположении, что начальная подстановка So выбирается случайно и равновероятно из Sm. Пусть имеется L

последовательностей z,,.....zL, выработанных либо RC4, либо являющихся

независимыми, случайными и равновероятными. Построены критерии отношения правдоподобия на основе обнаруженных неравновероятностях в распределениях первых знаков гаммы и биграмм, т.е. ищется неравновероятность в распределении знаков в L-граммах (z1, ¡..^г,1), (z^.-.^zj ) и (z,1 z\,~.z\\

Теорема 6. При различении последовательности, выработанной алгоритмом RC4, от случайнойравновероятной последовательности:

a) для критерия отношения правдоподобия с произвольно заданным уровнем значимости а и мощностью Д основанного на неравновероятностипервогознака zi гаммы (кромеслучая ii=2ja) объем выборки равен

b) для критериев отношения правдоподобия с произвольно заданным уровнем значимости а и мощностью Д основанных на неравновероятности второго знака гаммы, или на неравновероятности в распределение биграмм, или на

неравновероятности первого знака z¡ гаммы при i¡=2jo объем выборки равен. п= 0(т).

Из теоремы 6 получаем, что если основная гипотеза Но: р<у=——

т

последовательность случайная равновероятная, H¡: р\-—— последовательность

выработана RC4, то для различения последовательности выработанной RC4 от случайной равновероятной последовательности при уровнях значимости а=0.05 и Р=0.9, объем выборки л=12 т— 15.

В §2.3 исследуется метод генерации начального состояния алгоритма RC4. А именно, найдено число всех ключей алгоритма длины т, приводящих к начальным подстановкам с произвольной фиксированной цикловой структурой. Поскольку каждому ключу keZ" алгоритма RC4 однозначно соответствует произведение транспозиций где

У*е{0,/и — 1}, k = l,m, то задача оказалась эквивалентной проблеме порождения симметрической группы системой транспозиций с ограничениями, которая решалась с применением методов комбинаторного анализа. Полученный результат показывает наличие большого числа эквивалентных ключей и приводится в теореме 7.

Теорема 7. Пусть ключ к алгоритма RC4 выбирается случайно и равновероятно из Z™. Тогда число • начальных подстановок с произвольной фиксированной цикловой структурой {l"1!"г...тт}, l-a¡+2-a2+...+m-am=m, равно

0(а,.....ctm)= m\ Y\r' r)"r • £ П ^ * >

r=l (*r...*m)Oí<r0^yl kyiy+jy."

0<¡Zj,ky smin(aj ,at), m

t=0

где суммирование проводится по первым j+1 координатам (k0j, k¡j,..., kj вектора kj =(k0j, к,р..„ kmj) eZ"*\j=\,m, и

с,-2 №р+уг)

к-(п-к)-Г4 - | при 0<i<j,

Со,—1,

к

и+1

Укажем число ключей алгоритма ЛС4, приводящих к подстановкам с цикловыми структурами {1° 2°...от1}, {Г 2°...от0}, {1"^ 2°...с!1...от0}. Так 0(0,...,0,1)=оти"1. Следовательно, вероятность того, что случайно равновероятно выбранный ключ из множества всех ключей алгоритма И.С4

генерирует полноцикловую подстановку, равна —. Отметим, вероятность того,

от

что при случайном равновероятном выборе подстановки из множества всех

1

подстановок степени от она окажется полноцикловои, также равна —.

от

Число ключей, приводящих к тождественной подстановке, равно

П(от,0,...,0)= X

т/2

Й *Кт-2-*)12*'

Отметим, что С1(от,0,...,0) также есть число решений уравнения 52 =Е в симметрической группе 5т, отличных от тождественной подстановки, т.е. число инволюций. Известно, что при от->оо

Асимптотически число ключей, приводящих к начальным тождественным подстановкам алгоритма ЯС4 в у/л • ■ Пя^+114 раз больше

т

ожидаемого значения -, т.е. вероятность единичнои подстановки много

от!

больше вероятности любой фиксированной подстановки.

Полученные результаты позволяют рекомендовать при применении метода полного перебора для восстановления начального состояния алгоритма

RC4 начинать опробование с тождественной подстановки, а затем опробовать подстановки с наибольшим числом неподвижных элементов.

В §2.4 введено понятие /-граммы подстановки и показано, что распределение /-граммы подстановки также является неравномерным.

Зафиксируем произвольно / попарно различных элементов (г\,...,г,) из 2т. Будем называть /-граммой подстановки 5 образ (ri,..., г,)1 = (at,..., ai) при ее действии на множестве

ПустьрДги a,),.--, Ot, 0!))=P{sir,]=ab---,idtrt]=ai} и

fl, если А истинно,

°(Л) = \ n А

[ 0, если А ложно.

Теорема 8. Пусть {г/,...,г(}, {а\,...,а,}-произволъные подмножества из Zm,d>l, ii=d— 1 (mod от). Тогда выполняется рекуррентное соотношение'.

рМг ь «0>---> (ru а,))=0, если среди alt...,a, встречаются равные, pJLiTu cti),..., (ги адУ= Pd-i((n, ai),..., (r„ а,))-

где рДги аг,),..., (гь а,))=1 при «,),..., (г„ £ц))=0 при Г]*ау .

С учетом найденных неравномарностей в распределении /-грамм подстановки в §2.5 получено распределение первого знака гаммы RC4 при предположении, что ключ выбирается случайно и равновероятно из Z™.

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

1 v-

c-t r«(r,r ,г() т

.....(г„а,)),

с=1 otc т

модификациями RC4 или основанными на общей идеи, которые также могут быть использованы в электронной коммерции.

В третьей главе введено семейство алгоритмов поточного шифрования GI, в результате чего, известные алгоритмы LA, IBAA, ISAAC представляются в общей теоретико-автоматной модели. Алгоритмы, принадлежащие семейству GI, определяются шестью функциями cp; Zmx Z ьх Z™ —> Z b, р: ZmxZ™ —ïZm,

a:Z2„xZ2b->Z2b, S: Zm xZ™-> Zm, y;. ZmxZ™-> Zm, s: N-> N (e: t^t или

e: /—» (/-1)) и моделируются автономным автоматом AGi=(Zmx Z^ x Z^ x Z™b,

Z2j, FCi, Jgi), где функции FCi: Z^Z^xZ^xZ^-^xZ^xZ^xZ^, /Gi:

ZnjX Zjb x Z^ xZj"b-> Zjt будут описаны ниже.

Семейство алгоритмов GI зависит от параметров т=2", b>2n, п, beN, которые для практических приложений выбираются равными /я=256 (т.е. л=8) и ¿=32. Состоянием автомата Agi в такте / (/=0,1,...) является четверка (;'b at, q„ iJeZroxZ^xZ^xZ™, где 5г={5,[0],...л[»1-1]}-таблица из m «-мерных двоичных

векторов. Начальным состоянием является четверка (0, а0, qo, s0), причем щ, qo предполагаются известными параметрами GI.

Приведем описание /-го (/=1,2....) такта работы GI. Функиия переходов Fr.i /t= i',_i+l (mod m), а,=ф(/,, St-ь «t-i),

4i't]=(sbi[p(/„in)]+c(at, q,-.,)) (mod 2b), st[A:]=st_,[¿] при k=0,m-l и Шь

qristfii,, 5,)]+Je(,)[x(i„ «/)]) (mod 2b). Функиия выходов fr.l , z,=q,.

Шифрование t-то знака открытого текста Xt=(;c^b-|,... ,*t,o) e Z2b имеет вид С(=х,@2,. Расшифрование /-го знака шифртекста определяется выражением x,=c,®z,.

В §3.1 и §3.2 показано, что задача восстановления по гамме начального состояния автомата Agi сводится к решению системы уравнений и получена верхняя оценка числа знаков гаммы, необходимых для определения по гамме класса эквивалентных состояний.

Теорема 9. При т—^ао оценка сверху числа знаков гаммы, при которой с вероятностью, стремящейся к единице, находится хотя бы одно состояние из

т\пт + х-т

класса эквивалентных состоянии автомата Ась не превышает ---,

где х—>оо сколь угодно медленно.

В §3.3 описаны ряд свойств GI. Так если в автомате Agi для любого состояния (i,a,q, s)eZmxZ^ xZ^b xZ^ выполняются равенства: о{а, q}= 0(mod 2),

<f(i, s, a)=0(mod2), 50[î]=1 (mod 2), i=0,m —1, <7(f=0(mod 2), a<7=0(mod 2), то в любом такте f>l справедливы равенства a,=0(mod 2), z,=qr0(mod 2), и s,[/]=1 (mod 2), i- 0, m -1.

Доказаны следующие утверждения.

Утверждение 10. Пусть существует такое натуральное число bo, n<b0<b, что для любого состояния (i, a, q, s) е ZmxZ^ xZ^ xZ™b автомата Agi

выполняются равенства

<p(i, s, a) = <p(i, s(mod 2b°), a(mod 2b°))(mod 2\),

afa, q) =a(a(mod 2*°), q(mod 2b°))(mod 2b°),

p(i, s) —p(i, s(mod 2"*)), ô(i, s) =5(i, s(mod 2*°)),

Z(i, s) =x0. s (mod 2"°)). Будем считать bo наименьшим таким числом. Тогда для любых состояний (¡о,

во, Чо, So) и (io, а0', q0', s0') таких, что i0= id (mod m), q0= q0' (mod 2*»),

i=0,»i-l, в любом такте t>I выполняются равенства:

/,=//, а,= a,'(mod 2**), q,= =q,'(mod26a), s,[i]= s,[i] (mod 2b°), i=0,m-l.

Для формулировки следующего утверждения удобно обозначать GI=GI(i>), где Ь один из параметров алгоритма GI.

Утверждение 11. Пусть выполняются условия утверждения 10. Тогда при b>bo>n автомат есть гомоморфный образ автомата

Гомоморфизм задается парой сюрьективных отображений (Щ и), где ш: ZmxZ kxZ AxZ? ->ZmxZ , xZ. xZ"l Z,->Z, ,

Y 2 2 2 m 2ba 2 ° 2 0 2s 2 »

и

4}{i, a, s)= (/, a(mod 2*°), g(mod 2*°), ¿(mod 2*°)), u(z)=z (mod г4») для любых zeZ^, (i, a, q, s) eZmxZjb xZ^b xZ™b.

В §3.4 на основе построенного в утверждении Ц. гомоморфизма предложен метод определения состояния GI по гамме. Получено, что трудоемкость метода равна Т]=2ь"т'1т (21nm+2«+l) э.о.. Трудоемкость метода

_ *ып-1 т\пт + т1 _ ..

полного перебора равна Тп=2---- э.о.. Для алгоритма IA

трудоемкость определения начального состояния равна 22пт"1-от-(21п т+

+2/и+1)э.о.. В частности, для значений параметров ¿>=32, л=8, ти=256 имеем

Т,=7-101237 э.о., Тп =7,1-Ю2447 э.о.

Рассмотрены свойства функций щ р, а, 8, е, используемых в IA, и

предложен метод восстановления начального состояния по гамме

,т\пт + 3т2 , .nm-i „ трудоемкостью Т2=(---+4/я)-2 э.о.. В частности, для значении

параметров 6=32, и=8, т=256 имеем Тг= 1,5 10621 э.о..

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

- __ ~ь-ьп tn\v\m + ш2 _ . _ восстановления слабых состоянии равна Т3-2 °(3--2т). В случае

1А эту трудоемкость удалось существенно понизить и она не превышает

В §3.5 и §3.6 рассмотрен метод восстановления начального состояния алгоритмов IBAA, ISAAC по гамме, основанный на методе частичной линеаризации и зависящий от <р.. Получено, что трудоемкость восстановления начального состояния алгоритмов IBAA и ISAAC при т-х» равна

(0=0 в алгоритме IBAA). Для значений параметров, используемых в алгоритмах IBAA и ISAAC уточняется оценка на Г4. Получено, что ТШАА «5,0-10127* э.о., Tisaac =5.9-10Ш6 э.о. (Тп»7,Ы02447 э.о.). В настоящее время методов с трудоемкостью меньшей, чем предложенная, неизвестно.

В четвертой главе рассмотрен алгоритм поточного шифрования "Solitaire"(" Пасьянс") предложенный Б. Шнайером в 1999 г.. Согласно замыслу автора он предназначен для применения в качестве ручного шифра ("paper-and-pencil cipher") и построен на основе - перемешивания колоды игральных карт.

Пусть и>3. Назовем элемент п-2 джокером А, а элемент «-1 джокером В. Будем записи джокеров в виде буквы или числа считать тождественными, т.е. и-2=МА", «~1="В". Если в множестве Z„ выделены два элемента п-2, л-1, или один элемент п-2, или один элемент и-1, то будем, соответственно, использовать обозначения ZABn={0,«-3, А, В}, ZAn={0,w-3, п-1, А}, ZBn={0,/j-2, В}. Поскольку элементы п-2, и-1 отождествляются с буквами А, В, то можно считать, что множества ZA„, ZB„ совпадают с множеством Z„. Если конкретное расположение джокеров А, В в перестановке s не важно, то будем использовать запись s=<s[0] $[l]...i[№-l]> без указания положения джокеров в s.

J -у •

—т э.о.(при от=256 равна 98-10 э.о.).

3 2

Будем для удобства использовать одновременно две записи перестановки <y[0]...s[£i-l] A j[/t2-l] В s[/t2+l]...i[«-l]> =<5[0]...

6[Jtr-l] A 6[*i]„.б[*г-2] В 5[^1]...5[«-3]>дв, где s[/]=5[/] при /=0,^-1, s[j+l}=m приj-kt,k2 -2, i[/+2]=5[/] при j=k2-1,л-3, и <5[0]...5[«-3]>е5,^2-

Также будем понимать <r[0]...i[r-l] A i[H-l]...s[«-l]>s <8[0]...8[г-1] А 5[г]...5[и-2]>а, где s[/"H>[/'] при у=0,г-1, s[/+l]=S[/] при ;=г + 1,и-2 и <8[0]...S[ii-2]>eS^i(ZA.\ А). <s[0]...j[r-l] В i[rH]...s[«-l]>=<5[0]...8[r-l] В 5[г]...6[и-2]>в, где s[/]=8[/] при y'=0,r-l, s[/+1 ]=§[/'] при у'=г + 1,и-2 и <6 [0]... 5[и-2]> G .

Алгоритм Solitaire моделируется автономным автоматом А=(5„, Zmu{a), F, f), где F: S„ S„, f: S„-»Zmu{a) и a- некоторый дополнительный символ. Алгоритм зависит от параметров m, neN, которые предлагается брать равными т=26, п=54.

Перестановка s,eS„ является состоянием алгоритма Solitaire в такте t (/=0,1,...). Функция переходов F представима в виде композиции F^F^FyF* четьфех преобразований. В такте t выполняется равенство st+i=(st) F\ F2 F3 F4.

Алгоритм p. Zm'xSn—>Sn генерации начального состояния so по ключевой фразе кеZm* моделируется автоматом без выхода Ap=(Zm, Sn, Р) с функцией переходов Р: Z„,x Sa->S„. Частичная функция переходов Pr= Fi F2 F3 Pr, reZm, где преобразование Pr: есть

(<j[0]...i[r]j[H-l]...j[W-l]>)^ = <jtH-l]...s[n-l]5[0]...s[r]>.

Начальным состоянием автомата Ар является тождественная перестановка ¿>0=<О, 1,..., п-1 >.

Поскольку изучение преобразования F и полугруппы <F> непосредственно является проблематичным, поэтому рассматривались свойства полугрупп <F\>, <F2>, <F,,F2>, <F[J<\yF2>, <F\, Fi, F}, Ft> и свойства групп, порожденных обратимыми модификациями преобразования F. Поскольку <F>

есть подполугруппа из то ряд полученных результатов

непосредственно переносится на <F>.

В §4.2 рассмотрены свойства группы преобразований <F3, F4>. Пусть {Аь Аг}={А, В}. Получено, что F) есть инволюция. В группе <F3> длина орбит элементов вида <А, í[1]...s[«-2] А2> равна 1. Число орбит длины 1 равно

п\

2(л-2)!. Число орбит длины 2 равно —-(л-2)!. В группе <F3, F4> длина орбит

элементов вида s=<Ai í[l]...i[n-2] А2> равна 1. Число таких элементов равно 2-(и-2)!.

В §4.3 описаны свойства полугруппы преобразований <Fb F2, Fз, F¿>. Пусть S(ZAn, ry={seS(Z\) | s[r]=A}, S(Z\, r)={seS(Z\) | s[r]=B}, /=0,и-1, SíZ^n, r,t r2)= {s<=S(Z^) | j[r,]=A, s[r2]=B}, 0<r,, г2<и-1, r,*r2.

Множества S(ZA„, г), г=0,и-1, задают разбиение 5(ZA„); S(ZB„, г), г=0,и-1, задают разбиение 5(ZB„); SiZ^n, гь г2), 0<гьг2<я-1, r^r2, задают разбиение множества S'(ZABn). Отметим, что |S(ZA„, r)|=|^(ZBn, г)|=(и-1)!, RZ*3,, ru r2) K"-2)!, 0<r, r,, r2<n-1, r^r2.

Пусть стА: S(Za„)-> ^(Z^,), ctb: S(ZBn)-> S^,), где

<y[0]...í[A:-l] A 5[¿]...s[«-2]>acta=<j[0]...s[A:-1] s [*]...í[/j-2]>, <s[0]...s[£-l] В í[/t]...s[«-2]>bctb= <j[0]...í[it-l] i[/t]...i[n-2] >, где £=0,и —1, <s[0]...j[«-2]>eS„_,.

Пусть {Ai, A2}={A, B}, <s[0]...5[№-3]>g5^2 и преобразование CTAB^CZ^nb^^Z^) задается равенствами:

<у[0]„.л[А:,-1] A, i[it,+l]...s[Vl] А25[*2+1]...ф-3]>аАв= = í[*,+l]„. i[¡fc2+l]-í[l-3]>,

<s[0]...j[jt-l] A, A2 j[¿+l]...i[n-3] >Gab=<s[0].. .s [£— 1 ] s[¿+1]...s[h-3]>, где ¿i Фк2, k\= 0, n -1, k2= 0, n -1, £= 0, и -1.

Пусть def(G, A^jAj-IA!'3! - дефект полугруппы G преобразований, действующей на множестве X.

Получено, что 5(ZAn,0) Ff'=0, 5(ZB„, 0)F2'1 =0, def(Fb ZAn)= =(«-l)!, def(F2, ZB0)=(«-1)!. <F[>, <F¿> являются циклическими полугруппами порядка и, индексом 1 и периодом п-1. Кроме того, ограничение действия полугрупп <F,> на множество C2A=S(ZAn)\S(ZAn, 0), a <F2> на QB=5(ZBn)VS(ZBn, 0) являются циклическими группами порядка и-1, <Fi>s <F2>.

Пусть Qab=5(ZAfln)\(5'(ZAn,0)u5(ZBn,0)). Тогда C1AB<FU F2>=QAB, def(<Fb F2>, Zab„)=2(«-1)!. Кроме того, def(F1F2,ZABn)=def(F2FbZABn)= =2(n-l)!-<«-2)!. Ограничение полугруппы преобразований <FU F2> на множество QAb является 1/2 транзитивной группой, |(j)<Fi, f2>nab |=(и-1)(«-2). Число орбит группы <F¡, F¿>°At равно (и-2)!.

Получено, что (s) F'=0, если состояниями алгоритма Solitaire являются перестановки следующих видов: 1 ) 5 =<А, s[l] s[2]...j[«-2] B>e5(ZAB„);

2) s - <j[0] s[l] í[2]...s[w-3] A B>eS(ZABn);

3) s = <$[0]...j[)>-1] В s[p+l]...s[»-2] A>e5(ZABn), где pe Z^2;

4) s = <s[0]...it>-l] A j[jtH-l]...s[w-2] B>gS(Zab„), гдеpe7^u{n-2}.

Блоками импримитивности полугруппы <Fb F2, F¡> являются множества

r\,r2= 0, п -1, г\Фг2. Число блоков импримитивности равно и(и-1 ). Пусть 5s5(ZABn), As={s'j í'-abs, i'e5(ZAB„)}, |Д5|=и(и-1). Тогда полугруппа преобразования G, действующая на множестве блоков импримитивности, изоморфна полугруппе <F¡, F2>4*. Также доказано, что полугруппа <F2> делит полугруппу < F\, Ff>, a <F2> — полугруппу <F\, Fy>. Кроме того, <Fb F2, F¡> = <F|, F3> =<F2, F}>.

В §4.4 описаны, свойства полугруппы преобразований автомата Ар. Для их формулировки введены преобразования <V|/A>, <9а>, являющиеся двумя биективными модификациями преобразования Fi, а <ув>, <9в>-прсобразования F2, причем <V(/A>, <SA>- циклические группы преобразований,

действующие на множестве S(ZA„), a <v|/B>, <9В>- циклические группы преобразований, действующие на множестве S(ZB„), ij: i-H+1 (mod n).

Показано, что группа <\|/в> изоморфно вложена в группу <tj , ц/А, F3> и имеют место изоморфизмы групп <Т], v)/a, Ч/в, F3>=<0a, 6в, F3>= <г|, V|/a, F3>

=<еА, F3>.

Пусть Q={S(Zab„, п, г2)| п, г2=0,л-1, г^г2}. Тогда группа <rj, \|/в, F3> является импримитивной на множестве S^Z*8,,), число блоков импримитивности равно |Q|=«(n-l). Кроме того, группа G, действующая на множестве П блоков импримитивности группы <г], Vb. Fy>, изоморфна группе <vj/a, V|/b>. Известно, что импримитивность может являться слабостью алгоритма шифрования.

В пятой главе предложены методы восстановления начального состояния алгоритмов поточного шифрования Веста-2 и Веста-2М, разработанных в 1995-1998 гг. фирмой «ЛАН Крипто». Алгоритм Веста-2 используется в коммерческих продуктах этой фирмы, Веста-2М является стандартом газовой промышленности России. Также эти алгоритмы используются в электронной коммерции в России. Отличие алгоритма Веста-2М от алгоритма Веста-2 состоит в выборе функции обратной связи и расположением функций, осуществляющей перестановку координат двоичных 16-мерных векторов.

Алгоритмы семейства Веста моделируются автономным автоматом A=(Z„31x Z2,6 х Z It x Z, ,Z2, fj), где F: Z,"x Z^ x Z16 x Zj8 ->Zp3,xZ,6 xZ.xZ^,

f: Zp3lx Zjl6 x Zjl6 x Zj8 ->Z2g, р-простое число 215<p<216. Состоянием алгоритмов

семейства Веста в такте />1 является ((х^о, Хн29,-"Л). Щ v,, м/'^е Z/'xZ^n xZjI6 xZ^, где (х1+зо> Zp31 есть 31-мерный вектор над полем

GF(p), являющийся состоянием линейного регистра сдвига в такте t с функцией обратной связи ^(х) = х31+х10 —1. Начальное состояние ((х30,

X29i.-.>xo)> wo> Vo, является ключом. Перестановка тс действует на

множестве двоичных 16-мерных векторов.

Основная часть разработанных методов анализа фильтрующих генераторов с регистрами сдвига применима к анализу комбинирующих генераторов с линейными регистрами над полем GF(2). Развитый подход позволяет частично линеаризовать некоторый класс фильтрующих генераторов над полем GF(p). Его применение показано на примере алгоритмов Веста-2 и Веста-2М с тождественной перестановкой ж. Поэтому в §5.3, §5.5 рассмотрены методы восстановления начального состояния

Z^'xZ^xZ^xZ^ алгоритмов Веста-2М и Веста-2 с тождественной

перестановкой который сводится к восстановлению начального состояния линейного регистра по гамме

Получено, что трудоемкость предложенных методов для алгоритмов Веста-2М, Веста-2 с тождественной перестановкой одинакова и в среднем равна Тм<1)=2316 э.о.. Заметим, что трудоемкость метода полного перебора равна

В §5.4, §5.6 решается задача определения начального состояния ((хзо,

алгоритмов Веста-2М, Веста-2 с

реальной перестановкой Она сводится к восстановлению начального состояния (хзо, Xi<),...,хо) линейного регистра по гамме z. Для алгоритмов Веста -2М, Веста-2 с реальной перестановкой 71 частичная линеаризация, как для тождественной перестановки it, не получается. Но в силу свойств алгоритмов, также удалось построить линейные соотношения. Получено, что трудоемкость предложенных методов для алгоритма Веста-2М в среднем равна для алгоритма

В §5.7 для алгоритма Веста-2 рассмотрен метод восстановлению начального состояния линейного регистра по гамме для

произвольной перестановки Метод основан на выведенных алгебраических

соотношениях. Получено, что трудоемкость предложенного метода в среднем равна Тм<5)=2зшэ.о..

В §5.8 описан класс слабых состояний алгоритма Веста-2 и предложены методы их восстановления по гамме. Состояние вида

/ N

х30,...,х2о+11,0,....,0,х1д,....,х1)0.....,0

, где 1<£<11, линейного регистра сдвига

Утверждение 12. Пусть состояние х, линейного регистра сдвига

а) состояние *,+31 является (к-3)-благоприятным;

Отметим, что число различных заполнений линейного регистра сдвига равно р31&216 31. Число 8-благоприятных состояний есть р15'3**-*]р}[. Число 11-

Теорема 13. Пусть состояние х линейного регистра сдвига является к-благоприятным. Тогда трудоемкость метода определения начального состояния алгоритма Веста-2 по гамме г:

a) при к=11 не превышает 233 элементарных операций;

b) при 8<к<11 не превышает 270 элементарных операций.

Для сравнения трудоемкость метода полного перебора равна /?31-239«2544.

Таким образом, если в гамме

встречаются постоянные

подпоследовательности г*"1, , то можно предположить, что состояние линейного регистра сдвига является ¿-благоприятным и определить состояние алгоритма Веста-2 с трудоемкостью существенно меньшей трудоемкости полного перебора.

В §5.9 описаны групповые свойства семейства Веста.

Утверждение 14. Пусть D(g, р, d) — подстановка степени pd, р— простое число, deN, реализуемая автономным регистром сдвига длины d с функцией обратной g над полем GF(p). Пусть Vj eSm, j=Q,p-\ и S,^:

GF(pf-> Smx Sm где (th tje Zdx Z* t,<t2, и (a,tif\Ji =(apx ,bvx ). Пусть

'i '1

M=< fij\j=Q,p-\>, r=<Vj\ j=0,p-1> . Тогда группа семейства Веста есть

сплетение прямого произведения групп подстановок МхГ и циклической группы < D(g, р, п)>, причем

, . (<5, , ,D(g.P,d» , j.

((a,b),x) = ((a,b)\'2 ,xD(g,p,d)).

Основные публикации по теме диссертации:

1. Варфоломеев А. А., Жуков А.Е., Пудовкина М. А. Поточные криптосистемы. Основные свойства и методы анализа стойкости. Учебное пособие- ПАИМС - Москва, 2000.

2. Пудовкина М. А. Методы криптоанализа алгоритма поточного шифрования IA // Безопасность Информационных Технологий, 3- 2000-с. 40-46.

3. Пудовкина М.А Криптоанализ алгоритма поточного шифрования ISAAC// В сб. научных трудов конференции Проблемы информационной безопасности в системе высшей школы - Москва-2001- с. 85-87.

4. Pudovkina M. Probabilistic relations for the jokers at the Solitaire keystream generator// In: Proceedings of first International IFIP TC-11 WG 11.4 Working Conference on NETWORK SECURITY - Leuven, Belgium- 2001-pp. 110— 118.

5. Pudovkina M. Short cycles of the alleged RC4 keystream generator// In: Proceedings of 3nd International Workshop on Computer Science and Information Technologies- CSIT' 2001- UFA- 2001-pp. 200-206.

6. Pudovkina M., Analysis of the IA keystream generator // In: Proceedings of 3nd International Workshop on Computer Science and Information Technologies- CSIT 2001- UFA- 2001- pp. 207-215.

7. Pudovkina M., Varfolomeev A.A., A cycle structure of the Solitaire keystream generator// In: Proceedings of 3nd International Workshop on Computer Science and Information Technologies- CSIT' 2001- UFA- 2001 -215-223.

8. Пудовкина М. А., О распределении первого выходного символа криптосхемы RC4 // В сб. научных трудов XLIV юбилейной научной конференции МФТИ. - Москва -Долгопрудный-2001-с. 201-202.

9. Пудовкина М. А., О распределении биграмм в криптосхеме RC4 // В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва- 2002- с. 41-42.

10.Пудовкина М. А., Об одной системе образующих с ограничениями //В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва- 2002- с. 43-44.

11.Пудовкина М. А., О группе преобразований криптосистемы Solitaire // В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации» - Санкт-Петербург- 2002- с. 66-67.

12.Пудовкина М. А., О слабых состояниях криптосистемы IA // В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы» - Москва- 2003- с. 37-38.

13.Pudovkina M., Statistical weaknesses in the alleged RC4 keystream generator // In: Proceedings of 4nd International Workshop on Computer Science and Information Technologies- CSIT'2002- Greece, Patras- 2002-pp. 301-307.

14.Пудовкина М. А., О слабых состояниях криптосистемы ВЕСТА-2 // В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург— 2002- с. 68-69.

15.Pogorelov В., Pudovkina M, Properties of the transformation semigroup of the Solitaire stream cipher // Discrete Mathematics and Theoretical Computer Science-DTMCS'03 Proceedings, Springer-Verlag-2003-pp. 260-274.

16.Погорелов Б.А.„ Пудовкина М.А., О свойствах криптоалгоритма GI. //В трудах конференции Мабит'03-МГУ-2003-с.100-102.

17.Пудовкина М.А., О групповых свойствах криптоалгоритма Веста.//В трудах конференции Мабит'03-МГУ-2003-с.103-105.

18.Пудовкина М. А., Вероятностные свойства криптоалгоритма ВестаУ/В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург- 2003-С.213-214.

19. Пудовкина М. А., О длине гаммы, необходимой для восстановления начального состояния криптоалгоритма GI.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург- 2003- с.215-216.

20. Pudovkina M., On the transformation group generated by the key-schedule of the Solitaire stream cipher. // 5nd International Workshop on Computer Science and Information Technologies- CSIT'2003- UFA- 2003-pp. 304309.

21.Pudovkina M., The number of initial states of the RC4 cipher with the same cycle structure. // 5nd International Workshop on Computer Science and Information Technologies-CSIT'2003- UFA- 2003- pp. 310-314.

22.Пудовкина М. А., О некоторых слабостях криптосистемы RC4// Защита информации, 2- 2002- с.50-56.

23.Пудовкина М. А., Свойства алгоритма поточного шифрования IA// Международный научный семинар «Дискретная математика и ее приложения»- Москва- МГУ-2001-с. 70-73.

24.Pudovkina M., The upper estimate of the unicity distance of the GI stream cipher // International conference computer data analysis and modeling -Minsk-2004- pp. 200-207.

25.Пудовкина М.А., О методе генерации начального состояния алгоритма поточного шифрования Solitaire.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»-Москва- 2000- с. 10-11.

Отпечатано в копицентре Москва, Ленинские горы, МГУ, 1 Гуманитарный корпус.

www.stprintru e-mail: zakaz@stprint.ru тел. 939-3338 Заказ № 22 тираж 60 экз. Подписано в печать 15.06.2004 г.

113048

ВВЕДЕНИЕ.

ГЛАВА 1. ОСНОВНЫЕ СВОЙСТВА И МЕТОДЫ АНАЛИЗА ПОТОЧНЫХ ШИФРОВ.

1.1. Основные понятия.

1.2. Классификация алгоритмов поточного шифрования.

1.3. Программно реализуемые алгоритмы поточного шифрования, предложенные в открытой литературе.

1.3.1. Программно реализуемые регистровые алгоритмы поточного шифрования.

1.3.2. Программно реализуемые нерегистровые алгоритмы поточного шифрования.

1.4. Обзор результатов по анализу алгоритма поточного шифрования RC4.

1.4.1. Описание алгоритма поточного шифрования RC4.

1.4.2. Построение линейной модели алгоритма RC4.

1.4.3. Распределение биграмм в гамме RC4.

1.4.4. Метод восстановления начального состояния RC4 по гамме, основанный на подходе "ветвей и границ".

1.4.5. Методы криптоанализа RC4, основанные на предсказывающих и благоприятных состояниях.

1.4.6. Алгоритм вскрытия RC4, основанный на методе связанных ключей.

1.4.7. Свойства алгоритма генерации начальной подстановки RC4.

ГЛАВА 2. АНАЛИЗ АЛГОРИТМА ПОТОЧНОГО ШИФРОВАНИЯ RC4.

2.1. Цикловая структура алгоритма RC4.

2.1.1. Циклы длины m(m-l) алгоритма RC4.

2.1.2. Изоморфные циклы в алгоритме RC4.

2.2. Статистические свойства алгоритма RC4.

2.2.1. Определение вероятностной модели.

2.2.2. Распределение первых знаков в гамме RC4.

2.2.3. Распределение биграмм в гамме RC4.

2.2.5. Критерий различения последовательности RC4 от случайной равновероятной последовательности.

2.3. Число ключей алгоритма RC4, приводящих к начальным подстановкам с произвольной фиксированной цикловой структурой.

2.4. Распределение t-грамм в начальной подстановки RC4.

2.5. Распределение первого знака алгоритма RC4 с учетом t-грамм.

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

Для таких крупнейших корпораций как Bosch, Merisel или Xerox, защищенные системы разработаны в России специалистами самих компаний или профессиональными контракторами. Некоторые компании, например, IBM, используют стандартную международную систему, адаптированную для российских реалий. Объединяет все эти системы, имеющие свои подсистемы защиты, использование стандартных средств Интернет для доступа к информации и осуществления бизнес-транзакций.

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

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

В значительной степени это объясняется разработанной теорией и удобством при аппаратной реализации алгоритмов шифрования. Для алгоритмов, основанных на регистрах сдвига над полем GF(2), достаточно хорошо разработаны методы синтеза и криптоанализа, в тоже время относительно мало изучены высокоскоростные программно реализуемые нерегистровые поточные алгоритмы и практически не развита теория их синтеза и методов криптоанализа, хотя при программной реализации они могут быть предпочтительнее.

Существенное повышение производительности микропроцессоров к 80-м годам вызвало в криптографии усиление интереса к программным методам реализации криптоалгоритмов как возможной альтернативе аппаратным схемам. Одним из самых первых подобных алгоритмов шифрования, получившим широкое распространение в электронной коммерции, стал RC4 (также известный как алгоритм ARCFOUR). Он, например, используется во многих платежных системах. В России, кроме RC4, программно реализуемыми поточными шифрами, используемыми в электронной коммерции, являются Веста-2, Веста-2М. Поэтому основное внимание в диссертации уделяется как программно реализуемым неригистровым шифрам: RC4, его модификациям (IA, IBAA, ISAAC), так и регистровым: Веста-2, Веста-2М. Рассмотренные алгоритмы включают большинство наиболее распространенные среди программно реализуемых поточных алгоритмов шифрования. Единство исследований достигается общей математической моделью, изложенной на теоретико-автоматном языке, едиными математическими методами.

Целью диссертационной работы является разработка общих математических моделей, включающих ряд алгоритмов шифрования и методов их криптоанализа; исследование криптографических свойств (теоретико-автоматных, теоретико-групповых, теоретиковероятностных) программно реализуемых поточных алгоритмов шифрования RC4 и различных его обобщений GI (IA, IBAA, ISAAC), Solitaire, Веста.

Для достижения поставленной цели, используя единую теоретико-автоматную модель, были решены следующие задачи:

• Проведен обзор современных программно реализуемых поточных алгоритмов и методов их криптоанализа в рамках этой модели;

• Введено в рамках теоретико-автоматной модели семейство алгоритмов поточного шифрования GI, обобщающее ряд алгоритмов шифрования (IA, IBAA, ISAAC), предложенных в открытой литературе, и получена верхняя оценка числа знаков, необходимых для восстановления начального состояния;

• Описан ряд криптографических свойств алгоритмов RC4, GI, Solitaire, Веста;

• Разработаны методы восстановления состояния по гамме алгоритмов GI и Веста, основанные на их алгебраических свойствах.

Отметим, что в последние 10 лет активно исследовались следующие программно реализуемые поточные алгоритмы: Pike, Scop, Dagger, Sober, Sober -tl6, Bmgl, Sober-t32, RSC, Lili, Leviathan, RC4, Wake, Seal, Twoprime, ISAAC, IA, IBAA, Chameleon, Panama, Rabbit, Solitaire, Веста, причем, из них только RC4, Wake, Веста используются практически.

Исследованием и разработкой алгоритмов, рассматриваемых в диссертации, занимались следующие известные криптографы: A. Shamir, J. Golic, R. Rivest, В. Schneier, L. Knudsen, V. Rijmen, B. Preneel, S. Fluhrer, D. McGrew, W. Meier, R. Jenkins, A.H. Лебедев.

Диссертация состоит из введения, пяти глав, списка литературы из 148 наименований. Работа изложена на 150 страницах с рисунками и таблицами.

5.10. Заключение

В пятой главе предложен метод, позволяющий частично линеаризовать некоторый класс фильтрующих генераторов над полем GF(p). Его применение продемонстрировано на примере алгоритмов Веста-2 и Веста-2М с тождественной перестановкой я. Трудоемкость предложенных методов для алгоритмов Веста-2М, Веста-2 с тождественной перестановкой п одинакова и в среднем равна Т„ =2316 э.о.(трудоемкость полного перебора 2544 э.о.).

Также рассмотрена задача определения начального состояния алгоритмов Веста-2М, Веста-2 с реальной перестановкой л. Она сводилась к восстановлению начального состояния линейного регистра по гамме и основана на частичной линеаризации криптоалгоритмов. Трудоемкость, предложенных методов, для алгоритма Веста-2М равна Тм = 2343'4 э.о., для алгоритма Веста-2 - Тм(4)=2345 э.о. (трудоемкость полного перебора 2544 э.о.).

Описан класс слабых (k-благоприятных) состояний алгоритма Веста-2. Показано, что для некоторого класса слабых состояний трудоемкость восстановления состояния алгоритма Веста-2 по гамме, не превышает 280 э.о.

Таким образом, если в гамме z встречаются постоянные подпоследовательности z*"1 , z";3\ , то можно предположить, что состояние линейного регистра сдвига является кблагоприятным и определить состояние алгоритма Веста-2 с трудоемкостью существенно меньшей трудоемкости полного перебора. Полученный результат не зависит от вида перестановки л, что является слабостью алгоритма Веста-2.

Показано, что группы, порождаемые алгоритмами Веста-2 и Веста-2М, изоморфны сплетению двух групп подстановок.

1. А.ГТ. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. Основы криптографии, учебное пособие.- М: Гелиос АРВ- 2001.

2. А.А. Варфоломеев, А.Е. Жуков, М.А. Пудовкина. Поточные криптосистемы. Основные свойства и методы анализа стойкости М: ПАИМС- 2000.

3. R.A. Rueppel, Stream ciphers.//Contemporary Cryptology: The Science of Information Integrity, G. Simmons ed., pp 65-134, New York: IEEE Press- 1991.

4. Бабаш A.B., Шанкин Г. П., Криптография М. СОЛОН-Р, 2002.

5. G. Rose, A stream cipher based on linear feedback over GF(28). //ACISP'98- Australian Conference on Information Security and Privacy- vol. 1438- Springer-Verlag.

6. Bleichenbacher D., Patel S., Sober cryptanalysis.// Fast Software Encryption(FSE) —1999— Springer-Verlag.

7. Biham E. New Types of Cryptoanalytic Attacks Using Related Keys.// Advances in Cryptology — EUROCRYPT '93- Springer-Verlag- 1994, pp. 398-409.

8. Daemen J., Clapp C., Fast Hashing and Stream Encryption with PANAMA.// Fast Software Encryption (Ed. S. Vaudenay}- LNCS 1372- Springer-Verlag- 1998, pp.60-74.

9. Rijmen V., Rompay В., Preneel В., Vadewalle J., Producing Collisions for PANAMA.// Fast Software Encryption- Springer-Verlag- 2001.

10. Пудовкина M. А., О слабостях криптосхемы PANAMA.// В сб. научных трудов XLIV юбилейной научной конференции МФТИ-Москва-Долгопрудный- 2001.

11. D. Watanabe, S. Furuya, Н. Yoshida, В. Preneel, A new keystream generator MUGI.// FSE'02- LNCS- Springer-Verlag- 2002.

12. E. Dawson, W. Millan, L. Penna, L. Simpson, Golic, The LILI-128 Keystream Generator, 2000, https://www.cosic.esat.kuleuven.ac.be/nessie/workshop/submissions.html/LILI-128

13. F. Jonsson, T. Johansson. A fast correlation attack on LILI-128.// Technical report- Lund University report- 2001.

14. M. O. Saarjnen. A time-memory tradeoff attack against LILI-128, 2001.// Presented at the Rump Session 2nd NESSIE Workshop. Available from http://eprint.iacr.org.

15. D.J. Wheeler, A Bulk Data Encryption Algorithm// Fast Software Encryption (Ed. R. Anderson)- LNCS, No. 809- Springer-Verlag- 1994, pp. 127-134.

16. Пудовкина M. А. О слабостях алгоритма поточного шифрования WAKE.// Труды семинара "Информационная безопасность-Юг России"-Таганрог-2001.

17. Pudovkina М., Analysis of chosen plaintext attacks on the WAKE Stream Cipher http://eprint.iacr.org/ report 2001/065.

18. Пудовкина M.A., О методе анализа алгоритма DAGGER по специально подобранному открытому тексту.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург-2001.

19. Simeon V. Maltchev, Peter Т. Antonov, The SCOP Stream Cipher, ftp://ftp.funet.fi/pub/crypt/cryptography/symmetric/scop/scop.tar.gz, Dec. 1997.

20. Пудовкина M. А., О слабостях криптосхемы SCOP.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург-2001.

21. Crowley P., Mirdek, http://www.hedonism.demon.co.uk/paul/crypto/mirdek/

22. Пудовкина М. А., Анализ криптосхемы Mirdek по специально подобранному открытому тексту.//Труды семинара "Информационная безопасность-Юг России"-Таганрог-2001.

23. SoftLabs, RSC Stream Cipher, http://www.safedisk.od.ua, http://www.softcomplete.com.

24. D. McGrew, S. Fluhrer. The stream cipher LEVIATHAN specification and supporting documentation, 2000, https://www.cosic.esat.kuleuven.ac.be/nessie/workshop/submissions.htm I/Leviathan

25. P. Crowley, S. Lucks, Bias in the LEVIATHAN stream cipher.// Advances in Cryptology-FSE' 2001-Springer-Verlag.

26. R. A. Fisher, F. Yates, Statistical Tables- London- 1938.

27. Golic, J. D, Linear Statistical Weakness of Alleged RC4 Keystream Generator.// Advances in Cryptology EUROCRYPT '97.

28. Fluhrer S., McGrew D. Statistical Analysis of the alleged RC4 keystream generator.// Advances in Cryptology- FSE'2000- Springer-Verlag.

29. Knudsen L., Meier W., Preneel В., Rijmen V., Verdoolaege S, Analysis method for (alleged) RC4// Proceeding of ASIACRYPT'99- Springer-Verlag-1999.

30. I. Mantin, A. Shamir, A practical attack on broadcast RC4// FSE'2001- Springer-Verlag-2001.

31. Wireless lan medium access control (MAC) and physical layer (PHY) specifications. (IEEE Standard 802.11), 1999, Edition, L.M.S.F. of IEEE Computer Society.

32. A. Rejnhold. The ciphersaber home page, 2002.

33. N.J.A. Sloan, Encryption by random rotations.// Eurocrypt'83- Springer-Verlag-1983.

34. Д. Э. Кнут, Искусство программирования, в 3 т.-М: Вильяме, 2000.

35. Глухов М.М., Зубов А. Ю. О длинах симметрических и знакопеременных групп подстановок в различных системах образующих (обзор).//Математические вопросы кибернетики- 1999.

36. Сачков В. Н. Введение в комбинаторные методы дискретной математики М.: Наука, 1982.384 с.

37. D. P. Robbins, E.D. Bolker. The bias of three pseudo-random shuffles.// Aequationes Mathematicae 22- 1981.

38. F. Schmidt, R. Simon. Card shuffling and a transformation on S„.// Aequationes Mathematicae 44-1992.

39. D. Goldstein, D. Moews, The identity is the most likely exchange shuffle for large n, arxiv:math.co/0010066 vl, 2000.

40. Колчин В.Ф., Случайные графы- M: ФИЗМАТЛИТ, 2000.

41. Mironov I. (Not So) Random shuffles of RC4.// Crypto-02- Springer-VerIag-2002.

42. Babbage S. Cryptanalysis of LILI-128.// In Proceedings of the 2 NESSIE Workshop- 2001.

43. R. Anderson, C. Manifavas, Chameleon A new kind of stream cipher.//FSE'97- Springer-Verlag-1997.

44. D. Copersmith, S. Halevi, C. Julta, Scream: a software-efficient stream cipher.// FSE'02-Springer-Verlag- 2002,.

45. D. Coppersmith, D.Wagner, J. Kelsey, Cryptanalysis of TWOPRIME.// Fast Software Encryption- 1998-Springer-Verlag.

46. Crowley P. Problems with Bruce Schneier "Solitaire". http://www.hedonism.demon.co.uk/paul/solitaire/

47. S.Fluher, I. Mantin, A. Shamir, Weaknesses in the key scheduling algorithm of RC4, SAC'2001- Springer-Verlag-2001.

48. C.Ding, V.Niemi, A.Renvall, A.Salomaa, TWOPRIME: A Fast Stream Ciphering Algorithm.// Fast Software Encryption- 1997- Springer-Verlag.

49. Golic J. D., Cryptanalysis of Alleged A5 Stream Cipher.//Eurocrypt '97- Springer-Verlag-1997.

50. Grosul A.L., Wallach D.S., A related key cryptanalysis of RC4- 2000, to appear.

51. Herve Chabanne , Emmanuel Michon, JEROBOAM. FSE '98- Springer-Verlag- 1998.

52. P. Hawkes, G. Rose, Primitive Specification and Supporting Documentation for SOBER-tl6 Submission to NESSIE, 2000, https://www.cosic.esat.kuleuven.ac.be/nessie/ workshop/submissions.html/SOBER-tl6

53. P. Hawkes, G. Rose. Primitive Specification and Supporting Documentation for SOBER-t32 Submission to NESSIE, 2000, https://www.cosic.esat.kuleuven.ac.be/nessie/ workshop/submissions.html/SOBER-t32

54. R. J. Jenkins " ISAAC" ,http://ourworld.compuserve.com/homepages/ bobjenkins/isaac.htm

55. R.J. Jenkins Jr., ISAAC.// Fast Software Encryption-Cambridge 1996, vol. 1039- D. Gollmann ed Springer-Verlag.

56. T. Johansson, P. Ekdahl. SNOW-a new stream cipher, 2000, https://www.cosic.esat.kuIeuven.ac.be/nessie/workshop/submissions.html/SNOW

57. Lidl R., Niederreiter H., Introduction to finite fields and their applications.- Cambridge University Press- 1986 (Ес^ русск. перевод)

58. Menezes A., van Oorschot P., Vanstone S. Handbook of applied cryptography- CRC Press-1996.

59. Mister S., Tavares S., Cryptanalysis of RC4-like ciphers.// Proceeding of SAC'98- Springer-Verlag.61. http://www.cryptonessie.org

60. Pudovkina M., A known plaintext attack on the ISAAC keystream generator, http://eprint.iacr.org/ report 2001/049.

61. Pudovkina M., Cryptanalysis of the Vesta-2M Stream Cipher, http://eprint.iacr.org/ report 2001/043.

62. Pudovkina M., Statistical weaknesses in the alleged RC4 keystream generator.// 4nd International Workshop on Computer Science and Information Technologies- CSIT'2002- Greece, Patras- 2002 .

63. Pudovkina M., Cryptanalysis of the RSC Stream Cipher.// 4nd International Workshop on Computer Science and Information Technologies- CSIT'2002- Patras, Greece- 2002 .

64. Pudovkina M., Short cycles of the alleged RC4 keystream generator.// 3nd International Workshop on Computer Science and Information Technologies- CSIT'2001- UFA- 2001.

65. Pudovkina M., Analysis of the IA Keystream Generator.// 3nd International Workshop on Computer Science and Information Technologies- CSIT'2001- UFA- 2001 .

66. Pudovkina M., Probabilistic relations for the jokers at the Solitaire keystream generator.// First International IFIP TC-11 WG 11.4 Working Conference on NETWORK SECURITY- Leuven-2001.

67. Pudovkina M., Varfolomeev A.A., A Cycle Structure of the Solitaire Keystream Generator.// 3nd International Workshop on Computer Science and Information Technologies-CSIT'2001-UFA- 2001 .

68. Ritter T. RNG Implementations: A Literature survey, http://www.io.com/~ritter/RES/RNGENS.HTM.

69. Ritter T. "The DAGGER Design An Extremely-Fast Commercial Cipher Engine", http\\www.io.com\~ritter\

70. Ritter T. 1990. Dynamic Substitution Combiner and Extractor. U.S. Patent 4,979,832.

71. Rivest R. Cryptography.Handbook of theoretical computer science- 1990.

72. Rivest R.L.,The RC4 encryption algorithm-RSA Data Security, Inc. -1992.

73. M.J.B. Robshaw. Stream Ciphers. Technical Report TR 401// RSA Laboratories, revised July 1995.

74. Rueppel R. Analysis and Design of Stream Ciphers.- Springer-Verlag- 1986.

75. Schneier B. Applied Cryptography-John Wiley&Sons-1996.

76. Schneier В., The Solitaire Encryption Algorithm, 1999, http://www.counterpane.com/solitaire.html.

77. Budi Sukmawan, SCOP, Stream Cipher Super Cepat, http://bdg.centrin.net.id/~ budskman/ scop.htm

78. D. Watanabe, S. Furuya, H. Yoshida, B. Preneel. A new keystream generator MUGI// FSE'02-LNCS- Springer-Verlag- 2002.

79. Боровков А. А. Теория вероятностей M., Наука, 1986.

80. В. Брауэр, Введение в теорию конечных автоматов.- М: Радио и связь, 1987.

81. Ван дер Варден Б. JT. Алгебра М.: Наука, 1979.

82. Варфоломеев А. А., Пудовкина М. А., О цикловой структуре алгоритма поточного шифрования Solitaire фирмы Counterpane// Безопасность Информационных Технологий- 4, 1999.

83. Варфоломеев А. А., Пудовкина М. А. Криптоанализ алгоритма поточного шифрования Solitaire.// Безопасность Информационных Технологий- 2, 2000.

84. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра.-части 1и 2-М. 1990.

85. М.М. Глухов, О 2-транзитивных произведениях регулярных групп подстановок.// Труды по дискретной математике-т.З-Физ-мат- 2000.

86. М.М. Глухов, О числовых параметрах, связанных с заданием конечных групп системами образующих элементов.// Труды по дискретной математике- т. 1— ТВП, 1997.

87. В.Б. Горяинов, И.В. Павлов, Г.М. Цветкова, О.И. Тескин, Математическая статистика.-М.: Изд-во МГТУ им Н.Э. Баумана, 2001.

88. Грэхм, Д. Кнут, О. Паташник, Конкретная математика. Основания информатики М, Мир, 1998.

89. Елизаров В. П. Конечные кольца. -М., 1993.

90. А.Ю. Зубов, О диаметре группы Sn относительно системы образующих, состоящих из полного цикла и транспозиции.//Труды по дискретной математике, т.2, ТВП- 1998.

91. Ивченко Г. И., Медведев Ю. И. Математическая статистика.- М., Высшая школа, 1984.

92. Камени Дж., Снелл Дж., Конечные цепи Маркова-М: Наука, 1970.

93. Клиффорд А., Престон Дж. Алгебраическая теория полугрупп М.: Мир, 1972. Т. 1, 285 е.; т. 2, 422 с.

94. Колчин В.Ф., Случайные отображения-М. Наука, 1984.

95. Колчин В.Ф., Системы случайных уравнений-М: МИЭМ, 1988.

96. Т. Кормен, Ч. Лейзер, Р. Ривест, Алгоритмы построение и анализ М: МЦНМО- 2000.

97. Колчин В.Ф., Севастьянов Б.А., Чистяков В.П., Случайные размещения М: Наука, 1976.

98. Леман Э., Проверка статистических гипотез, М: Наука, 1979.

99. Магнус В., Каррас А., Солитэр Д. Комбинаторная теория групп —М: Наука-1974.

100. Носов В.А. Основы теории алгоритмов и анализа их сложности, М. в/ч 33965, 1990.

101. ОСТ 51-08-98 Алгоритм формирования идентификатора доступа к данным.

102. ОСТ 51-06-98 Алгоритм кодирования данных.

103. Пудовкина М. А., О слабых состояниях криптосистемы IA.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»-Москва-2003.

104. Пудовкина М.А., Некоторые свойства и слабости алгоритма поточного шифрования JEROBOAM. //В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва-2000., с. 14-15 .

105. Пудовкина М. А., О распределение числа начальных подстановок с цикловой структурой {l"1"41 ,.,d',.,m0} в криптосистеме RC4.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург- 2002.

106. Пудовкина М. А., О свойствах алгоритма поточного шифрования RSC.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»-Москва- 2002.

107. Пудовкина М. А., О группе преобразований криптосистемы SOLITAIRE.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург- 2002.

108. Пудовкина М. А., О групповых свойствах алгоритма генерации начального состояния криптосистемы SOLITAIRE.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва-2003.

109. Пудовкина М. А., О числе ключей криптосхемы RC4, приводящих к подстановкам с одной цикловой структурой.// Безопасность Информационных Технологий-2, 2002.

110. Пудовкина М. А., Криптоанализ алгоритма поточного шифрования IBAA.// Безопасность Информационных Технологий- 3, 2001, с. 80-83.

111. Пудовкина М. А., О цикловой структуре алгоритма поточного шифрования RC4.// Безопасность Информационных Технологий- 4, 2000, с. 67-69.

112. Пудовкина М.А. Методы определения ключа криптосхемы «Веста-2М».// Безопасность Информационных Технологий-2, 2000, с. 31-36.

113. Пудовкина М.А., Криптоанализ алгоритма поточного шифрования JEROBOAM при некоторых ограничениях.// Безопасность Информационных Технологий- 2, 2000, с. 27-30.

114. Пудовкина М. А., Методы криптоанализа алгоритма поточного шифрования IA.// Безопасность Информационных Технологий- 3, 2000, с. 67-69.

115. Пудовкина М. А., Эквивалентные ключи RC4.// Безопасность Информационных Технологий-2, 2001, с. 69-72.

116. Пудовкина М. А., О слабых состояниях криптосистемы ВЕСТА-2.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»-Санкт-Петербург- 2002.

117. Пудовкина М.А., Вероятностные рекуррентные соотношения для поведения джокеров в криптосхеме Solitaire.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва- 2000, с.15-17.

118. Пудовкина М.А., О методе генерации начального состояния алгоритма поточного шифрования Solitaire.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва-2000, с. 10-11.

119. Пудовкина М. А., Свойства алгоритма поточного шифрования 1А.//Седьмой международный научный семинар "Дискретная математика и ее приложения"— Москва-МГУ, 2001.

120. Пудовкина М. А., О некоторых слабостях криптосистемы RC4. //Защита информации-2, 2002.

121. Пудовкина М. А., О свойствах алгоритма поточного шифрования JIOTO. //В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва- 2003.

122. Пудовкина М. А. Свойства криптосхемы Mirdek.// XXIII конференция молодых ученых мехмата МГУ-Москва- 2001.

123. Пудовкина М. А., Обзор поточных шифров и методов их анализа.// Защита информации- 3, 2002.

124. Б. А. Погорелов, Примитивные группы подстановок, содержащие 2т-цикл. //Алгебра и логика- 1980-т. 19, №2.

125. Б. А. Погорелов, Основы теории групп подстановок. I. Общие вопросы. —Москва, 1986.

126. Б. А. Погорелов, Группы подстановок. Часть I. (Обзор за 1981-95 гг.)// Труды по дискретной математике- т.2, ТВП- 1998.

127. Подуфалов Н. Д., Пудовкина М. А., Об анализе алгоритма поточного шифрования IBAA.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург- 2001.

128. Пудовкина М.А., Криптоанализ алгоритма поточного шифрования RC4.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»-Москва-2001, с. 83-85.

129. Пудовкина М. А., О распределении биграмм в криптосхеме RC4.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»-Москва- 2002.

130. Пудовкина М.А., Криптоанализ алгоритма поточного шифрования ISAAC.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы» Москва-2001, с. 85-87.

131. Пудовкина М. А., Об одной системе образующих с ограничениями.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»-Москва-2002.

132. Пудовкина М.А., О числе решений двухчленных систем случайных уравнений специального вида.// В сб. научных трудов конференции «Проблемы информационной безопасности в системе высшей школы»- Москва-2001, с. 88-90.

133. Пудовкина М. А., Метод криптоанализа фильтрующих генераторов над полем GF(p).// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»-Санкт-Петербург- 2000, с.120-122.

134. Пудовкина М. А., О новом виде алгоритмов поточного шифрования Хамелеон.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»- Санкт-Петербург- 2000, с. 122-124.

135. Пудовкина М. А., О свойствах алгоритма поточного шифрования RC4.// В сб. тезисов конференции «Методы и технические средства обеспечения безопасности информации»-Санкт-Петербург- 2001.

136. Пудовкина М.А., Методы определения ключа криптосхемы «Веста-2».// Труды семинара "Информационная безопасность-Юг России"- Таганрог- 2001.

137. Пудовкина М. А., О распределении первого выходного символа криптосхемы RC4.// В сб. научных трудов XLIV юбилейной научной конференции МФТИ.- Москва -Долгопрудный, 2001.

138. Поточные шифры. Результаты зарубежной открытой криптологии. http://www.ssl.stu.neva.ru/ctypto.htrnl/

139. Ростовцев А.Г., Алгебраические основы криптографии.- СПб.: НПО "Мир и семья", 2000.

140. В.Н. Сачков, Группы подстановок и полугруппы преобразований с заданным числом образующих.//Труды по дискретной математике, т.З, Физ-мат, 2000.

141. Супруненко Д. А., Группы матриц.-М.: Наука, 1972. 351 с.

142. М.В. Федюкин, О полугруппе преобразований конечного множества, порожденной случайными образующими// Дискретная математика, т. 13, вып. 2, 2001.

143. Феллер В., Введение в теорию вероятностей и ее приложения М: Мир, 1984

144. Ю.С. Харин, В.И. Берник, Г.В. Матвеев, Математические основы криптологии-Минск, Б ГУ, 1999.

145. Шафаревич И. Р., Основные понятия алгебры. Современные проблемы математики. Фундаментальные направления. Т. 11. Итоги науки и техники. ВИНИТИ АН СССР.- М., 1985.1. Основные обозначения

146. Х| модуль числа X, или мощность множества X, или длина последовательности, или вес X;

147. Fq =GF{q) конечное поле из q элементов;

148. Zm={0,l,.,m-1}- множество классов вычетов целых чисел по модулю т; Fn(qb n-мерное векторное пространство над полем Fq; Vn- n-мерное векторное пространство над полем F2;

149. Fk(*,*), F(*,*) — функция переходов состояний автомата, соответственно, зависящая и независящая от ключа к;

150. Л(>), Л>)— функция выходов автомата, соответственно, зависящая и независящая от ключа к

151. R множество вещественных чисел;х., UJ целая часть числа xeR, наибольшее целое п<х;

152. Гд:1 наименьшее целое п>х;0 1 . т-1 ^последовательность 5=<^0., 5[l].5[w-l]> или таблица s= запись0. s 1] . s[m- l]Jподстановки seSm\

153. Р{А | В} условная вероятность, вероятность того, что произойдет событие А при условии, что событие В произошло;

154. Р{А} вероятность наступления случайного события А; m<->v - поменять местами значения переменных и, v;

155. Кег ф ( Кег ф | X) ядро отображения ф (при ограничение его на множество X);

156. Р>- циклическая группа с образующим элементом Р;

157. Р\, Р2,.,Рп>- группа, порожденная п элементами Р\, Р2,.,Рп\

158. Е-тождественная подстановка (перестановка);s)<Pi, P2,.,Pn>=s<P\, Р2,--;Рп>-орбита элемента 5 в группе (полугруппе) <Р\, Р2,.,Рп>',

159. G{a} -стабилизатор множества Л в целом;

160. Gj- поточечный стабилизатор множества Л в группе G;

161. Gx (gx У- офаничение действия группы (элемента) на множество X;

162. Н< G (Н< G)~ Н-подгруппа (соответственноH*G) группы G;

163. As=Ag={ag | аеД}, где g элемент G группа (полугруппа) преобразований, действующая на множестве X, Дс: X;

164. Замечание. Все рассматриваемые в работе алгебраические структуры (множества, поля, кольца, векторные пространства) являются конечными.