Генератор переменного шага - Alternating step generator

В криптография, генератор переменного шага (ПГС) это криптографический генератор псевдослучайных чисел используется в потоковые шифры, на основе трех регистры сдвига с линейной обратной связью. Его выход представляет собой комбинацию двух LFSR, которые пошагово (синхронизируются) поочередно, в зависимости от выхода третьего LFSR.

Дизайн был опубликован в 1987 году и запатентован в 1989 году К. Г. Гюнтером.[1][2]

Обзор

Регистры сдвига с линейной обратной связью (LFSR), со статистической точки зрения, являются отличными генераторами псевдослучайных сигналов с хорошим распределением и простой реализацией. Однако их нельзя использовать как есть, потому что их результат можно легко предсказать.

ПГС состоит из трех регистры сдвига с линейной обратной связью, которые для удобства будем называть LFSR0, LFSR1 и LFSR2. Выход одного из регистров определяет, какой из двух других должен использоваться; например, если LFSR2 выдает 0, LFSR0 синхронизируется, а если он выдает 1, вместо этого синхронизируется LFSR1. На выходе получается Эксклюзивный или последнего бита, произведенного LFSR0 и LFSR1. Начальное состояние трех LFSR является ключевым.

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

Пример кода в C:

/ * 16-битная игрушечная ASG (слишком мала для практического использования); вернуть 0 или 1. * /беззнаковый ASG16игрушка(пустота){  статический беззнаковый / * беззнаковый тип минимум с 16 битами * /    lfsr2  = 0x8102, / * начальное состояние, 16 бит, не должно быть 0 * /    lfsr1  = 0x4210, / * начальное состояние, 15 бит, не должно быть 0 * /    lfsr0  = 0x2492; / * начальное состояние, 14 бит, не должно быть 0 * /  / * LFSR2 использует x ^^ 16 + x ^^ 14 + x ^^ 13 + x ^^ 11 + 1 * /  lfsr2 = (-(lfsr2&1))&0x8016 ^ lfsr2>>1;  если (lfsr2&1)    / * LFSR1 использует x ^^ 15 + x ^^ 14 + 1 * /    lfsr1 = (-(lfsr1&1))&0x4001 ^ lfsr1>>1;  еще    / * LFSR0 использует x ^^ 14 + x ^^ 13 + x ^^ 3 + x ^^ 2 + 1 * /    lfsr0 = (-(lfsr0&1))&0x2C01 ^ lfsr0>>1;  возвращаться (lfsr0 ^ lfsr1)&1;}

ASG очень просто реализовать аппаратно. В частности, вопреки усадочный генератор и самоусаживающийся генератор, выходной бит создается на каждом такте, обеспечивая стабильную производительность и устойчивость к время атаки.

Безопасность

Шахрам Хазаи, Саймон Фишер и Вилли Мейер[3] дать криптоанализ ASG, позволяющий выбирать различные компромиссы между временной сложностью и объемом выходных данных, необходимых для проведения атаки, например с асимптотической сложностью и биты, где - это размер самого короткого из трех LFSR.

Рекомендации

  1. ^ Гюнтер, К. Г. (1988). «Генераторы переменного шага, управляемые последовательностями Де Брёйна». Достижения в криптологии - EUROCRYPT '87. Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 304: 5–14. Дои:10.1007/3-540-39118-5_2. ISBN  978-3-540-39118-0 - через SpringerLink.
  2. ^ Гюнтер, Кристоф-Георг (1989-03-28). «US4817145A - Генератор для генерации двоичных последовательностей шифрования». Патенты Google.
  3. ^ Хазаи, Шахрам; Фишер, Саймон; Мейер, Вилли (2007). «Атаки пониженной сложности на генератор переменного шага». Избранные области криптографии. Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 4876: 1–16. Дои:10.1007/978-3-540-77360-3_1. ISBN  978-3-540-77360-3 - через SpringerLink.
  • Шнайер, Брюс. Прикладная криптография (p383-384), второе издание, John Wiley & Sons, 1996. ISBN  0-471-11709-9