Генераторы ПСП

k₀,k₁,…,k₇,k₀,k₁,…,k₇,k₀,k₁,…,k₇,k₇,k₆,…,k₀

Таким образом, в состав раунда ГОСТа  входят следующие преобразования 32-разрядных  двоичных наборов:

сложение правой половины R-блока данных с раундовым ключом;

разбиение результата на восемь 4-битовых  элементов и замена каждого из них по таблице замен;

циклический сдвиг результата на 11 разрядов влево;

поразрядное сложение по модулю 2 (XOR) результата с левой половиной L блока данных;

новое значение элемента L становится равным R, новое значение элемента R становится равным результату предыдущей операции.

32-й раунд отличается от остальных  – в нем отсутствует последняя  операция.

 

Перемешивание и рассеивание  информации (за счёт чего достигается)

 

2 раунд обеспечивает полное  рассеивание и перемешивание  информации.

 

Генератор ПСП – RC4

Алгоритм работы. Математическая модель

 

Одним из лучших поточных шифров является RC4 – шифр с переменным размером ключа, разработанный Р.Ривестом. Криптоалгоритм работает в режиме OFB, т.е. поток ключевой информации не зависит от открытого текста. Используются два 8-разрядных счетчика QI и Q2 и 8-разрядный блок замены (5-блок), таблица замен имеет размерность 8х256 и является перестановкой (зависящей от ключа) двоичных чисел от 0 до 255.

Схема генератора ПСП RCA

Рассмотрим алгоритм работы 8-разрядного генератора ПСП RC4, точнее, процедуру генерации очередного байта гаммы. Пусть S(i) и γ – содержимое ячейки с адресом i таблицы замен 5-блока и очередной байт гаммы.

Один такт работы генератора ПСП  RC4:

Такт работы первого счетчика:

.

Такт работы второго счетчика:

.

Ячейки таблицы замен 5-блока  с адресами Q1 и Q2 обмениваются своим содержимым:

.

Вычисление суммы содержимого  ячеек таблицы замен 5-блока с  адресами Q1 и Q2:

.

Считывание содержимого ячейки таблицы замен 5-блока с адресом T:

.

Таблица замен 5-блока медленно изменяется при использовании, при этом счетчик  Q1 обеспечивает изменение каждого элемента таблицы, a Q2 гарантирует, что элементы таблицы изменяются случайным образом.

Генератор ПСП Э.Блюм – М.Блюма

Рассмотрим так называемый BBS-генератор, получивший свое название в честь авторов Э.Блюм, М.Блюма и М. Шуба, основанный на криптосистеме Блюма.

Пусть p и q – два больших простых числа примерно одинакового размера, причем

.

Тогда число  называется целым числом Блюма. Пусть – множество целых положительных чисел, меньших n, которые не делятся ни на p, ни на q. Пусть QR_n – подмножество состоящее из квадратичных вычетов по модулю n. Число элементов множества равно , причем в точности четвертую их часть составляют элементы подмножества QR_n. Каждый элемент QR_n имеет ровно четыре различных квадратных корня в , из них лишь один, называемый примитивным, принадлежит QR_n.

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

эффективно вычисляется, а произвести обратное преобразование может лишь тот, кто знает 
секрет – разложение n на множители. Пусть n – целое число Блюма.

 

Генератор ПСП  Э. Блюм – М. Блюма – М. Шуба

 

Выберем в качестве инициализирующего  вектора случайное число  . Для этого возьмем случайное число x, такое, что , и вычислим

.

Искомой последовательностью бит  длиной m будет являться последовательность

,

где b_i – младший бит числа x_i,

.

Важным достоинством этого генератора является то, что при знании разложения n на множители он допускает прямое определение отдельных бит, которые в нем вырабатываются. Имеем

.

По теореме Эйлера

,

а значит,

,

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

Аналогичным образом можно построить  генератор ПСП на основе другой односторонней  функции с секретом, например, лежащей  в основе криптосистемы RSA, т.е. на основе функции

,

где ; p и q – простые числа, причем р ≠ q, а e взаимно простое с .

 

Операции сложения, вычитания, умножения  и деления в поле GF(2⁴). Их вид.

Элементами поля GF(2ⁿ) являются двоичные многочлены степени меньшей и, которые могут быть заданы строкой своих коэффициентов, т. е. в виде w-разрядных двоичных кодов.

Сложение в поле GF(2ⁿ) - это обычная операция сложения многочленов с использованием операции XOR при приведении подобных членов; или операция поразрядного XOR, если элементы поля представлены в виде строки коэффициентов соответст вующих многочледов. Например, в поле GF(2b> элементами которого являются двоичные многочлены, степень которых меньше восьми, байту 01010111 ({57} в шестнадцатеричной форме) соответствует многочлен

х⁶+х⁴ + х² + х + 1.

 

Устройства, соответствующие характеристическому  многочлену                                 φ(x) = x⁴ + x³ + x² + x + 1

 

Пример  выполнения сложения в поле GF(2⁸):

{57} + {83} = {D4}, так как

(х⁶ + х⁴ + £ + х + 1) + (х⁷ + х + 1) = х⁷ + х^в + х⁴ + х², или

01010111 4-10000011 = 11010100.

Программная реализация операции умножения двух элементов а и Р поля GF(2ⁿ) может быть выполнена двумя способами: табличным и вычислением результата аР «на лету».

 

а - LFSR, соответствующий характеристическому многочлену

ф(х)=х⁸ + х⁴ + х³ + х + 1;

б - генератор элементов 6F(2⁸) 
Имеем:

ф(х + 1) = (х + 1)⁸+(х + 1)⁴+(х + 1)³ + (х + 1) + 1 = = (х⁸+1) + (х⁴ + 1) + (х³+х²+х + 1) + (^ + 1) + 1 = = х⁸ + х⁴ + х³ + х² +1 = <р(х).

 
^{Сложение и умножение  в поле GF(2n)}

 

Пусть, например, для построения поля GF(2 ) выбран

<р(х) = х⁸ + х⁴ + х³ + х + 1

- неприводимый многочлен показателя 51. Диаграмма состояний соответствующего ему устройства (рис. 2.8, а), один такт работы которого суть умножение на х по модулю <р (х), имеет 5 кодовых колец по 51 состоянию в каждом и один вырожденный тривиальный цикл, соответствующий состоянию {00} (hex), переходящему самому в себя. Определим структуру устройства (генераторалементов поля), позволяющего сопоставить каждому ненулевому элементу поля соответствующую степень примитивного элемента.

 
Устройства, функционирующие в GF(L), L > 2

Пусть L>2- степень простого числа, GF(L) - поле Галуа из L элементов. Общий вид генератора L-рйчных последовательностей, соответствующего уравнению

Q(t+l) = fQ(t),

где Q(t) и Q(t+1) - состояния генератора соответственно в моменты времени t и t + 1 (до и после прихода синхроимпульса) 
Величина, на которую происходит умножение в каждом блоке умножения (БУ), определяется соответствующим коэффициентом

щ G   GF(L) сопровождающей матрицы  V = 7* (/ = 0,(N-1),

7=0,(^-1)). Если a,j = 0, это эквивалентно отсутствию связи

между выходом /-го элемента памяти ГПК  и входом /то блока сложения (БС). Если щ= 1, это эквивалентно наличию связи между выходом 1-го элемента памяти генератора и входом /-го блока сложения. При L = 2" блоки сложения и умножения в поле GF(T) реализуются на сумматорах по модулю два. 
Максимально возможное число состояний устройства, а значит, и максимально возможная длина формируемой L-ричной последовательности, снимаемой с выхода любого из элементов памяти, равны L^N - 1. В этом случае диаграмма состояний генератора состоит из одного тривиального цикла и цикла максимальной длины L^N - 1.

 

Генераторы M – последовательностей и их свойства 
Основные свойства и структурные особенности последовательностей максимальной длины [7, 8]:

1. каждому многочлену Ф(х) степени N, примитивному над GF(p), соответствует множество £1(Ф(х)) из p^N - 1 сдвинутых копий ^/-последовательности;
2. сумма по модулю р двух ^/-последовательностей из £1(Ф(х)) также является ^/-последовательностью из 0,(Ф(х))\
3. если

Q=QoQyQ₂-Q_ps_₂

- это ^/-последовательность из £2(Ф(х)), а а - ненулевой элемент поля GF(p), то а<2 также является Л/-последователь-ностью из £2(Ф(х));

4. ^/-последовательности 0 встречается р - 1 раз, а каждый ненулевой элемент поля GF(p) -p^N~^l раз;

5. ^/-последовательность имеет следующую структуру:

Q = b,(Ob, со²/?,..., g/~²Z>, где & - последовательность длины

<р"-Щр-1), а со - примитивный элемент поля GF(p)_t т. е. период Л/-по-следовательности всегда можно разделить на (р - 1) частей, причем элементы каждой последующей можно получить путем умножения соответствующих элементов предыдущей части на со;

6) пусть а - ненулевой элемент поля GF(p), n_a(l) и п₀(1) - число 
серий длиной / из элемента а и из / нулей соответственно. 
7) в ^/-последовательности имеется равное число серий из эле 
ментов поля GF(p), это число равно

pⁿ-²/(p-D;

8) частота появления символа а за период ^/-последовательности 
равна

pⁿ-¹/(p-d,

 

Стохастическое  преобразование информации

В качестве одного из алгоритмов нелинейного преобразования элементов jc,- «-разрядной информационной последовательности

длиной т под управлением ключевой и-разрядной последовательности

Y = Yi Y2Y3---Y/---Y«

такой же длины и качественного  генератора псевдослучайных последовательностей (ПСП) с числом состояний 2^п можно предложить следующий (рис. 3.1). Для каждого элемента х, (/ = 1, т) повторяем нижеприведенную последовательность действий:

• очередной элемент х, входной последовательности загружаем в память генератора ПСП;
• выполняем у, тактов работы генератора;
• состояние генератора после у, тактов работы при начальном состоянии х, объявляем результатом у, преобразования элемента JC,-.
• После преобразования всех элементов исходной последовательности будет получена результирующая последовательность

• У = У\УгУъ — У1 — Ут длиной т, для каждого элемента которой справедливо

• yi=R(x_ityd.
• Данное преобразование может эффективно использоваться для решения различных задач, связанных с защитой информации. Впервые оно было предложено С. А. Осмоловским для реализации стохастического кодирования информации [2, 3]. В данной главе рассматривается его применение для построения генераторов ПСП.

 

1. Понятие поля

Поле - это множество элементов, обладающее следующими свойствами:

2. Операции в конечных полях (+, -, *, /)

• в поле определены операции сложения, вычитания, умножения и деления;

• для любых элементов поля а, B и у должны выполняться соотношения (свойства ассоциативности, дистрибутивности и коммутативности)

    а + B = B + а, аB = Bа, а + (B + у) = (а + B) + у, а(Bу) = (аB)у, а(B + у) = aB + ay;

• в поле должны существовать такие элементы 0, 1, -а и (для 
а≠0) а^-1 что

0 + а  = а, а + (-а) = 0, 0а = 0, 1а = а, а(а^-1) = 1;

3. Примитивный элемент

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

4. Обозначение поля Галуа

Конечное поле содержит конечное число  элементов. Поле из L элементов обозначается GF(L) и называется полем Галуа в честь первооткрывателя Эвариста Галуа (1811—1832)/

5. Примеры полей Галуа

Простейшие поля получаются следующим  образом. Пусть р -простое число. Тогда целые числа 0, 1, 2, .,. , (р - 1) образуют поле GF(p), при этом операции сложения, вычитания, умножения и деления выполняются по модулю р. Более строго, GF(p) - это поле классов вычетов по модулю р, т. е.

GF(p)={0,1,2,...,(р-1)} 
где через 0 обозначаются все числа, кратные p, через 1 - все числа, дающие при делении на р остаток 1, и т. д. С учетом этого 
вместо р - 1 можно писать - 1. Утверждение а = Р в GF(p) означает, что а - р делится на р или что а сравнимо с р по модулю p, 
т. е. а = B(modp),

Поле, содержащее L = р^п элементов, где р - простое число, а/г- натуральное, не может быть образовано из совокупности целых чисел по модулю L. Например, в множестве классов вычетов по модулю 4 элемент 2 не имеет обратного, так как 2*2 = 0.

 

6. Вид поля GF(2⁴) и диаграмма его состояний

Пусть

р = 2, п = 4, ф(х) = х⁴ + х + 1 - примитивный над GF(2). Элементы поля GF(2⁴) имеют вид

0,1, х,x+ 1,... ,х³ + х² + х + 1.

Так как ф(х) - примитивный, ему соответствует  устройство, диаграмма состояний которого состоит из цикла максимальной длины 2⁴ - 1 и одного тривиального цикла, включающего состояние 0000, переходящее само в себя (рис. 2.1). Таким образом, в качестве w можно взять корень ф(х), а устройство, для которого ф(х) = х ⁴ + х + 1 является характеристическим многочленом, объявить генератором ненулевых элементов поля. В результате соответствие между различными представлениями элементов поля имеет вид, представленный на рис. 2.2. Состояния генератора определяют список элементов GF(2⁴) в порядке возрастания степеней w, т. е. один такт работы устройства, соответствующего характеристическому многочлену ф(х), суть умножение текущего состояния устройства наw = х.