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

Генератор был предложен в 1965 году американскими математиками Джорджем Марсальей  (англ.) (рус., и Дональдом Маклареном. В своих работах Дональд Кнут называет генератор Макларена — Марсальи «генератор М».

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

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

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

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

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

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

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

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

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

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

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-ти символьный дисплей и набор клавиш. Хоть и устройство было миниатюрным, оно обладало значительным функционалом шифрования того времени. По сравнению с другими аналогами того времени (например, «HP-41C») оно имело достаточный объём памяти, что позволяло применять различные алгоритмы перестановок и замены. В дополнении, можно было подключить два периферийных устройства: магнитная лента и принтер.

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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