《现代密码学》第五讲流密码（一）上讲内容回顾⏹分组密码定义（分组填充）⏹分组密码的发展历史（Shannon DES AES。

）⏹保密系统的安全性分析及分组密码的攻击（主动/被动唯密文/已知明（密）文/选择明（密）文/自适应选择明（密）文）⏹数据加密标准（DES）算法介绍⏹高级加密标准（AES）算法介绍⏹中国无限局域网标准（SMS4）算法介绍⏹分组密码算法的运行模式本章主要内容⏹流密码（序列密码）的思想起源⏹流密码技术的发展及分类⏹基于移位寄存器的流密码算法⏹其它流密码算法⏹Estream推荐流密码算法⏹软件算法⏹硬件算法密钥流生成器种子密钥明文m1k1c1m2k2c2加密过程密钥流生成器种子密钥密文c1k1m1c2k2m2解密过程⏹设明文为m=m1m2… m i∈GF(2), i>0⏹设密钥为k=k1k2… k i∈GF(2), i>0⏹设密文为c=c1c2… c i∈GF(2), i>0⏹则加密变换为c i＝m i+ k i(mod 2) i>0⏹则解密变换为m i＝c i+ k i(mod 2) i>0⏹思想起源：20世纪20年代的Vernam 体制，即“一次一密”密码体制。

香农利用信息论证明“一次一密”密码体制在理论上不可破译⏹由有限的种子密钥生成无限长的随机密钥序列⏹流密码研究内容——设计安全高效的伪随机序列发生器密钥流生成、存储和分发困难随机序列计算机无法实现评测标准：线性复杂度高；周期大Golomb伪随机性测试周期为r的0－1序列的随机性公设如下：⏹r是奇数，则0－1序列{si}的一个周期内0的个数比1的个数多一个或少一个；若r是偶数，则0的个数与1的个数相等.⏹在长度为r的周期内，长为1的游程的个数为游程总数的1/2，长为2的游程的个数占游程总数的1/22,…, 长为c的游程的个数占总游程的1/2c.而且对于任意长度，0的游程个数和1的游程个数相等.例：0110111101中，4个游程长度为1，1个游程长度为2，1个游程长度为4异相自相关函数是一个常数.设一个周期为r的序列a1, a2,…, a r, a r+1, a r+2,…，将序列平移T位得到另外一个序列a T, a T+1,… a r+T, a r+T+1,…，若a i= a i+T, 则称对应第i位相等。

设两个序列相同位的个数为n，不同位的个数为d，则R(T)=(n-d)/r为自相关函数流密码技术的发展及分类⏹序列密码是世界各国的军事和外交等领域中使用的主要密码体制之一⏹2000年1月欧洲启动的NESSIE 工程中，流密码算法的设计与分析也列上了公开征集评测的日程；6个流密码算法（Leviathan 、UIi 一128、BMGL 、SOBER —t32、SOBER —tl 、SNOW ）进入了第二阶段评估，但是因为他们都不符合NESSIE 的征集准则而最终全部落选⏹2003年3月，日本政府的密码研究与评估委员会（CRYPTREC ）推荐了三个流密码算法：MUGI 、MULTI-S01和RC4-128.⏹ECRYPT 是欧洲FP6下的IST 基金支持的一个为期四年的项目，该项目启动于2004年2月，STVL （Symmetric techniques virtual lab ）正在进行流密码算法的公开征集评估活动.征集活动到2005 年4月29 日结束，征集到了34个流密码算法.2007年4月开始进入第三轮评估，16个算法进入第三轮评估./stream/phase3list.html2008年4月8个算法成为推荐算法.2008年8月更新为7个推荐算法.Profile 1 (SW)Profile 2 (HW)CryptMT (CryptMT Version 3)DECIM (DECIM v2 and DECIM-128)Dragon Edon80HC (HC-128 and HC-256)F-FCSR (F-FCSR-H v2 and F-FCSR-16)LEX (LEX-128, LEX-192 and LEX-256)Grain (Grain v1 and Grain-128)NLS (NLSv2, encryption-only)MICKEY (MICKEY 2.0 and MICKEY-128 2.0)Rabbit Moustique Salsa20Pomaranch (Pomaranch Version 3)SOSEMANUK Trivium⏹在同步流密码中，密（明）文符号是独立的，一个错误传输只会影响一个符号，不影响后面的符号。

⏹缺点：一旦接收端和发送端的种子密钥和内部状态不同步，解密就会失败，两者必须立即借助外界手段重新建立同步。

k c ik 密钥流生成器密钥流生成器信道c iz i m iz im iE (z i ,m i )E (z i ,m i )自同步流密码的优点是即使接收端和发送端不同步，只要接收端能连续地正确地接受到n 个密文符号，就能重新建立同步。

因此自同步流密码具有有限的差错传播，且分析较同步流密码的分析困难得多k c ik 密钥流生成器密钥流生成器信道c iz im iz im iE (z i ,m i )E (z i ,m i )流密码技术的发展及分类思考：假设j=n/4,n为分组长度对于DES，n=64, j=16；对AES，n=128,j=32 CFB模式为（）流密码？OFB模式为（）流密码？CTR模式为（）流密码？自同步、同步、同步⏹挪威政府的首席密码学家Ernst Selmer 于1965年提出了移位寄存器理论，它是序列密码中研究随机密钥流的主要数学工具.⏹移位寄存器是指有n 个寄存器（称为n-级移位寄存器）r 1,r 2,…,r n 从右到左排列，每个寄存器中能存放1位二进制数，所有寄存器中的数可以统一向右（或向左）移动1位，称为进动1拍. 即r 1的值(b 1)右移1位后输出，然后r 2的值(b 2)送r 1, r 3的值(b 3)送r 2,……最后，r n 的值(b n )送r n-1.b nr n b n-1r n-1……b 2r 2b 1r 1⏹反馈移位寄存器(feedback shift register,FSR)是由n 位的寄存器和反馈函数(feedback function)组成，如下图所示，n 位的寄存器中的初始值称为移位寄存器的初态.⏹工作原理：移位寄存器中所有位的值右移1位，最右边的一个寄存器移出的值是输出位，最左边一个寄存器的值由反馈函数的输出值填充，此过程称为进动1拍. 反馈函数f 是n 个变元(b 1,b 2,…,b n )的布尔函数.移位寄存器根据需要不断地进动m 拍，便有m 位的输出，形成输出序列a 1,a 2,…,a m .b n r n b n-1r n-1……b 2r 2b 1r 1输出位o i反馈函数f⏹线性反馈移位寄存器LFSR(linear feedback shift register）的反馈函数为线性函数⏹作为密钥流的序列{a i}的周期一定要大否则密钥流的空间太小，利用穷举搜索可以得到密钥流{a i}⏹n级LFSR输出的序列的周期r不依赖于寄存器的初始值，而依赖于特征多项式p(x)定义设n 级LFSR 的输出序列{a i }满足递推关系这种递推关系可用一个一元高次多项式表示，称这个多项式为LFSR 的特征多项式。

n n 11n 21(1).k n k n k k a c a c a c a k ++--+-=⊕⊕⊕≥ 111()1n n n n f x c x c xc x --=++++定义设是上的多项式，使的最小的n 称为的周期或者阶。

例：为上多项式，以它为特征多项式的LFSR 的输出序列周期。

()f x ()f x (2)GF ()|(1)n f x x -432()1f x x x x x =++++(2)GF 5432(1)(1)(1)()(1)x x x x x x f x x -=++++-=-所以f(x)的周期为5()|1,5nf x x n -<解：对应的n 级LFSR 的反馈函数为10001100…f(b 1,b 2,b 3,b 4状态 输出位000111000011000011000011100011100001100b 4b 3b 2b 1)输出序列的周期为5⏹n级LFSR输出的序列的最大周期是2n-1为什么？⏹LFSR的寄存器状态遍历2n-1个非零状态⏹初始状态为全零，则输出序列为0的循环定义当LFSR的寄存器状态遍历2n-1个非零状态时，序列的周期达到最大2n-1，这种序列被称为m序列。

定义若n次不可约多项式f(x)的阶为2n-1，则称f(x)为n次本原多项式。

定理{a i}是周期为2n 1的m-序列的充要条件是其特征多项式f(x)为n阶本原多项式一个3-级的反馈移位寄存器，反馈函数f(x)= b 3⊕b 1，初态为100，输出序列？3()1f x x x =++742342(1)(1)(1)(1)()x x x x x x x x x f x -=+++++=+++ ()|1,7n f x x n -<所以f(x)的周期为7生成多项式为初态为100放入寄存器，输出序列情况如下b3b 2b 100111010011101…f(b 1,b 2,b 3)=b 1⊕b 3状态 输出位10001100111101111011010000111000输出序列的周期为7流密码的攻击攻击目的：确定整个密钥流{k i}攻击手段：惟密文已知明文选择明/密文自适应选择明/密文1 若LFSR 的反馈函数已知，破译者已知连续n 位明密文对和则可以推导出n 比特密钥流，继而由反馈函数得到整个密钥流{k i }2 已知明文攻击下，假设破译者已知了2n 位明密文对，，则可确定一段2n 位长的密钥序列，由此可以完全确定n 级反馈多项式的系数。

},,,{221n m m m M =},,,{21n m m m },,,{21n c c c },,,{221n c c c C =i i i c m k ⊕=},,,{21n k k k },,,{221n k k k K =n 个线性方程包含n 个未知数：b 1,b 2,...,b n ，所以可惟一解出b i (i=0，1，…，n )从而可确定该线性反馈移位寄存器接下来的状态，也就能够得到余下的密钥序列。

11211223111211211n n n n n n n n n n n n n n k k b k b k b k k b k b k b k k b k b k b +-+-++--=+++⎧⎪=+++⎪⎨⎪⎪=+++⎩例：5级线性反馈移位寄存器产生的密钥序列加密得到的明文串为011001111111001，对应的密文串为101101011110011。