13-10-2023
Генератор Макларена-Марсальи (MacLaren-Marsaglia) — генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был предложен в 1965 году американскими математиками Джорджом Марсалья (англ.)русск., и Дональдом Маклареном. В своих работах Дональд Кнут называет генератор Макларена-Марсальи — генератор М[1].
Данный генератор псевдослучайных чисел оперирует с тремя объектами: двумя конгруэнтными генераторами, которые порождают последовательности , , и матрицей , состоящей из элементов, обычно . На выходе последовательность [2].
Генератор состоит из четырёх основных стадий[2]:
Последние три стадии могут повторяться необходимое число раз[2].
Данный метод генерации позволяет получать большие периоды, если последовательности и имеют взаимно простые периоды. И даже если длина периода несущественна, соседние элементы последовательности почти не коррелируют друг с другом[2].
Метод серединных квадратов гораздо хуже, чем данный метод, так как у последнего достаточная случайность последовательностей и , которые не могут вырождаться[2].
Вместо двух конгруэнтных генераторов имеет место применять две таблицы случайных чисел[3].
В данном исходном коде на языке программирования Паскаль реализованы основные части генератора Макларена-Марсальи[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.
В данном исходном коде учтён второй дефект генератора, поэтому превышает число элементов выходной последовательности.
По крайней мере, выявлено четыре недостатка в генераторе при использовании его для криптографических целей[1]. Все четыре тесно связаны друг с другом. Первые три недостатка нашёл Чарльз Реттер[5].
Первый недостаток связан с неизменностью набора вариантов вывода генератора, так как таблица состоит лишь из значений последовательности , которые постоянные и в таблицу попадают случайным образом, заданным . В результате, можно криптоанализировать вне зависимости от [5].
Второй дефект обусловлен тем, что среднее число итераций генератора между значением, которое помещено из в , и его появлением в выходной последовательности примерно равно . Поэтому требуется, чтобы превышало число элементов выходной последовательности[5].
Третий недостаток заключается в том, что первоначальное содержание матрицы напрямую заменяется на элементы в соответствии с , то есть предыдущее содержание матрицы никак не влияет на текущее, нет обратной связи. Таким образом, если у злоумышленника имеется список значений выводимых генератором, то это является ключом к разгадке первоначального состояния таблицы [5].
Четвертый недостаток связан с реализацией данного метода. Зачастую генератор осуществляют, используя массивы, хранящие 32-х битные числа. Из-за этого возникает эффект ограничения элементов в последовательности , которые могут быть сохранены в , что является причиной группирования отдельных элементов в , которые чётко различимы[1].
Генератор Макларена — Марсальи в 80-х годах использовали в криптографическом устройстве, название которого «CSI-10». Устройство легко помещалось в кармане пиджака и представляло собой 12-ти символьный дисплей и набор клавиш. Хоть и устройство было миниатюрным, оно обладало значительным функционалом шифрования того времени. По сравнению с другими аналогами того времени (например, «HP-41C») оно имело достаточный объём памяти, что позволяло применять различные алгоритмы перестановок и замены. В дополнении, можно было подключить два периферийных устройства: магнитная лента и принтер[6].
Для запуска работы устройства необходимо было вначале ввести два ключа, каждый из которого инициализировал работу генераторов, которые в совокупности реализовывали метод Макларена — Марсальи. После выводимой на дисплей подсказки, нужно было ввести открытый текст[6].
В связи с тем, что на дисплее помещались всего 12 символов, входные и выходные данные делились на группы символов. В каждой группе могло быть расположено 6 знаков, а максимальное число групп равнялось 72, таким образом, максимальный размер открытого текста равнялся 432 символа[6].
Принцип работы шифрования состоял в перестановке и замене открытого текста на основе генерируемой последовательности генератора Макларена — Марсальи. Производители устройства оставили в тайне подробное описание работы[6].
Научно-исследовательская лаборатория в Data General, которая, в основном, занималась разработкой сетей, состоящих из соединенных друг с другом миникомпьютеров, отметила тот факт, что не стоит надеяться на операционную систему в защите файлов от несанкционированного доступа, просто потому что у большинства пользователь есть физический доступ к некоторым компьютерам. Это послужило причиной развития функции шифрования в файловых системах[7].
В 1980 году начали использовать в файловых системах миникомпьютеров генератор Макларена-Марсальи, как часть криптосистемы. В свою очередь, генератор состоял из двух конгруэнтных генераторов, период генератора значений равнялся , а период генератора указателей на вспомогательную таблицу равнялся . Поскольку эти числа взаимно просты, то период генератора в целом равнялся [7].
Суть шифрования состояла в том, что каждому слову, состоящему из 16-ти бит, ставилось в соответствие слово, генерируемое методом Макларена-Марсальи, и над этими кусочками производилась операция . Таким же образом осуществлялось расшифрование[7].
Однако, в 1984 году Чарльз Т. Реттер провёл исследования и показал, что данная криптосистема не является надёжной. Поэтому изменили данную защиту на криптосистему с использованием DES[7].
Идея объединения надлежащим образом нескольких генераторов псевдослучайных последовательностей для того, чтобы генерировать безопасный поток ключей в поточных шифрах, предлагалась в различных формах. Большинство методов предназначались для создания нелинейных последовательностей, используя линейные генераторы, поскольку линейные последовательности легко обратимы[5].
Однако, алгоритмы данного типа могут быть подвержены атаке на основе сбора статистики, используя подсчёт корреляции между входными генераторами и выходной последовательностью[5].
Это послужило поводом для создания более криптостойкого метода генерации случайных последовательностей. Им оказался генератор Макларена-Марсальи, который также стал применяться в качестве генератора потока ключей в поточных шифрах[5].
Однако, работы Чарльза Т. Реттера дали понять, что данный генератор не желательно использовать для генерации потока ключей, так как он не обладает достаточной криптостойкостью[5].
Чарльз Т. Реттер предложил атаку на систему поточного шифрования с использованием генератора Макларена — Марсальи, основная суть которой состоит в подборе ключа к одному из генераторов, игнорируя значение ключа другого генератора. То есть вначале ищется ключ к генератору значений (на рисунке генератор X), тестируя смещения получающейся последовательности относительно известному потоку ключей. После того, как ключ к генератору значений найден, ищется ключ к генератору указателей (на рисунке генератор Y) для вспомогательной таблицы V[5].
Практика показывает, что число вычислений, требуемое для поиска ключей к паре генераторов, лишь чуть больше, чем число вычислений, требуемое для отдельных генераторов. Поэтому использование генератора Макларена — Марсальи не сильно увеличивает безопасность системы поточного шифрования по сравнению с системой, в которой используется единственный генератор[5].
Генератор Макларена — Марсальи.
