Генератор переменного шага

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

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

Обзор [ править ]

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

ASG состоит из трех регистров сдвига с линейной обратной связью , которые для удобства мы назовем LFSR0, LFSR1 и LFSR2. Выходные данные одного из регистров решают, какой из двух других будет использоваться; например, если LFSR2 выводит 0, тактируется LFSR0, а если он выводит 1, вместо этого тактируется LFSR1. Выходные данные представляют собой исключающее ИЛИ последнего бита, созданного LFSR0 и LFSR1. Начальное состояние трех LFSR является ключевым.

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

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

/* 16-bit toy ASG (much too small for practical usage); return 0 or 1. */
unsigned ASG16toy(void)
{
  static unsigned /* unsigned type with at least 16 bits */
    lfsr2  = 0x8102, /* initial state, 16 bits, must not be 0 */
    lfsr1  = 0x4210, /* initial state, 15 bits, must not be 0 */
    lfsr0  = 0x2492; /* initial state, 14 bits, must not be 0 */

  /* LFSR2 use  x^^16 + x^^14 + x^^13 + x^^11 + 1 */
  lfsr2 = (-(lfsr2&1))&0x8016 ^ lfsr2>>1;

  if (lfsr2&1)
    /* LFSR1 use  x^^15 + x^^14 + 1 */
    lfsr1 = (-(lfsr1&1))&0x4001 ^ lfsr1>>1;
  else
    /* LFSR0 use  x^^14 + x^^13 + x^^3 + x^^2 + 1 */
    lfsr0 = (-(lfsr0&1))&0x2C01 ^ lfsr0>>1;

  return (lfsr0 ^ lfsr1)&1;
}

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

Безопасность [ править ]

Шахрам Хазаи, Саймон Фишер и Вилли Мейер ^[3] дать криптоанализ ASG, позволяющий найти различные компромиссы между временной сложностью и объемом вывода, необходимым для организации атаки, например, с асимптотической сложностью $O(L^{2}.2^{2L/3})$ и $O(2^{2L/3})$ биты, где $L$ - размер самого короткого из трех LFSR.

Ссылки [ править ]

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

Шнайер, Брюс. Прикладная криптография (стр. 383–384), второе издание, John Wiley & Sons, 1996. ISBN 0-471-11709-9

[1] Гюнтер, CG (1988). «Генератор переменного шага, управляемый последовательностями де Брейна». Достижения в криптологии — EUROCRYPT '87 . Конспекты лекций по информатике. Том. 304. Берлин, Гейдельберг: Шпрингер. стр. 5–14. дои : 10.1007/3-540-39118-5_2 . ISBN 978-3-540-39118-0 .

[2] Гюнтер, Кристоф-Георг (28 марта 1989 г.). «US4817145A — Генератор для формирования двоичных шифропоследовательностей» . Гугл Патенты .

[3] Хазаи, Шахрам; Фишер, Саймон; Мейер, Вилли (2007). «Атаки пониженной сложности на генератор переменного шага». Избранные области криптографии . Конспекты лекций по информатике. Том. 4876. Берлин, Гейдельберг: Springer. стр. 1–16. дои : 10.1007/978-3-540-77360-3_1 . ISBN 978-3-540-77360-3 .

[1]

[2]

[3]