Генератор усадки - Shrinking generator

В криптография, то усадочный генератор это форма генератор псевдослучайных чисел предназначен для использования в потоковый шифр. Он был опубликован в Crypto 1993 г. Дон Копперсмит, Уго Кравчик, и Ишай Мансур.[1]

Генератор усадки использует два регистры сдвига с линейной обратной связью. Один, названный А последовательность, генерирует выходные биты, а другая, называемая S последовательность, контролирует их вывод. Обе А и S синхронизированы; если S кусочек равно 1, то А бит выводится; если S бит равен 0, А бит сбрасывается, ничего не выводится, и мы снова синхронизируем регистры. Это имеет недостаток, заключающийся в том, что выходная мощность генератора изменяется нерегулярно и таким образом, что намекает на состояние S; эту проблему можно решить путем буферизации вывода. Случайная последовательность, сгенерированная LFSR, не может гарантировать непредсказуемость в защищенной системе, и были предложены различные методы для улучшения ее случайности. [2]

Несмотря на эту простоту, в настоящее время нет известных атак лучше, чем исчерпывающий поиск, когда полиномы обратной связи являются секретными. Однако, если известны полиномы обратной связи, наиболее известная атака требует меньше, чем А • S бит вывода.[3]

Интересный вариант - самоусаживающийся генератор.

Реализация на Python

В этом примере используются два LFRS Галуа для создания выходного псевдослучайного потока битов. Код Python можно использовать для шифрования и дешифрования файла или любого байтового потока.

#! / usr / bin / env python3импорт sys# ----------------------------------------------------------------------------# Функции Crypto4o начинаются здесь# ----------------------------------------------------------------------------учебный класс GLFSR:    "" "Регистр сдвига Галуа с линейной обратной связью." ""    def __в этом__(себя, полином, Первоначальный значение):        Распечатать "Использование полинома 0x%ИКС, начальное значение: 0x%ИКС." % (полином, Первоначальный значение)        себя.полином = полином | 1        себя.данные = Первоначальный значение        tmp = полином        себя.маска = 1        пока tmp != 0:            если tmp & себя.маска != 0:                tmp ^= себя.маска            если tmp == 0:                перемена            себя.маска <<= 1    def next_state(себя):        себя.данные <<= 1        Retval = 0        если себя.данные & себя.маска != 0:            Retval = 1            себя.данные ^= себя.полином        возвращаться Retvalучебный класс SPRNG:    def __в этом__(себя, polynom_d, init_value_d, polynom_c, init_value_c):        Распечатать "GLFSR D0:",        себя.glfsr_d = GLFSR(polynom_d, init_value_d)        Распечатать "GLFSR C0:",        себя.glfsr_c = GLFSR(polynom_c, init_value_c)    def next_byte(себя):        байт = 0        битпо = 7        пока Истинный:            bit_d = себя.glfsr_d.next_state()            bit_c = себя.glfsr_c.next_state()            если bit_c != 0:                bit_r = bit_d                байт |= bit_r << битпо                битпо -= 1                если битпо < 0:                    перемена        возвращаться байт# ----------------------------------------------------------------------------# Функции Crypto4o заканчиваются здесь# ----------------------------------------------------------------------------def главный():    prng = SPRNG(        int(sys.argv[3], 16),        int(sys.argv[4], 16),        int(sys.argv[5], 16),        int(sys.argv[6], 16),    )    с открыто(sys.argv[1], "рб") в качестве ж, открыто(sys.argv[2], "wb") в качестве грамм:        пока Истинный:            input_ch = ж.читать(1)            если input_ch == "":                перемена            random_ch = prng.next_byte() & 0xFF            грамм.записывать(chr(ord(input_ch) ^ random_ch))если __имя__ == "__главный__":    главный()

Смотрите также

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

  1. ^ Д. Копперсмит, Х. Кравчик и Ю. Мансур, "Усадочный генератор, ”В CRYPTO ’93: Материалы 13-й ежегодной международной криптологической конференции по достижениям в криптологии (Нью-Йорк, Нью-Йорк, США), стр. 22–39, Springer-Verlag New York, Inc., 1994.
  2. ^ Poorghanad, A. et al. Генерация высококачественного псевдослучайного числа с помощью эволюционных методов IEEE, DOI: 10.1109 / CIS.2008.220.
  3. ^ Caballero-Gil, P. et al. Новая стратегия атаки для сжимающегося генератора Журнал исследований и практики информационных технологий, Vol. 1, страницы 331–335, декабрь 2008 г.