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

Генератор Макларена — Марсальи (MacLaren–Marsaglia) — криптографически стойкий генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был предложен в 1965 году американскими математиками Джорджем Марсальей, и Дональдом Маклареном. В своих работах Дональд Кнут называет генератор Макларена — Марсальи «генератор М».

Описание

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

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

• Инициализация $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$;

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

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

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

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

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

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

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

Пример

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

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.

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

Недостатки

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

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

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

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

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

Применение

CSI-10

Генератор Макларена — Марсальи в 1980-х годах использовали в криптографическом устройстве, название которого «CSI-10». Устройство легко помещалось в кармане пиджака и представляло собой 12-ти символьный дисплей и набор клавиш. Хоть и устройство было миниатюрным, оно обладало значительным функционалом шифрования того времени. По сравнению с другими аналогами того времени (например, «HP-41C») оно имело достаточный объём памяти, что позволяло применять различные алгоритмы перестановок и замены. В дополнении, можно было подключить два периферийных устройства: магнитная лента и принтер.

Для запуска работы устройства необходимо было вначале ввести два ключа, каждый из которого инициализировал работу генераторов, которые в совокупности реализовывали метод Макларена — Марсальи. После выводимой на дисплей подсказки, нужно было ввести открытый текст.

В связи с тем, что на дисплее помещались всего 12 символов, входные и выходные данные делились на группы символов. В каждой группе могло быть расположено 6 знаков, а максимальное число групп равнялось 72, таким образом, максимальный размер открытого текста равнялся 432 символа.

Принцип работы шифрования состоял в перестановке и замене открытого текста на основе генерируемой последовательности генератора Макларена — Марсальи. Производители устройства оставили в тайне подробное описание работы.

Файловая система

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

В 1980 году начали использовать в файловых системах мини-компьютеров генератор Макларена-Марсальи, как часть криптосистемы. В свою очередь, генератор состоял из двух конгруэнтных генераторов, период генератора значений равнялся $32768$, а период генератора указателей на вспомогательную таблицу равнялся $59049$. Поскольку эти числа взаимно просты, то период генератора в целом равнялся $1934917632$.

Суть шифрования состояла в том, что каждому слову, состоящему из 16 битов, ставилось в соответствие слово, генерируемое методом Макларена — Марсальи, и над этими кусочками производилась операция $\oplus$. Таким же образом осуществлялось расшифрование.

Однако, в 1984 году Чарльз Т. Реттер провёл исследования и показал, что данная криптосистема не является надёжной. Поэтому изменили данную защиту на криптосистему с использованием DES.

Поточное шифрование

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

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

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

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

Однако, работы Чарльза Т. Реттера дали понять, что данный генератор не желательно использовать для генерации потока ключей, так как он не обладает достаточной криптостойкостью.

Атака

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

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

См. также

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

Литература

• Дональд Э. Кнут. Искусство программирования = 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.