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

"Случайность - это такая закономерность, которую не удалось обнаружить"

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

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

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

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

Линейный конгуэнтный генератор псевдослучайных чисел (ЛКГ ПСЧ)

x_k+1 = (ax_k + b) mod m,

где

• x₀ - начальное значение (инициализирующий вектор)
• a - множитель
• b - приращение
• m - модуль

У такого генератора максимальный период равен m. Он достигается, например, при выборе констант Парка-Милера:

x_k+1 = 75x_k mod (2³¹ – 1)

Нелинейные конгуэнтные генераторы псевдослучайных чисел (НКГ ПСЧ)

Квадратный конгуэнтный генератор выглядит следующим образом:

x_k+1 = (ax_k² + bx_k +c) mod m

Аналогично выглядят кубический и другие НКГ. Для увеличения периода повторения часто используют суперпозицию нелинейных конгуэнтных генераторов.

Физические датчики случайных процессов

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

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

Биологический датчик случайных чисел

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

Физические датчики шума
Резисторы, полупроводниковые и вакуумные электронные приборы - генерируют случайные последовательности импульсов различной амплитуды. Наиболее удобно применять в вычислительных устройствах физические датчики шума на основе полупроводниковых приборов с Зенеровским пробоем (стабилитроны).

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

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

Понравилась статья? Нажми на кнопку и расскажи друзьям: