应用密码学-2016-(第11讲)-流密码

应用密码学计算机科学与技术学院温蜜第11讲流密码相关内容主要内容•流密码（序列密码）的思想起源•流密码技术的发展及分类•基于移位寄存器的流密码算法•RC4流密码算法第十一讲流密码的思想起源密钥流生成器种子密钥明文m1k1c1m2k2c2加密过程第十三讲流密码的思想起源密钥流生成器种子密钥密文c1k1m1c2k2m2解密过程第十一讲流密码的思想起源•设明文为m=m1m2…mi∈GF(2),i0•设密钥为k=k1k2…ki∈GF(2),i0•设密文为c=c1c2…ci∈GF(2),i0•则加密变换为ci＝mi+ki(mod2)i0•则解密变换为mi＝ci+ki(mod2)i0第十一讲流密码的思想起源•思想起源：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第十一讲流密码技术的发展及分类•序列密码是世界各国的军事和外交等领域中使用的主要密码体制之一•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（Symmetrictechniquesvirtuallab）正在进行流密码算法的公开征集评估活动.征集活动到2005年4月29日结束，征集到了34个流密码算法.2007年4月开始进入第三轮评估，16个算法进入第三轮评估.年4月8个算法成为推荐算法.2008年8月更新为7个推荐算法.Profile1(SW)Profile2(HW)CryptMT(CryptMTVersion3)DECIM(DECIMv2andDECIM-128)DragonEdon80HC(HC-128andHC-256)F-FCSR(F-FCSR-Hv2andF-FCSR-16)LEX(LEX-128,LEX-192andLEX-256)Grain(Grainv1andGrain-128)NLS(NLSv2,encryption-only)MICKEY(MICKEY2.0andMICKEY-1282.0)RabbitMoustiqueSalsa20Pomaranch(PomaranchVersion3)SOSEMANUKTrivium流密码技术的发展及分类•在同步流密码中，密（明）文符号是独立的，一个错误传输只会影响一个符号，不影响后面的符号。•缺点：一旦接收端和发送端的种子密钥和内部状态不同步，解密就会失败，两者必须立即借助外界手段重新建立同步。kcik密钥流生成器密钥流生成器信道cizimizimiE(zi,mi)E(zi,mi)流密码技术的发展及分类•自同步流密码的优点是即使接收端和发送端不同步，只要接收端能连续地正确地接受到n个密文符号，就能重新建立同步。因此自同步流密码具有有限的差错传播，且分析较同步流密码的分析困难得多kcik密钥流生成器密钥流生成器信道cizimizimiE(zi,mi)E(zi,mi)基于移位寄存器的流密码算法•挪威政府的首席密码学家ErnstSelmer于1965年提出了移位寄存器理论，它是序列密码中研究随机密钥流的主要数学工具.•移位寄存器是指有n个寄存器（称为n-级移位寄存器）r1,r2,…,rn从右到左排列，每个寄存器中能存放1位二进制数，所有寄存器中的数可以统一向右（或向左）移动1位，称为进动1拍.即r1的值(b1)右移1位后输出，然后r2的值(b2)送r1,r3的值(b3)送r2,……最后，rn的值(bn)送rn-1.bnrnbn-1rn-1……b2r2b1r1基于移位寄存器的流密码算法•反馈移位寄存器(feedbackshiftregister,FSR)是由n位的寄存器和反馈函数(feedbackfunction)组成，如下图所示，n位的寄存器中的初始值称为移位寄存器的初态.•工作原理：.反馈函数f是n个变元(b1,b2,…,bn)的布尔函数.移位寄存器根据需要不断地进动m拍，便有m位的输出，形成输出序列a1,a2,…,am.bnrnbn-1rn-1……b2r2b1r1输出位oi反馈函数f基于移位寄存器的流密码算法•线性反馈移位寄存器LFSR(linearfeedbackshiftregister）的反馈函数为线性函数•作为密钥流的序列{ai}的周期一定要大否则密钥流的空间太小，利用穷举搜索可以得到密钥流{ai}•n级LFSR输出的序列的周期r不依赖于寄存器的初始值，而依赖于特征多项式p(x)基于移位寄存器的流密码算法•初态为100放入寄存器，输出序列情况如下b3b2b100111010011101…f(b1,b2,b3)=b1⊕b3状态输出位10001100111101111011010000111000输出序列的周期为7目前大多数研究成果都是关于同步流密码的。滚动密钥生成器滚动密钥生成器……安全信道kkxiziyizixi图3.20同步流密码体制模型)x(eizi)y(eizi流密码的结构•典型的流密码每次加密一个字节的明文；•密钥输入到一个伪随机数发生器，产生一串随机的8比特数；•发生器的输出称为密钥流；•11001100明文•⊕01101100密钥流•10100000密文•解密使用相同的伪随机序列：•10100000密文•⊕01101100密钥流•11001100明文•设计流密码需要考虑的主要因素：–加密序列的周期要长。伪随机发生器实质上使用的是产生确定的比特流的函数。该比特流最终将出现重复。–密钥流应该尽可能地接近于一个真正的随机数流的特征。如1和0的个数应近似相等，密钥流的随机特性越好，则密文越随机。–图中伪随机发生器的输出取决于输入密钥的值。密钥应该足够长，应当保证不小于128位。流密码的优缺点•和分组密码相比，速度更快，而且需要编写的代码少；•对不同的明文需要使用不同的流密钥，否则容易破解；•适用于需要对数据流进行加密解密的应用，如通过一个数据通信信道或网页浏览连接；•不适用于处理成块的数据：文件传输、电子邮件和数据库。流密码与分组密码区别：流密码几乎总是比分组密码快，通常使用的代码也比分组密码少得多。如最常用的流密码RC4，大概比最快的分组密码至少快两倍。RC4可以用30行代码写成，而大多数分组密码需要数百行代码。流密码和RC4•流密码的结构•RC4算法RC4•RC4是RonRivest为RSA公司在1987年设计的一种流密码；•是一个可变密钥长度，面向字节操作的流密码；•算法以随机置换作为基础，密码的周期大于10100。•每输出一个字节的结果仅需要8条到16条机器操作指令。•可能是应用最广泛的流密码，被应用于SSL/TLS标准。RC4算法•主要包括两个步骤：–密钥调度算法（KSA,Key-SchedulingAlgorithm）–伪随机生成算法（PRGA,PseudoRandomGenerationAlgorithm）密钥调度算法（KSA,Key-SchedulingAlgorithm）•设置内部状态（s[0]，…，s[255]）的随机排列。•开始时，内部状态中的元素被初始化为0~255，既s[i]=i(i=0，…，255)；•密钥长度可变，设为L个字节（K[0]，…，K[L-1]）；•L一般为5~32之间，用L个字节不断重复填充，直至得到K[0]，…，K[255]，用于对内部状态S进行随机化。j=0对i=0,…,255做j=j+S[i]+K[i]mod256互换s[i]与s[j]伪随机生成算法（PRGA,PseudoRandomGenerationAlgorithm）•从内部状态中选取一个随机元素作为密钥流中的一个字节，并修改内部状态以便下一次选择。•选取过程取决于索引值i和j，它们的初始值均为0。i=0j=0重复下述步骤，直至获得足够长度的密钥流：i=i+1mod256j=j+S[i]mod256互换s[i]与s[j]t=S[i]+S[j]mod256K=S[t]RC4算法01234567S0123456756756756K01234567假如使用3位（从0到7）的RC4，其操作是对8取模（而不是对256取模）。数据表S只有8个元素，初始化为：选取一个密钥，该密钥是由0到7的数以任意顺序组成的。例如选取5、6和7作为密钥。该密钥如下填入密钥数据表中：密钥调度算法KSA然后利用如下循环构建实际的S数据表：j:=0;fori=0to7doj:=(j+s(i)+k(i))mod8;swap(S(i),S(j));该循环以j=0和i=0开始。使用更新公式后j为：j=(0+S(0)+K(0))mod8=5S数据表的第一个操作是将S(0)与S(5)互换。51234067S01234567RC4算法索引i加1后，j的下一个值为：j=(5+S(1)+K(1))mod8=(5+1+6)mod8=4即将S数据表的S(1)和S(4)互换：54231067S01234567当该循环执行完后，数据表S就被随机化：54071632S01234567RC4算法伪随机数生成算法PRGA这样数据表S就可以用来生成随机的密钥流序列。从j=0和i=0开始，RC4如下计算第一个密钥字：i=(i+1)mod8=(0+1)mod8=1j=(j+s(i))mod8=(0+s(1))mod8=(0+4)mod8=4swapS(1)和S(4)51074632S01234567RC4算法RC4算法然后如下计算t和k:•t=(S(j)+S(i))mod8=(S(4)+S(1))mod8=(1+4)mod8=5•k=S(t)=S(5)=6第一个密钥字为6，其二进制表示为110。反复进行该过程，直到生成的二进制的数量等于明文位的数量。小结•掌握–RC4