隨機(jī)性與偽隨機(jī)數(shù)生成器

隨機(jī)性與偽隨機(jī)數(shù)生成器主講人：趙永哲e_mail:yongzhe@電話：安全的密鑰加密算法的安全性是以密鑰的安全性為基礎(chǔ)的。安全的密鑰指的是這個密鑰必須是隨機(jī)數(shù)。如果它們不隨機(jī)，或如果在產(chǎn)生隨機(jī)數(shù)過程中有一點(diǎn)偏差，破譯者就能利用這個偏差對保密信息進(jìn)行破譯隨機(jī)性偽隨機(jī)序列密碼學(xué)意義上的偽隨機(jī)序列真隨機(jī)序列偽隨機(jī)序列均勻分布數(shù)列中每個數(shù)出現(xiàn)的頻率應(yīng)相等或近似相等。應(yīng)該有大約相同的0和1

長度為1的游程大約占一半長度為2的游程大約占1/4長度為3的游程大約占1/8密碼學(xué)意義上的偽隨機(jī)序列不可預(yù)測的

即使給出產(chǎn)生序列的算法或硬件和所有以前產(chǎn)生的位序列，也不能預(yù)測下一個隨機(jī)位是什么真隨機(jī)序列不能重復(fù)產(chǎn)生即使在完全相同的操作條件下用完全相同的輸入對序列發(fā)生器操作兩次，也將得到兩個完全不同的、毫不相關(guān)的位序列。獨(dú)立性數(shù)列中任意一數(shù)都不能由其他數(shù)推出密鑰的分類和對隨機(jī)性的要求主密鑰（MasterKey）真隨機(jī)序列會話密鑰（SessionKey）偽隨機(jī)序列真隨機(jī)數(shù)生成器RNG–RandomNumberGeneratorsRandomNumberGeneratorsaregeneratingnumbersinasequenceinsuchawaythatthenextnumberhasnorelationwiththepreviousnumbersGoodRNGsTuringAwardwinnerin2000 AndrewChi-ChihYao姚期智

Contributions貢獻(xiàn)TheoryofcomputationComplexityTheoryofRNGs隨機(jī)數(shù)理論

1946-IfthereisnopracticalwaytopredictthenextbitofanRNGwithmorethan50%chance,theRNGwillpassallstatisticaltests.OR肥IO緞N'邪s宴Ra厘nd扇om竹N賓um衫be英r陣Ge慮ne敵ra塊to五rOR瞎IO賤N'皇sRa流nd拍om給N真um依be搶r漠Ge修ne爺ra馳to候r阻co殊ns斬is窗ts濁o形f次tw勾o壺in身de桃pe揭nd茅en厲t棉an慌al橡og偵ueZe酒ne村rdi截od祝e棍ba獲se飲d絹no耀is微e遣so董ur燃ce倦s.深B摧ot閘h桐si商gn惱al狡s晨ar萌e能co芝nv謝er壘te悄d蓄in郵to然r娃an擁do宅m先bi綢t嗎st橋re晉am需s,量c鑒om村bi候ne嶄d曉an膛d待su慎bs拐eq萌ue插nt筍ly婦t猶ra新ns表mi否tt詳ed演i元n筍th箏e悼fo未rm幸o柏f紫by臨te避s琴to筒t寸he箏R獸S-疼23啞2丙po僻rt前o蛾f計(jì)yo窯ur突c架om戶pu精te擴(kuò)r.Th霞e圍ba幅ud眼r膛at晉e換is瀉9陰60某0.溝S藥o置th秀e揪de醫(yī)vi淺ce啞i嫩s綿ca報(bào)pa擦bl快e科of插s然up液pl此yi懸ng按y憶ou罰w粥it徒h韻ab煙ou噸t鴿96斑0r發(fā)an豪do撒m惜by晉te干s勸or竄7爆60數(shù)0昌ra薪nd蒜om刪b透it綁s土pe題r紛se遮co至nd€58兵0Qu某an扛tu撈m是Ra陣nd妖om躲B得it糠G鐵en葉er廟at傘orQR旗BG頂12秤1昆is歷a團(tuán)f餅as灑t據(jù)no齊n-丈de撒te吉rm娘in葛is凝ti遣c顫ra惱nd桌om假b慮it晌(移nu蘆mb蓮er帝)脆ge愧ne逼ra年to辮r闊wh稈os側(cè)e兄ra標(biāo)nd濃om陜ne市ss子r導(dǎo)el湖ie硬s驚on天i賊nt萍ri表ns危ic賽r裹an碑do獸mn體es畫s偶o(jì)f數(shù)t朽he革q徐ua愁nt菜um源p太hy已si母ca惕l忌pr梢oc姜es賣s趕of項(xiàng)p惡ho逆to綢ni程c躺em形is醒si蠻on青i課n屬se墳mi鞏co禾nd遼uc貝to敗rs壘a泥nd贊s貴ub西se盾qu豪en繩t盜de塞te塌ct飾io候n料by鴨p嶺ho參to華el獵ec撿tr障ic豪e磁ff畏ec量t.埋I木n訂th鎖is觸p巨r(nóng)o唐ce谷ss范p摩ho疑to烈ns箱a茶re五d普et丹ec芳te忌d寺at毒r菠an夫do郵m,搬o萍ne鍛b金y樹on棟e艙in看de侵pe堵nd綁en螞tl蛾y題of遍e歇ac壩h耳ot憂he捧r.誰T堤im鴉in唱g懸in渠fo蒜rm懸at俱io明n鳴of遣d下et銹ec橫te媽d漢ph伶ot鍋on暗s賣is括u斥se忘d腿to祝g櫻en甩er膚at妹e塞ra紡nd法om雨b恥in生ar芬y折di娛gi犁ts監(jiān)-遭b雹it團(tuán)s.偽隨辭機(jī)數(shù)概生成軟器PR齡NG綁–穗P倘se漿ud剃o過Ra戒nd段om處N胡um做be乞r添Ge常ne槐ra妖to蜓rs偽隨傭機(jī)數(shù)狼生成射器是膏一個尖確定勵性算養(yǎng)法，自用一轎個長肅度為k的二逆進(jìn)制傍序列臂作為扒愉入吊，算蝕法就退能產(chǎn)透生長依度為m集(m垂>>夕k)的隨腿機(jī)數(shù)所序列檢。偽隨臂機(jī)生革成器矮的輸下入稱積為產(chǎn)球生器驕的種晚子。線性餅同余壞算法涉的P愈RN岔GXn+陵1=(臨aXn+c魄)北mo迫d雪m模數(shù)m(礎(chǔ)m>降0)搬，乘數(shù)a(繡0≤長a<陰m)蜂，增量c(底0≤哥c<躲m)助，初值信即種抬子X0(0糟≤X0<m銜)；如果m、姻a、銀c、史X0都為完整數(shù)婆，則躬產(chǎn)生吹的隨秩機(jī)數(shù)材數(shù)列第{Xn}也都艘是整帽數(shù)，招且0喝≤Xn<m庭。線性賣同余度算法拾的P插RN帖GSi井mp歌le裙,歸fa鍋st經(jīng)es績tFo喂r筑32跳-b鏟it渣w婦or甘ds撿,怨th架e括pe耕ri扒od保c城an高r述ea晃ch戀232In晃se駁cu盛re豬,完th籮e稈fo鐮rm雷u(yù)l深a遺ca漸n柄be莊w睜or值ke陶d疊ou般t鵝fr馬om左o歉ut膏pu驅(qū)tFa負(fù)il艘s用in說m慘an陵y素te宇st陳sSu范ff圓ic忘ie匠nt嗚ly釘r攪an皂do壞m駱fo果r施ma技ny銅a槐pp岡li缸ca嚇ti墓on該sAN喂SI耳X路9鋒.1煉7的偽思隨機(jī)忘數(shù)產(chǎn)廣生器其中兼加密EK(X弟)表示秧用密叨鑰對X進(jìn)行身三重DE驢S加密總。K是密止鑰。V0是秘援密的64位種泰子。T是時幻玉間標(biāo)爽記。Ri是預(yù)恩產(chǎn)生境的隨身機(jī)密濤鑰。BB艷S偽相隨機(jī)友數(shù)產(chǎn)挎生器Bl梅um薦-B踐lu欠m-鍋Sh丟ub(B良SS姓)少ge篇ne燙ra梢to缺rs親,窮19慣86m=棚pq,pan第dqar母e少di盯st濱in語ct樸p其ri御me賽s極(質(zhì)數(shù))夸of難t見he辟f盞or唉m訴4z+3mha木s垃10慨24續(xù)t佛o銅40釘96逆b磨it坡sOu詠tp股ut像t塑he左l蕉as私t鳳bi理t遷ofXn+1We核ll蕩d重is宣tr鋼ib擠ut鉆ed砌:利pa廈ss邁a紋ll萬t溜es漠ts豎i糠n現(xiàn)th萍eo是ry可以納通過腐所有檢驗(yàn)Se殲cu寒re霉b銹ut汗v泉er果y帖sl起owTh危e癢pe椒ri蠟od值d矛ep詳en馳ds柱o杠n皇th慚e峽se起ed艦a汗nd利c沿an馳o客nl父y柴be持w片or脈ke再d溝ou殊t鏡us個in囑g金an黃a那lg并or頌it棚hm旗.使用供偽隨優(yōu)機(jī)數(shù)望產(chǎn)生膊器應(yīng)鐵注意茄的問幣題基于插歷未史尿先耕例，PR頂NG的種送子通旅常是桐參照法系統(tǒng)即時鐘毅生成藝的。尺這個誕想法題是使抖用系旨統(tǒng)時犬間的腫某一毅點(diǎn)來碑作為綱種子提。這呈意味礦著如高果能謀算出鑰生成溝器什攝么時派間發(fā)尸生，腥那么比就可威以知休道由拆生成磚器生期成的困每一機(jī)個值咽?？舍u見，返用時港鐘播偉種的避偽隨慘機(jī)數(shù)甩，所記有結(jié)屬果不鄙是不熱可預(yù)旺測的科。如是果想新要安母全性柄，必裹須為揭數(shù)字乓生成診器播除種一綠個真醉正的存隨機(jī)不數(shù)。在線手賭博干中欺廳騙Re駕li豎ab猾le屠S蝕of組tw抓ar斯e畜Te粱ch繳no周lo問gi漢es樣(絨RS諸T)的軟擋件安懲全性卻組最爸近在Te場xa蘋s隔Ho墓ld治‘emPo萄ke村r（由AS網(wǎng)F軟件早公司磨發(fā)行甚）的單實(shí)現(xiàn)盲中發(fā)續(xù)現(xiàn)了時一系戚列缺診陷。妥這個筍揭秘器允許坊欺騙芽性的觸玩家叫可以勇實(shí)時陵計(jì)算錫每人眼手中滾確切妹的牌協(xié)。這食意味井著，碑使用祝這個怠揭秘盆的玩輔家可怎以知說道每桐個對石家手屋中的財(cái)牌和喊將要微發(fā)出硬的牌趨。調(diào)用ra院nd價om識iz瓣e(沉)來在腐每副罩牌生棍成前接生成字一副繪隨機(jī)請牌。肺這個跪?qū)崿F(xiàn)海是用De逮lp塊hi求4（一傾種Pa賣sc喇a(chǎn)l猜I粒DE）構(gòu)仆建的勺，隨秩機(jī)數(shù)駝生成述器的細(xì)種子雀是按背照系賠統(tǒng)時美鐘，浮用午扎夜后座的毫腹秒數(shù)候選取你的。惰這意魄味著劇隨機(jī)鍛數(shù)生盛成器俗的輸?shù)癯鍪瞧嫒菀准侯A(yù)測漠的。Te育xa濁s愈Ho吧ld孕'能em朗P糖ok丸er的一傍系列獨(dú)缺陷在實(shí)料際的專紙牌黎中，僅有52恭!（大智約是222衣6）種捆可能量的、壩不同能的洗攏牌順桐序。32位的騾隨機(jī)知數(shù)生水成器身的種站