Принципы использования генераторов псевдослучайных чисел при потоковом шифровании

    Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от методов математической статистики и имитационного моделирования до криптографии. При этом от качества используемых генераторов псевдослучайных чисел (ГПСЧ) напрямую зависит качество получаемых результатов.

    ГПСЧ могут использоваться в качестве генераторов ключей в поточных шифрах. Целью использования генераторов псевдослучайных чисел является получение "бесконечного" ключевого слова, располагая относительно малой длиной самого ключа. Генератор псевдослучайных чисел создает последовательность битов, похожую на случайную. На самом деле, конечно же, такие последовательности вычисляются по определенным правилам и не являются случайными, поэтому они могут быть абсолютно точно воспроизведены как на передающей, так и на принимающей стороне. Последовательность ключевых символов, использующаяся при шифровании, должна быть не только достаточно длинной.     Если генератор ключей при каждом включении создает одну и ту же последовательность битов, то взломать такую систему также будет возможно.     Следовательно, выходгенератора потока ключей должен быть функцией ключа. В этом случае расшифровать и прочитать сообщения можно будет только с использованием того же ключа, который использовался при шифровании.

    Для использования в криптографических целях генератор псевдослучайных чисел должен обладать следующими свойствами:

1.              период последовательности должен быть очень большой;

2.              порождаемая последовательность должна быть "почти" неотличима от действительно случайной;

3.              вероятности порождения различных значений должны быть в точности равны;

4.              для того, чтобы только законный получатель мог расшифровать сообщение, следует при получении потока ключевых битов k_i использовать и учитывать некоторый секретный ключ, причем вычисление числа k_i+1 по известным предыдущим элементам последовательности k_i без знания ключа должно быть трудной задачей.

    При наличии указанных свойств последовательности псевдослучайных чисел могут быть использованы в поточных шифрах.

Линейный конгруэнтный генератор псевдослучайных чисел

Генераторы псевдослучайных чисел могут работать по разным алгоритмам. Одним из простейших генераторов является так называемый линейный конгруэнтный генератор, который для вычисления очередного числа k_i использует формулу:

ki=(a*k_i-1+b)mod c,

где а, b, с — некоторые константы, a k_i-1 — предыдущее псевдослучайное число. Для получения k₁ задается начальное значение k₀. Возьмем в качестве примера a=5, b=3, c=11 и пусть k₀= 1. В этом случае мы сможем по приведенной выше формуле получать значения от 0 до 10 (так как с = 11). Вычислим несколько элементов последовательности:

k1 = (5 * 1 + 3) mod 11 = 8;

k2 = (5 * 8 + 3) mod 11 = 10;

k3 = (5 * 10 + 3) mod 11 = 9;

k4 = (5 * 9 + 3) mod 11 = 4;

k5 = (5 * 4 + 3) mod 11 = 1.

Полученные значения (8, 10, 9, 4, 1) выглядят похожими на случайные числа. Однако следующее значение k₆ будет снова равно 8:

k6 = (5 * 1 + 3) mod 11 = 8,

а значения k₇ и k₈ будут равны 10 и 9 соответственно:

k₇ = (5 * 8 + 3) mod 11 = 10; 

k₈= (5 * 10 + 3) mod 11 = 9.

    Выходит, наш генератор псевдослучайных чисел повторяется, порождая периодически числа 8, 10, 9, 4, 1. К сожалению, это свойство характерно для всех линейных конгруэнтных генераторов. Изменяя значения основных параметров a, b и c, можно влиять на длину периода и на сами порождаемые значения k_i. Так, например, увеличение числа с в общем случае ведет к увеличению периода. Если параметры a, b и c выбраны правильно, то генератор будет порождать случайные числа с максимальным периодом, равным c. При программной реализации значение с обычно устанавливается равным 2^b-1 или 2^b, где b — длина слова ЭВМ в битах.

    Достоинством линейных конгруэнтных генераторов псевдослучайных чисел является их простота и высокая скорость получения псевдослучайных значений. Линейные конгруэнтные генераторы находят применение при решении задач моделирования и математической статистики, однако в криптографических целях их нельзя рекомендовать к использованию, так как специалисты по криптоанализу научились восстанавливать всю последовательность ПСЧ по нескольким значениям. Например, предположим, что противник может определить значения k₀, k₁, k₂, k₃. Тогда:

k₁=(a*k₀+b) mod c

k₂=(a*k₁+b) mod c

k₃=(a*k₂+b) mod c

Решив систему из этих трех уравнений, можно найти a, b и c.

    Для получения псевдослучайных чисел предлагалось использовать также квадратичные и кубические генераторы:

    Однако такие генераторы тоже оказались непригодными для целей криптографии по той же самой причине "предсказуемости".