Генераторы случайных и псевдослучайных чисел



Те, кто знаком с криптографией, прекрасно понимают важность случайных чисел. Практически каждый алгоритм шифрования содержит как минимум один параметр с характеристиками «случайное число». Алгоритмы формирования электронно-цифровых подписей используют случайные числа для формирования ключей. При чём требования к этим числам крайне строгие, ведь от их выполнения зависит криптостойкость всей системы шифрования. Обычный пользователь не может себе представить важность случайного числа в его жизни. Однако, каждый из нас ежедневно отправляет сообщения в интернете, совершает телефонные звонки, но никто не хочет, чтобы третья сторона знала о чём ведётся беседа. Шифрование данных применяется не только для сокрытия важной государственной информации, данные каждого человека ежедневно подвергаются шифрованию. Поэтому нельзя недооценивать роль случайного числа в жизни современного человека. Это обстоятельство подчёркивает известный афоризм математика ORNL Роберта Кавью: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».

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

Известно, что при реализации криптографических преобразований, используют различные случайные первичные состояния либо целые последовательности. Отсюда следует, что стойкость криптопреобразования напрямую зависит от алгоритма формирования случайных чисел и последовательностей, точнее от их степени случайности.

Современные компиляторы обладают собственной реализацией генератора псевдослучайных последовательностей, однако с криптографической точки зрения они являются непригодными. Основная сложность генерации последовательности псевдослучайных чисел на компьютере в том, что компьютеры детерминистичны по своей сути. Компьютер может находиться только в конечном количестве состояний (количество состояний огромно, но все-таки конечно). Следовательно, любой датчик случайных чисел по определению периодичен. Все периодическое — предсказуемо, т. е. не случайно.

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

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

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

Альтернативным решением является создание набора из большого количества случайных чисел и опубликование его в некотором словаре, называемом «одноразовым блокнотом». Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с тем количеством, которое требуется приложениям сетевой безопасности. Хотя данные наборы действительно обеспечивают статистическую случайность, они недостаточно безопасны, так как злоумышленник может получить копию словаря.

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

Однако, если каждый раз при включении генератор будет выдавать одну и ту же последовательность, то взлом криптосистемы будет тривиальной задачей. Например, в случае использования потокового шифрования, перехватив два шифрованных текста, злоумышленник может сложить их по модулю 2 и получить два исходных текста, сложенных также по модулю 2. Такую систему раскрыть очень просто. Если же в руках противника окажется пара «исходный текст — шифрованный текст», то задача вообще становится тривиальной.

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

‒ блока памяти, хранящего информацию о состоянии генератора,

‒ выходной функции, генерирующей бит ключевой последовательности в зависимости от состояния,

‒ функции переходов, задающей новое состояние, в которое перейдет генератор на следующем шаге.

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

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

‒ Генерация ключей,

‒ Одноразовые случайные числа,

‒ Одноразовые шифроблокноты,

‒ Соль в схемах цифровой подписи, например, ECDSA.

Требуемое «качество» случайности меняется от задачи к задаче. Например, генерация одного случайного числа в некоторых протоколах требует только уникальности, тогда как генерация мастер-ключа или одноразового шифроблокнота требует высокой энтропии. В идеале, генерация случайных чисел в КСГПСЧ использует высоконадёжный источник энтропии, которым может быть аппаратный генератор случайных чисел или ход непредсказуемых процессов в системе — хотя в обоих случаях возможны неожиданные уязвимости. С точки зрения теории информации количество случайности — энтропия, которая может быть получена, равна энтропии, предоставляемой системой. Но зачастую в реальных ситуация требуется больше случайных чисел, чем можно получить при существующей энтропии. К тому же процедура получения случайности из самой системы требует достаточно много ресурсов (памяти и времени). В таких случаях, оправданно использование КСГПСЧ — это позволяет «растянуть» имеющуюся энтропию на большее число бит. Когда вся энтропия доступна до выполнения криптографического алгоритма, получается потоковый шифр. Однако некоторые криптосистемы позволяют добавлять энтропию по мере работы, в таком случае алгоритм не является эквивалентом потокового шифра и не может использоваться в этом качестве. Таким образом, разработка потоковых шифров и КСГПСЧ тесно связаны.

Основная идея криптографически стойких генераторов псевдослучайных чисел в том, что они идеально подходят для потоковых шифров. Выход таких генераторов неотличим (точнее, должен быть неотличим) от настоящих случайных последовательностей. С другой стороны, они детерминистичны.

Известно 4 подхода к их конструированию:

‒ системно-теоретический подход;

‒ сложностно-теоретический подход;

‒ информационно-теоретический подход;

‒ рандомизированный подход.

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

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

‒ Большой период, отсутствие повторений;

‒ Критерий линейной сложности: повышенная линейная сложность, локальная линейная сложность (Линейная сложность генератора — это длина кратчайшего LFSR, которая может сгенерировать выход генератора; линейная сложность есть мера случайности псевдослучайного генератора);

‒ Статистические критерии, такие как идеальное распределение:

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

В общем, этот список критериев годится не только для потоковых шифров, созданных в рамках системно-теоретического подхода, но и для всех потоковых шифров. Более того, эти критерии годятся и для всех блочных шифров. Но при системно- теоретическом подходе потоковые шифры создаются таким образом, чтобы напрямую удовлетворять вышеописанным критериям.

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

С другой стороны, взлом каждой такой системы — отдельная задача. Если бы таких шифров было много, то криптоаналитикам могло бы и не захотеться их атаковать. В конце концов, потоковые шифры во многом похожи на блочные шифры — для них нет доказательств стойкости. Существует набор известных способов атаки, но стойкость к ним ничего не гарантирует.

Самый лучший способ получить случайное число — это обратиться к естественной случайности реального мира — радиоактивный распад, шумные диоды и т. п. В принципе, элемент случайности есть и в компьютерах:

‒ время дня;

‒ загруженность процессора;

‒ время прибытия сетевых пакетов и т. п.

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

Литература:

1. Долгов В. И. Криптографическая защита информации в АСУ СН. —:, 1998. — с.
2. Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования. — 3-е изд. — М.: Вильямс, 2000. — 832 с.
3. Жельников В. Псевдослучайные последовательности чисел // Кpиптография от папируса до компьютера. — М.: ABF, 1996. — 335 с.