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

• генерируемая последовательность должна иметь большой период;
• генерируемая последовательность не должна иметь скрытых периодичностей;
• генерируемая последовательность должна иметь равномерный спектр.

Одними из наиболее часто используемых являются варианты схемы, предложенной Д.Х.Лемером (линейный конгруэнтный генератор):

G_n+1 = (a*G_n+c) mod m

Сложность использования этого генератора состоит в выборе хороших значений G₀, a, c и m. Например, в государственном стандарте РФ ГОСТ Р34.10-94 "Процедуры выработки и проверки цифровой подписи на базе асимметричных криптографических алгоритмов" полу-чение псевдослучайных чисел осуществляется с использованием линейного конгруэнтного датчика:

G_n+1 = (19381*G_n+c) mod 2¹⁶

Пользователь выбирает начальное значение G₀ и c, причем c - нечетное. Вообще говоря, существует ряд правил для выбора коэффициентов:

• число m должно быть достаточно велико;
• при использовании двоичной системы a выбирается таким образом, что a mod 8=5;
• число c должно быть нечетным. Желательно также соблюдать соотношение c/m = 0.5-(1/6)*sqrt(3);

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

Бинарная псевдослучайная последовательность периода 2ⁿ-1 образуется при делении некоторого начального значения на неприводимый многочлен степени n, который называется порождающим многочленом. Шаг деления состоит в сдвиге начального значения влево на один бит (умножение на 2) и установке крайнего правого бита в значение суммы бит по модулю 2 (XOR), умноженных на соответствующие коэффициенты порождающего многочлена.

var
 rg:byte;
 counter,carry,c7,c3,c0:byte;
begin
 rg:=1;
 for counter:=1 to 128 do
 begin
 if (rg AND 128)<>0
 then c7:=1
 else c7:=0;
 if (rg AND 8)<>0
 then c3:=1
 else c3:=0;
 if (rg AND 1)<>0
 then c0:=1
 else c0:=0;
 Carry:=c7 XOR c3 XOR c0;
 rg:=rg*2 OR Carry;
 end;
end;

Приведенный алгоритм реализует деление начального значения на порождающий многочлен x⁷+x³+1 и генерирует последовательность с периодом 127. Алгоритм реализован на Delphi, но для практического использования предпочтительным представляется ассемблерный вариант.

Несколько слов о неприводимых многочленах. Их нахождение производится путем подбора и требует больших вычислительных мощностей. Несомненно, криптографические ведомства развитых стран ведут работу в этой области, но результаты не попадают в открытую печать. Известен неприводимый многочлен x⁶¹+x³+1 (период генерируемой последовательности 2 305 843 009 213 693 951), по многочленам больших степеней информацию обнаружить не удалось. Опубликованы таблицы неприводимых многочленов, например, для сте-пеней <=33. Для получения последовательностей больших периодов можно использовать несколько параллельно работающих генераторов.

А.В.БЫЧЕНКОВ,
[email protected]