Генератор Макларена

Генератор Макларена-Марсальи - генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был предложен в 1965 году американскими математиками (George Marsaglia (англ.)русск., Джорджом Марсалья) и Дональдом Маклареном. В своих работах Дональд Кнут называет генератор Макларена-Марсальи - генератор М^[1].

Описание

Данный генератор псевдослучайных чисел оперирует с тремя объектами: двумя конгруэнтными генераторами, которые порождают последовательности $<X_{n}>$, $<Y_{n}>$, и матрицей $V$, состоящей из $k$ элементов, обычно $k = 64, 128, 256$. На выходе последовательность $<Z_{N}>$^[2].

Генератор состоит из четырёх основных стадий^[2]:

• Инициализация $V$ и $Z$ с помощью заполнения первыми $k$ элементами последовательности $<X_{n}>$ - выполняется один раз;
• Выборка $X, Y$ из $<X_{n}>, <Y_{n}>$, то есть $X, Y$ очередные члены последовательностей $<X_{n}>$, $<Y_{n}>$;
• Вычисление $j =$ $\lfloor k * Y/m \rfloor$, где $m$ - модуль, использующийся в $<Y_{n}>$. Поэтому $j \in [0,k)$ - случайное число, определяемое $Y$;
• Присвоение $Z_{i} = V_{j}$ и замена $V_{j} = X$;

Последние три стадии могут повторяться необходимое число раз^[2].

Данный метод генерации позволяет получать большие периоды, если последовательности $<X_{n}>$ и $<Y_{n}>$ имеют взаимно простые периоды. И даже если длина периода несущественна, соседние элементы последовательности почти не коррелируют друг с другом^[2].

Метод серединных квадратов гораздо хуже, чем данный метод, так как у последнего достаточная случайность последовательностей $<X_{n}>$ и $<Y_{n}>$, которые не могут вырождаться^[2].

Вместо двух конгруэнтных генераторов имеет место применять две таблицы случайных чисел^[3].

Пример

В данном исходном коде на языке программирования Паскаль реализованы основные части генератора Макларена-Марсальи^[4].

Const
  k = 128; {размер матрицы V}
  N = 100; {размер выходной последовательности}
Var
  i: word;
  V: array[1..k] of extended; {вспомогательная матрица}
  Z: array[1..N] of extended; {выходная последовательность}
  out: extended;
 
Function GMM: extended;
Var
  Result, x, y: extended;
  j: word;
Begin
  x := Random; {случайное число первой последовательности}
  y := Random; {случайное число второй последовательности}
  j := Trunc( y * k );
  If j < 1 then 
    j := 1;
  Result := V[j];
  V[j] := x; {случайное заполнение новым числом}
  GMM := Result;
End;
 
Begin
  Randomize;
  For i:=1 to k do
    V[i] := Random; {Инициализация матрицы V}
  For i:=1 to N do 
    Z[i] := GMM;
End.

В данном исходном коде учтён второй дефект генератора, поэтому $k$ превышает число элементов выходной последовательности.

Применение

Применение в поточных шифрах

Генератор Макларена-Марсальи ранее применялся в качестве генератора потока ключей в поточных шифрах. Однако, работы Чарльза Т. Реттера дали понять, что данный генератор не желательно использовать для генерации потока ключей, так как он не обладает достаточной криптостойкостью^[5].

Недостатки

По крайней мере, выявлено четыре недостатка в генераторе при использовании его для криптографических целей^[1]. Все четыре тесно связаны друг с другом. Первые три недостатка нашёл Чарльз Реттер^[5].

Первый недостаток связан с неизменностью набора вариантов вывода генератора, так как таблица $V$ состоит лишь из значений последовательности $X_{n}$, которые постоянные и в таблицу $V$ попадают случайным образом, заданным $Y_{n}$. В результате, $X_{n}$ можно криптоанализировать вне зависимости от $Y_{n}$^[5].

Второй дефект обусловлен тем, что среднее число итераций генератора между значением, которое помещено из $X_{n}$ в $V$, и его появлением в выходной последовательности примерно равно $k$. Поэтому требуется, чтобы $k$ превышало число элементов выходной последовательности^[5].

Третий недостаток заключается в том, что первоначальное содержание матрицы $V$ напрямую заменяется на элементы $X_{n}$ в соответствии с $Y_{n}$, то есть предыдущее содержание матрицы $V$ никак не влияет на текущее, нет обратной связи. Таким образом, если у злоумышленника имеется список значений выводимых генератором, то это является ключом к разгадке первоначального состояния таблицы $V$^[5].

Четвертый недостаток связан с реализацией данного метода. Зачастую генератор осуществляют, используя массивы, хранящие 32-х битные числа. Из-за этого возникает эффект ограничения элементов в последовательности $X_{n}$, которые могут быть сохранены в $V$, что является причиной группирования отдельных элементов в $V$, которые чётко различимы^[1].

См. также

• Метод Монте-Карло
• Линейный конгруэнтный метод

Примечания

1. ↑ ^{1 2 3} Churchill, 2011
2. ↑ ^{1 2 3 4 5} Knuth, 2000
3. ↑ MacLaren
4. ↑ Артемкин, 2004
5. ↑ ^{1 2 3 4 5} Charles, 1985

Литература

1. Дональд Э. Кнут. Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6
2. M. Donald MacLaren, George Marsaglia Uniform Random Number Generators. — Boeing Scientific Research Laboratories, Seatle, Washington.
3. Richard Lloyd Churchill Modified McLaren-Marsaglia pseudo-random number generator and stochastic key agreement. — Oklahoma State University, 2011. — С. 66-104. — ISBN 9781267185099.
4. Charles T. Retter A KEY-SEARCH ATTACK ON MACLAREN-MARSAGLIA SYSTEMS // Cryptologia. — 1985. — В. 2. — № 9. — С. 114-130.
5. Артемкин Д.Е., Баринов В.В., Овечкин Г.В., Степнов И.М. Основы компьютерного моделирования систем. — М.: Лаборатория Базовых Знаний, 2004. — 152 с. — ISBN 5-93208-162-7