16.1 Линейные конгруэнтные генераторы
Линейными конгруэнтными генераторамиявляютсягенераторы следующей формы
Хп = (аХпЛ + Ъ) mod m
в которых Х„ - это й-ый член последовательности, аХ„л - предыдущий член последовательности. Переменные a, bum - постоянные: а - множитель, Ъ - инкремент,и т - модуль. Ключом, или затравкой, служит значение Х0.
Период такого генератора не больше, чем т. Если a, bum выбраны правильно, то генератор будет генератором с максимальным периодом(иногда называемым максимальной длиной), и его период будет равен т. (Например, Ъ должно быть взаимно простым с т.) Подробное описание выбора констант для получения максимального периода можно найти в [863, 942]. Еще одной хорошей статьей по линейным конгруэнтным генераторам и их теории является [1446].
В 15-й, взятой из [1272,], перечисляются хорошие константы линейных конгруэнтных генераторов . Все они обеспечивают генераторы с максимальным периодом и, что даже более важно, удовлетворяют спектральному тесту на случайность для размерностей 2, 3, 4, 5 и 6 [385, 863]. Таблица организована по максимальному произведению, которое не вызывает переполнения в слове указанной длины .
Преимуществом линейных конгруэнтных генераторов является их быстрота за счет малого количества операций на бит.
К несчастью линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предск а-зуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds) [1294, 1295, 1296], а затем Джоан Бояр (Joan Boyar) [1251]. Ей удалось также вскрыть квадратичные генераторы :
Хп = (аХп.,2 + ЬХп.,+с)тойт
и кубические генераторы:
Хп = (aXj + ЪХпЛг + с ХпЛ+ d) mod m
Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального ген е-ратора [923, 899, 900]. Были взломаны и усеченные линейные конгруэнтные генераторы [581, 705, 580], и усеченные линейные конгруэнтные генераторы с неизвестными параметрами [1500, 212]. Таким образом была доказана бесполезность конгруэнтных генераторов для криптографии.