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

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

Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как ) и наиболее часто применяется в таких регистрах.

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

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

В течение каждого такта времени выполняются следующие операции:

Регистр сдвига с линейной обратной связью

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

Свойства примитивных многочленов

Свойства

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

Линейная сложность

Линейная сложность бинарной последовательности - одна из самых важных характеристик работы РСЛОС. Введём следующие обозначения:

Определение

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

Линейной сложностью конечной двоичной последовательности называется число , которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых членов .

Свойства линейной сложности

Пусть и - двоичные последовательности. Тогда:

Корреляционная независимость

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

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

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

Пример

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

Номер шага	Состояние	Генерируемый бит
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

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

Алгоритмы генерации примитивных многочленов

Готовые таблицы

Вычисление примитивности многочлена - достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Например, для 32-битового сдвигового регистра имеется последовательность . Это означает, что для генерации нового бита необходимо с помощью функции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Код для такого РСЛОС на языке Си следующий:

Int LFSR (void ) { static unsigned long S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 ) << 31 ) | (S>> 1 ) ; return S & 1 ; }

Программные реализации РСЛОС генераторов достаточно медленны и быстрее работают, если они написаны на ассемблере, а не на языке Си. Одним из решений является использование параллельно 16-ти РСЛОС (или 32, в зависимости от длины слова в архитектуре конкретного компьютера). В такой схеме используется массив слов, размер которого равен длине РСЛОС, а каждый бит слова массива относится к своему РСЛОС. При условии, что используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности. [нужен пример кода ] (См.: bitslice).

Конфигурация Галуа

Конфигурация Галуа регистра сдвига с линейной обратной связью

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

Int LFSR (void ) { static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; }

Выигрыш состоит том, что все XOR выполняются за одну операцию.

• можно доказать, что приведенная первой конфигурация Фибоначчи и приведенная здесь конфигурация Галуа дают одинаковые последовательности (длиной 2 32 −1), но смещённые по фазе одна от другой
• цикл из фиксированного числа вызовов функции LFSR в конфигурации Галуа выполняется примерно в два раза быстрее, чем в конфигурации Фибоначчи (компилятор MS VS 2010 на Intel Core i5)
• обратите внимание, что в конфигурации Галуа порядок бит в слове, определяющем обратную связь, обратный по сравнению с конфигурацией Фибоначчи

Примеры генераторов

Генераторы «стоп-пошёл»

Чередующийся генератор «стоп-пошёл»

Этот генератор использует вывод одного РСЛОС для управления тактовой частотой другого РСЛОС. Тактовый выход РСЛОС-2 управляется выходом РСЛОС-1, так что РСЛОС-2 может менять своё состояние в момент времени t, только если выход РСДОС-1 в момент времени t-1 был равен единице. Но эта схема не устояла перед корреляционным вскрытием.

Поэтому был предложен улучшенный генератор, основанный на этой же идее. Его называют чередующийся генератор «стоп-пошёл». В нём используются три РСЛОС различной длины. РСЛОС-2 тактируется, когда выход РСЛОС-1 равен единице, а РСЛОС-3, когда выход РСЛОС-1 равен нулю. Выходом генератора является сумма по модулю 2 РСЛОС-2 и РСЛОС-3. У данного генератора большой период и большая линейная сложность. Его авторы показали также способ корреляционного вскрытия РСЛОС-1, но это не сильно ослабляет генератор.

Каскад Голлманна

Каскад Голлманна

Каскад Голлманна представляет собой усиленную версию генератора «стоп-пошёл». Он состоит из последовательности РСЛОС, тактирование каждого из которых управляется предыдущим РСЛОС. Если выходом РСЛОС-1 в момент времени t является 1,то тактируется РСЛОС-2. Если выходом РСЛОС-2 в момент времени t является 1, то тактируется РСЛОС-3, и так далее. Выход последнего РСЛОС является выходом генератора. Если длина всех РСЛОС одинакова и равна n, то линейная сложность системы из k РСЛОС равна .

Эта идея проста и может быть использована для генерации последовательностей с огромными периодами, большими линейными сложностями и хорошими статистическими свойствами. Но, к сожалению, они чувствительны к вскрытию, называемому «запиранием» (lock-in). Для большей стойкости рекомендуется использовать k не менее 15. Причём лучше использовать больше коротких РСЛОС, чем меньше длинных РСЛОС.

Пороговый генератор

Пороговый генератор

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

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

Для случая трёх регистров сдвига генератор можно представить как:

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

где , , - длины первого, второго и третьего регистров сдвига.

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

Другие виды

Самопрореживающие

Самопрореживающими называются генераторы, которые управляют собственной частотой. Было предложено два типа таких генераторов. Первый состоит из регистра сдвига с обратной линейной связью и некоторой схемы, которая тактирует этот регистр, в зависимости от того какими получаются выходные значения регистра сдвига. Если выход РСЛОС равен единице, то регистр тактируется d раз. Если выход равен нулю, то регистр тактируется k раз. Второй имеет практически ту же конструкцию, но несколько модифицированную: в схеме тактирования на вход, в качестве проверки на 0 или 1, поступает не сам выходной сигнал, а XOR определённых битов регистра сдвига с линейной обратной связью. К сожалению, этот вид генератора не безопасен.

Многоскоростной генератор с внутренним произведением

Этот генератор использует два регистра сдвига с линейной обратной связью с разными тактовыми частотами: РСЛОС-1 и РСЛОС-2. Тактовая частота РСЛОС-2 в d раз больше чем РСЛОС-1. Отдельные биты этих регистров объединяются операцией AND. Затем с выходами операции AND выполняется операция XOR. С этого блока XOR снимается выходная последовательность. Опять же и этот генератор не безупречен (Он не выстоял перед вскрытием линейной согласованности. Если - длина РСЛОС-1,- длина РСЛОС-2, а d - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной ), но он имеет высокую линейную сложность и обладает великолепными статистическими характеристиками.

Регистр сдвига с линейной обратной связью (РСЛОС, англ. linear feedback shift register , LFSR ) - регистр сдвига битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов , что находит применение, в частности, в криптографии .

Описание

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

Принцип работы

Линейная сложность

Корреляционная независимость

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

Программная реализация

Программные реализации РСЛОС достаточно медленны и работают быстрее, если они написаны на ассемблере . Одно из решений - параллельное использование 16-ти РСЛОС (или 32-х, в зависимости от длины слова в архитектуре компьютера). В такой схеме используется массив слов, размер которого равен длине регистра сдвига , а каждый бит слова относится к своему РСЛОС. Так как используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности генератора .

Конфигурация Фибоначчи

Рассмотрим 32-битовый сдвиговый регистр. Для него имеется отводная последовательность (32 , 31 , 30 , 28 , 26 , 1) {\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)} . Это означает, что для генерации нового бита необходимо с помощью операции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Полученный РСЛОС имеет максимальный период 2 32 − 1 {\displaystyle 2^{32}-1} . Код для такого регистра на языке Си следующий:

int LFSR_Fibonacci (void ) { static unsigned long S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25 ) ^ S ) & 0x00000001 ) << 31 ) | (S >> 1 ); return S & 0x00000001 ; }

Конфигурация Галуа

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

Код для регистра сдвига длины 32 бит на языке Си следующий:

int LFSR_Galois (void ) { static unsigned long S = 0x00000001 ; if (S & 0x00000001 ) { S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; return 1 ;} else { S >>= 1 ; return 0 ;} }

Стоит отметить, что цикл из фиксированного числа вызовов функции LFSR_Galois в конфигурации Галуа выполняется примерно в 2 раза быстрее, чем функция LFSR_Fibonacci в конфигурации Фибоначчи (компилятор MS VS 2010 на Intel Core i5).

Пример генерируемой последовательности

Конфигурация Фибоначчи

Пусть РСЛОС задаётся характеристическим многочленом x 3 + x + 1 {\displaystyle x^{3}+x+1} . Это значит, что битами отвода будут 2-й и 0-й, а единица в формуле многочлена означает, что 0-й бит - входной. Функция обратной связи имеет вид S j = S j − 1 ⊕ S j − 3 {\displaystyle S_{j}=S_{j-1}\oplus S_{j-3}} . Допустим, изначальным состоянием регистра сдвига была последовательность . Дальнейшие состояния регистра приведены в таблице ниже:

Номер шага	Состояние	Генерируемый бит
0	[ 0 , 0 , 1 ] {\displaystyle \left}	1
1		0
2		0
3		1
4		1
5		1
6		0
7	[ 0 , 0 , 1 ] {\displaystyle \left}	1

Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор битов. То есть генерируемая последовательность такова: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] {\displaystyle \left} (порядок бит в последовательности соответствует порядку их генерации РСЛОС). Таким образом, период последовательности равен 7, то есть максимально возможному значению, что произошло в силу примитивности заданного многочлена.

Конфигурация Галуа

Возьмём тот же характеристический многочлен, то есть c 3 = c 1 = 1 {\displaystyle c_{3}=c_{1}=1} , c 2 = 0 {\displaystyle c_{2}=0} . С выходным битом складывается только 1-й бит. Начальное состояние то же самое. Дальнейшие состояния регистра:

Номер шага	Состояние	Генерируемый бит
0	[ 0 , 0 , 1 ] {\displaystyle \left}	-
1	[ 1 , 0 , 0 ] {\displaystyle \left}	0
2	[ 0 , 1 , 1 ] {\displaystyle \left}	1
3	[ 1 , 0 , 1 ] {\displaystyle \left}	1
4	[ 1 , 1 , 1 ] {\displaystyle \left}	1
5	[ 1 , 1 , 0 ] {\displaystyle \left}	0
6	[ 0 , 1 , 0 ] {\displaystyle \left}	0
7	[ 0 , 0 , 1 ] {\displaystyle \left}	1

Внутреннее состояние регистра на седьмом шаге вернулось к исходному, следовательно, его период также равен 7. В отличие от конфигурации Фибоначчи, внутренние состояния регистра получились другие, но генерируемая последовательность та же, только сдвинута на 4 такта : [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] {\displaystyle \left} (порядок бит в последовательности соответствует порядку их генерации РСЛОС).

Генерация примитивных многочленов

Биты, n {\displaystyle n}	Примитивный многочлен	Период, 2 n − 1 {\displaystyle 2^{n}-1}	Число примитивных многочленов
2	x 2 + x + 1 {\displaystyle x^{2}+x+1}	3	1
3	x 3 + x 2 + 1 {\displaystyle x^{3}+x^{2}+1}	7	2
4	x 4 + x 3 + 1 {\displaystyle x^{4}+x^{3}+1}	15	2
5	x 5 + x 3 + 1 {\displaystyle x^{5}+x^{3}+1}	31	6
6	x 6 + x 5 + 1 {\displaystyle x^{6}+x^{5}+1}	63	6
7	x 7 + x 6 + 1 {\displaystyle x^{7}+x^{6}+1}	127	18
8	x 8 + x 6 + x 5 + x 4 + 1 {\displaystyle x^{8}+x^{6}+x^{5}+x^{4}+1}	255	16
9	x 9 + x 5 + 1 {\displaystyle x^{9}+x^{5}+1}	511	48
10	x 10 + x 7 + 1 {\displaystyle x^{10}+x^{7}+1}	1023	60
11	x 11 + x 9 + 1 {\displaystyle x^{11}+x^{9}+1}	2047	176
12	x 12 + x 11 + x 10 + x 4 + 1 {\displaystyle x^{12}+x^{11}+x^{10}+x^{4}+1}	4095	144
13	x 13 + x 12 + x 11 + x 8 + 1 {\displaystyle x^{13}+x^{12}+x^{11}+x^{8}+1}	8191	630
14	x 14 + x 13 + x 12 + x 2 + 1 {\displaystyle x^{14}+x^{13}+x^{12}+x^{2}+1}	16383	756
15	x 15 + x 14 + 1 {\displaystyle x^{15}+x^{14}+1}	32767	1800
16	x 16 + x 14 + x 13 + x 11 + 1 {\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1}	65535	2048
17	x 17 + x 14 + 1 {\displaystyle x^{17}+x^{14}+1}	131071	7710
18	x 18 + x 11 + 1 {\displaystyle x^{18}+x^{11}+1}	262143	7776
19	x 19 + x 18 + x 17 + x 14 + 1 {\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}	524287	27594
20 - 168
2 - 786, 1024, 2048, 4096

Преимущества и недостатки

Преимущества

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

Недостатки

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

Генераторы с несколькими регистрами сдвига

Генератор такого типа состоит из нескольких регистров сдвига с линейной обратной связью, которые генерируют биты x 1 , i , x 2 , i , … , x M , i {\displaystyle x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i}} соответственно. Далее, генерируемые биты преобразуются некоторой булевой функцией f (x 1 , i , x 2 , i , … , x M , i) {\displaystyle f(x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i})} . Необходимо отметить, что у генераторов такого типа длины регистров L i {\displaystyle L_{i}} , i = 1 , 2 , … , M {\displaystyle i=1,\;2,\;\dots ,\;M} , взаимно просты между собой.

Период данного генератора равен T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L {\displaystyle T=(2^{L_{1}}-1)\cdot (2^{L_{2}}-1)\cdots (2^{L_{M}}-1)\lesssim 2^{L}} , где L = ∑ i = 1 M L i {\displaystyle L=\sum \limits _{i=1}^{M}L_{i}} - общее число ячеек. Следовательно, использование нескольких РСЛОС увеличивает период генерируемой последовательности по сравнению с одним регистром, что увеличивает криптостойкость генератора. Также увеличивается линейная сложность или длина кратчайшего регистра, соответствующего данному генератору. Такой регистр находится с помощью алгоритма Берлекэмпа - Мэсси по генерируемой последовательности. В лучшем случае его длина соизмерима с периодом генерируемой последовательности .

Генераторы с нелинейными преобразованиями

Структурная схема такого генератора ничем не отличается от схемы предыдущего генератора. Главное отличие заключается в том, что устройство преобразования задано нелинейной булевой функцией f (x 1 , x 2 , … , x M) {\displaystyle f(x_{1},x_{2},\dots ,x_{M})} . В качестве такой функции берётся, например, полином Жегалкина (согласно теореме Жегалкина , всякая булева функция единственным образом может быть представлена полиномом Жегалкина).

Нелинейный генератор может быть также реализован на регистре сдвига с нелинейной обратной связью . Он может дать 2 2 L − 1 − L {\displaystyle 2^{2^{L-1}-L}} вариантов последовательностей максимального периода , что больше, чем у РСЛОС .

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

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

Генераторы с различным тактированием регистров сдвига

Генератор «стоп-пошёл»

Генератор «стоп-пошёл» (англ. Stop-and-Go , Both-Piper ) использует вывод РСЛОС-1 для управления тактовой частотой РСЛОС-2, так что РСЛОС-2 меняет своё состояние в некоторый момент времени , только если выход РСЛОС-1 в момент времени был равен единице. Данная схема не устояла перед корреляционным вскрытием .

В целях увеличения криптостойкости был предложен чередующийся генератор «стоп-пошёл» . В нём используются три регистра сдвига различной длины. Здесь РСЛОС-1 управляет тактовой частотой 2-го и 3-го регистров, то есть РСЛОС-2 меняет своё состояние, когда выход РСЛОС-1 равен единице, а РСЛОС-3 - когда выход РСЛОС-1 равен нулю. Выходом генератора является операция сложения по модулю два выходов РСЛОС-2 и РСЛОС-3. У данного генератора большой период и большая линейная сложность. Существует способ корреляционного вскрытия РСЛОС-1, но это не сильно ослабляет криптографические свойства генератора.

Усложнённая схема тактирования использована в двустороннем генераторе «стоп-пошёл» , в котором используются 2 регистра сдвига одинаковой длины. Если выход РСЛОС-1 в некоторый момент времени t i − 1 {\displaystyle t_{i-1}} - единице, то РСЛОС-2 не тактируется в момент времени t i {\displaystyle t_{i}} . Если выход РСЛОС-2 в момент времени t i − 1 {\displaystyle t_{i-1}} равен нулю, а в момент времени t i − 2 {\displaystyle t_{i-2}} - единице, и если этот регистр тактируется в момент времени t i {\displaystyle t_{i}} , то в этот же момент РСЛОС-1 не тактируется. Линейная сложность данной схемы примерно равна периоду генерируемой последовательности.

Самопрореживающий генератор

Многоскоростной генератор с внутренним произведением

Данный генератор использует два регистра сдвига РСЛОС-1 и РСЛОС-2. Тактовая частота РСЛОС-2 в d {\displaystyle d} раз больше, чем у РСЛОС-1. Определённые биты этих регистров перемножаются друг с другом операцией AND . Результаты умножений суммируются операцией XOR, и получается выходная последовательность. Этот генератор имеет высокую линейную сложность и обладает хорошими статистическими свойствами. Однако его состояние может быть определено по выходной последовательности длиной L 1 + L 2 + log 2 ⁡ d {\displaystyle L_{1}+L_{2}+\log _{2}{d}} , где L 1 {\displaystyle L_{1}} и L 2 {\displaystyle L_{2}} - длины РСЛОС-1 и РСЛОС-2 соответственно, а d {\displaystyle d} - отношение их тактовых частот.

Каскад Голлманна

Данная схема представляет собой улучшенную версию генератора «стоп-пошёл». Он состоит из последовательности РСЛОС, тактирование каждого из которых управляется предыдущим РСЛОС. Если выходом РСЛОС-1 в момент времени t i {\displaystyle t_{i}} является 1,то тактируется РСЛОС-2. Если выходом РСЛОС-2 в момент времени t i {\displaystyle t_{i}} является 1, то тактируется РСЛОС-3, и так далее. Выход последнего РСЛОС является выходом генератора. Если длина всех РСЛОС одинакова и равна L {\displaystyle L} , то период системы из M {\displaystyle M} РСЛОС равен (2 L − 1) M {\displaystyle (2^{L}-1)^{M}} , а линейная сложность - L (S) = L (2 L − 1) M − 1 {\displaystyle L(S)=L(2^{L}-1)^{M-1}} .

Эта идея проста и может быть использована для генерации последовательностей с огромными периодами, большими линейными сложностями и хорошими статистическими свойствами. Но, к сожалению, они чувствительны к вскрытию, называемому запиранием (англ. lock-in ), когда

Гаммирование. Гамма шифра. Методы генерации гаммы шифра. Линейный сдвиговый регистр.

Глава 3. Порядок регистрации отдельных актов гражданского состояния

Государственная регистрация выпуска (дополнительного выпуска) ценых бумаг.

Регистр линейного сдвига c обратной связью (Linear Feedback Shift Register - LFSR) – механизм создания псевдослучайной последовательности двоичных битов. Регистр (рис. 1) состоит из ряда ячеек, которые устанавливаются вектором инициализации (чаще всего секретным ключом). Работа регистра определяется наличием или отсутствием связи от каждого разряда к обратной связи. Отводы регистра с обратной связью не фиксированы, а являются частью ключа. На очередном шаге содержимое ячеек регистра сдвигается на одну позицию вправо, а один бит, оставшийся в результате операции XOR свободным, помещается в крайнюю левую ячейку.

Рис. 1. Линейный регистр сдвига с обратной связью

Для достижения максимального периода гаммы шифра число разрядов m сдвигового регистра выбирается равным одному из простых чисел Мерсенна (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 …), а внутренние связи регистра должны выбираться в соответствии с неприводимыми примитивными многочленами со старшей степенью m . В этом случае период гаммы шифра может достигать (2 m -1).

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

Каскад регистров – набор LFSR, связанных таким образом, что поведение одного регистра LFSR зависит от поведения предыдущего регистра LFSR в каскаде. Такое «зависимое» поведение обычно организуется для управления с помощью первого LFSR счетчиком сдвигов следующего за ним LFSR.

Например, регистр сдвигается на один шаг, если значение предшествующего регистра – 1, а если значение 0, то регистр сдвигается на два шага или как-то иначе. Большое количество подобных сочетаний позволяет обеспечить весьма высокую безопасность.

Наиболее криптостойкие последовательности дает сжимающий генератор (shrinking generator), основанный на простом взаимодействии между результатами двух регистров LFSR. Биты одного результата определяют, будут ли соответствующие биты второго результата использоваться как часть полного «потокового ключа». Сжимающий генератор прост, масштабируем и имеет хорошие защитные свойства. Его недостаток состоит в том, что скорость генерации «потокового ключа» не будет постоянной, если не принять некоторых предосторожностей.

Метод Фибоначчи с запаздываниями Один из широко распространённых фибоначчиевых генераторов основан на следующей итеративной формуле:

где Y k - вещественные числа из диапазона

Рис. 2. Циклическое шифрование

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

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

Генератор ANSI X9.17 состоит из следующих частей (рис. 3):

1. Вход: генератором управляют два псевдослучайных входа. Первый вход является 64-битным представлением текущих даты и времени (DT i ), которые изменяются каждый раз при создании числа. Второй вход является 64-битным начальным значением, которое инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел (V i ).

2. Ключи: генератор использует три модуля тройного DES с двумя ключами K 1 , K 2 . Все три используют одну и ту же пару 56-битных ключей, которая должна держаться в секрете и применяться только для генерации псевдослучайного числа.

EDE

EDE

EDE

+

+

K 1 , K 2

DT i

V i

R i

V i+1

3. Выход: выход состоит из 64-битного псевдослучайного числа R i и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа (V i +1 ) .

Рис. 3. Генератор псевдослучайных чисел ANSI X9.17

Министерство образования и науки

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КАФЕДРА ЗАЩИТЫ ИНФОРМАЦИИ

Криптографические методы и средства обеспечения информационной безопасности

Курсовая работа

«Р егистры сдвига с линейной обратной связью как генераторы псевдослучайных чисел»

Выполнил:

студент 3-го курса

группа КЗОИ-Д-3

Ларионов И.П.

Проверила:

доц. Баранова Е.К.

Москва 2011
СОДЕРЖАНИЕ

Введение ……………………………..…………………………………….3

1. Теоретические основы работы …………………………………………4
   1. Общие сведения о регистрах сдвига с обратной связью……...…..4
      1. О потоковых шифрах на базе РгСсЛОС………………….………10
      2. О линейной сложности генерируемой псевдослучайной последовательности РгСсЛОС………………………………….……12
      3. О корреляционной независимости генерируемой последовательности псевдослучайных чисел РгСсЛОС………..….13
      4. О других способах вскрытия генерируемой последовательности псевдослучайных чисел РгСсЛОС…………………………………..14
2. Программная реализация РгСсЛОС как генератора псевдослучайной последовательности ….…………………………….15
   1. Обобщенная схема алгоритма…………………………………...15
   2. Описание программных модулей и интерфейса.……………….16
   3. Инструкция пользователя………………………………………...20

Заключение ………………………………………………………………22

Список литературы ………………………………………………….....23

Приложение А ….………………………………………………………..24

ВВЕДЕНИЕ

Целью данной работы является разработка программного приложения, реализующего работу генератора псевдослучайных чисел на регистрах сдвига с обратной связью. Разработка данного приложения с графическим интерфейсом осуществляется на языке C ++ для ОС Windows .

С развитием криптографии в ХХ веке перед криптографами встала задача создания шифровальных устройств и машин, которые могли бы быстро и надежно зашифровывать и расшифровывать сообщения. Этому требованию отвечали уже открытые в то время симметричные системы шифрования, однако их слабым местом была сильная зависимость от ключа и его секретность. Наиболее удобным классом шифров, которые можно было использовать для этой цели это шифры гаммирования. Возникла задача генерации гаммы, которую нельзя было бы обнаружить при дешифровании сообщения. Теоретически это было возможно, если каждый раз гамма была случайной и изменялась во времени. Однако при использовании абсолютно случайной изменяющейся гаммы было бы трудно обеспечить достоверную шифровку-дешифровку сообщения. Криптографы занялись решением этой задачи, целью которой было нахождения алгоритма реализующего генерацию случайной гаммы по определенному правилу, такая последовательность должна содержать в себе нули и единицы на «якобы» случайных позициях, причем число единиц и нулей должно быть примерно одинаково. Такая случайная последовательность была названа псевдослучайной, так как генерировалась она по определенному правилу, а не случайным образом.

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

1.Теоретические основы работы

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

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

Регистр сдвига с обратной связью (далее РгСсОС) состоит из двух частей: регистра сдвига и функции обратной связи. Регистр сдвига представляет собой последовательность битов. Количество битов определяется длиной сдвигового регистра , если длина равна n битам, то регистр называется n-битовым сдвиговым регистром . Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина получаемой последовательности до начала ее повторения.

Рисунок Регистр сдвига с обратной связью

Регистры сдвига очень быстро нашли применение в потоковых шифрах, так как они легко реализовывались с помощью цифровой аппаратуры. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности регистров сдвига . Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера . Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (linear feedback shift register , далее LFSR или РгСсЛОС) . Обратная связь таких регистров представляет собой просто XOR (сложение по модулю два) некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа РгСсЛОС можно использовать довольно развитую математическую теорию. Проанализировав получаемые выходные последовательности, можно убедиться в том, что эти последовательности достаточно случайны, чтобы быть безопасными. РгСсЛОС чаще других сдвиговых регистров используются в криптографии.

Рисунок РгСсЛОС Фиббоначи

В общем случае n -битовый РгСсЛОС может находиться в одном из N =2 n -1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом Т=2 n -1 битов. (Число внутренних состояний и период равны N = T max =2 n -1, потому что заполнение РгСсЛОС нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно). Только при определенных отводных последовательностях РгСсЛОС циклически пройдет через все 2 n -1 внутренних состояний, такие РгСсЛОС являются РгСсЛОС с максимальным периодом . Получившийся результат называется М-последовательностью .

Пример . На рисунке ниже показан 4-битовый РгСсЛОС с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния:

Номер такта сдвига (внутреннего состояния)	Состояние регистров				Выходной бит
Инициальное значение
15 (возврат в инициальное состояние)
16 (повтор состояний)

Выходной последовательностью будет строка младших значащих битов: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 с периодом Т=15, общее число возможных внутренних состояний (кроме нулевого), N =2 4 -1=16-1=15= T max , следовательно, выходная последовательность – M -последовательность.

Для того чтобы конкретный РгСсЛОС имел максимальный период, многочлен, образованный из отводной последовательности и константы 1, должен быть примитивным по модулю 2. Многочлен представляется в виде суммы степеней, например многочлен степени n представляется так:

a n x n +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 +…+a 1 x+a 0 , где а i ={0,1} для i=1…n, a x i – указывает разряд .

Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем x 2n−1 +1, но не является делителем x d +1 для всех d, являющихся делителями 2 n -1. Соответствующую математическую теорию можно найти в .

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

Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2, приведены далее. Например, запись

(32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1.

Это можно легко обобщить для РгСсЛОС с максимальным периодом. Первым числом является длина РгСсЛОС. Последнее число всегда равно 0, и его можно опустить. Все числа, за исключением 0, задают отводную последовательность, отсчитываемую от левого края сдвигового регистра. То есть, члены многочлена с меньшей степенью соответствуют позициям ближе к правому краю регистра.

Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра новый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов, получающийся РгСсЛОС будет иметь максимальную длину, циклически проходя до повторения через 2 32 -1 значений.

Рисунок 4 32-битовый РгСсЛОС с максимальной длиной

Рассмотрим программный код РгСсЛОС, у которого отводная последовательность характеризуется многочленом (32, 7, 5, 3, 2, 1, 0). На языке C выглядит следующим образом :

int LFSR () {

static unsigned long ShiftRegister = 1;

/* Все , кроме 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

return ShiftRegister & 0 x 00000001;}

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

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

Если p(x) примитивен, то примитивен и x n p(1/x), поэтому каждый элемент таблицы на самом деле определяет два примитивных многочлена. Например, если (a, b, 0) примитивен, то примитивен и (a, a-b, 0). Если примитивен (a, b, c, d, 0), то примитивен и (a, a-d, a-c, a-b, 0). Математически:

если примитивен x a +x b +1, то примитивен и x a +x a-b +1,

если примитивен x a +x b +x c +x d +1, то примитивен и x a +x a-d +x a-c +x a-b +1. Быстрее всего программно реализуются примитивные трехчлены, так как для генерации нового бита нужно выполнять XOR только двух битов сдвигового регистра (нулевой член не учитывается, т.е. х 0 =1, см. пример выше). Действительно, все многочлены обратной связи, приведенные в таблице, являются разреженными, то есть, у них немного коэффициентов. Разреженность всегда представляет собой источник слабости, которой иногда достаточно для вскрытия алгоритма. Для криптографических алгоритмов гораздо лучше использовать плотные примитивные многочлены, те, у которых много коэффициентов. Применяя плотные многочлены, особенно в качестве части ключа, можно использовать значительно более короткие РгСсЛОС.

Генерировать плотные примитивные многочлены по модулю 2 нелегко. В общем случае для генерации примитивных многочленов степени k нужно знать разложение на множители числа 2 k -1.

Сами по себе РгСсЛОС являются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными (детерминированными) свойствами. Последовательные биты линейны, что делает их бесполезными для шифрования. Для РгСсЛОС длины n внутреннее состояние представляет собой предыдущие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью высоко эффективного алгоритма Berlekamp-Massey .

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

1.2.О потоковых шифрах на базе РгСсЛОС

Основной подход при проектировании генератора потока ключей на базе РгСсЛОС прост. Сначала берется один или несколько РгСсЛОС, обычно с различными длинами и различными многочленами обратной связи. (Если длины взаимно просты, а все многочлены обратной связи примитивны, то у образованного генератора будет максимальная длина.) Ключ является начальным состоянием регистров РгСсЛОС. Каждый раз, когда необходим новый бит, сдвиньте на бит регистры РгСсЛОС (это иногда называют тактированием (clocking)). Бит выхода представляет собой функцию, желательно нелинейную, некоторых битов регистров РгСсЛОС. Эта функция называется комбинирующей функцией, а генератор в целом - комбинационным генератором. (Если бит выхода является функцией единственного РгСсЛОС, то генератор называется фильтрующим генератором.) Большая часть теории подобного рода устройств разработана Селмером (Selmer) и Нилом Цирлером (Neal Zierler). Можно ввести ряд усложнений. В некоторых генераторах для различных РгСсЛОС используется различная тактовая частота, иногда частота одного генератора зависит от выхода другого. Все это электронные версии идей шифровальных машин, появившихся до Второй мировой войны, которые называются генераторами с управлением тактовой частотой (clock - controlled generators ). Управление тактовой частотой может быть с прямой связью, когда выход одного РгСсЛОС управляет тактовой частотой другого РгСсЛОС, или с обратной связью, когда выход одного РгСсЛОС управляет его собственной тактовой частотой. Хотя все эти генераторы чувствительны, по крайней мере теоретически, к вскрытиям вложением и вероятной корреляцией, многие из них безопасны до сих пор.

Ян Касселлс (Ian Cassells), ранее возглавлявший кафедру чистой математики в Кембридже и работавший криптоаналитиком в Блетчли Парк (Bletchly Park), сказал, что «криптография - это смесь математики и путаницы, и без путаницы математика может быть использована против вас». Он имел в виду, что в потоковых шифрах для обеспечения максимальной длины и других свойств необходимы определенные математические структуры, такие как РгСсЛОС, но, чтобы помешать кому-то получить содержание регистра и вскрыть алгоритм, необходимо внести некоторый сложный нелинейный беспорядок. Этот совет справедлив и для блочных алгоритмов.

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

Эта отрасль криптографии быстро развивается и находится под зорким государственным контролем со стороны NSA . Большинство разработок засекречены - множество используемых сегодня военных систем шифрования основаны на РгСсЛОС. Действительно, у большинства компьютеров Cray (Cray 1, Cray X-MP, Cray Y-MP) есть весьма любопытная инструкция, обычно называемая как "счетчик совокупности" (population count). Она подсчитывает количество единиц в регистре и может быть использована как для эффективного вычисления расстояния Хэмминга между двумя двоичными словами и для реализации векторизированной версии РгСсЛОС. Эта инструкция считается канонической инструкцией NSA, обязательно фигурирующей почти во всех контрактах, касающихся компьютеров.

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

1.3.О линейной сложности генерируемой последовательности псевдослучайных чисел РгСсЛОС

Анализировать потоковые шифры часто проще, чем блочные. Например, важным параметром, используемым для анализа генераторов на базе РгСсЛОС, является линейная сложность (linear complexity), или линейный интервал. Она определяется как длина n самого короткого РгСсЛОС, который может имитировать выход генератора. Любая последовательность, генерированная конечным автоматом над конечным полем, имеет конечную линейную сложность . Линейная сложность важна, потому что с помощью простого алгоритма, называемого алгоритмом Berlekamp-Massey, можно определить этот РгСсЛОС, проверив только 2n битов потока ключей . Воссоздавая нужный РгСсЛОС, вы взламываете потоковый шифр.

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

1.4.О корреляционной независимости генерируемой последовательности псевдослучайных чисел РгСсЛОС

Криптографы пытаются получить высокую линейную сложность, нелинейно объединяя результаты некоторых выходных последовательностей. При этом опасность состоит в том, что одна или несколько внутренних выходных последовательностей - часто просто выходы отдельных РгСсЛОС - могут быть связаны общим ключевым потоком и вскрыты при помощи линейной алгебры. Часто такое вскрытие называют корреляционным вскрытием или вскрытием разделяй-и-властвуй. Томас Сигенталер (Thomas Siegenthaler) показал, что можно точно определить корреляционную независимость, и что существует компромисс между корреляционной независимостью и линейной сложностью .

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

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

1.5.О других способах вскрытия генерируемой последовательности псевдослучайных чисел РгСсЛОС

Существуют и другие способы вскрытия генераторов потоков ключей. Тест на линейную корректность (linear consistency) пытается найти некоторое подмножество ключа шифрования с помощью матричной техники. Существует и вскрытие корректности "встречей посередине" (meet-in-the-middle consistency attack). Алгоритм линейного синдрома (linear syndrome algorithm) основан на возможности записать фрагмент выходной последовательности в виде линейного уравнения. Существует вскрытие лучшим аффинным приближением (best afflne approximation attack) и вскрытие выведенным предложением (derived sequence attack). К потоковым шифрам можно применить также методы дифференциального и линейного криптоанализа.

2. Описание программной реализации РгСсЛОС как генератора псевдослучайной последовательности

2.1.Обобщенная схема алгоритма

2.2.Описание программных модулей и интерфейса

Ниже на рисунке 3 представлено окно программы.

Рисунок Интерфейс программы

В меню есть следующие функции:

• Файл->Сохранить отчет

Эта функция осуществляет создание файла отчета, куда записывается инициальное состояние РгСсЛОС, отводная последовательность, период полученной псевдослучайной последовательности бит, сама последовательность и таблица состояний. Если файл успешно был сохранен, то выдается сообщение об успешном сохранении (рисунок 4). Рекомендуемое расширение файла отчета *. txt .

Рисунок

• Файл- > Выход

Эта функция обеспечивает закрытие приложения.

• Задать отводную последовательность

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

Рисунок

• Установить инициальное значение

Эта функция считывает введенное пользователем инициальное значение регистра из окна Edit 1 и осуществляет проверку введенного значения согласно заданным условиям: введенная строка непустая (рисунок 6), введенная строка имеет длину равную восьми (8бит=1байт, рисунок 7), введенная строка содержит только нули и/или единицы (рисунок 8), введенная строка ненулевая (рисунок 9). В противном случае выдаются сообщения об ошибке, пользователь должен их исправить и снова нажать на кнопку. В случае успешной проверки инициальное значение будет записано в таблицу состояний в строке «Инициальное» и выдано уведомление (рисунок 10).

Рисунок

Рисунок

Рисунок

Рисунок

Рисунок

• Произвести сдвиг регистра

Эта функция эмулирует работу регистра сдвига. Последовательно производя 256 сдвигов, каждый сдвиг формирует выходной бит псевдослучайной последовательности и новое состояние регистра. Как только находится состояние регистра равное инициальному, вычисляется период и выводит в поле Memo 1 полученную псевдослучайную последовательность.

• Помощь- > О программе

Эта функция выводит на экран краткое описание программы и инструкцию (рисунок 11).

Рисунок

• Помощь- > Об авторе

Эта функция выводит на экран информацию об авторе программы (рисунок 12).

Рисунок

2.3.Инструкция пользователя

1. Сначала установите инициальное состояние регистра. Оно должно содержать восемь двоичных символов. В противном случае будет выдано сообщение об ошибке и Вам придется исправить введенное значение. Нажмите пункт меню «Задать инициальное значение».
2. Затем отметьте флажками в клеточках обратные связи регистра (Отводная последовательность). Нажмите пункт меню «Задать отводную последовательность».
3. Далее нажмите пункт меню «Сдвиг регистра». Обязательно перед этим удостоверьтесь в том, что вы выполнили пункт 1 и 2, иначе произойдет программная ошибка.
4. Получив результаты вы можете их сохранить нажав пункт меню «Файл->Сохранить отчет». Обязательно перед этим удостоверьтесь в том, что вы выполнили пункты 1-3, иначе произойдет программная ошибка.
5. Для получения справки нажмите пункты меню «Файл->О программе», «Файл->Об авторе».
6. Чтобы посмотреть работу регистра при других значениях отводной последовательности и инициального состояния регистра, повторите последовательно действия в пунктах 1-3, введя другие параметры.

ЗАКЛЮЧЕНИЕ

В данной работе были рассмотрены РгСсЛОС в качестве генераторов псевдослучайных чисел. Программа может служить наглядной демонстрацией принципов работы регистров сдвига с линейной обратной связью по XOR . На ней можно изучать принцип формирования псевдослучайной последовательности битов, зависимость между инициальным значением регистра и значением псевдослучайной последовательности, отводной последовательностью и периодом. Получаемую псевдослучайную гамму можно использовать в другом программном приложении (например, программная реализация шифра гаммирования).

На сегодняшний момент данные регистры не используются как самостоятельные генераторы псевдослучайных чисел, а входят в состав более сложных устройств. Однако именно они открыли новые направления в математике (поиск примитивных многочленов в конечных полях, математические способы взлома генераторов псевдослучайных чисел). Без знания принципов работы генераторов на РгСсЛОС нельзя понять работу более сложных устройств. Благодаря своей простой аппаратной реализации они получили широкое распространение в технике. Исследование РгСсОС привело к возникновению новых шифров - блочных и потоковых - основанных на этих типах регистров (шифр скользящей перестановки, DES и т.п.; ЭЦП, хеш-функции).

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

СПИСОК ЛИТЕРАТУРЫ

1. Шнайер Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: Триумф, 2002
2. Бабаш А.В. Криптографические и теоретико-автоматные аспекты современной защиты информации. Том 1 – М.: Изд. центр ЕАОИ, 2009. – 414 с.
3. Е.С. Селмер. Монография: «Линейная рекурсия в конечном поле». Университет Бергена, Норвегия, 1966.
4. Н.Зиерлер и Дж. Бриллхарт. "О примитивных трехчленах по модулю 2", журнал Информация и Контроль, издание 13 №6 декабрь 1968, стр. 541-544.
5. К.Х. Мейер и У.Л.Тучман. "Псевдослучайные коды могут быть взломаны, " журнал Электроник Дизайн, №. 23, ноябрь 1972.
6. Дж.Л.Массей. "Обобщение регистров сдвига и дешифровка кода Бозе-Чоудхури-Хоквингема", IEEE Transactions on Information Theory , v . IT -15, n . 1, январь 1969, стр. 122-127.
7. С.У. Голомб. Последовательности регистров сдвига, Сан-Франциско, Голден-Дей, 1967 (переиздано Аигеан Парк Пресс, 1982).

Приложение А

Таблица некоторых примитивных многочленов по модулю 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Ввод инициального состояния (ИС)

роверка на правильность ввода

Выдача сообщения об ошибке

Установка отводной последовательности

Запись ИС в таблицу состояний

Запись i -го состояния регистра и выходного бита в таблицу состояний

ИС==Текущее состояние

Сохранение результатов

Вывод псевдослучайно последовательности

Выход

Запуск

Да

Да

Нет

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

Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи (рисунок 1.2.1). Сдвиговый регистр представляет собой последовательность битов. (Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым сдвиговым регистром.) Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина получаемой последовательности до начала ее повторения.

Рис. 1.2.1.

Криптографам нравились потоковые шифры на базе сдвиговых регистров: они легко реализовывались с помощью цифровой аппаратуры. Я лишь слегка затрону математическую теорию. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности сдвиговых регистров. Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера.

Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register, или LFSR) (рисунок 1.2.2). Обратная связь представляет собой просто XOR некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа LFSR можно использовать довольно развитую математическую теорию. Криптографы любят анализировать последовательности, убеждая себя, что эти последовательности достаточно случайны, чтобы быть безопасными. LFSR чаще других сдвиговых регистров используются в криптографии.

Рис. 1.2.2.

На Рис. 1.2.3 показан 4-битовый LFSR с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния:

Рис. 1.2.3. 4

Выходной последовательностью будет строка младших значащих битов:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

n-битовый LFSR может находиться в одном из 2n-1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2n-1 битов. (Число внутренних состояний и период равны 2n-1, потому что заполнение LFSR нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях LFSR циклически пройдет через все 2n-1 внутренних состояний, такие LFSR являются LFSR с максимальным периодом. Получившийся результат называется М-последовательностью.

Для того, чтобы конкретный LFSR имел максимальный период, многочлен, образованный из отводной последовательности и константы 1, должен быть примитивным по модулю 2. Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем, но не является делителем xd+1 для всех d, являющихся делителями 2n-1.

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

Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2. Например, запись (32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2:

x32 + x7 +x5 + x3 + x2 + x + 1

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

Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра новый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов получающийся LFSR будет иметь максимальную длину, циклически проходя до повторения через 232-1 значений.