Линейные конгруэнтные генераторы
Линейными конгруэнтными генераторамиявляются генераторы следующей формы
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;