ПСП нулей и единиц (гамма).docx
Оценка 4.7

ПСП нулей и единиц (гамма).docx

Оценка 4.7
docx
13.05.2020
ПСП нулей и единиц (гамма).docx
ПСП нулей и единиц (гамма).docx

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

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


×   + C × q


1 + ... + Cm × qi m = 0


(2)


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

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


q+ ... + Cm


× qi -( m-1) + qi -m


(3)


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


1001010 )     1


+ 0 ×


+ 0 × q5 + 1× q 4 + 0 × q3 + 1× q 2 + 0 × q1 + 1× q0 = q 7 + 4


1 =


f (q)


Применение полиномов упрощает рассмотрение операций с ПСП бит. Полином f(q) называют неприводимым, если:

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

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

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

Примеры неприводимых полиномов и соответственно рекуррентных соотношений (3). 3-го порядка:   1 + q + q3 = 0     qi = qi-1 + qi-3

1 + q2 + q3 = 0     qi  = qi-2 + qi-3

 

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

1 + q + q2 + q3 + q4 = 0

 

5- го порядка:     1 + q2 + q3 + q4 + q5 = 0

 

11-го порядка:   1 + q9 + q11 = 0   qi = qi-9 + qi-11

 

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



 

ПСП нулей и единиц (гамма)

ПСП нулей и единиц (гамма)

ПСП бит. Полином f(q) называют неприводимым , если: f(0) = 1 и f(1) = 1 (4)

ПСП бит. Полином f(q) называют неприводимым , если: f(0) = 1 и f(1) = 1 (4)
Скачать файл