Русская Википедия:Генератор Макларена — Марсальи

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Описание

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

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

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

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

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

Метод серединных квадратов гораздо хуже, чем данный метод, так как у последнего достаточная случайность последовательностей <math><X_{n}></math> и <math><Y_{n}></math>, которые не могут вырождатьсяШаблон: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.

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

Недостатки

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

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

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

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

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

Применение

CSI-10

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

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

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

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

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

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

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

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

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

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

Файл:Генератор ММ в поточных шифрах.png
Применение в поточных шифрах

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

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

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

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

Атака

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Генератор_Макларена_—_Марсальи&oldid=9526804