Статистические атаки на подстановочные и перестановочные шифры, частотный анализ

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

Частотный анализ – раздел криптоанализа, занимающийся расшифровкой перечисленных шифров на основе статистических свойств языка исходного текста:

1. Частота встречающихся монограмм(отдельных символов), биграмм(пар букв) и т. п.
2. Частота появления буквы на первой, второй и т.д. позиции в словах языка.
3. Частота появления сдвоенных символов
4. Анализ слов по частоте употребления в тексте слов из определенного числа символов.

Анализ подстановочных шифров оуществляется путем сопоставления частот символов обычных текстов и зашифрованного.(Т. е. если в нормальных текстах буква А - каждая 17-ая, а в зашифрованном тексте буква Ц – каждая 17-ая, то можно предположить, что подстановка заменила А на Ц), аналогично для перестановочных шифров сопоставляется частота появления символов на определенных позициях (буква О с вероятностью в 21% является первой в словах обычного текста, а в зашифрованном она с той же вероятностью является третьей. Можно предположить, что первый символ был переставлен на третью позицию).

 

9. Мера информации: понятие собственной информации и энтропии, энтропия естественного языка, избыточность естественного языка.

Собственная информация символа – это величина обратно пропорциональная вероятности его появления в тексте (чем меньше ожидается символ, тем он более информативен), она обозначается как I и определяется следующим образом:

,

где - вероятность появления символа в тексте, а - собственная информация символа .

 

Информационная энтропия — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

 

- формула энтропии

В идеальном случае, когда появления всех символов равновероятно энтропия равна:

,

где k – число символов в алфавите. Для любого k:

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u») количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия), очевидно, меньше. Для учёта таких фактов используется условная энтропия и условная мера информации:

- условная мера информации

- условная энтропия.

 

Взаимная энтропия

Взаимная энтропия или энтропия объединения предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H(AB):

- взаимная мера информации

- взаимная энтропия.

 

Энтропия естественного языка на основе алфавита А, определяется, как:

 

- где N- длина слова.

Устремив N к бесконечности можно получить энтропию языка в целом:

 

Тогда избыточность естественного языка, показывающая избыточность информации в тексте на таком языке, будет определяться как:

10. Блочные шифры. Атака созданием кодовой книги. Режим электронной книги, режим сцепления блоков зашифрованного текста: достоинства и недостатки.

 

Блочный шифр – симметричный шифр, выполняющий преобразование над группой бит фиксированной длины (блоком).

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

Но длина самой книги равна 2ⁿ, где n -длина блока и уже при длине блока в 50 символов книга будет занимать больше миллиона терабайт, что делает ее хранение практически невозможным.

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

 

Режимы работы блочных шифров:

 

1. Режим электронной книги:

 

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

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

Ошибка при шифровании в этом режиме повреждает только один блок, в котором она и была допущена.

 

1. Режим обратной связи по шифротексту.

 

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

1. Неуязвимость к атаке по кодовой книге

Недостатки:

a. Только последовательное шифрование

b. Теряется произвольный доступ

c. Ошибка шифрования распространяется на два блока

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

 

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

 

1. Режим обратной связи по зашифрованному тексту:

Шифрование

Свойства:

1. Нет произвольного доступа к блокам
2. Ошибка влияет на два блока
3. Используется одна и та же функция, как в шифровке, так и в расшифровке

 

1. Режим обратной связи по выходу:

Шифрование

 

Расшифрование

Свойства:

1. Произвольный доступ к блокам, если заранее произвести все операции шифрования над вектором инициализации)
2. Ошибка влияет только на один блок

 

1. Режим счетчика

Шифрование

В самом простом случае f – это простая операция инкрементирования, таким образом входной вектор на каждой операции шифрования – это просто счетчик с номером текущего блока

Расшифрование

Свойства этого режима аналогичны предыдущем, за исключением того, что обеспечить произвольный доступ легче – для доступа к n-ному блоку не нужно выполнять заранее n операций шифрования, а достаточно n-1 раз выполнить функцию f и 1 раз операцию шифрования.

 

 

12. Параметры блочного шифра: длина блока, длина ключа. Смешивание и рассеивание, линейные и нелинейные преобразования. Понятие итерационного шифра. Понятие алгоритма развертки ключа.

 

Длина блока: n>= 64 бит для исключения атака по кодовой книге

Длина ключа: k>= 64 бит для исключения атаки полным перебором

Для противостояния всем 4 видам атак должны выполняться следующие два действия:

1. Смешивание – использование смеси линейных и нелинейных преобразований
2. Рассеивание – каждый бит открытого текста и каждый бит ключа влияют на все биты зашифрованного, чтобы исключить частотный анализ

Линейные преобразования: преобразования, которые позволяют по паре открытый и зашифрованный текст восстановить ключ шифрования.

Нелинейные преобразования не допускают подобного.

 

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

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

 

13. Сеть Feistel и шифр Feistel: достоинства, функция раунда, примеры шифров с параметрами. Эквивалентные ключи: пример.

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

 

Достоинства и недостатки:

Достоинства:

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

Недостатки:

1. За один раунд шифруется только половина входного блока

 

 

Параметры шифров на сете Фейстеля:

1. Длина исходного текста m
2. Длина ключа к
3. Кол-во раундов N
4. Функция раунда
5. Алгоритм развертки ключа

Пример шифра с переменными значениями параметров: TEA(tiny encryption algorithm)

 

Количество раундов в данном шифре по умолчанию равно 64, но может быть изменено от 16 до 128, хотя т. н. «эффективная диффузия»(смешивание) достигается только за 32 раунда.

 

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

Тот же TEA является и примером криптосистемы с эквивалентными ключами. Дело в том, что на каждом нечетном раунде в нем используются под ключи K0 и K1, а на каждом четном K2 и K3 (по 32 бита каждый), каждый из которых соответствует одной четверти исходного ключа K(128 бит). В силу этого и самой структуры алгоритма получается, что каждый ключи имеет по три ему эквивалентных:

1 ключ	K0	K1	K2	K3
2 ключ	K0+231	K1+231	K2	K3
3 ключ	K0	K1	K2+231	K3+231
4 ключ	K0+231	K1+231	K2+231	K3+231

 

 

14. Минимальное число раундов в шифре Feistel. Атаки типа «встреча посередине» и «разделяй и властвуй»: примеры. Слабые ключи и слабые шифрующие функции.

 

Минимальное число раундов в шифвре Feistel напрямую зависит от длины ключа, в силу возможности применения атаки «встречи по середине». Количество раундов должно выбираться таким образом, чтобы данная атака не оказалась легче, чем подбор ключа полным перебором.

 

Атака типа встречи по середине заключается в проведение математических преобразований над результатами на каждом раунде и ключами раундов, чтобы выразить часть ключей друг через друга и результаты раундов. В таком случае подбирать надо только часть ключей раунда, что упрощает атаку полным перебором.. Возможность подобных атак показывает, что количество раундов следует выбирать в зависимости от длины ключа(т.к. атака в любом случае будет проходить по более слабому параметру). Для 64 битного ключа – минимальное кол-во раундов – 4.

Пример:

Пусть сеть состоит из 4 раундов с шифрующей функцией F. Тогда конечный результат можно записать, как:

, где F_k3 – шифрующая функция на ключе k3 и т. д.

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

Поскольку, очевидно что каждый этап дешифрации нейтрализует один этап шифрования, то можно предположить, что:

- т. е. результат первых двух раундов шифрования совпадет с результатом первых двух раундов дешифрации.

Тогда владея парой C и P, злоумышленник может полным перебором для пары ключей раунда k0 и k1 найти все значения , а для пары ключей раунда k2 и k3 – все значения . Далее ему останется лишь сравнить эти два набора значений и выбрать все случаи, когда они равны, как ключи подозрительные на истинность. Перебор подозрительных ключей даст в результате истинный ключ. Если считать, что каждый ki имеет длину N, то такая атака использует перебор в размере 2^2N+2^2N+k, где k- число подозрительных ключей. А полный перебор потребовал бы обработать 2^4N вариантов

 

 

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

 

 

Пример:

Тогда обозначив правый и левый вход сети Фейстеля, как L и R, получим итерационную систему уравнений:

, где Ki по переменно принимает значения K1 и K2

Выделим подзадачу нахождения последнего бита ключа из последних битов L и R Для отдельных битов двух чисел операция сложения эквивалентна операция сложения по модуля два между ними и битом переноса с прошлых двух битов:

, где N[k] – перенос с k-1-ых на k-тые биты на i-том шаге. Поскольку для последних битов перенос всегда равен нулю для них задача упрощается:

Теперь, если пройти по всей итерационной формуле, получим:

…

Поскольку и R0, L0(исходный текст) и R64, L64(зашифрованный текст) нам известны, то можно найти и K2[0] и K1[0]. Дальше зная их, можно посчитать бит переноса N[1] на каждом шаге итераций и составить такую же систему для 1-ых битов, найдя из нее K2[1] и K1[1]. Повторять до нахождения всех битов обоих ключей раунда.

 

 

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

 

 

15. Линейный криптоанализ блочных шифров: пример линейного приближения и вычисления вероятности приближения.

Криптоанализ происходит в два шага:

1. Построение соотношений между открытым текстом, шифротекстом и ключом, которые справедливы с высокой вероятностью.
2. Использование этих соотношений вместе с известными парами открытый текст — шифротекст для получения битов ключа.

Пример: пусть шифрующая функция: . Ее таблица истинности для каждого отдельного бита следующая:

A	B	C	F

 

Таким образом, заданную F можно аппроксимировать выражением с вероятностью (7 из 8 строк таблицы истинности совпадают у F и F’). Вероятность правильности аппроксимации для текста в N бит равна

16. Разностный криптоанализ блочных шифров и атака на основе подобранного зашифрованного текста: пример восстановления ключа.

 

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

Дифференциальный криптоанализ применим для взлома DES и некоторые других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES и др.) рассчитывалось с учетом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.

 

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

 

Пример:

p, p’ – пара открытых текстов

c, c’ – пара зашифрованных текстов.

- характеристики открытого и зашифрованного текста.

Теперь, если подобрать p и p’ такие, что , то:

Отсюда можно узнать N-1 бит k₀. Оставшийся бит теряется из-за сдвига и должен быть восстановлен полным перебором (всех 2-х вариантов!).

 

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

 

Параметры:

1. Длина текста - 64 бита

2. Длина ключа – 56 бит(+ 8 бит проверки на четность)

3. Кол-во раундов – 16

Схема

 

Функция раунда (слева) и алгоритм развертки ключа(справа)

 

Таким образом DES представляет собой 16-раундную сеть Фейстеля, где функция шифрования включает в себя расширение 32-битного блока до 48-бит, XOR его с 48-битным ключом, затем обратное сжатие результат до 32-бит и перестановку. Кроме того, как видно из общей схемы, сама сеть Фейстеля также обрамлена начальной и конечной перестановкой.

Развертка ключа производится в два этапа:

1. Из исходного ключа конструируются два вектора С₀ и D₀ – каждый равный по размеру половину ключа(без учетов 8 битов контроля нечетности), но получаемые сложной перестановкой из его битов.
2. Каждый из векторов С и D циклически сдвигается влево на три бита, после чего из объединенного вектора CD сжимающей перестановкой получается очередной ключ раунда.

Криптостойскость DES:

1. Нелинейность преобразований в DES средствами только S-блоков, и использование слабых S-блоков позволяет осуществлять контроль за шифрованной перепиской.
2. Из-за небольшого числа возможных ключей (всего ), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время. В 1998 году Electronic Frontier Foundation используя специальный компьютер DES-Cracker, удалось взломать DES за 3 дня.

 

3DES – улучшение DES:

Ключ длиной в 168 бит (3*56). Алгоритм реализуется, как троекратное применение DES на основе трех частей полной ключа:

- шифрование

- расшифровка

При этом вводится ограничение, что каждая из трех частей ключа не совпадает с другой (или по крайней мере k2 не совпадает с k1 и k3).

3DES лишен уязвимости к полному перебору, т. к. число возможных ключей теперь лишь несколько меньше, чем 2¹⁶⁸(меньше из-за ограничение на неповторимость частей). Однако, второй нарекание к криптостойкости сохраняется.

 

18. Шифр ГОСТ 28147-89: параметры, общая схема шифрования и дешифрования, функция раунда, алгоритм развертки ключей, использование шифра в РФ.

 

Параметры:

1. Длина текста - 64 бита

2. Длина ключа – 256 бит

3. Кол-во раундов – 32

Функция раунда

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

При расшифровке ключи следует подавать в тот же алгоритм в обратном порядке.

 

19. Операция над элементами множества. Группа и абелева группа: определение, порядок, примеры.

 

Группа – множество элементов с заданной над ними бинарной операцией (принимающей два аргумента и возвращающей один результат)

Операция должна быть:

1. Замкнутой (принимает элементы множествава и возвращает элемент того же множества)
2. Ассоциативной(неважно в каком порядке выполняются операции – справа налево или слева направо: (а*б)*с=а*(б*с))
3. Существует нейтральный элемент, такой что а*е=е*а=а
4. Для любого элемента существует обратный элемент: а*а^-1=е

Абелева группа требует также

1. Коммутативность: а*б=б*а

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

1. Операция замкнута – сумма двух целых чисел – целое число
2. Операция сложения ассоциативна
3. Нейтральный элемент – ноль
4. Обратный элемент к числу – это оно же с противоположным знаком
5. Операция сложения коммутативна.

Пример некоммутативной группы: группа из всех матриц перестановок с числом столбцов больше 2-х. Например:

Операцией в данном случае будет объединение(произведение) перестановок. Так, например:

1. Операции замкнуты. Любая перестановка из трех элементов входит в множество и последовательные две перестановки всегда дадут некую объединенную перестановку.
2. Операция ассоциативна.
3. Нейтральный элемент:
4. Обратный элемент существует для каждой матрицы, а именно - обратны друг другу, а каждая оставшаяся перестановка обратна самой себе.
5. Операция НЕ коммутативна, так: , а не

20. Операции над элементами множества. Кольцо и коммутативное кольцо: определение, примеры коммутативных и некоммутативных колец.

Кольцо – множество элементов с заданными над ними двумя операциями. Первая операция должна образовывать с множеством Абелеву группу. Для второй должны выполняться:

1. Замкнутость: принимает элементы множества и возвращает элемент того же множества
2. Ассоциативность (неважно в каком порядке выполняются операции – справа налево или слева направо: (а*б)*с=а*(б*с))
3. Дистрибутивность с первой операцией ((a+b)*c=a*c+b*c)

Если выполняется еще и

1. Коммутативность: а*б=б*а,

то это коммутативное кольцо

Примеры:

Коммутативное кольцо: множество целых чисел с операциями сложения и умножения:

1. Про сложение см. выше
2. Умножение целых чисел – замкнуто
3. Умножение целых чисел - ассоциативно
4. Умножение целых чисел дистрибутивно по отношению к сложению
5. Умножение целых чисел – коммутативно

Некоммутативное кольцо: множество квадратных матриц с операциями сложения и умножения:

1. Сложение матриц – замкнуто, ассоциативно, коммутативно, нейтральный элемент – матрица из нулей, обратный элемент – матрица с обратными знаками элементов
2. Умножение квадратных матриц – замкнуто
3. Умножение квадратных матриц - ассоциативно
4. Умножение квадратных матриц дистрибутивно по отношению к их сложению
5. Умножение матриц НЕ коммутативно. И в случае квадратных тоже.

 

21. Поле и простое конечное поле: определение, связь с кольцом, примеры.

Поле – множество элементов с заданными над ними двумя операциями. Первая операция должна образовывать с множеством Абелеву группу. Для второй должны выполняться:

1. Замкнутость
2. Без нейтрального элемента по первой множество образует с ней также Абелеву группу
3. Дистрибутивность с первой операцией((a+b)*c=a*c+b*c)

Поле – это коммутативное кольца с единицей(то есть коммутативное кольцо, где есть нейтральный элемент по второй операции), в котором каждый ненулевой(не являющийся нейтральным по первой операции) элемент имеет обратный элемент по второй операции.

Следствие: любое поле на двух операциях, это всегда коммутативное кольцо на них же.

 

Пример: множество рациональных чисел.

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

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

Пример простоты: множество вещественных чисел с операциями сложения и умножения – это не простое поле, т. к. из него можно выделить подмножество рациональных чисел, которые также будут полем на операциях сложения и умножения. А вот из самого множества рациональных чисел выделить подмножество уже нельзя, следовательно это простое поле.

Пример простого конечного поля: множество целых чисел от 0 до N-1 c операциями сложения и умножения по модулю N, где N- простое число. Например {0,1,2} и +mod(3) и *mod(3).

 

22. Расширение простого конечного поля: примитивный элемент и примитивный многочлен, операция деления, пример.

Алгебраическое расширение поля – это также поле, содержащее исходное поле в качестве подполя и при этом все элементы, входящего в него множества являются корнями из многочленов с коэффициентами взятыми из множества исходного поля.

 

Примитивный элемент конечного поля GF(p^m)(т. е. поля содержащего p^m элементов) – элемент, который при возведении в степень p^m-1 становится равен 1, но не равен 1 при любой степень 0< и < p^m-1. Другими словами, возводя его в последовательные степени по очереди будут получаться все элементы поля кроме 0, при этом 1 будет получена последней.

 

Примитивный многочлен - минимальный многочлен примитивного элемента(многочлен который не раскладывается на произведение многочленов низшей степени)

 

Основываясь на том, что любое двоичное число можно представить в качестве многочлена, использую биты как коэффициенты. И все эти многочлены могут быть получены путем возведения примитивного многочлена в некую степень, то деление может быть заменено на домножение на число, соответствующее многочлену полученному путем возведения примитивного элемента в степень = (p^m-1 – k, где k степень многочлена, соответствующего делителю)(домножение на обратное).

Пример: поле содержащее 8 элементов:

		нет
		a0=а7
	a	a1
	a2	a2
	a+1	a3
	a2+1	a4
	a2+a	a5
	a2+a+1	a6

 

Тогда деление будет осуществлять следующим образом:

 

23. Шифр AES (Rijndael): параметры, общая схема шифрования и дешифрования, подстановка, сдвиг, смешивание, смешивание с ключом, особенности использования.

 

Параметры:

1. Длина текста - 128 бит
2. Длина ключа – 128/192/256 бит
3. Кол-во раундов – 10/12/14

Схема:

S:=AddRoundKey(S,k0)

For i:=1 to 9 do

S:=Subbytes(S)

S:=ShiftRows(S)

S:=MixColumns(S);

S:=AddRoundKey(S,ki)

Endfor;

S:=Subbytes(S)

S:=ShiftRows(S)

S:=AddRoundKey(S,kn)

Дешифровка осуществляется путем выполнения операций в обратном порядке

 

Ф-ции:

1. Subbytes(S) – преобразует каждый входной байт х в y=Ax^-1+b – где x^-1 обратный элемент по GF(2⁸) – это операция подстановки
2. ShiftRows(S) – 16 байт записываются в виде матрицы 4*4, где каждая строка побитно сдвигается влево на свой номер(нумерация с нуля) – это операция сдвига
3. В процедуре MixColumns, четыре байта каждой колонки State смешиваются, используя для этого обратимую линейную трансформацию. Она обрабатывает состояния по колонкам, трактуя каждую из них как полином четвёртой степени. Над этими полиномами производится умножение в GF (2⁸) по модулю x ⁴ + 1 на фиксированный многочлен c (x) = 3 x ³ + x ² + x + 2 – это операциям смешивание
4. AddRoundKey(S,k) производит побитный S xor K – это операция смешивания с ключом

 

Шифр одноразовый блокнот. Поточные шифры и задача генерации равномерно распределенных псевдослучайных чисел. Линейный конгруэнтный генератор псевдослучайных чисел и его криптоанализ.

 

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

 

Одноразовый блокнот – зашифрованный текст получается путем операции XOR(«исключающее или») открытого текста с результатом преобразования ключа. Это преобразование должно приводить ключ к произвольной длине открытого текста и по сути решает проблему генерации псевдослучайных чисел на основе данного ей ключа. Одним из вариантов решения подобной задачи является линейный конгруэнтный генератор псевдослучайных чисел:

 

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

 

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

 

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

 

Альтернатива линейному конгруэнтному генератору более стойкая к криптоанализу – это регистр сдвига с линейной обратной связью:

 

Общая схема регистра сдвига с линейной обратной связью

Математическое описание:

В качестве функции обратной связи берётся логическая операция XOR (исключающее ИЛИ), то есть:

• на первом шаге:
• на втором шаге:
• …
• на j − L − 1-м шаге:

Где каждый коэффициент с_i - это либо 0, либо 1.

 

Пример: Пусть имеется четыре регистра, начальные значения которых A1=1, A2=0, A3=0. A4=0. Коэффициенты С имеют значения C1=1,C2=0, С3=1, C4=1 реализуя уравнение: . Тогда псевдослучайная последовательность примет вид:

Номер шага	A1	A2	A3	A4	S	Выход системы
						нет

 

- как видно из таблицы за 6 шагов система вернулась к начальному состоянию. Следовательно ее период равен 6. (А максимальный мог бы быть 15)

Так как существует 2L − 1 разных ненулевых состояний регистра, то период последовательности, генерируемой РСЛОС при любом ненулевом начальном состоянии, не превышает 2L − 1. При этом период зависит от ассоциированного многочлена:

• если старший коэффициент ассоциированного многочлена CL равен нулю, то периодичная часть генерируемой последовательности может проявляться не сразу;
• если CL = 1, то соответствующая последовательность называется неособой. Такая последовательность начинается со своей периодичной части. Наиболее интересны неособые последовательности, соответствующие многочленам со следующими дополнительными свойствами:
• если C(x) неприводим, то при любом ненулевом начальном состоянии регистра период генерируемой последовательности равен наименьшему числу N, при котором многочлен C(x) делит 1 + xN. Как следствие, период последовательности будет делить число 2L − 1;
• если C(x) примитивен (то есть, является делителем , но не является делителем xd + 1 для всех d, делящих 2L − 1), то любое ненулевое начальное состояние регистра дает последовательность с максимально возможным периодом 2L − 1. Например, РСЛОС с отводной последовательностью, состоящей из первого и четвёртого битов имеет максимальный период тогда и только тогда, когда ассоциированный многочлен x⁴ + x + 1 является примитивным.

 

 

В случае криптоанализа для нахождения всех последующих чисел необходимо знать о