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

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

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

В этом генераторе потока ключей используются три 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.

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

Построение внутренней памяти процессорной системы, состоящей из ПЗУ и статического ОЗУ
Построить внутреннюю память процессорной системы, состоящую из ПЗУ и статического ОЗУ. Процессорная система работает в реальном режиме. Разрядность ША - 20, ШД - 8. ИСХОДНЫЕ ДАННЫЕ: ...

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

Модуль дистанционного запуска двигателя автомобиля
Назначение устройства - производить запуск двигателя с помощью SMS сообщения. Курсовая работа состоит из 5 частей: В первой части работы на основе технического задания описывается ...