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

Описание

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

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

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

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

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

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

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

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

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

Пример

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

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}$ превышает число элементов выходной последовательности.

Недостатки

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

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

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

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

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

Применение

CSI-10

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

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

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

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

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

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

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

Суть шифрования состояла в том, что каждому слову, состоящему из 16 битов , ставилось в соответствие слово, генерируемое методом Макларена — Марсальи, и над этими кусочками производилась операция ${\displaystyle \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 : .
• 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. // Cryptologia. — 1985. — Вып. 2 , № 9 . — С. 114-130 .
• Charles T. Retter. // Cryptologia. — 1984. — Вып. 2 , № 8 . — С. 97-108 .
• Louis Kruh. // Cryptologia. — 1983. — Вып. 1 , № 7 . — С. 83-88 .
• Артемкин Д. Е., Баринов В. В., Овечкин Г. В., Степнов И. М. . — М. : Лаборатория Базовых Знаний, 2004. — 152 с. — ISBN 5-93208-162-7 .