Информационная безопасность / Информационная безопасность2006

Псп нулей и единиц (гамма).

Считается, что «гарантированно» хорошим для криптографии способом генерации является построение гаммы рекуррентным соотношением

(2)

Здесь и ниже обозначено: С и q– двоичные числа {0, 1}, а символом «+» обозначено сложение по модулю два (логическая операцияXOR). Множество полиномов (2) составляет одно из полей Галуа, т.е. поле, над которым определено: сложение – операцияXOR, вычитание – операцияXOR, умножение – операцияAND.

Коэффициенты С₀и С_mобязаны быть равны 1. следовательно, очередное псевдослучайное число вычисляется по ф-ле:

(3)

Последовательность бит, например, байт или слово (два бита) удобно рассматривать как многочлены. Например, байт представляется полиномом 7-й степени, каждый член которого соответствует ненулевому биту в байте:

Применение полиномов упрощает рассмотрение операций с ПСП бит.

Полином f(q) называютнеприводимым, если:

f(0) = 1 иf(1) = 1 (4)

Другими словами, полином m-ой степени неприводим, если он не раскладывается на множители (полиномы) степени нижеm.

ПСП бит, вычисляемая по формуле (3), будет иметь максимальную длину периода, равную 2^m–1, если полином (2) неприводим.

Примеры неприводимых полиномови соответственно рекуррентных соотношений (3).

3-го порядка: 1 + q+q³= 0q_i=q_i_-1+q_i_-3

1 + q²+q³= 0q_i=q_i_-2+q_i_-3

4-го порядка: 1 + q+q⁴= 0

1 + q+q²+q³+q⁴= 0

5-го порядка: 1 + q²+q³+q⁴+q⁵= 0

11-го порядка: 1 + q⁹+q¹¹= 0q_i=q_i_-9+q_i_-11

Заметим, что все неприводимые полиномы имеют нечетное количество членов.

Содержание