Разработка блока вычисления индекса для системы нелинейного шифрования данных
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
менять конфигурацию Фиббоначи, если есть возможность использовать параллелизм - конфигурацию Галуа.
Проблема LFSR состоит в том, что их программная реализация очень неэффективна. Выход любого потокового шифра является побитовым, для шифрования того, что можно выполнить за одну итерацию DES, необходимо выполнить 64 итерации потокового алгоритма [8,10,13].
В работе [12] приведена структура генератора "стоп-пошел" (Stop-and-Go) Both-Piper. Этот генератор использует выход одного LFSR для управления тактовой частотой другого LFSR. Тактовый вход LFSR-2 управляется выходом LFSR-l, так что LFSR-2 может изменять свое состояние в момент времени t только, если выход LFSR-l в момент времени t-1 был равен 1.
Рисунок 3.4 - Генератор "стоп-пошел" Bоth-Piper
Никому не удалось привести для общего случая достоверные данные о линейной сложности этого генератора. Однако он не устоял перед корреляционным вскрытием. [8,17,20]
Данного недостатка лишен чередующийся генератор "стоп-пошел". В этом генераторе используются три LFSR различной длины. LFSR-2 повторяется, когда выход LFSR-l равен 1, LFSR-3 повторяется, когда выход LFSR-l равен 0. Выходом генератора является XOR LFSR-2 и LFSR-3. У этого генератора большой период и линейная сложность. Были предложены и другие генераторы такого типа.
Рисунок 3.5 - Чередующийся генератор "стоп-пошел"
Дальнейшим развитием явился двусторонний генератор "стоп-пошел". В этом генераторе используется два LFSR с одинаковой длиной n (Рисунок 3.8). Выходом генератора является XOR выходов каждого LFSR. Если выход LFSR-l в момент времени t-1 равен 0, а в момент времени t-2 - 1, то LFSR-2 не повторяется в момент времени t. Наоборот, если выход LFSR-2 в момент времени t-1 равен 0, а в момент времени t-2 - 1, и если LFSR-2 повторяется в момент времени t, то LFSR-l не повторяется в момент времени t.
Рисунок 3.6 - Двусторонний генератор "стоп-пошел"
Линейная сложность такой системы примерно равна ее периоду.
Особое место среди генераторов ПСП занимает генератор Геффа. В этом генераторе ПСП используются три LFSR, объединенные нелинейным образом, как показано на рисунке 3.7.
Рисунок 3.7 - Генератор Геффа
Два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора. Если a1, a2 и a3 - выходы трех LFSR, выход генератора Геффа можно описать как
. (3.2)
Если длины LFSR равны n1, n2 и n3, соответственно, то линейная сложность генератора равна (n1+1)n2+n1n3,
Период генератора равен наименьшему общему делителю периодов трех генераторов. При условии, что степени трех примитивных многочленов обратной связи взаимно просты, период этого генератора будет равен произведению периодов трех LFSR.
Генератор Геффа криптографически слаб и не может устоять против корреляционного вскрытия. Если известны отводные последовательности обратной связи, можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра.
Дальнейшим развититем явился обобщенный генератор Геффа. Вместо выбора между двумя LFSR в этой схеме выбирается один из k LFSR, где k является степенью 2. Всего используется k+1 LFSR. Структура генератора показана на рисунке 3.8. Тактовая частота LFSR-l должна быть в log2k раз выше, чем у остальных k LFSR [8,15,17]. Несмотря на то, что эта схема сложнее генератора Геффа, для взлома можно использовать то же корреляционное вскрытие
Рисунок 3.8 - Обобщенный генератор Геффа
В работе [12] рассмотрен пороговый генератор. Этот генератор более криптостокойкий в связи с переменным числом LFSR. При использовании большего количества LFSR вскрыть шифр сложнее.
Для получения максимального периода необходимо, чтобы длины всех LFSR взаимно просты, а многочлены обратной связи - примитивны. Если более половины выходных битов LFSR-1, то выходом генератора является 1. Если более половины выходных битов LFSR-0, то выходом генератора является 0.
Рисунок 3.9 - Пороговый генератор
Для трех LFSR выход генератора можно представить как:
. (3.3)
Это очень похоже на генератор Геффа за исключением того, что пороговый генератор обладает большей линейной сложностью
n1n2 + n1n3 + n2n3, (3.4)
где n1, n2 и n3 - длины первого, второго и третьего LFSR.
Каждый выходной бит дает некоторую информацию о состоянии LFSR - точнее 0.189 бита - и в целом генератор не может устоять перед корреляционным вскрытием.
Выводы
1. Проведен анализ основных требований, которые предъявляются к псевдослучайным последовательностям. Показано, что данные последовательности целесообразно использовать при поточном шифровании.
. Рассмотрены структуры основных видов генераторов псевдослучайных последовательностей. Проведенный анализ показал, что данные генераторы используют различные комбинации регистров сдвигов с обратной связью.
. Показаны достоинства и недостатки схемных реализаций генераторов двоичных псевдослучайных последовательностей.
4. Разработка блока вычисления индекса для системы НЕЛИНЕЙНОГО ШИФРОВАНИЯ
4.1 Основы нелинейного шифрование потока данных в расширенных полях Галуа
С появлением новых средств мультимедиа и сетей с высокой пропускной способностью, обеспечивающих передачу мультимедийных данных большого объема, в современных вычислительных системах начинают применяться технологии, осуществляющие обработку и передачу больших массивов. Для обеспечения интерактивного об