chap7-偽隨機數和流密碼

Chap7偽隨機數和流密碼

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

線性同余發(fā)生器真正的隨機數難以產生偽隨機數線性同余法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評價隨機數發(fā)生器的三個標準:生成函數應是全周期的，即函數再重復之前應該產生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