隨機數(shù)的用途課件

隨機數(shù)的用途相互認證對稱密碼算法中會話密鑰的產生公鑰密碼算法中的密鑰產生(RSA)5.1序列的隨機性2023/8/301隨機數(shù)的用途相互認證5.1序列的隨機性2023/8/21隨機數(shù)的要求－隨機性均勻分布(周期大)序列中每個數(shù)出現(xiàn)的頻率相等或近似相等獨立性序列中任一數(shù)不能由其他數(shù)推出經常使用的是偽隨機序列2023/8/302隨機數(shù)的要求－隨機性均勻分布(周期大)2023/8/22隨機數(shù)的要求－不可預測性對序列中以后的數(shù)是不可預測的對于真隨機數(shù)，滿足獨立性，所以不可預測偽隨機序列需要特別注意滿足不可預測性2023/8/303隨機數(shù)的要求－不可預測性對序列中以后的數(shù)是不可預測的20231.周期對于序列{xn}，滿足對任意i∈Z+,xi=xi+p的最小正整數(shù)p2.游程對于序列{xn}，若有xt-1≠xt=xt+1…=xt+l-1≠xt+l,則（xt，xt+1…，xt+l-1）是一個長為l的游程序列隨機性衡量參數(shù)2023/8/3041.周期對于序列{xn}，滿足對任意i∈Z+,xi=xi+p設序列{xn}的周期為p，定義序列隨機性衡量參數(shù)3.周期自相關函數(shù)若p|j,則R（j）為同相自相關函數(shù)，此時A=p,D=0,R（j）=1若p∕j,則R（j）為異相自相關函數(shù)2023/8/305設序列{xn}的周期為p，定義序列隨機性衡量參數(shù)3.周期自相(1)若序列的周期為偶數(shù)，則在一個周期內，0、1的個數(shù)相等，若周期為奇數(shù)，則在一個周期內，0、1的個數(shù)相差1。（2）在一個周期內，長度為l的游程數(shù)占游程總數(shù)的1/2l，且對于任意長度，0游程與1游程個數(shù)相等。（3）所有異相自相關函數(shù)值相等。Golomb隨機性假設2023/8/306(1)若序列的周期為偶數(shù)，則在一個周期內，0、1的個數(shù)相等，隨機數(shù)源真隨機數(shù)源－物理噪聲產生器離子輻射脈沖檢測器氣體放電管漏電容數(shù)的隨機性和精度不夠這些設備很難聯(lián)入網絡2023/8/307隨機數(shù)源真隨機數(shù)源－物理噪聲產生器2023/8/27偽隨機數(shù)產生器-線性同余法參數(shù)：模數(shù)m(m>0)乘數(shù)a(0≤a<m)增量c(0≤c<m)初值種子X0(0≤X0<m)Xn(0≤Xn<m)a,c,m的取值是產生高質量隨機數(shù)的關鍵一般c=0,模數(shù)m確定,此時a的取值非常重要,a一般取為模m的本原元素2023/8/308偽隨機數(shù)產生器-線性同余法參數(shù)：a,c,m的取值是產生高質量偽隨機數(shù)產生器-線性同余法a=7,c=0,m=32,X0=1{7,17,23,1,7,…}a=3,c=0,m=32,X0=1{3,9,27,17,19,25,11,1,3,…}選m盡可能大，使其接近或等于計算機能表示的最大整數(shù)周期為4周期為82023/8/309偽隨機數(shù)產生器-線性同余法a=7,c=0,m=32,X0=1偽隨機數(shù)產生器-線性同余法迭代函數(shù)應是整周期的，在重復之前應出現(xiàn)0到m間的所有數(shù)產生的數(shù)列看上去應是隨機的迭代函數(shù)能有效的利用32位運算實現(xiàn)如果m為素數(shù)，且a為m的本原根，產生的數(shù)列是整周期的。a=16807(本原根),m=231-1,c=0產生數(shù)列是整周期的Xn+1=(16807Xn)mod(231-1)已被廣泛應用2023/8/3010偽隨機數(shù)產生器-線性同余法迭代函數(shù)應是整周期的，在重復之前應偽隨機數(shù)產生器-線性同余法假定敵手知道X0,X1,X2,X3,可以確定參數(shù)算法運算速度快，序列周期長，但安全性能不佳的弱點始終制約著該算法在密碼學領域的應用.2023/8/3011偽隨機數(shù)產生器-線性同余法假定敵手知道X0,X1,X2,X3基于密碼算法的隨機數(shù)產生器循環(huán)加密CC+1加密算法

主密鑰Km周期為N的計數(shù)器周期為N,序列不可預測2023/8/3012基于密碼算法的隨機數(shù)產生器循環(huán)加密CC+1加密算法主密鑰K基于密碼算法的隨機數(shù)產生器DES的輸出反饋方式(OFB)模式采用OFB模式能用來產生密鑰并用于流加密。加密算法的輸出構成偽隨機序列2023/8/3013基于密碼算法的隨機數(shù)產生器DES的輸出反饋方式(OFB)模式DES的輸出反饋方式(CBC)模式(2)P1中有一比特錯誤,將在所有密文中傳播.接收者解密時,僅影響相應分組,后續(xù)分組可正常解密2023/8/3014DES的輸出反饋方式(CBC)模式(2)P1中有一比特錯誤,基于密碼算法的隨機數(shù)產生器ANSIX9.17偽隨機數(shù)產生器(PGP中IDEA)EDEEDEEDE＋＋K1K2Vi+1ViRiDTiDTi:當前的日期和時間Vi:是產生第i個隨機數(shù)時的種子EDEK1K2=EK1DK2EK1隨時更新2023/8/3015基于密碼算法的隨機數(shù)產生器ANSIX9.17偽隨機數(shù)產生器(隨機數(shù)產生器-BBS產生器密碼強度最強，基于大整數(shù)分解困難性選擇p,q,滿足p=q=3mod4,n=p×q。選隨機數(shù)s，s和n互素X0＝s2modnFori=1to∞do{Xi=Xi-12modn;Bi=Ximod2}Bi為產生的隨機數(shù)序列2023/8/3016隨機數(shù)產生器-BBS產生器密碼強度最強，基于大整數(shù)分解困難性2023/8/30172023/8/2175.3流密碼(序列密碼)的基本概念明文:密鑰:密文:加密變換:解密變換:2023/8/30185.3流密碼(序列密碼)的基本概念明文:密鑰:密文:加密

加法流密碼體制模型2023/8/30192023/8/219移位寄存器是流密碼產生密鑰流的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數(shù)f(a1,a2,…,an)組成

。線性反饋移位寄存器2023/8/3020移位寄存器是流密碼產生密鑰流的一個主要組成部分。線性反GF(2)上的n級反饋移位寄存器存儲器存儲器存儲器存儲器2023/8/3021GF(2)上的n級反饋移位寄存器存儲器存儲器存儲器存儲在任一時刻，這些級的內容構成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應于GF(2)上的一個n維向量，共有2n種可能的狀態(tài)。每一時刻的狀態(tài)可用n維向量(a1,a2,…,an)表示，其中ai是第i級存儲器的內容。2023/8/3022在任一時刻，這些級的內容構成該反饋移位寄存器的狀態(tài)，每一狀態(tài)初始狀態(tài)由用戶確定反饋函數(shù)f(a1,a2,…,an)是n元布爾函數(shù)，即函數(shù)的自變量和因變量只取0和1這兩個可能的值。函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算。2023/8/3023初始狀態(tài)由用戶確定2023/8/223例下圖是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由下表求出。圖

一個3級反饋移位寄存器狀態(tài)（a3,a2,a1)輸出101110111011101110

101110一個3級反饋移位寄存器的狀態(tài)和輸出即輸出序列為101110111011…，周期為4。2023/8/3024例下圖是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,aGF(2)上的n級線性反饋移位寄存器線性反饋移位寄存器LFSR（linearfeedbackshiftregister）2023/8/3025GF(2)上的n級線性反饋移位寄存器線性反饋移位寄存器LFS輸出序列{at}滿足：線性反饋移位寄存器：實現(xiàn)簡單、速度快、有較為成熟的理論，成為構造密鑰流生成器的最重要的部件之一。2023/8/3026輸出序列{at}滿足：線性反饋移位寄存器：實現(xiàn)簡單、速度快、例下圖是一個5級線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)可求出輸出序列為1001101001000010101110110001111100110…周期為31。2023/8/3027例下圖是一個5級線性反饋移位寄存器，其初始狀態(tài)為（a1,a總是假定c1,c2,…,cn中至少

0，否則f(a1,a2,…,an)≡0?？偸羌俣╟n=