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

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

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

c增量0c<mX0

種子0X0<m“s0”istheseed

Xn+1=(aXn+c)modm

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