Информатика и выч. техника \ Криптографические методы защиты информации

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

Страницы работы

45 страниц (Word-файл)

Скачать файл

Фрагмент текста работы

обозначим через (L_k , f⁽^k)(x)) регистр сдвига минимальной длины, генерирующий a₁,…, a_k. Примем за предположение индукции, что

L_k=max[L_k_-1, k-L_k_-1], k=1,…,r-1 ,

каждый раз, когда f⁽^k) (x) ≠f⁽^k-1)(x). Это, очевидно, верно для k=0, если a₁отличен от нуля, поскольку L₀=0 и L₁ =1. В более общем случае, если а_i-первый ненулевой элемент в заданной последовательности, то L_i_-1=0 и L_i =i . Тогда предположение индукции относится к индукции k=i. Значение k в последней итерации, приведшей к изменению длины, будем обозначать через m. Последнее означает, что при завершении (r-1)-й итерации m является целым числом, таким, что

L_r_-1=L_m>L_m_-1.

Теперь имеет место следующее равенство:

a₁+ ^(r-1)a_j-i=^(r-1)a_j-i=

Если =0, то регистр (L_r_-1,f^(-1)(x)) также генерирует первые r символов, и таким образом,

L_r=L_r-1 и f^(r)(x) = f^(r-1)(x).

Если ≠0, то необходимо построить новый регистр сдвига. Поскольку изменение длины регистра сдвига произошло при k=m. Следовательно,

a_i+_i^(m-1)a_j-i=

и по предложению индукции

L_r_-1=L_m=max [L_m_-1,m-L_m_-1]=m-L_m_-1,

поскольку L_m>L_m_-1. Новый многочлен :

f^(r)(x)=f^(r-1)(x)-^-1x^r-mf^(m-1)(x)

и пусть L_r=deg f⁽^r)(x). В этом случае поскольку deg f⁽^r-1)(x)≤L_r_-1 и deg[x^r^-^mf⁽^m-1)(x)]≤r-m+L_m_-1, то

L_r≤max [L_r_-1,r-m+L_m_-1] ≤max[L_r_-1,r-L_r_-1].

Из теоремы 1 при условии, что (L_r,f⁽^r)(x)) генерирует a₁,…,a_r, следует, что L_r=max [L_r_-1, r-L_r_-1]. Осталось только доказать, что регистр сдвига (L_r,f⁽^r)(x)) генерирует требуемую последовательность. Доказывается это непосредственным вычислением разности между a_jи сигналом на выходе обратной связи регистра сдвига:

a_j-(-_i^(r)a_j-i)=a_i+_i^(r-1)a_j-i-^-1[a_i-r+m+_i^(m-1)a_i-r+m-i]=

Регистр (L_r, f⁽ⁿ⁾(x)) генерирует a₁,…,a_r. В частности, (L_n, f⁽ⁿ⁾(x)) генерирует a₁,…,a_n и теорема доказана.

Теорема 3. (Алгоритм Берлекэмпа-Месси)

Пусть заданы a₁,…,a_n из некоторого поля, и пусть при начальных условиях f⁽⁰⁾(x)=1, t⁽⁰⁾(x) =1 и L₀=0 выполняются следующие рекуррентные равенства, используемые для вычисления f⁽ⁿ⁾(x):

=_i^(r-1)a_r-1 ,

L_r=б_r(r-L_r-1)+(1- б_r)L_r,

r =1,…, 2n, где б_r =1, если одновременно ≠0 и 2L_r_-1≤r-1, и б_r=0 в противном случае. Тогда f⁽²^r)(x) является многочленом наименьшей степени, коэффициенты которого удовлетворяют равенствам f₀⁽²^r)=1 и a_r+_i⁽²^r)a_r_-1 =0, r=L₂_r+1,…, 2r. Доказательство следует из теоремы 2.

В этой теореме может обращаться в нуль, но только в том случае, когда б_r=0. Положим тогда по определению ^-1 б_r =0. Блок-схема алгоритма Берлекэмпа-Месси приведена на рисунке 4. На r-м шаге указанный алгоритм содержит число умножений, равное примерно удвоенной степени многочлена f⁽^r)(x). Степень многочлена f⁽^r)(x) равна примерно r/2, и всего имеется 2n итераций, так что всего алгоритм содержит примерно 2n²= умножений и примерно такое же число сложений. Можно сказать, что порядок числа умножений в алгоритме Берлекэмпа-Месси равен n², или формально , O(n²).

Задание на лабораторную работу

Реализовать алгоритм Берлекэмпа –Месси на произвольных значениях.

Пример лабораторной работы

Лабораторная работа выполнена на Mapple 13.

> Berlekamp(x^31-1,x)mod 2;

> alias(a=RootOf(x^5+x^4+x^3+x^2+1)mod 2);

> for i from 0 to 30 do y[i]:= Rem(x^i,x^5+x^4+x^3+x^2+1,x) mod 2 od;

> n:=31;#длина кода

> k:=21;d:=11;#число информационных символов и расстояние Хемминга

> #генераторный полином

> g1:=(x-a)*(x-a^2)*(x-a^3)*(x-a^4)*(x-a^5)*(x-a^6)*(x-a^7)*(x-a^8)*(x-a^9)*(x-a^10);

> g2:= expand(g1)mod 2;#умножение

> g3:= collect (g2,x)mod 2;#вычисление коэффициентов при x

> g4:= simplify (g3)mod 2;#раскрытие скобок

> g5:= collect (g4,x)mod 2;#вычисление коэффициентов

> g:=collect(simplify (g5),x)mod 2;

> m:=m0+x*m1+x^2*m2+x^3*m3+x^4*m4+x^5*m5;#общий вид сообщения

> m0:=a^3;m1:=a^2;m2:=a;m3:=a^4;m4:=a^2;m5:=a;#произвольные коэффициенты

> m;

> c:=m*g5;#получение кодового слова

> c1:= expand (c)mod 2;

> c2:= simplify (c1)mod 2;

> c3:= collect (c2,x) mod 2;

> sort (c3);

> for i from 0 to 30 do v[i]:=(x-a^(i)) od;

> for i from 0 to 30 do R[i]:=Quo(x^31-1,v[i],x)mod 2;r[i]:=Rem(R[i],v[i],x)mod 2 od;#строим вспомогательные полиномы для базиса

> #Базис для преобразования Фурье.

> for i from 0 to 30 do B[i]:=Quo(R[i],r[i],x)mod 2 od;

> #Преобразование Фурье от принятого кодового слова.

> for i from 0 to 30 do f[i]:=Rem (c,v[i],x)mod 2 od;

> #Обратное преобразование Фурье.С-кодовое слово

> C:=(f[0]*B[0]+f[1]*B[1]+f[2]*B[2]+f[3]*B[3]+f[4]*B[4]+f[5]*B[5]+f[6]*B[6]+f[7]*B[7]+f[8]*B[8]+f[9]*B[9]+f[10]*B[10]+f[11]*B[11]+f[12]*B[12]+f[13]*B[13]+f[14]*B[14]+f[15]*B[15]+f[16]*B[16]+f[17]*B[17]+f[18]*B[18]+f[19]*B[19]+f[20]*B[20]+f[21]*B[21]+f[22]*B[22]+f[23]*B[23]+f[24]*B[24]+f[25]*B[25]+f[26]*B[26]+f[27]*B[27]+f[28]*B[28]+f[29]*B[29]+f[30]*B[30])mod 2;

> C1:=simplify (C)mod 2;

> C2:=collect (C1,x)mod 2;

> C3:=(C2-c)mod 2;

> simplify (C3)mod 2;

> c;

> c3;

> E:=(a^4*x^2+a^5*x^5+a^6*x^6+a^2*x^7+a^3*x^9);#набор ошибок

> b:=(c3+E)mod 2;#принятая последоватнльность

> #Преобразование Фурье в принятой последовательности.

> for i from 0 to 30 do f[i]:=Rem (b,v[i],x)mod 2 od;

> #синдром(полином, с коэффициентами относящимися к корням генераторного полинома

> S:=(f[1]+f[2]*x+f[3]*x^2+f[4]*x^3+f[5]*x^4+f[6]*x^5+f[7]*x^6+f[8]*x^7+f[9]*x^8+f[10]*x^9);

> T:=(x^10);#количество подряд идущих нулей

> #Алгоритм Евклида.частное от деления Quo,остаток от деления Rem

> q[1]:= Quo (S,T,x)mod 2;p[1]:=Rem(S,T,x)mod 2;

> q[2]:= Quo (T,p[1],x)mod 2;p[2]:=Rem(T,p[1],x)mod 2;

> for i from 1 to 4 do q[i+2]:= Quo (p[i],p[i+1],x)mod 2; p[i+2]:=Rem(p[i],p[i+1],x)mod 2 od;

> Q[0]:=0;Q[1]:=(1);for i from 0 to 4 do Q[i+2]:=collect(simplify((q[i+2]*Q[i+1]+Q[i])),x) od;

> coeff (Q[6],x,5);#коэффициенты при x^5

> #Ошибки.

> Qn:=Quo (Q[6],coeff (Q[6],x,5),x)mod 2;

> Berlekamp (Qn,x,a)mod 2;

> i:=Rem ((S)*Qn,T,x)mod 2;

> u:=Quo (i*(x^31-1),Qn,x) mod 2;

> H1:=sort(collect (u,x)mod 2);

> for i from 0 to 30 do f[i]:=Rem (E,v[i],x)mod 2 od;

> H12:=simplify((coeff(H1,x,0)*B[1]+coeff(H1,x,1)*B[2]+coeff(H1,x,2)*B[3]+coeff(H1,x,3)*B[4]+coeff(H1,x,4)*B[5]+coeff(H1,x,5)*B[6]+coeff(H1,x,6)*B[7]+coeff(H1,x,7)*B[8]+coeff(H1,x,8)*B[9]+coeff(H1,x,9)*B[10]+coeff(H1,x,10)*B[11]+coeff(H1,x,11)*B[12]+coeff(H1,x,12)*B[13]+coeff(H1,x,13)*B[14]+coeff(H1,x,14)*B[15]+coeff(H1,x,15)*B[16]+coeff(H1,x,16)*B[17]+coeff(H1,x,17)*B[18]+coeff(H1,x,18)*B[19]+coeff(H1,x,19)*B[20]+coeff(H1,x,20)*B[21]+coeff(H1,x,21)*B[22]+coeff(H1,x,22)*B[23]+coeff(H1,x,23)*B[24]+coeff(H1,x,24)*B[25]+coeff(H1,x,25)*B[26]+coeff(H1,x,26)*B[27]+coeff(H1,x,27)*B[28]+coeff(H1,x,28)*B[29]+coeff(H1,x,29)*B[30]+coeff(H1,x,30)*B[0])mod 2);