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

Генератор Макларена — Марсальи (Шаблон:Lang-en2) — криптографически стойкий генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был предложен в 1965 году американскими математиками Шаблон:Нп3, и Дональдом Маклареном. В своих работах Дональд Кнут называет генератор Макларена — Марсальи «генератор М»Шаблон:Sfn.

Описание

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

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

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

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

Данный метод генерации позволяет получать большие периоды, если последовательности $<X_n>$ и $<Y_n>$ имеют взаимно простые периоды. И даже если длина периода несущественна, соседние элементы последовательности почти не коррелируют друг с другомШаблон:Sfn.

Метод серединных квадратов гораздо хуже, чем данный метод, так как у последнего достаточная случайность последовательностей $<X_n>$ и $<Y_n>$, которые не могут вырождатьсяШаблон:Sfn.

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

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

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

Пример

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

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

Недостатки

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

Первый недостаток связан с неизменностью набора вариантов вывода генератора, так как таблица $V$ состоит лишь из значений последовательности $X_n$, которые постоянные и в таблицу $V$ попадают случайным образом, заданным $Y_n$. В результате, $X_n$ можно криптоанализировать вне зависимости от $Y_n$Шаблон:Sfn.

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

Третий недостаток заключается в том, что первоначальное содержание матрицы $V$ напрямую заменяется на элементы $X_n$ в соответствии с $Y_n$, то есть предыдущее содержание матрицы $V$ никак не влияет на текущее, нет обратной связи. Таким образом, если у злоумышленника имеется список значений выводимых генератором, то это является ключом к разгадке первоначального состояния таблицы $V$Шаблон:Sfn.

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

Применение

CSI-10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Атака

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга