Линейные рекуррентные генераторы

Использование LFSR в программной реализации криптосхем намного проблематичней. Эффективны по скорости лишь прореженные полиномы, но они слабы в отношении корреляционных атак; плотные же полиномы обратной связи слишком неэффективны. Стандартный поточный шифр выдает по одному биту за раз, и этот алгоритм приходится итерировать 64 раза для шифрования того, что DES делает за одну итерацию. Фактически оказывается, что несложный LFSR-алгоритм, типа сжимающего генератора в программной реализации оказывается не быстрее, чем значительно более сложный DES.

Генератор Геффа

В этом генераторе потока ключей используются три LFSR, объединенные нелинейным образом. Два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора. Если а1, а2 и а3 - выходы трех LFSR, выход генератора Геффа (Geffe) можно описать как:

= (a1^a2) + ((-a1)^a3). (2.10)

Если длины LFSR равны n1 n2 и n3, соответственно, то линейная сложность генератора равна:

(n1+1)*n2+n1*n3. (2.11)

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

Рисунок 2.7 - Генератор Геффа

Хотя этот генератор неплохо выглядит на бумаге, он криптографически слаб и не может устоять против корреляционного вскрытия. В 75% времени выход генератора равен выходу LFSR-2. Поэтому, если известны отводные последовательности обратной связи, можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра. Тогда можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора. Если начальное значение определено неверно, две последовательности будут согласовываться в 50 процентах времени, а если правильно, то в 75% времени.

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

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

Этот генератор использует выход одного LFSR для управления тактовой частотой другого LFSR. Тактовый вход LFSR-2 управляется выходом LFSR-1,так что LFSR-2 может изменять своё состояние в момент времени t только, если выход LFSR-1 в момент времени t-1 был равен 1.

Рисунок 2.8 - Генератор «стоп - пошёл»

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

В этом генераторе используются три LSFR различной длинны.LSFR-2 тактируется, когда выход LSFR-1равен 1, LSFR-3 тактируется, когда выход LSFR-1равен 0.

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

У этого генератора большой период и большая линейная сложность.

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

Каскад Голлманна, представляет собой усиленную версию генератора "стоп-пошел". Он состоит из последовательности LFSR, тактирование каждого из которых управляется предыдущим LFSR. Если выходом LFSR-1 в момент времени t является 1, то тактируется LFSR-2. Если выходом LFSR-2 в момент времени t является 1, то тактируется LFSR-3, и так далее. Выход последнего LFSR и является выходом генератора.

Если длина всех LFSR одинакова и равна n, линейная сложность системы из k LFSR равна n(2n-1)k-1.

Перейти на страницу: 1 2 3 4 5 6

Читайте также

Организация связи по оптическому кабелю магистрали Коченево-Мамонтово
Телекоммуникации являются основой развития общества. Постоянно растущий спрос, как на обычные телефонные, так и на новые виды услуг связи, включая услуги Интернет, предъявляет новые тре ...

Передаточная функция разомкнутой системы
1. Определить передаточную функцию разомкнутой системы рис.1, представить её в канонической .форме. Построить её логарифмические частотные характеристики. 2. Оценить показатели к ...

Применение системы автоматического проектирования на ИП Суслова
Почти все крупные предприятия используют в своей работе возможности компьютерной техники, в частности CAD, CAM, САЕ технологии, т.к. они предоставляют ряд преимуществ, таких как ...

Основные разделы

Все права защищены! (с)2020 - www.generallytech.ru