Линейный конгруэнтный генератор псевдослучайных чисел и метод раскрытия его параметров

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

Линейный конгруэнтный генератор.

Линейный конгруэнтный генератор (ЛКГ) является простейшим генератором псевдослучайных чисел. Алгоритм его работы заключается в следующем:

1.  Выбираются числа-параметры a, m и c. Свойства, которыми должны обладать данные числа будут рассмотрены ниже.

2.  Выбирается некоторое число s₀ < m.

3.  Все последующие числа находятся по формуле s_n = (a*s_n-1 + с) mod m.

Последовательность, выдаваемая ЛКГ, называется линейной конгруэнтной последовательностью, максимальный период которой равен m. Ее период максимален в том случае, когда параметры a, m и c обладают следующими свойствами:

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

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

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

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

Нахождение параметров ЛКГ.

В данном разделе мы рассмотрим алгоритмы нахождения параметров a, с и m по известной последовательности выданных генератором чисел.

Нахождение параметра m.

Обозначим через t_n+1 разность чисел s_n+1 и s_n. Тогда получаем:

t_n+1 = s_n+1 – s_n = (as_n – с) – (as_n-1 – с) = as_n – as_n-1 = at_n mod m

t_n+2 = a²t_n mod m

t_n+2 t_n – t_n+1² = a²t_n * t_n – (at_n) ² = 0 (mod m)

Следовательно, число u_n = |t_n+2 t_n – t_n+1²| делится на m без остатка. Из теории чисел известно, что, если u и v – случайно выбираемые целые числа, то вероятность того, что НОД(u, v) = 1, равна 6/π² = 0.60793. В нашем случае такую же вероятность будет иметь случай, когда НОД(u_i, u_j) = НОД(m*x, m*y) = m * 1 = m. При этом, чем больше мы имеем чисел вида u_n = |t_n+2 t_n – t_n+1²|, тем эта вероятность быстрее будет стремиться к 1, так как НОД(u₁,..,u_n) = НОД(u₁, НОД(u₂,..,u_n)) = … = НОД(u₁, НОД(u₂, …, НОД(u_n-1, u_n)…)) и НОД(u₁,…,u_n-1, 1) = 1.

Нахождение параметра а.

Возьмем 4 подряд выданных генератором числа s_k, s_k+1, s_k+2, s_k+3. Введем следующие обозначения: x = s_k+2 – s_k, b = s_k+3 – s_k+1.

В результате получаем:

x = as_k+1 + c – s_k = a²s_k + ac + c – s_k = s_k(a²–1) + c(a+1) = (a+1)(as_k–s_k+c) = (a+1)(s_k+1 – s_k).

b = as_k+2 + с – as_k – c = a(a²s_k + ac + c) – as_k = a(a²s_k + ac + c – s_k) = a(s_k(a²-1) + c(a+1)) = a(a+1)(as_k – s_k + c) = a(a+1)(s_k+1 – s_k).

Тогда, найдя обратный к x элемент по модулю m:

x^-1 = (a+1)^-1(s_k+1 – s_k)^-1,

получим следующее выражение:

b*x^-1 = a(a+1)(s_k+1 – s_k)* (a+1)^-1(s_k+1 – s_k)^-1 = a (mod m)

Нахождение параметра с.

Взяв из предыдущего пункта числа, например, s_k+3 и s_k+2, найдем c:

s_k+3 – as_k+2 = as_k+2 + с – as_k+2 = c (mod m)

Усовершенствование генератора.

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

Так, например, в компиляторах Borland C/C++, Watcom C, Microsoft Visual/Quick C/C++ отбрасываются младшие 16 бит и один старший.

Пример.

Рассмотрим пример вычисления параметров генератора. Сгенерируем псевдослучайную последовательность, выбрав случайные параметры. Например, a = 52, c = 65, m = 71, s₀ = 7. Получим последовательность

[3, 8, 55, 14, 12, 50, 38, 53, 52]

Тогда массив с числами t_n будет выглядеть следующим образом:

[5, 47, -41, -2, 38, -12, 15, -1]

Массив с числами u_n:

[2414, 1775, 1562, 1420, 426, 213]

Факторизуем все числа u_n. Получим следующие результаты: 2414 = 2 * 17 * 71, 1775 = 5² * 71, 1562 = 2 * 11 * 71, 1420 = 2² * 5 * 71, 426 = 2 * 3 * 71, 213 = 3 * 71.

Вычисляем параметр m: m = НОД(2414, 1775, 1562, 1420, 426, 213) = 71.

Для нахождения параметра а возьмем последние 4 числа последовательности: 50, 38, 53, 52. Тогда x = 53 – 50 = 3, b = 52 – 38 = 14. Найдем обратный к х элемент x^-1: 3^-1 = 24 (mod 71), так как 3 * 24 = 1 (mod 71). В итоге получаем, что а = b*x^-1 = 14 * 24 = 52 (mod 71).

Параметр c получается равным 52 – 52 * 53 = – 2704 = 65 (mod m).

Таким образом, мы нашли параметры генератора с помощью приведенного выше алгоритма. Найденные параметры совпадают с теми, которые использовались при генерации последовательности.

Заключение.

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