基于移位寄存器的流密码算法

1 若LFSR的反馈函数已知，破译者已知连续n位明密文对{m1,m2,?,mn}和{c1,c2,?,cn}则可以推导出n比特密钥流{k1,k2,?,kn}，ki?mi?ci继而由反馈函数得到整个密钥流{ki}

2 已知明文攻击下，假设破译者已知了2n位明密文

C?{c1,c2,?,c2n}，则可确定对M?{m1,m2,?,m2n}，

一段2n位长的密钥序列K?{k1,k2,?,k2n}，由此可以完全确定n级反馈多项式的系数。

基于移位寄存器的流密码算法

?kn?1?k1bn?k2bn?1???knb1?k?kb?kb???kb?n?22n3n?1n?11?????k2n?knbn?kn?1bn?1???k2n?1b1n个线性方程包含n个未知数：b1,b2,...,bn，所以可惟一解出bi (i=0，1，…，n)

从而可确定该线性反馈移位寄存器接下来的状态，也就能够得到余下的密钥序列。

基于移位寄存器的流密码算法

例：5级线性反馈移位寄存器产生的密钥序列加密得到的明文串为011001111111001，对应的密文串为101101011110011。求该LFSR的反馈函数。

解：由明密文得相应的密钥序列为110100100001010；

利用前10个密钥序列比特建立如下方程：

基于移位寄存器的流密码算法

?k6??k1????k7??k2?k???k?8??3?k9??k4?k??k?10??5k2k3k4k5k6k3k4k5k6k7k4k5k6k7k8k5??a5??0??1??????k6??a4??1??1k7??a3???0???0??????k8??a2??0??1??????k9??a1??0??0?15????a4??1??a3???0????a2??1?a???1??0a5ki??a2k反馈函数为a??1?3?ki?ki?3?a5??1101ki0?0???5?i?010100001010?0?1??0??0????????a4??0??1??0???a3???0????????a2?的级数未知？?1??0?若LFSR?a????0?如何求其反馈函数？0??1????1010??a5????0100??a4????a10013???0010??a2??a??0100??1?