Самоусадочный генератор - Self-shrinking generator
А самоусаживающийся генератор это псевдослучайный генератор это основано на усадочный генератор концепция. Варианты самоусаживающегося генератора на основе регистр сдвига с линейной обратной связью (LFSR) изучаются для использования в криптография.
Алгоритм
В отличие от усадочный генератор, который использует второй регистр сдвига с обратной связью для управления выходом первого, самосжимающийся генератор использует чередующиеся выходные биты одного регистра для управления своим конечным выходом. Процедура тактирования такого генератора следующая:
- Дважды синхронизируйте LFSR, чтобы получить пару битов на выходе LFSR.
- Если пара равна 10, выведите ноль.
- Если пара 11, выведите единицу.
- В противном случае ничего не выводить.
- Вернитесь к первому шагу.
Пример
В этом примере будет использоваться полином соединения Икс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 дает период выходной последовательности не менее 2L / 2, и линейная сложность не менее 2L / 2-1.
Кроме того, они показывают, что любой самозакрывающийся генератор можно представить как термоусадочный генератор. Верно и обратное: любой генератор сжатия может быть реализован как генератор самосжатия, хотя результирующий генератор может не иметь максимальной длины.
Атака, представленная авторами, требует около 20,7 л шагов, предполагая известный полином соединения.
Более продвинутая атака,[2] обнаруженный Михалевичем, способен разбить регистр длиной в сто бит примерно за 257 шагов, используя выходную последовательность всего 4,9 x 108 биты.
Еще одна атака [3]
Рекомендации
- ^ "Самоусаживающийся генератор", Advances in Cryptology-Eurocrypt 1994 (LNCS 950), 205-214, 1995.
- ^ «Проверка безопасности самозатухающего генератора», Circencester, UK, декабрь 1995 г.
- ^ Зеннер, Эрик; Краузе, Матиас; Удачи, Стефан. «Улучшенный криптоанализ самозатухающего генератора». Информационная безопасность и конфиденциальность 13-я Австралазийская конференция ACISP 2008: 30. Получено 12 апреля 2016.