Линейные конгруэнтные генераторы


Линейными конгруэнтными генераторамиявляются генераторы следующей формы

Xn= (aXn-1 + b) mod m

в которых Xn- это n-ый член последовательности, а Xn-1 - предыдущий член последовательности. Переменные a, b и m - постоянные: a- множитель, b - инкремент, и m - модуль. Ключом, или затравкой, служит значение X0.

Период такого генератора не больше, чем m. Если a, b и m выбраны правильно, то генератор будет генератором с максимальным периодом (иногда называемым максимальной длиной), и его период будет равен m. (Например, bдолжно быть взаимно простым с m.) Подробное описание выбора констант для получения максимального периода можно найти в [863, 942]. Еще одной хорошей статьей по линейным конгруэнтным генераторам и их теории является [1446].

В Табл. 16-1, взятой из [1272,], перечисляются хорошие константы линейных конгруэнтных генераторов. Все они обеспечивают генераторы с максимальным периодом и, что даже более важно, удовлетворяют спектральному тесту на случайность для размерностей 2, 3, 4, 5 и 6 [385, 863]. Таблица организована по максимальному произведению, которое не вызывает переполнения в слове указанной длины.

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

К несчастью линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предсказуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds) [1294, 1295, 1296], а затем Джоан Бояр (Joan Boyar) [1251]. Ей удалось также вскрыть квадратичные генераторы:

Xn= (aXn-12 + bXn-1 + c) mod m

и кубические генераторы:

Xn= (aXn-13 + bXn-12 + c Xn-1+ d) mod m

Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального генератора [923, 899, 900]. Были взломаны и усеченные линейные конгруэнтные генераторы [581, 705, 580], и усеченные линейные конгруэнтные генераторы с неизвестными параметрами [1500, 212]. Таким образом была доказана бесполезность конгруэнтных генераторов для криптографии.

Табл. 16-1.
Константы для линейных конгруэнтных генераторов

Переполняется при a b m
220
221
222
223
 
 
224
 
 
 
225
 
 
 
 
 
226
 
 
227
 
 
 
228
 
 
229
 
 
 
 
 
 
230
 
 
231
 
 
232
 
233
234
 
235

 

Однако, линейные конгруэнтные генераторы сохраняют свою полезность для некриптографических приложений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестах демонстрируют хорошие статистические характеристики. Важную информацию о линейных конгруэнтных генераторах и их теории можно найти в [942].



Дата добавления: 2021-01-26; просмотров: 355;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.