密碼學(xué)基礎(chǔ) 課件 第4章 序列密碼

第一節(jié)序列的隨機性２學(xué)時序列的隨機性隨機性的概念及參數(shù)隨機性假設(shè)偽隨機數(shù)發(fā)生器線性同余發(fā)生器用密碼編碼產(chǎn)生隨機數(shù)BBS發(fā)生器主要內(nèi)容掌握隨機性的含義及衡量方法理解隨機性假設(shè)的含義掌握線性同余發(fā)生器的原理及參數(shù)選擇理解如何用密碼產(chǎn)生隨機數(shù)理解BBS發(fā)生器的原理教學(xué)目的隨機序列：不能重復(fù)產(chǎn)生的序列幾個相關(guān)概念真隨機——不能重復(fù)產(chǎn)生密碼學(xué)意義上的隨機——不能預(yù)測偽隨機——看起來是隨機的，并能通過許多隨機性測試第一節(jié)序列的隨機性真隨機數(shù)發(fā)生器（TRNG）：利用物理方法實現(xiàn)的隨機數(shù)發(fā)生器，它是自然界隨機的物理過程（所產(chǎn)生物理現(xiàn)象的不確定性）的反映，即使算法等重要信息被暴露，都無法猜測其結(jié)果如何產(chǎn)生真隨機數(shù)1．若序列的周期為偶數(shù)，則在一個周期內(nèi)，0、1的個數(shù)相等；若周期為奇數(shù)，則在一個周期內(nèi)，0、1的個數(shù)相差1。2．在一個周期內(nèi)，長度為l的游程數(shù)占游程總數(shù)的1/2l，且對于任意長度，0游程與1游程個數(shù)相等。3．所有異相自相關(guān)函數(shù)值相等。Golomb隨機性假設(shè)第一節(jié)序列的隨機性偽隨機數(shù)發(fā)生器——將一個短的隨機數(shù)“種子”擴展為較長的偽隨機序列的確定算法。線性同余發(fā)生器（Linearcongruentialgenerator）用加密方式產(chǎn)生隨機數(shù)BBS發(fā)生器偽隨機數(shù)發(fā)生器第一節(jié)序列的隨機性評價線性同余發(fā)生器有以下準(zhǔn)則：（1）完整周期：即在一個周期中，０至m-1之間的數(shù)都出現(xiàn)。（2）滿足隨機性測試。（3）可以高效地實現(xiàn)。線性同余法的優(yōu)點：方便，快速；缺點：除初值外，其它數(shù)字都用確定算法產(chǎn)生。第一節(jié)序列的隨機性線性同余發(fā)生器線性同余發(fā)生器先后被JimReeds和JoanBoyar破譯后者還破譯了二次同余發(fā)生器Xn=(ax2n-1+bxn+c)modm和三次同余發(fā)生器Xn=ax3n-1+bx2n-1+cxn-1+d線性同余發(fā)生器NIST為銀行電子支付系統(tǒng)建議的標(biāo)準(zhǔn)算法，被PGP采納，在Internet中使用。方法：用三重DES的EDE模式產(chǎn)生，使用兩個密鑰K1，K2兩個驅(qū)動隨機數(shù)：初始化時，設(shè)DT0為初始時刻的日期和時間(64bit)，V0為種子密鑰(64bit)輸出：64bit的隨機數(shù)Ri和更新后的Vi+1偽隨機數(shù)發(fā)生器第一節(jié)序列的隨機性（3）ANSIX9.17偽隨機數(shù)產(chǎn)生器

每一時刻要進(jìn)行三次加密，相當(dāng)于9次DES加密，由兩個偽隨機數(shù)驅(qū)動。偽隨機數(shù)發(fā)生器第一節(jié)序列的隨機性用K1，K2對DT0加密，結(jié)果與V0相加，再對其加密，得到R0BlumBlumShub產(chǎn)生器（BBS發(fā)生器）:

利用數(shù)論方法產(chǎn)生偽隨機數(shù)選擇兩個大素數(shù)p，q，滿足p≡q≡3mod4；計算其乘積n=pq；選擇隨機數(shù)s，(s,n)=1；通過以下公式迭代計算序列{Bi}偽隨機數(shù)發(fā)生器第一節(jié)序列的隨機性BBS發(fā)生器在密碼學(xué)意義上是相對安全的，但計算量比較大。偽隨機數(shù)發(fā)生器第一節(jié)序列的隨機性第二節(jié)序列密碼的原理2學(xué)時序列密碼的基本概念加密方式密鑰序列生成器線性反饋移位寄存器與m序列線性反饋移位寄存器移位寄存器的周期及m序列序列的線性復(fù)雜度與B-M算法主要內(nèi)容明文符號序列與密鑰符號序列逐個加密密鑰序列z=z1z2…的第i個符號加密明文序列m=m1m2…的第i個符號，即若密鑰序列重復(fù)使用，則稱為周期序列密碼，否則，就是一次一密密碼。序列密碼的加密方式第二節(jié)序列密碼的基本概念由密鑰流生成器生成第i個密鑰取決于第i時刻密鑰生成器的內(nèi)部狀態(tài)和初始密鑰。對序列密碼的安全性有兩個基本要求：根據(jù)密鑰序列以前的狀態(tài)，不能很容易地推導(dǎo)出后續(xù)狀態(tài)，即密鑰序列要有足夠高的隨機性；傳輸密鑰的秘密信道必須足夠安全。序列密碼中的密鑰密碼的安全性主要取決于所用密鑰的隨機性，所以設(shè)計序列密碼的核心問題是設(shè)計隨機性較好的密鑰流生成器設(shè)計密鑰流生成器的關(guān)鍵：尋找狀態(tài)轉(zhuǎn)移函數(shù)和輸出函數(shù)，使輸出的密鑰序列有良好的偽隨機性。密鑰流生成器第二節(jié)序列密碼的基本概念Rueppel將密鑰流生成器分為兩部分：驅(qū)動部分和非線性組合部分。驅(qū)動部分控制生成器的狀態(tài)，并為非線性組合部分提供周期長、統(tǒng)計性能良好的序列；非線性組合部分利用這些序列組合出滿足要求的密鑰序列。密鑰流生成器第二節(jié)序列密碼的基本概念根據(jù)密鑰序列的產(chǎn)生方法，可將序列密碼可分為兩類：同步序列密碼（SynchronousStreamCipher）：狀態(tài)轉(zhuǎn)移函數(shù)與明文字符無關(guān)自同步序列密碼（Self-SynchronousStreamCipher）：狀態(tài)轉(zhuǎn)移函數(shù)與明文字符相關(guān)。在同步流密碼中，只要發(fā)送端和接收端有相同的種子或?qū)嶋H密鑰和內(nèi)部狀態(tài)，就能產(chǎn)生出相同的密鑰流，此時，認(rèn)為發(fā)送端和接收端的密鑰生成器是同步的。序列密碼的分類第二節(jié)序列密碼的基本概念衡量密碼體制安全性的方法計算安全性（computationalsecurity），又稱實際安全性（practicalsecrecy）：利用已有的最好的方法破譯該系統(tǒng)所需要的努力超過了敵手的破譯能力?？勺C明安全性（provablesecurity）：能用嚴(yán)格的數(shù)學(xué)方法證明破譯該體制等價于某個困難問題。無條件安全性（unconditionalsecurity）或完善保密性（perfectsecrecy）：在信息論意義上是安全的。理論保密的密碼體制定理若某一密碼系統(tǒng)的明文數(shù)、密文數(shù)和密鑰數(shù)都相等，則該密碼體制完全保密的充要條件是：將某一明文加密成某一密文的密鑰只能有一個；所有密鑰都是等概率的。理論保密的密碼體制組成：一系列存儲單元、若干個乘法器和加法器通過電路連接而成。假設(shè)共有n個存儲單元（此時稱該移位寄存器為n級），每個存儲單元可存儲一比特信息，在第i時刻各個存儲單元中的比特序列(aiai+1…ai+n-1)稱為移位寄存器的狀態(tài)，為初始狀態(tài)。線性反饋移位寄存器第三節(jié)線性反饋移位寄存器與m序列給定初態(tài)（101），按照反饋函數(shù)可求出各個時刻的狀態(tài)及輸出.狀態(tài)在第5時刻開始重復(fù)，因此輸出序列的周期是4，輸出序列為1011101110111011……線性反饋移位寄存器（LFSR）第三節(jié)線性反饋移位寄存器與m序列定理5-1

n級LFSR的周期≤2n-1證明：n級LFSR最多有2n種不同狀態(tài)，若初態(tài)為全零，則其后續(xù)狀態(tài)恒為零，構(gòu)成一個平凡序列，若初態(tài)不為零，則一個周期中最多出現(xiàn)2n-1種非零狀態(tài)，故狀態(tài)周期小于等于2n