chap7-偽隨機(jī)數(shù)和流密碼

Chap7偽隨機(jī)數(shù)和流密碼

討論議題隨機(jī)數(shù)的產(chǎn)生流密碼7.1隨機(jī)數(shù)（Randomnumber）隨機(jī)數(shù)用途，重要的角色，例如認(rèn)證過程中，避免重放攻擊會話密鑰RSA公鑰算法隨機(jī)數(shù)的基本特點(diǎn)隨機(jī)性均勻分布，有大量的測試方案獨(dú)立性，難以測試，只能測試足夠獨(dú)立不可預(yù)測性隨機(jī)數(shù)的產(chǎn)生隨機(jī)性分布一致性：01出現(xiàn)概率大約相等獨(dú)立性：任何子序列不能由其他子序列推導(dǎo)出不可預(yù)測性隨機(jī)數(shù)的源物理噪聲已公布的好的隨機(jī)數(shù)算法生成的偽隨機(jī)數(shù)偽隨機(jī)數(shù)Pseudo-randomnumber密碼應(yīng)用大多使用算法來生成隨機(jī)數(shù)。這些算法是確定的，所以產(chǎn)生的序列并非統(tǒng)計隨機(jī)的。但是，算法足夠好的話，產(chǎn)生的序列可以經(jīng)受住隨機(jī)性檢測，這樣的樹一般稱為偽隨機(jī)數(shù)。althougharenottrulyrandomcanpassmanytestsof“randomness”createdby“PseudorandomNumberGenerators(PRNGs)”Random&PseudorandomNumberGeneratorsPRNGRequirementsrandomnessuniformity,scalability,consistencyunpredictabilityforward&backwardunpredictabilityusesameteststocheckcharacteristicsoftheseedsecureifknownadversarycandetermineoutputsomustberandomorpseudorandomnumberPRNG算法設(shè)計特意構(gòu)造算法基于現(xiàn)存密碼算法的算法對稱非對稱Hash函數(shù)和消息認(rèn)證碼線性擬合法Xn+1=(aXn+c)modm評價隨機(jī)數(shù)發(fā)生器的三個標(biāo)準(zhǔn)：全周期“顯得”隨機(jī)，使用多種方法評估其隨機(jī)程度方便實(shí)現(xiàn)注意，敵手如果知道一些東西就可重構(gòu)后續(xù)所有序列。107.2偽隨機(jī)數(shù)的產(chǎn)生：

線性同余發(fā)生器真正的隨機(jī)數(shù)難以產(chǎn)生偽隨機(jī)數(shù)線性同余法linearcongruencem模數(shù)m>0231a乘數(shù)0a<ma=75=16807

c增量0c<mX0

種子0X0<m“s0”istheseed

Xn+1=(aXn+c)modm

線性同余偽隨機(jī)數(shù)缺乏不可預(yù)測性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評價隨機(jī)數(shù)發(fā)生器的三個標(biāo)準(zhǔn):生成函數(shù)應(yīng)是全周期的，即函數(shù)再重復(fù)之前應(yīng)該產(chǎn)生0andm-1之間所有數(shù)產(chǎn)生的序列應(yīng)是隨機(jī)的生成函數(shù)可以用32位運(yùn)算器方便地實(shí)現(xiàn)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位的情況下預(yù)測出第k+1位的概率大于0.5BBS的安全性同樣基于分解n的難度15使用分組密碼的偽隨機(jī)數(shù)產(chǎn)生

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