Генерация псевдослучайных чисел

В большинстве алгоритмов шифрования используются генераторы ключевой последовательности. Генератор ключевой последовательности выдает набор битов, который выглядит случайными, но в действительности является детерминированным и может быть в точности воспроизведен на стороне получателя. Чем больше генерируемый поток похож на случайный, тем больше времени потребуется криптоаналитику для взлома шифра.

Для того чтобы у принимающей стороны была возможность дешифровать сообщение, необходимо передать только инициализирующую генератор псевдослучайных чисел переменную. Существует несколько методов генерации псевдослучайных чисел, среди них – линейно конгруэнтный метод, алгоритм которого был предложен Д. Х. Лемером в 1948 году.

Рекуррентная формула выглядит следующим образом:

(10)

Период порождаемой последовательности не превышает m. Естественно, что от выбора параметров a, c, m и значения первого члена x ₀ существенно зависят основные свойства порождаемой последовательности. Длина периода будет максимальной (равной m) только в том случае, когда [7]:

· НОД(c, m) = 1 (т.е. c и m взаимно просты);

· a – 1 кратно всем простым делителям m;

· если m кратно 4, то и .

Зная первые четыре генерируемых числа в последовательности криптоаналитик может составить систему из четырёх уравнений и получить параметры a, c и m. Использование сложных функций в качестве параметров a и с усложняет работу алгоритма, но исключает возможность раскрытия значения параметров путём простого составления системы из четырёх уравнений.

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