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

Он заключается в следующем. Вначале выбираются два больших простых 1 Целое положительное число большее единицы называется простым , если оно не делится ни на какое другое число, кроме самого себя и единицы. Подробнее о простых числах см. в "Основные положения теории чисел, используемые в криптографии с открытым ключом" . числа p и q . Числа p и q должны быть оба сравнимы с 3 по модулю 4, то есть при делении p и q на 4 должен получаться одинаковый остаток 3. Далее вычисляется число M = p* q , называемое целым числом Блюма. Затем выбирается другое случайное целое число х , взаимно простое (то есть не имеющее общих делителей, кроме единицы) с М . Вычисляем х0= х 2 mod M . х 0 называется стартовым числом генератора.

На каждом n-м шаге работы генератора вычисляется х n+1 = х n 2 mod M . Результатом n-го шага является один (обычно младший) бит числа х n+1 . Иногда в качестве результата принимают бит чётности, то есть количество единиц в двоичном представлении элемента. Если количество единиц в записи числа четное – бит четности принимается равным 0 , нечетное – бит четности принимается равным 1 .

Например , пусть p = 11, q = 19 (убеждаемся, что 11 mod 4 = 3, 19 mod 4 = 3 ). Тогда M = p* q = 11*19=209 . Выберем х , взаимно простое с М : пусть х = 3 . Вычислим стартовое число генератора х 0 :

х 0 = х 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.

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

Самым интересным для практических целей свойством этого метода является то, что для получения n-го числа последовательности не нужно вычислять все предыдущие n чисел х i . Оказывается х n можно сразу получить по формуле

Например, вычислим х 10 сразу из х 0 :

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

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

Безопасность алгоритма BBS основана на сложности разложения большого числа М на множители. Утверждается, что если М достаточно велико, его можно даже не держать в секрете; до тех пор, пока М не разложено на множители, никто не сможет предсказать выход генератора ПСЧ. Это связано с тем, что задача разложения чисел вида n = pq (р и q - простые числа) на множители является вычислительно очень трудной, если мы знаем только n , а р и q - большие числа, состоящие из нескольких десятков или сотен бит (это так называемая задача факторизации ).

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

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

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

Ключевые термины

Stream cipher – поточный шифр .

Алгоритм BBS – один из методов генерации псевдослучайных чисел. Название алгоритма происходит от фамилий авторов - L. Blum, M. Blum, M. Shub. Алгоритм может использоваться в криптографии. Для вычислений очередного числа x n+1 по алгоритму BBS используется формула х n+1 = х n 2 mod M , где M = pq является произведением двух больших простых p и q .

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

Линейный конгруэнтный генератор псевдослучайных чисел – один из простейших ГПСЧ, который для вычисления очередного числа k i использует формулу k i =(a*k i-1 +b)mod c , где а, b, с - некоторые константы , a k i-1 - предыдущее псевдослучайное число .

Метод Фибоначчи с запаздываниями – один из методов генерации псевдослучайных чисел. Может использоваться в криптографии.

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

Краткие итоги

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

В компьютерных программах нередко требуется эмуляция случайности. Например, при разработке игр. Если в программе имеется некий генератор, т. е. производитель, случайного числа, то, используя полученное таким образом число, можно выбирать ту или иную ветку выполнения программы, или произвольный объект из коллекции. Другими словами, главное – сгенерировать число. Эмуляция случайности иного рода основывается на нем.

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

"Зерно" – это исходные данные для формулы. Им может быть, например, системное время в миллисекундах, которое постоянно меняется. Следовательно, "зерно" будет постоянно разным. Или программист может задавать его самостоятельно.

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

В этом уроке будут рассмотрены функции random(), randrange() и randint() из модуля random. Обратите внимание, что модуль random содержит одноименную функцию random(). Так бывает.

Чтобы обращаться к функциям, надо импортировать модуль random:

>>> import random

Или импортировать отдельные функции из него:

>>> from random import random , randrange, randint

Функции для получения целых "случайных" чисел – randint() и randrange()

Функции randint() и randrange() генерируют псевдослучайные целые числа. Первая из них наиболее простая и всегда принимает только два аргумента – пределы целочисленного диапазона, из которого выбирается любое число:

>>> random .randint (0 , 10 ) 6

или (если импортировались отдельные функции):

>>> randint(100 , 200 ) 110

В случае randint() обе границы включаются в диапазон, т. е. на языке математики отрезок описывается как .

Числа могут быть отрицательными:

>>> random .randint (-100 , 10 ) -83 >>> random .randint (-100 , -10 ) -38

Но первое число всегда должно быть меньше или, по-крайней мере, равно второму. То есть a <= b.

Функция randrange() сложнее. Она может принимать один аргумент, два или даже три. Если указан только один, то она возвращает случайное число от 0 до указанного аргумента. Причем сам аргумент в диапазон не входит. На языке математики – это Vi ] 2 Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.

Аппаратные ГПСЧ

Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы или держатся в секрете . Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA - или ASIC -ячеек). Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, поэтому до сих пор все известные аппаратные ГПСЧ были взломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR-генераторами, и оба были взломаны с помощью алгебраических атак.

Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры (DES , AES) и хеш-функции (SHA-1) в поточных режимах.