Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).
Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов.
ГПСЧ в криптографии
Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ. seed), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.
Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.
В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.
Примеры криптостойких ГПСЧ
Циклическое шифрование
В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.
ANSI X9.17
ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:
Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.
DTi — значение даты и времени на начало i-ой стадии генерации.
Vi — начальное значение для i-ой стадии генерации.
Ri — псевдослучайное число, созданное на i-ой стадии генерации.
K1, K2 — ключи, используемые на каждой стадии.
Тогда:
Ri = EDEK1,K2 [ EDEK1,K2 [ DTi] Vi ]
Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]
Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.
Метод Винижера
Используется специальный ключ. Буквы, из которых будет строиться сообщение, нумеруется в естественном порядке. В качестве ключа выбирается произвольная комбинация букв из этого алфавита. Под буквами сообщения записывается ключ, если необходимо, то он повторяется, и затем складываются цифровые эквиваленты букв сообщения и ключа по модулю количества букв в алфавите. Дешифрование производится в обратном порядке.
Пример.
Возьмем латинский алфавит A B C D E F…L… R S V … X Y Z
0 1 2 3 4 5 11 17 18 19 23 24 25
Зашифруем CAREFUL – осторожный.
В качестве ключа возьмем P I E S – 15 8 4 18
-
C
A
R
E
F
U
L
2
0
17
4
5
20
11
P
I
E
S
P
I
E
15
8
4
18
15
8
4
1
- зашифрованное сообщение
78
21
22
20
2
15
Расшифруем полученное сообщение.
-
17
8
21
22
20
2
15
P
I
E
S
P
I
E
15
8
4
18
15
8
4
2
0
17
4
5
20
11
C
A
R
E
F
U
L
Шифр Винижера с ключом в 1-ой букве – шифр Цезаря.
Шифр с неограниченным ключом– шифр Вернама.
Шифрование с гаммированием
Цифровой эквивалент сообщения складывается с какой-то последовательностью чисел, которая является случайной. Эта последовательность называется гаммой, затем складываются по |K|, где К – количество букв в алфавите. Если гамма> длины текста, взломать шифр нельзя.
При шифровании с гаммированием используют линейные конгуэтные датчики – датчики псевдослучайных чисел.
T (i)= (A* T (i-1)+C) mod M,
T (i) – последовательность псевдослучайных чисел
A, C – константы
T0 – выбирается порождающее число.
Такой датчик выдает числа с периодом М1, который зависит от А и С. Датчик имеет максимальный период повторений, когда C нечетно и A mod 4= 1. Цифры ключа a1, a2, a3…ai…an, используются в качестве исходной величины Т0. Для каждой ai, генерируется последовательность псевдослучайных чисел H (i), тогда гамма равна объединению непересекающихся подмножеств H (i)
G= H(1)UH(2)…H(i)…H(n)
Для усиления криптографической стойкости очень часто применяют гаммирование с обратной связью. Здесь отказываются от ключа, и его формирование зависит от сообщения. Для получения G используется контрольная сумма различных частей сообщений а1, а2, а3 – (s1), a4, a5, a6 – (s2)…an. Для каждого контрольного H(s1), H(s2) суммы генерируется последовательность псевдослучайных чисел.