Криптография > Псевдослучайные последовательности

Псевдослучайные последовательности

Секретные ключи представляют собой основу криптографических преобразований, для которых, следуя правилу Керкхофа, стойкость хорошей шифровальной системы определяется лишь секретностью ключа. Однако в практике создание, распределение и хранение ключей редко были сложными технически, хотя и дорогими задачами. Основная проблема классической криптографии долгое время заключалась в трудности генерирования непредсказуемых двоичных последовательностей большой длины с применением короткого случайного ключа. Для ее решения широко используются генераторы двоичных псевдослучайных последовательностей. Существенный прогресс в разработке и анализе этих генераторов был достигнут лишь к началу шестидесятых годов. Поэтому в данной главе рассмотрены правила получения ключей и генерации на их основе длинных псевдослучайных последовательностей, используемых криптографическими системами для преобразования сообщения в шифровку.

Получаемые программно из ключа, случайные или псевдослучайные ряды чисел называются на жаргоне отечественных криптографов гаммой, по названию у - буквы греческого алфавита, которой в математических записях обозначаются случайные величины. Интересно отметить, что в книге "Незнакомцы на мосту", написанной адвокатом разведчика Абеля, приводится термин гамма, который специалисты ЦРУ пометили комментарием - "музыкальное упражнение?", то есть в пятидесятые годы они не знали его смысла. Получение и размножение реализаций настоящих случайных рядов опасно, сложно и накладно. Физическое моделирование случайности с помощью таких физических явлений, как радиоактивное излучение, дробовой шум в электронной лампе или туннельный пробой полупроводникового стабилитрона не дают настоящих случайных процессов. Хотя известны случаи удачных применений их в генерации ключей, например, в российском криптографическом устройстве КРИПТОН. Поэтому вместо физических процессов для генерации гаммы применяют программы для ЭВМ, которые хотя и называются генераторами случайных чисел, но на самом деле выдающие детерминированные числовые ряды, которые только кажутся случайными по своим свойствам. От них требуется, чтобы, даже зная закон формирования, но не зная ключа в виде начальных условий, никто не смог бы отличить числовой ряд от случайного, как будто он получен бросанием идеальных игральных костей. Можно сформулировать три основных требования к криптографически стойкому генератору псевдослучайной последовательности или гаммы:

Период гаммы должен быть достаточно большим для шифрования сообщений различной длины.
Гамма должна быть трудно предсказуемой. Это значит, что если известны тип генератора и кусок гаммы, то невозможно предсказать следующий за этим куском бит гаммы с вероятностью выше х. Если криптоаналитику станет известна какая-то часть гаммы, он все же не сможет определить биты, предшествующие ей или следующие за ней.
Генерирование гаммы не должно быть связано с большими техническими и организационными трудностями.

Псевдослучайные последовательности

Разделы