Генератор Макларена — Марсальи

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

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

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

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

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

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

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

Впоследствии Кнут установил следующее[1]:

Опора на первое утверждение Кнута привела некоторых к уверованию в полезность интуитивного вида алгоритма Макларена — Марсальи в криптографии. Это не тот случай, как было показано Чарльзом Т. Реттером. Алгоритм никогда не был предназначен для такого использования, как показано в оригинальной работе Макларена и Марсальи. Тем не менее, согласно второму утверждению Кнута, алгоритм достаточно эффективен[1].

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

Const
  k = 128; {размер матрицы V}
  N = 100; {размер выходной последовательности}
Var
  i: word;
  V: array[1..k] of extended; {вспомогательная матрица}
  Z: array[1..N] of 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.

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

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

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

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

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

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

Чарльз Т. Реттер предложил атаку на систему поточного шифрования с использованием генератора Макларена — Марсальи, основная суть которой состоит в подборе ключа к одному из генераторов, игнорируя значение ключа другого генератора. То есть вначале ищется ключ к генератору значений (на рисунке генератор X), тестируя смещения получающейся последовательности относительно известному потоку ключей. После того, как ключ к генератору значений найден, ищется ключ к генератору указателей (на рисунке генератор Y) для вспомогательной таблицы V[5].

Практика показывает, что число вычислений, требуемое для поиска ключей к паре генераторов, лишь чуть больше, чем число вычислений, требуемое для отдельных генераторов. Поэтому использование генератора Макларена — Марсальи не сильно увеличивает безопасность системы поточного шифрования по сравнению с системой, в которой используется единственный генератор[5].

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

• Дональд Э. Кнут. Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6.
• M. Donald MacLaren, George Marsaglia. Uniform Random Number Generators // Journal of the ACM (JACM). — Boeing Scientific Research Laboratories, Seatle, Washington, 1965. — С. Pages 83-89. — doi:10.1145/321250.321257.
• Richard Lloyd Churchill. Modified McLaren-Marsaglia pseudo-random number generator and stochastic key agreement. — Oklahoma State University, 2011. — С. 66-104. — ISBN 9781267185099.
• Charles T. Retter. A KEY-SEARCH ATTACK ON MACLAREN-MARSAGLIA SYSTEMS // Cryptologia. — 1985. — Вып. 2, № 9. — С. 114-130.
• Charles T. Retter. CRYPTANALYSIS OF A MACLAREN-MARSAGLIA SYSTEM // Cryptologia. — 1984. — Вып. 2, № 8. — С. 97-108.
• Louis Kruh. CIPHER EQUIPMENT THE CRYPTOGRAPHIC UNIT CSI-10 // Cryptologia. — 1983. — Вып. 1, № 7. — С. 83-88.
• Артемкин Д. Е., Баринов В. В., Овечкин Г. В., Степнов И. М. Основы компьютерного моделирования систем. — М.: Лаборатория Базовых Знаний, 2004. — 152 с. — ISBN 5-93208-162-7.