chap7-伪随机数和流密码

Chap7伪随机数和流密码

讨论议题随机数的产生流密码7.1随机数（Randomnumber）随机数用途，重要的角色，例如认证过程中，避免重放攻击会话密钥RSA公钥算法随机数的基本特点随机性均匀分布，有大量的测试方案独立性，难以测试，只能测试足够独立不可预测性随机数的产生随机性分布一致性：01出现概率大约相等独立性：任何子序列不能由其他子序列推导出不可预测性随机数的源物理噪声已公布的好的随机数算法生成的伪随机数伪随机数Pseudo-randomnumber密码应用大多使用算法来生成随机数。这些算法是确定的，所以产生的序列并非统计随机的。但是，算法足够好的话，产生的序列可以经受住随机性检测，这样的树一般称为伪随机数。althougharenottrulyrandomcanpassmanytestsof“randomness”createdby“PseudorandomNumberGenerators(PRNGs)”Random&PseudorandomNumberGeneratorsPRNGRequirementsrandomnessuniformity,scalability,consistencyunpredictabilityforward&backwardunpredictabilityusesameteststocheckcharacteristicsoftheseedsecureifknownadversarycandetermineoutputsomustberandomorpseudorandomnumberPRNG算法设计特意构造算法基于现存密码算法的算法对称非对称Hash函数和消息认证码线性拟合法Xn+1=(aXn+c)modm评价随机数发生器的三个标准：全周期“显得”随机，使用多种方法评估其随机程度方便实现注意，敌手如果知道一些东西就可重构后续所有序列。107.2伪随机数的产生：

线性同余发生器真正的随机数难以产生伪随机数线性同余法linearcongruencem模数m>0231a乘数0a<ma=75=16807

c增量0c<mX0

种子0X0<m“s0”istheseed

Xn+1=(aXn+c)modm

线性同余伪随机数缺乏不可预测性11PseudorandomNumbersXn+1=(aXn+c)modm；Xn

si<mChoiceofa,candmarecriticala=c=X0=1andm=8producesrandomnumbers{2,3,4,5,6,7,0,1}.Thissetisnotrandomatall.n=7,c=0,m=32ands0=1producestheset{7,17,23,1,7,17,23,1,…}.Thissethasaperiod4,meaningthatafterthe4thnumberthereisrepetitioninthesequence12评价随机数发生器的三个标准:生成函数应是全周期的，即函数再重复之前应该产生0andm-1之间所有数产生的序列应是随机的生成函数可以用32位运算器方便地实现m231-1；a=75=16807；c=013BBSmethodTakelargeprimespandqthathaveareminderof3upondivisionby4：

p=q=3mod4Letn=p*qChooseaseed“s”relativelyprimewithnAlgorithm:X0=s2modnFori=1to{Xi=(Xi-1)2modnBi=Ximod2}14BBSmethodBidenotestheleastsignificantbitineachiterationThealgorithmgeneratesthebitscontinuouslyUserdecideshowmanyofthebitstochoosetoformthenumber,e.g.,64-bitschosentoformakey

不存在多项式时间的算法使得在已知前k位的情况下预测出第k+1位的概率大于0.5BBS的安全性同样基于分解n的难度15使用分组密码的伪随机数产生

ANSIX9.17

Ri=EDEK1,K2(ViEDEK1,K2(DTi)) Vi+1=EDEK1,K2(RiEDEK1,K2(DTi))7.4流密码StreamCiphersStreamCipherStructureStreamCiphers19StreamCiphers20TheRC4StreamCipherDesignedbyRonRivestin1987forRSASecurity.Keptasatradesecretuntilleakedoutin1994.Themostpopularstreamcipher.Simpleandfast.Witha128bitskey,theperiodis>10100.UsedintheSSL/TLSstandards(forsecureWebcommunication),IEEE802.11wirelessLANstandard,MicrosoftPoint-to-PointEncryption,andmanyothers.21RC422RC4:InitialPermutation23RC4:KeyStreamGeneration24RC4OverviewSecurityofRC4ThekeystreamgeneratedbyRC4isbiased.Thesecondbyteisbiasedtowardzerowithhighprobability.Thefirstfewbytesarestronglynon-randomandleakinformationabouttheinputkey.Defense:discardtheinitialnbytesofthekeystream.Called“RC4-drop[n-bytes]”.Recommendedvaluesforn=256,768,or3072bytes.Effortsareunderway(e.g.theeSTREAMproject)todevelopmoresecurestreamciphers.26RC4andWEPWEPisaprotocolusingRC4toencryptpacketsfortransmissionoverIEEE802.11wirelessLAN.WEPrequireseachpackettobeencryptedwithaseparateRC4key.TheRC4keyforeachpacketisaconcatenationofa24-bitIV(initializationvector)anda40or104-bitlong-termkey.27lRC4key:IV(24)Long-termkey(40or104bits)802.11framesusingWEP28lHeaderIVPacketICVFCSencryptedICV:integritycheckvalue(fordataintegrity)FCS:framechecksequence(forerrordetection)Both