Обзор генераторов псевдослучайных чисел

Размещено на http://www.allbest.ru/

Обзор генераторов псевдослучайных чисел

Прокофьев А.В.

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

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

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

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

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

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

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

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

Линейный регистр сдвига с обратной связью. Большинство реальных поточных шифров основано на регистрах сдвига с обратной связью (РСОС). Регистр сдвига применяют для генерации ключевой последовательности. Регистр сдвига с обратной связью показан на рисунке 1 и состоит из двух частей: регистра сдвига и функции обратной связи.

Рисунок 1 - регистр сдвига с обратной связью

Регистр сдвига представляет собой последовательность битов. Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым регистром сдвига.

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

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

Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (РСЛОС). Обратная связь представляет собой логическую операцию «ИЛИ»некоторых битов регистра - эти биты называются отводной последовательностью. Регистр сдвига с линейной обратной связью показан на рисунке 2.

РСЛОС (n - битовый) может находиться в одном из 2ⁿ?1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2ⁿ?1 битов.

Число внутренних состояний и период равны 2ⁿ?1, потому что заполнение РСЛОС нулями приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.

Только при определенных отводных последовательностях РСЛОС циклически пройдет через все 2ⁿ?1 внутренних состояний. Такие РСЛОС имеют максимальный период. Получившийся результат называется М-последовательностью. Для того чтобы конкретный РСЛОС имел максимальный период, многочлен, ассоциированный с отводной последовательностью, должен быть примитивным по модулю 2 -- то есть не раскладываться на произведение двоичных многочленов меньшей степени.

Регистр сдвига представляет собой электронную схему, позволяющая вырабатывать последовательность, определяемую линейным рекуррентным уравнением. Схема состоит из двух элементов. Один из элементов называется сумматор, второй - задержкой. Сумматор имеет два входа и один выход. Задержка имеет один вход и один выход.

Если на вход сумматора подаются два одинаковых сигнала, то на выход подается 0, в противном случае 1. Сумматор реализует двоичную функцию.

Если на вход задержки подается какой-нибудь сигнал, то на выход идет тот же сигнал. Сумматор и задержка показаны на рисунке 2.

Пример. Уравнению (1.1) построена схема регистра сдвига, изображенная на рисунке 2.

, (1.1.)

где - ;

;

;

;

.

Периодическая последовательность: 1000101011101100000… с примитивным периодом 31.

Рисунок 3 - регистр сдвига с линейной обратной связью

РСЛОС являются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными свойствами. Для РСЛОС длины равной n, внутреннее состояние представляет собой предыдущие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью алгоритма Берлекэмпа-Мэсси.

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

Линейный конгруэнтный метод был предложен Д. Г. Лемером в 1949 году [1]. Цель метода заключалась в вычислении последовательности случайных чисел X_n, полагая по формуле (1.2):

X_n+1 = (aX_n + c) mod m, (1.2)

где m - модуль (натуральное число, относительно которого вычисляет остаток от деления; m ? 2), a - множитель (0 ? X₀ < m).

Эта последовательность называется линейной конгруэнтной последовательностью. Например, для m = 10, X₀ = a = c = 7 получим последовательность 7,6,9,0,7,6,9, 0, ….

Линейная конгруэнтная последовательность, определенная числами m, a, c и X₀, периодична с периодом, не превышающим m. При этом, длина периода равна m тогда и только тогда, когда [3]:

1. Числа c и m взаимно простые;

2. a - 1 кратно p для каждого простого p, являющегося делителем m;

3. a - 1 кратно 4, если m кратно 4.

Наличие этого свойства для случая m = 2^e, где e - число битов в машинном слове, было доказано М. Гринбергом [4]. Наличие этого свойства для общего случая и достаточность условий были доказаны Т. Е. Халлом и А. Р. Добеллом [5].

Метод генерации линейной конгруэнтной последовательности при c = 0 называют мультипликативным конгруэнтным методом, а при c ? 0 {\displaystyle c=0}{\displaystyle c=0}{\displaystyle c\neq 0}- смешанным конгруэнтным методом. При c = 0{\displaystyle c=0} генерируемые числа будут иметь меньший период, чем при c ? 0{\displaystyle c\neq 0}, но при определенных условиях можно получить период длиной m - 1{\displaystyle m-1}, если m {\displaystyle m}- простое число. Тот факт, что условие{\displaystyle c\neq 0} c ? 0 может приводить к появлению более длинных периодов, был установлен В. Е. Томсоном и независимо от него А. Ротенбергом [2]. Чтобы гарантировать максимальность цикла повторения последовательности при c = 0{\displaystyle c=0}{\displaystyle c=0}, необходимо в качестве значения параметра m выбирать простое число. Самым известным генератором подобного рода является так называемый минимальный стандартный генератор случайных чисел, предложенный Стивеном Парком и Кейтом Миллером в 1988 году. Для него a = 16807{\displaystyle a=16807}, а m = 2147483647 [6] [7]{\displaystyle m=2147483647}.

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

При выборе числа{\displaystyle m} m необходимо учитывать следующие условия:

1) число m должно быть довольно большим, так как период не может иметь больше m элементов;

2) значение числа m должно быть таким, чтобы (aX_n + c) mod m вычислялось быстро.

На практике при реализации метода исходя из указанных условий чаще всего выбирают m = 2^e {\displaystyle m=2^{e}}, где e - число битов в машинном слове. При этом стоит учитывать, что младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Подобная ситуация не возникает, когда m = w ± 1, где w - длина машинного слова. В таком случае младшие разряды X_n ведут себя так же случайно, как и старшие [2]. Выбор множителя a и приращения c, в основном, обусловлен необходимостью выполнения условия достижения периода максимальной длины.

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

Тем не менее, линейные конгруэнтные генераторы являются полезными для не криптографических приложений. Например, в моделировании или в игровых приложениях.

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

В отличие от линейного конгруэнтного генератора в правую часть рекуррентного соотношения обобщенного генератора Фибоначчи входит два члена предшествующей последовательности. Другое название этого генератора «запаздывающий генератор Фибоначчи» (LFG). Известны разные схемы использования метода Фибоначчи с запаздыванием. Один из широко распространённых «Фибоначиевых» датчиков основан на рекуррентной формуле (1.3):

(1.3)

где - - вещественное число диапозона [0,1];

a,b - параметры генератора, вещественные числа

Для оптимальной работы датчику «Фибоначи» требуется знать max{a,b} предыдущих сгенерированных случайных чисел.

Для достижения цели программной реализации, хранения сгенерированных случайных чисел, необходим некоторый объем памяти, зависящих от вышеуказанных параметров a и b из формулы (1.1).

Параметры должны быть протестированы на качество. Качество получаемых случайных чисел зависит от значения константы.

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

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

Генератор с квадратичным остатком. Для достижения целей криптографии в 1986 году предложен генератор с квадратичным остатком.

Суть генератора заключается в следующем:

1) Изначально выбираются два больших простых числа p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4;

2) Далее вычисляется целое число Блюма:

(1.4)

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

4) Далее считают стартовое число генератора (1.5):

(1.5)

На каждом (n-м) шаге работы генератора вычисляется:

(1.6)

Результатом n-го шага является один младший бит числа - (). Так же в качестве результата принимают бит чётности, то есть количество единиц в двоичном представлении элемента. Если количество единиц в записи числа четное - бит четности принимается равным 0, нечетное - бит четности принимается равным.

Безопасность алгоритма BBS реализована на сложности разложения большого числа М на несколько множителей. Если М достаточно большое, то его можно даже не держать в секрете. Или держать до тех пор, пока М не разложено на множители, никто не сможет предсказать выход генератора ПСЧ.

Это связано с тем, что задача разложения чисел на множители вида:

(1.7)

где - p, q - простые числа.

Является вычислительно очень трудной, если знать только n, а р и q -большие числа, состоящие из нескольких десятков или сотен бит - задача факторизации.

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

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

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

Инверсный конгруэнтный метод был предложен Эйченауэром и Лехном в 1986 году [4] как замена линейному конгруэнтному методу, не обладающему решётчатой структурой [5].

Данный метод состоит в вычислении последовательности случайных чисел x_n в кольце вычетов по модулю натурального числа n.

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

Параметрами генератора являются [6]:

seed - соль,

a - множитель (0 ? a < n),

b - приращение (0 ? b < n).

В случае простого n значение членов последовательности задается в виде (1.7) и (1.8):

x₀ = seed, (1.7)

x_i+1 (a + b) mod n. (1.8)

Параметры подбираются таким образом, чтобы (1.9) и (1.10):

(seed, n) = 1; (1.9)

(a, n) = 1. (1.10)

Последовательность, формируемая инверсным конгруэнтным генератором, определенным числами a, b и n, имеет максимальный период, равный n + 1, когда многочлен f(x) = x² - cx - a обладает следующими свойствами:

1. x^p+1 mod f(x) равняется отличной от нуля константе;

2. x^(p+1)/q mod f(x) имеет степень 1 для каждого простого q, делящего значение p + 1.

Значение p + 1 является исключительно теоретическим, так как получается в предположении, что 0^-1 = ? и ?^-1 = 0. На практике обычно полагают 0^-1 = 0, в этом случае максимальный период равен p.

В качестве примера рассмотрим инверсный конгруэнтный генератор с параметрами n = 5, a = 2, b = 3, seed = 1. Он генерирует последовательность {1,0,3,2,4,1, …} в кольце F₅, где числа 1 и 4, а также 2 и 3 обратны друг другу. В данном примере многочлен f(x) = x² - 3x - 2 неприводимом в F5[x] и числа 0,1,2,3,4 не являются его корнями, благодаря чему период максимален и равен n = 5.

В инверсных конгруэнтных генераторах отсутствует «решетчатая» структура.

Список литературы

1 Дональд Э. Кнут. Искусство программирования. -- 3-е изд. -- М.: Вильямс, 2000. -- Т. 2. Получисленные алгоритмы. -- 832 с.

2 Л. Бараш Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел // Безопасность информационных технологий. -- 2005. -- № 2. -- с. 27-38.

3 Stephen K. Park and Keith W. Miller Random Number Generators: Good Ones Are Hard To Find. -- 1988. -- № 2. -- с. 1192-1201.

4 Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi.Библиотека программиста. // Delphi Informant Magazine. -- 2002.

5 Дональд Кнут. Том 2. Получисленные методы // Искусство программирования. Указ. соч. -- с. 21--37.

6 M. Greenberger, Method in randomness, Comm. ACM 8 -- 1965 -- с. 177--179.

7 T.E. Hull and A.R. Dobell «Random Number Generators», SIAM Review 4-3 -- 1962 -- с. 230-254.

Размещено на Allbest.ru