Самосокращающийся генератор
Самосжимающийся генератор — это псевдослучайный генератор , основанный на концепции сжимающегося генератора . варианты самосжимающегося генератора на основе регистра сдвига с линейной обратной связью Изучены (LFSR) для использования в криптографии . [ ВОЗ? ]
Алгоритм [ править ]
В отличие от генератора сжатия , который использует второй регистр сдвига с обратной связью для управления выходом первого, генератор самосжимания использует чередующиеся выходные биты одного регистра для управления своим окончательным выходом. Процедура тактирования такого типа генератора следующая:
- Дважды тактируйте LFSR, чтобы получить пару битов на выходе LFSR.
- Если пара равна 10, выведите ноль.
- Если пара равна 11, выведите единицу.
- В противном случае ничего не выводить.
- Вернитесь к первому шагу.
Пример [ править ]
В этом примере будет использоваться полином связи x 8 + х 4 + х 3 + х 2 + 1 ,и начальное заполнение регистра 1 0 1 1 0 1 1 0 .
В таблице ниже для каждой итерации LFSR перечислены его промежуточные выходные данные перед самосжатием, а также окончательные выходные данные генератора. Положения ответвлений, определенные полиномом соединения, отмечены синими заголовками. Состояние нулевой итерации представляет собой начальный ввод.
| Итерация № | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | Промежуточный результат | Выход генератора |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | Н/Д | Н/Д |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | Н/Д |
| 2 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 4 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
В конце четырех итераций создается следующая последовательность промежуточных битов: 0110 .
Первая пара битов, 01 , отбрасывается, поскольку она не соответствует ни 10 , ни 11 . Вторая пара бит, 10 , соответствует второму шагу алгоритма, поэтому на выходе выводится ноль.
Дополнительные биты создаются путем продолжения тактирования LFSR и сокращения его выходного сигнала, как описано выше.
Криптоанализ [ править ]
В своей статье [1] Мейер и Стеффельбах доказывают, что самосужающийся генератор на основе LFSR с полиномом связи длины L приводит к периоду выходной последовательности не менее 2. Л/2 и линейной сложностью не менее 2 Л/2-1 .
Более того, они показывают, что любой самосжимающийся генератор можно представить как сжимающийся генератор. Обратное также верно:Любой сжимающий генератор может быть реализован как самосжимающийся генератор, хотя результирующий генератор может не иметь максимальной длины.
Атака, представленная авторами, требует около 2 0,7 л шагов, предполагая известный полином связи.
Более продвинутая атака, [2] обнаруженный Михалевичем, способен разбить регистр длиной в сто бит примерно за 2 57 шагов, используя выходную последовательность всего 4,9 x 10 8 биты.
Еще одна атака [3]
Ссылки [ править ]
- ^ «Самосжимающийся генератор», Достижения в криптологии - Eurocrypt 1994 (LNCS 950), 205-214, 1995.
- ^ «Проверка безопасности самосокращающегося генератора», Сиренсестер, Великобритания, декабрь 1995 г.
- ^ Зеннер, Эрик; Краузе, Матиас; Удачи, Стефан. «Улучшенный криптоанализ самосжимающегося генератора» . Информационная безопасность и конфиденциальность 13-я Австралазийская конференция ACISP 2008 : 30 . Проверено 12 апреля 2016 г.