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

第一節(jié)序列的隨機(jī)性２學(xué)時(shí)序列的隨機(jī)性隨機(jī)性的概念及參數(shù)隨機(jī)性假設(shè)偽隨機(jī)數(shù)發(fā)生器線性同余發(fā)生器用密碼編碼產(chǎn)生隨機(jī)數(shù)BBS發(fā)生器主要內(nèi)容掌握隨機(jī)性的含義及衡量方法理解隨機(jī)性假設(shè)的含義掌握線性同余發(fā)生器的原理及參數(shù)選擇理解如何用密碼產(chǎn)生隨機(jī)數(shù)理解BBS發(fā)生器的原理教學(xué)目的隨機(jī)序列：不能重復(fù)產(chǎn)生的序列幾個(gè)相關(guān)概念真隨機(jī)——不能重復(fù)產(chǎn)生密碼學(xué)意義上的隨機(jī)——不能預(yù)測(cè)偽隨機(jī)——看起來(lái)是隨機(jī)的，并能通過(guò)許多隨機(jī)性測(cè)試第一節(jié)序列的隨機(jī)性真隨機(jī)數(shù)發(fā)生器（TRNG）：利用物理方法實(shí)現(xiàn)的隨機(jī)數(shù)發(fā)生器，它是自然界隨機(jī)的物理過(guò)程（所產(chǎn)生物理現(xiàn)象的不確定性）的反映，即使算法等重要信息被暴露，都無(wú)法猜測(cè)其結(jié)果如何產(chǎn)生真隨機(jī)數(shù)1．若序列的周期為偶數(shù)，則在一個(gè)周期內(nèi)，0、1的個(gè)數(shù)相等；若周期為奇數(shù)，則在一個(gè)周期內(nèi)，0、1的個(gè)數(shù)相差1。2．在一個(gè)周期內(nèi)，長(zhǎng)度為l的游程數(shù)占游程總數(shù)的1/2l，且對(duì)于任意長(zhǎng)度，0游程與1游程個(gè)數(shù)相等。3．所有異相自相關(guān)函數(shù)值相等。Golomb隨機(jī)性假設(shè)第一節(jié)序列的隨機(jī)性偽隨機(jī)數(shù)發(fā)生器——將一個(gè)短的隨機(jī)數(shù)“種子”擴(kuò)展為較長(zhǎng)的偽隨機(jī)序列的確定算法。線性同余發(fā)生器（Linearcongruentialgenerator）用加密方式產(chǎn)生隨機(jī)數(shù)BBS發(fā)生器偽隨機(jī)數(shù)發(fā)生器第一節(jié)序列的隨機(jī)性評(píng)價(jià)線性同余發(fā)生器有以下準(zhǔn)則：（1）完整周期：即在一個(gè)周期中，０至m-1之間的數(shù)都出現(xiàn)。（2）滿足隨機(jī)性測(cè)試。（3）可以高效地實(shí)現(xiàn)。線性同余法的優(yōu)點(diǎn)：方便，快速；缺點(diǎn)：除初值外，其它數(shù)字都用確定算法產(chǎn)生。第一節(jié)序列的隨機(jī)性線性同余發(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)生，使用兩個(gè)密鑰K1，K2兩個(gè)驅(qū)動(dòng)隨機(jī)數(shù)：初始化時(shí)，設(shè)DT0為初始時(shí)刻的日期和時(shí)間(64bit)，V0為種子密鑰(64bit)輸出：64bit的隨機(jī)數(shù)Ri和更新后的Vi+1偽隨機(jī)數(shù)發(fā)生器第一節(jié)序列的隨機(jī)性（3）ANSIX9.17偽隨機(jī)數(shù)產(chǎn)生器

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

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

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