Сжимающий генератор
В криптографии представляет сокращающийся генератор собой разновидность генератора псевдослучайных чисел, предназначенного для использования в поточном шифре . Его опубликовали в Crypto 1993 Дон Копперсмит , Хьюго Кравчик и Ишай Мансур . [1]
Генератор сжатия использует два регистра сдвига с линейной обратной связью . Одна, называемая последовательностью A , генерирует выходные биты, а другая, называемая последовательностью S , управляет их выходом. И A , и S синхронизированы; если S бит равен 1, то A выводится бит ; если бит S равен 0, бит A отбрасывается, ничего не выводится, и регистры синхронизируются снова. Недостаток этого метода заключается в том, что выходная мощность генератора меняется нерегулярно, что указывает на состояние S ; эту проблему можно решить путем буферизации вывода. Случайная последовательность, генерируемая LFSR, не может гарантировать непредсказуемость в защищенной системе, и для улучшения ее случайности были предложены различные методы. [2]
Несмотря на эту простоту, в настоящее время не известны атаки лучше, чем исчерпывающий перебор, когда полиномы обратной связи являются секретными. Однако если полиномы обратной связи известны, наиболее известная атака требует меньше, чем A • S бит вывода. [3]
Вариант — самосужающийся генератор .
Реализация на Python [ править ]
В этом примере используются два LFRS Галуа для создания выходного псевдослучайного битового потока. Код Python можно использовать для шифрования и дешифрования файла или любого байтового потока.
#!/usr/bin/env python3 import sys # -------------------------------------- -------------------------------------- # Здесь начинаются функции Crypto4o # ------ -------------------------------------------------- -------------------- class GLFSR : """Сдвиговый регистр Галуа с линейной обратной связью.""" def __init__ ( self , polynom , Initial_value ): print "Использование полинома 0x %X , начальное значение: 0x %X .» % ( полином , начальное_значение ) self . полином = полином | 1 себя . data = начальное_значение tmp = полином self . маска = 1 while tmp != 0 : если tmp & self . маска != 0 : tmp ^= self . маска, если tmp == 0 : сломать себя . маска <<= 1 def next_state ( self ): self . данные <<= 1 retval = 0, если self . данные и я . маска != 0 : retval = 1 self . данные ^= сам . полинома возврата " класс SPRNG : def __init__ ( self , polynom_d , init_value_d , polynom_c , init_value_c ): напечатайте "GLFSR D0: , self . glfsr_d = GLFSR ( polynom_d , init_value_d ) напечатать «GLFSR C0:» , self . glfsr_c = GLFSR ( polynom_c , init_value_c ) def next_byte ( self ): byte = 0 bitpos = 7 , в то время как True : bit_d = self . glfsr_d . next_state () bit_c = self . glfsr_c . next_state () if bit_c != 0 : bit_r = bit_d byte |= bit_r << bitpos bitpos -= 1 if bitpos < 0 : прерывания возврат номер байта ------------------------------------------------ ---------------------------- # Здесь функции Crypto4o заканчиваются # ---------------- -------------------------------------------------- ---------- def main (): prng = SPRNG ( int ( sys . argv [ 3 ], 16 ), int ( sys . argv [ 4 ], 16 ), int ( sys . argv [ 5 ] ], 16 ), int ( sys . argv [ 6 ], 16 ), ) с open ( sys . argv [ 1 ], "rb" ) как f , open ( sys . argv [ 2 ], "wb" ) как g : while True : input_ch = f . read ( 1 ) , если input_ch == "" : сломать random_ch = prng . next_byte ) и 0xFF г. ( write ( chr ( ord ( input_ch ) ^ random_ch )) if __name__ == "__main__" : main () См. также [ править ]
- FISH — (небезопасный) поточный шифр, основанный на принципе сжимающего генератора.
- Генератор переменного шага , аналогичный потоковый шифр
Ссылки [ править ]
- ^ Д. Копперсмит, Х. Кравчик и Ю. Мансур, « Сжимающий генератор », в CRYPTO '93: Материалы 13-й ежегодной международной конференции по криптологии «Достижения в криптологии» (Нью-Йорк, штат Нью-Йорк, США), стр. 22. –39, Springer-Verlag New York, Inc., 1994 г.
- ^ Порганад, А. и др. Генерация высококачественных псевдослучайных чисел с использованием эволюционных методов IEEE , DOI: 10.1109/CIS.2008.220.
- ^ Кабальеро-Хил, П. и др. Новая стратегия атаки на сокращающийся генератор Журнал исследований и практики в области информационных технологий , Vol. 1, страницы 331–335, декабрь 2008 г.