- Генератор Макларена
-
Генератор Макларена-Марсальи - генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был предложен в 1965 году американскими математиками (George Marsaglia (англ.)русск., Джорджом Марсалья) и Дональдом Маклареном. В своих работах Дональд Кнут называет генератор Макларена-Марсальи - генератор М[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; {выходная последовательность} out: 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.
В данном исходном коде учтён второй дефект генератора, поэтому превышает число элементов выходной последовательности.
Применение
Генератор Макларена-Марсальи ранее применялся в качестве генератора потока ключей в поточных шифрах. Однако, работы Чарльза Т. Реттера дали понять, что данный генератор не желательно использовать для генерации потока ключей, так как он не обладает достаточной криптостойкостью[5].
Недостатки
По крайней мере, выявлено четыре недостатка в генераторе при использовании его для криптографических целей[1]. Все четыре тесно связаны друг с другом. Первые три недостатка нашёл Чарльз Реттер[5].
Первый недостаток связан с неизменностью набора вариантов вывода генератора, так как таблица состоит лишь из значений последовательности , которые постоянные и в таблицу попадают случайным образом, заданным . В результате, можно криптоанализировать вне зависимости от [5].
Второй дефект обусловлен тем, что среднее число итераций генератора между значением, которое помещено из в , и его появлением в выходной последовательности примерно равно . Поэтому требуется, чтобы превышало число элементов выходной последовательности[5].
Третий недостаток заключается в том, что первоначальное содержание матрицы напрямую заменяется на элементы в соответствии с , то есть предыдущее содержание матрицы никак не влияет на текущее, нет обратной связи. Таким образом, если у злоумышленника имеется список значений выводимых генератором, то это является ключом к разгадке первоначального состояния таблицы [5].
Четвертый недостаток связан с реализацией данного метода. Зачастую генератор осуществляют, используя массивы, хранящие 32-х битные числа. Из-за этого возникает эффект ограничения элементов в последовательности , которые могут быть сохранены в , что является причиной группирования отдельных элементов в , которые чётко различимы[1].
См. также
Примечания
- ↑ 1 2 3 Churchill, 2011
- ↑ 1 2 3 4 5 Knuth, 2000
- ↑ MacLaren
- ↑ Артемкин, 2004
- ↑ 1 2 3 4 5 Charles, 1985
Литература
- Дональд Э. Кнут. Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6
- M. Donald MacLaren, George Marsaglia Uniform Random Number Generators. — Boeing Scientific Research Laboratories, Seatle, Washington.
- 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 A KEY-SEARCH ATTACK ON MACLAREN-MARSAGLIA SYSTEMS // Cryptologia. — 1985. — В. 2. — № 9. — С. 114-130.
- Артемкин Д.Е., Баринов В.В., Овечкин Г.В., Степнов И.М. Основы компьютерного моделирования систем. — М.: Лаборатория Базовых Знаний, 2004. — 152 с. — ISBN 5-93208-162-7
Категории:- Генераторы псевдослучайных чисел
- Случайность
- Криптография
Wikimedia Foundation. 2010.