信息安全導(dǎo)論 4流密碼

信息安全導(dǎo)論第四講流密碼信息安全研究室

2/28/20241流密碼流密碼介紹流密碼的分類(lèi)一種流密碼算法——RC4流密碼的設(shè)計(jì)準(zhǔn)則流密碼和分組密碼的比較混沌變碼本流密碼2/28/20242流密碼的一般性描述序列密碼的思想來(lái)源于早期著名的一次一密，其核心是通過(guò)固定算法，將一串短的密鑰序列擴(kuò)展為長(zhǎng)周期的密鑰流序列，且密鑰流序列在計(jì)算能力內(nèi)應(yīng)與隨機(jī)序列不可區(qū)分。2/28/20243流密碼的一般性描述為理解流密碼（第二類(lèi)對(duì)稱密鑰算法），你首先需要理解一種叫做一次一密的密碼技術(shù)，該技術(shù)在間諜中很流行。在該技術(shù)的一個(gè)變形中，生成一大堆隨機(jī)數(shù)字，每個(gè)都在0-25之間。然后打印2份該序列。這就是“密碼本”。其中，一份副件留在總部，間諜帶走另一份。為了將信息送回總部，間諜對(duì)信息中的每個(gè)字母都用密碼本上的一個(gè)數(shù)字進(jìn)行加密。消息的第一個(gè)字母用密碼本上的第一個(gè)數(shù)字加密，第二個(gè)字母用第二個(gè)數(shù)字加密，等等。2/28/20244加密是這樣一件事情：將由字母指定的一個(gè)數(shù)字值與相應(yīng)數(shù)字相加。由字母指定的數(shù)字值是這樣的：如果明文字母是G，密碼本上的數(shù)字是11，則密文字母為R(R是G后面的第11個(gè)字母，或者說(shuō)G十11＝R)。如果明文字母是Y而密碼本上的數(shù)字為4，密文的字母就是C．或Y十4＝C(Y，Z，A，B，C；當(dāng)?shù)搅俗帜副碜詈髸r(shí)，你就從A重新開(kāi)始)。當(dāng)總部得到加密的消息時(shí)，翻譯者只需將算法反過(guò)來(lái)使用便可。如果密文是B而密碼本中的相關(guān)數(shù)是11，則計(jì)算R一11＝G。若間諜和總部使用相同的密碼本，則通信將成功。2/28/20245下圖顯示了一次一密的一個(gè)例子。密碼本從何而來(lái)?2/28/20246流密碼與一次一密類(lèi)似。為加密數(shù)據(jù)，算法生成一個(gè)基于密鑰的密碼本。這個(gè)密碼本可以足夠大。算法將用密碼本和明文進(jìn)行異或運(yùn)算。2/28/20247用一次一密的技術(shù)，間諜和總部預(yù)先生成一個(gè)密碼本(實(shí)際上，可能是很多密碼本)。流密碼當(dāng)且僅當(dāng)需要時(shí)才生成一個(gè)密碼本。在密碼學(xué)界，該“密碼本”被稱為密鑰流(keystream)。一個(gè)真正的密碼本應(yīng)是隨機(jī)的，而流密碼生成的是偽隨機(jī)值，所以在技術(shù)上不能稱之為密碼本。大多數(shù)流密碼是這樣工作的。首先，利用密鑰建立—個(gè)密鑰表。然后加密數(shù)據(jù)：先取一個(gè)明文字節(jié)；之后在密鑰表中取得密鑰流的一個(gè)字節(jié)，將其與該明文字節(jié)異或；然后扔掉流密鑰的字節(jié)。2/28/20248然后你再取得數(shù)據(jù)的下一個(gè)字節(jié)，重復(fù)上述步驟。密鑰表以及密鑰流，都不依賴于輸入的數(shù)據(jù)。在一次一密的例子中，間諜通過(guò)將數(shù)字加到字母上實(shí)現(xiàn)數(shù)據(jù)的加密，而總部則通過(guò)減去而進(jìn)行解密。因?yàn)榧用芎徒饷苁窍嗤倪\(yùn)算，所以流密碼使用異或運(yùn)算。這里只存在一個(gè)程序而不是兩個(gè)程序。2/28/20249流密碼的形式化描述

流密碼的基本思想是利用密鑰k產(chǎn)生一個(gè)密鑰流，并使用如下規(guī)則加密明文得到密文。密鑰流由密鑰流發(fā)生器f產(chǎn)生：，這里是加密器中的記憶元件（存儲(chǔ)器）在時(shí)刻i的狀態(tài)，f是由密鑰k和產(chǎn)生的函數(shù)。2/28/202410流密碼流密碼介紹流密碼的分類(lèi)一種流密碼算法——RC4流密碼的設(shè)計(jì)準(zhǔn)則流密碼和分組密碼的比較混沌變碼本流密碼2/28/202411流密碼的分類(lèi)根據(jù)加密器中的記憶元件的存儲(chǔ)狀態(tài)σi是否依賴于輸入的明文字符，流密碼可進(jìn)一步分成同步和自同步兩種。σi獨(dú)立于明文字符的叫做同步流密碼，否則叫做自同步流密碼。同步流密碼中，由于與明文字符無(wú)關(guān)，密文字符也不依賴于此前的明文字符。因而，可將同步流密碼的加密器分成密鑰流生成和加密變換器兩個(gè)部分。如果與上述變換對(duì)應(yīng)的解密變換為，則可給出同步流密碼的模型。2/28/202412密鑰產(chǎn)生器最初是由種子密鑰啟動(dòng)的。同步流密碼體制模型

同步流密碼2/28/202413同步流密碼的密鑰序列

K=k1k2…是獨(dú)立于消息序列產(chǎn)生的。產(chǎn)生它的算法必須是確定性的，這樣才能保證解密時(shí)可以重新產(chǎn)生它，如果把K存貯起來(lái)，則沒(méi)有這個(gè)要求，但存貯和傳送長(zhǎng)密鑰序列K是不切實(shí)際的。所以，不能使用計(jì)算機(jī)的任何隨機(jī)性質(zhì)來(lái)設(shè)計(jì)產(chǎn)生密鑰序列的算法。如果密鑰序列重復(fù)或者有冗余，流密碼往往是可以破譯的。為了使它不可破譯，密鑰序列必須是長(zhǎng)度等于明文的”隨機(jī)”序列。顯然，密鑰各元素在密鑰序列中應(yīng)該均勻分布，并且沒(méi)有校長(zhǎng)的重復(fù)子序列或其他樣本。2/28/202414任何有限算法都不能產(chǎn)生真正的隨機(jī)序列。雖然不排斥由偽隨機(jī)數(shù)發(fā)生器也能生成有實(shí)用價(jià)值的密鑰序列，但常用的同余類(lèi)發(fā)生器是不能勝任這項(xiàng)工作的，甚至性能很好的偽隨機(jī)數(shù)發(fā)生器也不見(jiàn)得總能產(chǎn)生安全的密鑰序列，線性反饋移位寄存器就是一個(gè)例子。只要知道一小段明文及其相應(yīng)的密文，密碼分析者就能很容易地導(dǎo)出整個(gè)密鑰序列。由于線性反饋移位寄存器的情況反映了密鑰產(chǎn)生器危機(jī)四伏的狀況，所以在介紹較好的方法之前首先討論它。2/28/202415同步流密碼—線性反饋移位寄存器n級(jí)線性反饋移位寄存器(LFSR)由移位寄存器：和節(jié)拍序列：組成，其中和是二進(jìn)制數(shù)字。2/28/202416線性反饋移位寄存器（LFSR）

每進(jìn)行一步，都將移入密鑰序列，右移一位，從T、R導(dǎo)出的新位則插到寄存器左端(如圖)。nr1nr-...1r+nt1nt-...1t密鑰序列移位寄存器R2/28/202417令

表示R的下一狀態(tài)，則

即

其中，H為

階矩陣2/28/202418

n級(jí)線性反饋移位寄存器可以產(chǎn)生周期為2n-1(極大周期）的偽隨機(jī)位串。為此，節(jié)拍序列T必須使R循環(huán)地遍歷全部2n-1個(gè)非零的位序列。以節(jié)拍序列的元素做系數(shù)的多項(xiàng)式D．Denning指出，形如的三項(xiàng)本原多項(xiàng)式特別實(shí)用，因?yàn)樗鶎?duì)應(yīng)的反饋移位寄存器僅有兩級(jí)反饋線。極大周期LFRS序列稱為m-序列，鑒于它具有硬件實(shí)現(xiàn)速度快、周期長(zhǎng)、統(tǒng)計(jì)特性好等優(yōu)點(diǎn)，因而早期的序列密碼體制多數(shù)都以m-序列為原本。2/28/202419本原多項(xiàng)式定義1設(shè)n(n≥1)次整系數(shù)多項(xiàng)式為為本原多項(xiàng)式。定理1（高斯Gauss引理）兩個(gè)本原多項(xiàng)式的乘積仍是本原多項(xiàng)式。2/28/202420設(shè)一個(gè)0－1消息序列則：加密計(jì)算為解密計(jì)算為用線性反饋移位寄存器進(jìn)行加密和解密

LFSR的不安全性圖中種子I0即用來(lái)啟動(dòng)R進(jìn)行加密，也用來(lái)啟動(dòng)R進(jìn)行解密。2/28/202421進(jìn)行線性反饋的目的實(shí)際上是要把一個(gè)短密鑰變成一個(gè)長(zhǎng)的偽隨機(jī)序列K，以模擬一次一密的密碼。不幸的是，所產(chǎn)生的結(jié)果并不理想，若巳知2n位明文與對(duì)應(yīng)的密文，則很容易在已知明文問(wèn)題中求出節(jié)拍序列T。設(shè)：是已知明文，其對(duì)應(yīng)的密文為利用

2/28/202422可以求出密鑰序列。令列向量表示進(jìn)行第步計(jì)算時(shí)寄存器R的值，則：2/28/202423設(shè)和是下列矩陣我們有（見(jiàn)P18）:由于是非奇異的，所以為:從的第一行即可得到節(jié)拍序列。2/28/202424計(jì)算逆矩陣X-1的時(shí)間復(fù)雜度為O(n3)（n為移位寄存器的長(zhǎng)度）。在n為1000時(shí)，用每微秒執(zhí)行一條指令的計(jì)算機(jī)可在不到一天的時(shí)間內(nèi)破譯這種密碼。所以，LFSR是不安全的。著名伯利坎-梅塞（Berlekamp-Massey）算法首次揭示了m-序列的線性弱點(diǎn)，即線性復(fù)雜度低，使得m-序列自身不能直接作為密鑰流序列使用。自然地，為了彌補(bǔ)線性復(fù)雜度低的缺點(diǎn)，人們想辦法對(duì)LFSR序列進(jìn)行各種非線性改造，掩蓋LFSR序列的線性本質(zhì)。大致有三種經(jīng)典的非線性改造思想：鐘控、非線性過(guò)濾和非線性組合。2/28/202425鐘控生成器時(shí)鐘生成器的基本思想是通過(guò)改變LFSR的輸出時(shí)鐘，從位置上破壞LFSR序列的線性結(jié)構(gòu)。停走生成器（Stop-and－GoGenerator）1984年，T.Beth和F.C.Piper等人提出了第一個(gè)鐘控生成器－停走生成器，其思想是用一個(gè)LFSR的輸出比特來(lái)控制另一個(gè)LFSR的輸出時(shí)鐘。設(shè)a是控制序列，b是受控序列，則停走生成器的輸出序列Z=(Z(t))t≥0滿足：

文中研究了停走生成器的線性復(fù)雜度和周期，并指出停走生成器生成序列的統(tǒng)計(jì)特性不理想，建議在輸出序列上模2加一條m-序列。2/28/202426變步生成器變步生成器（AlternatingStepGenerators）1987年，提出了變步生成器。變步生成器由3個(gè)LFSR組成，一個(gè)為控制LFSR，另兩個(gè)為受控LFSR。設(shè)a是控制序列，b和c是受控序列，則變步生成器的輸出序列z滿足實(shí)際上，序列(bs(t))t≥0就是b受a控制的停走序列，而(ci+1-s(t))t≥0序列是c受a⊕1控制的停走序列。因而，變步生成器輸出序列就是兩個(gè)停走序列的模2和。它基本保留了停走序列周期和線性復(fù)雜度的優(yōu)良性質(zhì)，并具有理想的統(tǒng)計(jì)特性。2/28/202427非線性組合生成器非線性組合生成器的思想是將多條m-序列通過(guò)非線性的方式合并成一條密鑰流序列。圖1是非線性組合生成器的簡(jiǎn)單模型圖，其中f=f(x1,x2,…,xn)是一個(gè)n元布爾函數(shù)，密鑰流序列z=(z(t))t≥0滿足z(t)=f(a1(t),a2(t),…an(t)),t≥0。LFSR1LFSRnf=f(x1,x2,…,xn)LFSR2……za1a2an非線性組合生成器2/28/2024281987年，解決了組合生成器輸出序列的線性復(fù)雜度。記ai的線性復(fù)雜度為L(zhǎng)i，1≤i≤n，若L1，L2，…,Ln各不相同且均大于1，則密鑰流序列z的線性復(fù)雜度為f(L1,L2,…,Ln)，這里f(L1,L2,…,Ln)中的運(yùn)算是整數(shù)上的運(yùn)算。顯然，該結(jié)果表明，布爾函數(shù)f(x1,x2,…,xn)的代數(shù)次數(shù)的大小對(duì)密鑰流序列的線性復(fù)雜度影響較大。針對(duì)非線性組合生成器，1984年，提出了利用輸出序列和某些輸入分量序列之間的相關(guān)性逐個(gè)攻破的相關(guān)攻擊。1989年，對(duì)相關(guān)攻擊進(jìn)行改進(jìn)，提出快速相關(guān)攻擊，主要思想是在LFSR的連接多項(xiàng)式是低重的（非零項(xiàng)少）假設(shè)下，利用概率迭代譯碼算法。2/28/202429針對(duì)相關(guān)攻擊的特點(diǎn)，有文獻(xiàn)對(duì)組合函數(shù)引入了相關(guān)免疫的概念。為了能抵抗相關(guān)攻擊，組合函數(shù)必須具有足夠高的相關(guān)免疫階數(shù)。該文獻(xiàn)還進(jìn)一步給出代數(shù)次數(shù)和相關(guān)免疫階數(shù)之間相互制約的代數(shù)關(guān)系，結(jié)果表明相關(guān)免疫階數(shù)越大的布爾函數(shù)能達(dá)到的最大代數(shù)次數(shù)必然越小，因此，同時(shí)具有最大代數(shù)次數(shù)和最大相關(guān)免疫階數(shù)的布爾函數(shù)是不存在的。1988年，G.Z.Xiao和J.L.Massey提出了相關(guān)免疫函數(shù)的沃爾什(Walsh)譜等價(jià)條件，即肖-梅塞(Xiao-Massey)定理，之后，該結(jié)果成為研究相關(guān)免疫函數(shù)的基礎(chǔ)理論之一。2/28/202430非線性過(guò)慮生成器非線性過(guò)濾生成器的思想是對(duì)單條m-序列進(jìn)行非線性運(yùn)算得到的密鑰流序列。下圖是非線性過(guò)濾生成器的簡(jiǎn)單模型圖，LFSR的輸出序列為a，f=f(x1,x2,…,xn)是一個(gè)n元布爾函數(shù)，密鑰流序列z=(z(t))t=0滿足

z(t)=f(a(t),a(t+1),…,a(t+n-1)),t≥0LFSRf(x1,x2,…,xn)z…

非線性過(guò)濾生成器2/28/202431一些文獻(xiàn)研究了前饋序列的線性復(fù)雜度。相對(duì)于組合序列，前饋序列線性復(fù)雜度的研究困難較大，研究的進(jìn)展也較緩慢，目前對(duì)其下界的最好估計(jì)結(jié)果也是針對(duì)一類(lèi)非常特殊的前饋函數(shù)；另一反面，有文獻(xiàn)給出若前饋生成器的輸入序列a的級(jí)數(shù)L是素?cái)?shù)時(shí)，保證非線性過(guò)濾序列具有最大線性復(fù)雜度的k次非線性過(guò)濾函數(shù)占所有k次布爾函數(shù)的比例，隨L的增大，該比例接近于1，即幾乎所有k次布爾函數(shù)作用在a上得到的前饋序列具有最大線性復(fù)雜度。2/28/2024321985年，描述了非線性過(guò)濾生成器的相關(guān)攻擊。1990年，對(duì)非線性過(guò)濾生成器應(yīng)用了快速相關(guān)攻擊。有學(xué)者指出，非線性過(guò)濾生成器可能存在其他的相關(guān)性，從而可以用來(lái)提高相關(guān)攻擊的成功性。1996年，提出了可逆攻擊(InversionAttack)思想，對(duì)一類(lèi)特殊的前饋函數(shù)進(jìn)行了分析，并給出非線性過(guò)濾生成器抵抗快速相關(guān)攻擊，條件相關(guān)攻擊，可逆攻擊的一些設(shè)計(jì)準(zhǔn)則。2000年，又進(jìn)一步推廣可逆攻擊思想，對(duì)一般前饋攻擊序列進(jìn)行了有效分析。

2/28/202433同步流密碼—輸出分組反饋方式線性反饋移位寄存器加密的弱點(diǎn)在于它的線性性質(zhì)。為了得到較高的安全性，必須使用非線性變換產(chǎn)生密鑰序列。非線性分組密碼(如DES密碼)的加密變換就是非線性變換，因此很適合于產(chǎn)生密鑰序列。下圖說(shuō)明了如何利用輸出分組反饋方式(OFM)產(chǎn)生密鑰序列。2/28/202434分組加密算法EB的密鑰為B，反饋寄存器R為加密變換提供輸入。在第i次迭代時(shí)，EB(R)的輸出分組的低端（最右）字符變成第i個(gè)密鑰字符Ki。同時(shí)，整個(gè)分組又通過(guò)R反饋回來(lái)作為下一次迭代的輸入。2/28/202435需要注意的是，每個(gè)Ki是一個(gè)字符，而不是一位。這樣可以減少用EB加密的次數(shù)，因?yàn)镋B加密一次比線性反饋移位寄存器迭代一次消耗的時(shí)間要多得多。明文消息被分成連續(xù)的字符序列，在按上述方式產(chǎn)生密鑰序列的同時(shí)，消息序列的各字符被生成的密鑰字符加密。接受端解密的情形也與發(fā)送端完全類(lèi)同。上述這種反饋方式也叫內(nèi)反饋，因?yàn)榉答伆l(fā)生在產(chǎn)生密鑰序列的過(guò)程內(nèi)部。與此相反，在自同步方法中，反饋是從密碼文中導(dǎo)出的，因而也叫外反饋。2/28/202436同步流密碼—計(jì)數(shù)器方法Diffie和Hellman提出了另一種產(chǎn)生密鑰序列的方案——計(jì)數(shù)器方法。它不把的輸出重新送回，而是用計(jì)數(shù)器產(chǎn)生連續(xù)的輸入分組(如圖)。用計(jì)數(shù)器產(chǎn)生同步流密碼2/28/202437

在計(jì)數(shù)器方法中，只要把計(jì)數(shù)器置為I0+i-1就能不生成前i-1個(gè)密鑰字符而直接產(chǎn)生第i個(gè)密鑰字符ki。這種能力對(duì)直接訪問(wèn)文件中的第i個(gè)字符特別有用，而在輸出分組反饋方法中，不計(jì)算前i-1個(gè)密鑰字符就無(wú)法產(chǎn)生第i個(gè)密鑰字符。

2/28/202438計(jì)數(shù)器式同步流密碼具有抵抗密文搜索的能力，因?yàn)槊魑男蛄兄邢嗤淖址幻荑€序列的不同部分加密，產(chǎn)生不同的密文。它也有能力抵御假密文的摻入、密文的挪用和刪除，因?yàn)樵黾雍蛣h除密文序列都會(huì)破壞同步，使密文無(wú)法解密還原成明文。計(jì)數(shù)器式同步流密碼還有不傳播錯(cuò)誤的優(yōu)點(diǎn)，一次傳輸錯(cuò)誤只影響—個(gè)字符．不會(huì)影響到以后的字符。但這也是一個(gè)缺點(diǎn)，因?yàn)檫@使得敵方篡改單個(gè)密文字符的活動(dòng)不太容易覺(jué)察?？梢岳脦荑€的查錯(cuò)碼或非線性查錯(cuò)碼克服這個(gè)缺點(diǎn)。2/28/202439同步流密碼的加密變換可以有多種選擇，只要保證變換是可逆的即可。實(shí)際使用的數(shù)字保密通信系統(tǒng)一般都是二元系統(tǒng)，因而在有限域GF(2)上討論的二元加法流密碼是最受歡迎的流密碼體制，其加密變換可表示為2/28/202440加法流密碼體制模型2/28/202441自同步流密碼自同步流密碼由加密過(guò)程中的當(dāng)前密文字符的前n個(gè)字符(n為常數(shù))導(dǎo)出各密鑰字符。這一思想起源于16世紀(jì)的維吉尼亞（Vigenere）第二密碼。

Vigenere第二密碼的密鑰由根密鑰字符I0后附加明文序列構(gòu)成，即：2/28/202442當(dāng)然，用今天的標(biāo)準(zhǔn)來(lái)看，這些密碼不很安全，特別是維吉尼亞（Vigenere）第二密碼，它的密鑰暴露在密文中，使敵方的密碼分析者可以相當(dāng)容易地用僅有密文問(wèn)題破譯。但是，Vigenere發(fā)現(xiàn)了從被加密或加密后的數(shù)據(jù)中可以得到不重復(fù)的密鑰序列，這對(duì)密碼學(xué)無(wú)疑是一項(xiàng)重大貢獻(xiàn)。2/28/202443維吉尼亞（Vigenere）第二密碼是一種自同步的自身密鑰密碼，各密鑰字符將由它前面那個(gè)密文算出，所用的計(jì)算就是簡(jiǎn)單的相等運(yùn)算。由于各密鑰字符由它前面的密文字符算出，所以它函數(shù)依賴于根密鑰和前面的密文字符。這樣，每個(gè)密文字符都函數(shù)依賴于它前面的整個(gè)消息。這種現(xiàn)象被有的密碼學(xué)家稱力“扭曲延伸”。由于明文的統(tǒng)計(jì)性質(zhì)在密文中得到充分?jǐn)U散，從而增大了密碼分析的難度。2/28/202444自同步流密碼—密文反饋Vigenere第二密碼的密鑰暴露在密文序列中導(dǎo)致了它的脆弱性。然而，如果不取簡(jiǎn)單的恒等運(yùn)算，而讓密文字符被非線性分組密碼體制加密之后再產(chǎn)生密鑰字符，那么就可以克服這個(gè)缺陷。因?yàn)槊芪淖址M(jìn)入了反饋回路，所以這種做法叫做密文反饋(CFB)。由于這種反饋發(fā)生在產(chǎn)生密鑰序列的過(guò)程的外部，所以也叫外反饋。在這種加密方式中，每個(gè)密文字符函數(shù)依賴于(鏈接到)前面的密文字符，因此也被稱為密文鏈接。2/28/202445

下圖說(shuō)明了密文反饋方式是如何產(chǎn)生密鑰序列的。密文反饋方式（CFB）的自同步流密碼2/28/202446

反饋寄存器R是一個(gè)移位寄存器．它用作加密變換的輸入。輸出分組中最右端的字符被用做密鑰字符，加密明文序列中的，產(chǎn)生密文符。輸出分組中的其他字符則被舍棄。密文字符一方面進(jìn)入密文序列傳送給接收者，同時(shí)還進(jìn)入移位寄存器R的左端。與前面介紹的一樣，R也是由種子啟動(dòng)的。2/28/202447用密文反饋方式時(shí)，傳輸錯(cuò)誤將影響反饋回路。若密文字符在傳輸中改變或丟失，則在錯(cuò)誤字符移出寄存器之前，接收端的移位寄存器中的內(nèi)容將不同于發(fā)送端中的內(nèi)容，因此對(duì)密文不能正確解密。由于移位寄存器在n(n為每分組的字符數(shù))次循環(huán)后能夠同步，所以一個(gè)錯(cuò)誤至多影響n個(gè)字符。在此之后，密文又將能夠正常解密。自同步流密碼的特點(diǎn)2/28/202448

密文反饋方式也象計(jì)數(shù)器方法一樣有能力直接隨機(jī)的訪問(wèn)文件中的數(shù)據(jù)。為了解密第i個(gè)密文字符，只要將它前面的n個(gè)密文字符ci-n,…,ci-1裝入反饋寄存器，然后執(zhí)行一次反饋回路的循環(huán)，求得Ki即可。用密文反饋方式可以在文件中進(jìn)行插入和刪除，無(wú)需重新加密整個(gè)文件。但是插入、刪除位置后面的所有字符卻必須重新加密，否則后面的字符分組將無(wú)法解密。如果在加密時(shí)，對(duì)每個(gè)記錄都重新啟動(dòng)一次反饋回路，那就可以把重新加密限制在單個(gè)記錄的范圍內(nèi)。當(dāng)然，這樣做會(huì)暴露出相同的記錄來(lái)，但是只要在所有記錄前面加上一個(gè)隨機(jī)的字符串，在記錄解密后進(jìn)行數(shù)據(jù)處理時(shí)再把它們刪去，就可以把相同記錄隱蔽起來(lái)。2/28/202449自同步流密碼能夠抵抗密文搜索，因?yàn)橄⑿蛄械南嗤糠直幻荑€序列的不同部分加密。自同步流密碼也能抵抗所有破壞真實(shí)性的活動(dòng)，因?yàn)槊芪牡娜魏胃淖兌紩?huì)影響密鑰序列。由于最后一個(gè)分組的密文函數(shù)依賴于整個(gè)消息，所以可以用它做整個(gè)消息的校驗(yàn)和。2/28/202450校驗(yàn)和是指函數(shù)依賴于消息中的每一位的任何定長(zhǎng)分組，所以不同的消息幾乎總有不同的校驗(yàn)和。為了驗(yàn)證真實(shí)性，總是把校驗(yàn)和加在消息的末尾。計(jì)算校驗(yàn)和的方法應(yīng)能保證兩個(gè)不同消息(至少有一位不同)產(chǎn)生同一校驗(yàn)和的概率僅為2-n(n是校驗(yàn)和的長(zhǎng)度)。在不要求保密性，只要求真實(shí)性的場(chǎng)合，密文反饋方式可用來(lái)計(jì)算明文數(shù)據(jù)的校驗(yàn)和。盡管校驗(yàn)和通常不能象對(duì)整個(gè)消息進(jìn)行真實(shí)性加密那么可靠，但是對(duì)于許多要求不太高的應(yīng)用卻已經(jīng)足夠了。

2/28/202451流密碼流密碼介紹流密碼的分類(lèi)一種流密碼算法——RC4流密碼和分組密碼的比較流密碼的設(shè)計(jì)準(zhǔn)則混沌變碼本流密碼2/28/202452流密碼算法RC4

RC4是RonRivest在1987年為RSA數(shù)據(jù)安全公司開(kāi)發(fā)的一個(gè)密鑰長(zhǎng)度可變的序列密碼。已經(jīng)應(yīng)用于SSL/TLS協(xié)議，WEP（IEEE802.11)。在開(kāi)始的七年中它有專利保護(hù),算法的細(xì)節(jié)僅在簽署一個(gè)保密協(xié)議后才能得到。1994年9月，有人把它的源代碼仍匿名張貼到Cypherpunks郵件列表中，從而把這個(gè)算法泄露了出去。盡管RSA公司宣稱即使公開(kāi)代碼它仍然是商業(yè)秘密，但為時(shí)己晚。2/28/202453RC4的特點(diǎn)RC4具有以下特點(diǎn)：面向字節(jié)的流密碼；密鑰序列獨(dú)立于明文；RSA聲稱RC4對(duì)線性和差分分析具有免疫力；由于RC4是流密碼，避免了重復(fù)使用密鑰；所需要代碼少；加密速度很快，大約比DES快10倍；有一個(gè)8×8的S盒，所有項(xiàng)都是數(shù)字0到255的置換，并且這個(gè)置換是一個(gè)長(zhǎng)度可變的密鑰函數(shù)；密鑰長(zhǎng)度可變。2/28/202454RC4算法的示意圖2/28/202455S和T的初始化對(duì)S盒進(jìn)行線性填充：用密鑰K填充另一個(gè)256字節(jié)的數(shù)組T，不斷重復(fù)密鑰直至填充到整個(gè)數(shù)組中：T[0],T[1],…,T[255]。S盒初始化2/28/202456將指針j設(shè)為0，對(duì)i＝0至255完成以下操作：交換和（如下圖所示）S盒的初始置換2/28/202457產(chǎn)生隨機(jī)密鑰

設(shè)置i和j的初值均為0。產(chǎn)生一個(gè)字節(jié)隨機(jī)密鑰k的步驟如下：交換和用以產(chǎn)生下一字節(jié)隨機(jī)密鑰。產(chǎn)生密鑰流2/28/202458

RSADSI聲稱，RC4對(duì)差分攻擊和線性分析具有免疫力，沒(méi)有短循環(huán)，且具有高度非線性，尚無(wú)公開(kāi)的分析結(jié)果。它大約有個(gè)可能的狀態(tài)。各S在i和j的控制下卷入加密。指標(biāo)i保證每個(gè)元素變化，指標(biāo)j保證元素的隨機(jī)改變，算法簡(jiǎn)單，易于編程實(shí)現(xiàn)。2/28/202459

可以設(shè)想利用更大的盒和更長(zhǎng)的字。當(dāng)然不一定要采用16×16的S盒，否則初始化工作將太漫長(zhǎng)。40比特密鑰的RC4允許出口，但其安全性是無(wú)保證的。已有采用RC4算法的商業(yè)產(chǎn)品，其中包括LottusNotes，Apple公司的AOEC，以及OracleSecureSQL，它也是美國(guó)移動(dòng)通信技術(shù)公司的CDPD系統(tǒng)的一個(gè)組成部分。2/28/202460RC－4自身的不足

2001年Fluhrer、Mantin、Shamir發(fā)表了論文，提出了兩種攻擊RC4算法的方法：InvarianceWeakness和IVWeakness攻擊，合稱FMS攻擊方法。其中InvarianceWeakness是針對(duì)RC4自身的一種相關(guān)密鑰攻擊方法。由此分析可知，RC4算法有一簇弱密鑰。當(dāng)RC4的輸入密鑰為弱密鑰時(shí)，RC4輸出的偽隨機(jī)密鑰序列的頭若干個(gè)字節(jié)的最低有效q比特Bq-1,Bq-2,…,B0以一定概率符合某種已知的特定格式，即具有格式化前綴。所以，這些密鑰的脆弱性導(dǎo)致輸出的偽隨機(jī)密鑰序列具有易識(shí)別的格式化前綴，稱之為“InvarianceWeakness”。有人提出了基于“InvarianceWeakness”的攻擊RC4的方法，其基本思想是：通過(guò)捕獲具有格式化前綴的輸出，反推出此時(shí)輸入的弱密鑰。2/28/202461流密碼流密碼介紹流密碼的分類(lèi)流密碼的設(shè)計(jì)準(zhǔn)則流密碼和分組密碼的比較一種流密碼算法——RC4混沌變碼本流密碼2/28/202462流密碼的設(shè)計(jì)準(zhǔn)則大多數(shù)實(shí)際的序列密碼都圍繞線性反饋移位寄存器（LFSR）而設(shè)計(jì)。在早期，它們非常容易構(gòu)造。一個(gè)移位寄存器和一串異或門(mén)。一個(gè)基于LFSR的序列密碼僅用一些邏輯門(mén)就能給你較高的安全性。LFSR的問(wèn)題是用軟件實(shí)現(xiàn)的效率非常低。想要避免稀疏的反饋多項(xiàng)式——它們很容易遭到相關(guān)攻擊——但是稠密的反饋多項(xiàng)式效率很低。而且序列密碼一次只輸出一個(gè)位。另一方面，令人吃驚的是大量看上去很復(fù)雜的基于移位寄存器的密鑰發(fā)生器均被破譯了。2/28/202463實(shí)際中，設(shè)計(jì)流密碼的目標(biāo)主要有兩個(gè)：一個(gè)是根據(jù)某些度量指標(biāo)（諸如周期、線件復(fù)雜度等）研制設(shè)汁方法和具有可證明特性的模塊；另一個(gè)是研究密碼分析原理，并建立一些使得基于這些原理的攻擊變得不可行的設(shè)計(jì)準(zhǔn)則。為了抵抗基于這些基本原理的密碼分析，人們對(duì)密鑰流生成器已提出了一系列設(shè)計(jì)準(zhǔn)則。2/28/2024641．為防止強(qiáng)力攻擊,密鑰應(yīng)該足夠長(zhǎng).不小于128位；2．周期準(zhǔn)則：周期長(zhǎng)度不小于1016；3．線性復(fù)雜度準(zhǔn)則：2/28/202465線性復(fù)雜性用于分析基于LFSR的一個(gè)重要的公認(rèn)準(zhǔn)則是線性復(fù)雜性。在序列密碼（流密碼）理論中線性復(fù)雜度是序列密碼體制的一個(gè)重要指標(biāo)，無(wú)論在密碼的設(shè)計(jì)與分析中，任何一個(gè)新的密碼體制的出現(xiàn)，首先要分析它的線性復(fù)雜度。線性復(fù)雜度是度量有限長(zhǎng)或周期序列的隨機(jī)性的一種指標(biāo)，實(shí)際上它衡量了序列的線性不可預(yù)測(cè)性。一個(gè)序列的線性復(fù)雜度可以利用B-M算法求得。2/28/202466線性復(fù)雜性的重要性體現(xiàn)在：一個(gè)被稱做B-M的簡(jiǎn)單算法，在檢測(cè)密鑰序列的2n個(gè)位后就能夠產(chǎn)生LFSR。一旦你產(chǎn)生了這個(gè)LFSR，你就破譯了這個(gè)序列密碼。在任何情況下，都必須記?。焊叩木€性復(fù)雜性并不代表有一個(gè)安全的發(fā)生器，而一個(gè)低的線性復(fù)雜性則表明它肯定不安全。人們圍繞線性復(fù)雜度進(jìn)行了一系列的研究，提出了各種衡量隨機(jī)性的指標(biāo)，其中線性復(fù)雜度輪廓是一種易于計(jì)算的指標(biāo)。2/28/202467線性復(fù)雜度輪廓

定義：設(shè)aN=a0,a1,…,aN-1是q元域GF(q)上的一個(gè)長(zhǎng)度為N的序列，Li=L(ai)是子序列ai=a0,a1,…,ai-1的線性復(fù)雜度，則稱序列L1,L2,…,LN是序列aN

的線性復(fù)雜度輪。2/28/202468

盧珀研究了輪廓隨n增長(zhǎng)時(shí)的變化情況。他證明了二元隨機(jī)序列的線性復(fù)雜度曲線輪廓應(yīng)近似地按變化，但這種變化應(yīng)是無(wú)規(guī)則的。線性復(fù)雜度輪廓在一定程度上反映了序列（有限或無(wú)限）線性復(fù)雜度穩(wěn)定性程度。安全的密鑰序列其線性復(fù)雜度輪廓應(yīng)接近直線(表示序列的長(zhǎng)度)。2/28/2024694．統(tǒng)計(jì)準(zhǔn)則：比如理想的游程分布等；理想的游程分布

Golomb定義一個(gè)二元的真正隨機(jī)序列，具有下面三條隨機(jī)特性：Ⅰ.序列中1的個(gè)數(shù)和0的個(gè)數(shù)接近相等；Ⅱ.序列的自相關(guān)函數(shù)，當(dāng)時(shí)延為零時(shí)最高，而當(dāng)時(shí)延增加時(shí)迅速下降；Ⅲ.把連在一起的1（或0）稱為游程，其中1（或0）的個(gè)數(shù)稱為此游程的長(zhǎng)度。其中長(zhǎng)為1的游程的長(zhǎng)度約占游程總數(shù)的1/2，長(zhǎng)為2的游程約占游程總數(shù)的1/22，長(zhǎng)為3的約占游程總數(shù)的1/23，……。在同樣長(zhǎng)度的所有游程中，1游程和0游程大致各占一半。上述三條是真正的二元隨機(jī)序列的特性。這三個(gè)特性實(shí)際上描述了一個(gè)真隨機(jī)二元序列的0（1）串分布特性。密鑰流應(yīng)該盡可能地接近于一個(gè)真正的隨機(jī)數(shù)流的特征.2/28/202470

5．混淆準(zhǔn)則（密鑰）：密鑰流中每“比特值依賴于所有或大多數(shù)根密鑰的比特值，混淆是一個(gè)復(fù)雜變換。6．?dāng)U散準(zhǔn)則（明文）：子結(jié)構(gòu)的冗余度必須擴(kuò)散到大范圍的統(tǒng)計(jì)中去。

7．函數(shù)的非線性準(zhǔn)則：比如相關(guān)免疫性等。2/28/202471

密碼設(shè)計(jì)者通過(guò)采用非線性方法組合幾個(gè)輸出序列得到高的線性復(fù)雜性。這里的危險(xiǎn)性在于一個(gè)或者更多的內(nèi)部輸出序列與組合密碼序列間所存在的相關(guān)性，并且易受攻擊。常常將這稱做相關(guān)攻擊或分割解決攻擊。相關(guān)攻擊的基本思想是識(shí)別發(fā)生器的輸出與它內(nèi)部的某一塊之間的相關(guān)性。通過(guò)觀察輸出序列，獲得關(guān)于其內(nèi)部輸出的一些信息。用這些信息和其他的相關(guān)性，搜索其他內(nèi)部輸出的相關(guān)性，直到整個(gè)發(fā)生器被破譯。相關(guān)免疫性2/28/202472測(cè)試指標(biāo)D.H.Lehmer在1951對(duì)隨機(jī)序列給出了一個(gè)模糊的定義：在一個(gè)序列中，每一項(xiàng)對(duì)于非初始項(xiàng)來(lái)說(shuō)是不可預(yù)測(cè)的，其統(tǒng)計(jì)特性可以通過(guò)一些由統(tǒng)計(jì)學(xué)家所沿用且與序列的用途有關(guān)的檢驗(yàn)。J.N.Franklin在1962年對(duì)D.H.Lehmer的定義進(jìn)行了推廣。隨后，D.E.Knuth在綜合研究上述定義的基礎(chǔ)上，提出了頻數(shù)檢驗(yàn)，序列檢驗(yàn)，間隔檢驗(yàn)，撲克檢驗(yàn)等11種對(duì)序列的隨機(jī)性進(jìn)行統(tǒng)計(jì)檢驗(yàn)的標(biāo)準(zhǔn)。2/28/202473美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所在2003年頒布了用于密碼學(xué)的隨機(jī)和偽隨機(jī)數(shù)統(tǒng)計(jì)測(cè)試標(biāo)準(zhǔn)“SpecialPublication800-22”（SP800-22）。這是迄今為止使用最為廣泛的檢驗(yàn)標(biāo)準(zhǔn)之一。2004年，歐洲在NESSIE密碼計(jì)劃中公布了一套隨機(jī)性檢驗(yàn)標(biāo)準(zhǔn)。此外，還包括G.Marsaglia所提出的DIEHARD檢測(cè)方法等一些被公認(rèn)的準(zhǔn)則。2/28/202474SpecialPublication800-22單比特頻數(shù)測(cè)試游程測(cè)試二進(jìn)制矩陣秩測(cè)試非重疊塊比配測(cè)試Maurer的通用統(tǒng)計(jì)測(cè)試串行檢測(cè)累加和測(cè)試Lempel-Ziv壓縮測(cè)試分塊塊內(nèi)頻數(shù)測(cè)試塊內(nèi)長(zhǎng)游程測(cè)試離散傅立葉變換測(cè)試重疊塊比配測(cè)試線性復(fù)雜度測(cè)試近似熵檢測(cè)隨機(jī)游動(dòng)測(cè)試隨機(jī)游動(dòng)狀態(tài)頻數(shù)測(cè)試2/28/202475

任何安全的密鑰流生成器必須滿足上述設(shè)計(jì)準(zhǔn)則。但值得注意的是設(shè)計(jì)準(zhǔn)則只能部分地針對(duì)一般的密碼分析原理。一個(gè)滿足所有設(shè)計(jì)準(zhǔn)則的生成器也可能是不安全的。換句話說(shuō)，這些設(shè)計(jì)準(zhǔn)則是密鑰流生成器安全的必要條件而非充分條件。2/28/202476流密碼流密碼介紹流密碼的分類(lèi)一種流密碼算法——RC4流密碼的設(shè)計(jì)準(zhǔn)則流密碼和分組密碼的比較混沌變碼本流密碼2/28/202477分組密碼與流密碼的比較基本思想的區(qū)別

分組密碼的的基本思想是用相同的密鑰K對(duì)明文分組進(jìn)行加密。密文分組是通過(guò)如下方式對(duì)明文組加密得到流密碼的基本思想是利用密鑰K產(chǎn)生一個(gè)密鑰流，并使用如下規(guī)則加密明文串得到2/28/202478本質(zhì)區(qū)別

分組密碼與流密碼的區(qū)別就在于記憶性。流密碼的滾動(dòng)密鑰z0＝f(k,σ0)，由函數(shù)f、密鑰k和指定的初態(tài)σ0完全確定。此后，由于輸入加密器的明文X可能影響加密器中內(nèi)部記憶元件的存儲(chǔ)狀態(tài)，因而σi(i＞0)可能依賴于參數(shù)k,σ0,x0,x1,…,xi-1等。2/28/2024792/28/202480速度

流密碼幾乎總是比分組密碼快，通常使用的代碼也比分組密碼少得多。最常用的流密碼RC4，大概比最快的分組密碼至少還要快兩倍。RC4可以由30行代碼寫(xiě)成，而大多數(shù)分組密碼需要數(shù)百行的代碼。奔騰II上對(duì)稱密碼的速度對(duì)比2/28/202481在不同的情況下的選擇

對(duì)于分組密碼，你可以重復(fù)使用密鑰。記住，流密碼更像一次一密?！耙淮涡浴币馕吨阒荒苁褂妹艽a本一次。類(lèi)似地，流密碼密鑰也應(yīng)只使用一次。一般情況下，這不成問(wèn)題，但有時(shí)有必要使用同一密鑰加密許多東西。例如，一個(gè)電子商務(wù)公司可能有一個(gè)客戶信息數(shù)據(jù)庫(kù)，其中包括信用卡號(hào)。與其用不同的密鑰加密每個(gè)條目(由此便要管理成百上千的密鑰)，不如用一個(gè)密鑰加密所有的條目。當(dāng)需要某一條目時(shí)，就用這個(gè)唯一的密鑰將之解密。當(dāng)只有一個(gè)密鑰需要管理時(shí)，密鑰管理相當(dāng)容易。2/28/202482標(biāo)準(zhǔn)化另一因素是標(biāo)準(zhǔn)化。每個(gè)人都有兩個(gè)算法——DES和AES———它們均是分組密碼。由于互操作性的原因，你可能想要一個(gè)廣泛使用的算法。你的數(shù)據(jù)連接的另一端可能有也可能沒(méi)有RC4，但幾乎肯定會(huì)有DES和AES。你選擇分組密碼是因?yàn)樗菢?biāo)準(zhǔn)的。換句話說(shuō)，沒(méi)有哪種更好。若你需要重復(fù)使用密鑰，就使用分組密碼。如果必須保證互用性，那么最好用AES。否則，就使用流密碼。下表列出一些應(yīng)用及你可能想要使用的每一種密碼類(lèi)型。2/28/202483對(duì)比選擇一覽表2/28/202484流密碼介紹流密碼的分類(lèi)一種流密碼算法——RC4流密碼的設(shè)計(jì)準(zhǔn)則流密碼和分組密碼的比較混沌變碼本流密碼2/28/202485序列密碼的發(fā)展現(xiàn)狀基于線性反饋移位寄存器的序列密碼的顯著特點(diǎn)是線性部分和非線性部分相對(duì)獨(dú)立，通過(guò)各種非線性手段改變LFSR序列的線性本質(zhì)，提高其線性復(fù)雜度。然而，隨著研究的深入和攻擊手段的改進(jìn)，尤其是相關(guān)攻擊、快速相關(guān)攻擊、代數(shù)攻擊和快速代數(shù)攻擊的發(fā)展，逐步認(rèn)識(shí)到這種線性部分和非線性部分相對(duì)獨(dú)立的設(shè)計(jì)思想，根本無(wú)法完美掩蓋LFSR序列的線性本質(zhì)，LFSR的線性關(guān)系總會(huì)通過(guò)某種相關(guān)性暴露在密鑰流序列中。2/28/202486序列密碼的發(fā)展有兩個(gè)方面的顯著特點(diǎn)：隨著對(duì)非線性序列認(rèn)識(shí)的深入，用于構(gòu)造序列密碼的序列源有了根本的變化——從簡(jiǎn)單的對(duì)線性序列進(jìn)行非線性改造轉(zhuǎn)向開(kāi)始探尋直接快速有效產(chǎn)生非線性序列的方法。序列密碼的發(fā)展逐步趨于軟件化（面向快速軟件實(shí)現(xiàn)）、分組化（密鑰流序列以字節(jié)為單位輸出，而不是單比特）和標(biāo)準(zhǔn)化。2/28/202487混沌變碼本流密碼的總體方案

基于混沌變碼本流密碼系統(tǒng)框圖如圖所示。該系統(tǒng)由驅(qū)動(dòng)部分，碼本變換部分和輸出部分組成。它利用混沌系統(tǒng)產(chǎn)生驅(qū)動(dòng)序列元素，通過(guò)變換碼本,可產(chǎn)生良好密碼學(xué)特性的密鑰流，將與明文相異或可產(chǎn)生相應(yīng)的密文。輸出部分非線性變換部分混沌驅(qū)動(dòng)部分改進(jìn)混沌映射采樣組合編碼初始化混沌軌道碼本驅(qū)動(dòng)序列變碼本按位異或密鑰序列信息流輸出初始化混沌變碼本流密碼系統(tǒng)框圖2/28/202488驅(qū)動(dòng)部分驅(qū)動(dòng)部分為碼本變換提供指令，并與碼本相互作用產(chǎn)生密鑰流。驅(qū)動(dòng)部分框圖2/28/202489由于有限精度效應(yīng)，導(dǎo)致數(shù)字化混沌系統(tǒng)的特性退化：短周期問(wèn)題(shortcyclelength)、不理想的軌道分布和相關(guān)性質(zhì)(non-idealdistributionsandcorrelationfunctions)。該問(wèn)題是目前混沌系統(tǒng)從理論走向應(yīng)用中的出現(xiàn)的一大瓶頸，它所帶來(lái)的混沌密碼系統(tǒng)安全的不穩(wěn)定性嚴(yán)重影響著混沌密碼系統(tǒng)的實(shí)用化進(jìn)程。

數(shù)字化混沌系統(tǒng)的特性退化問(wèn)題2/28/202490例如：對(duì)于一維Logistic映射

按照雙精度格式，在IntelPentium4計(jì)算機(jī)中把映射的初值寫(xiě)為如下形式：逐個(gè)分析以這些為初值所得到的軌道。實(shí)驗(yàn)發(fā)現(xiàn)，不管如何變化，按照迭代式反復(fù)迭代，其軌跡都有會(huì)進(jìn)入周期軌道甚至不動(dòng)點(diǎn)（即周期為1）。理論上，Logistic映射在區(qū)間[-1,1]上，周期點(diǎn)的測(cè)度為0，非周期點(diǎn)的測(cè)度為1。但是實(shí)驗(yàn)結(jié)果卻與理論分析大相徑庭。下圖為短周期問(wèn)題的示意圖。短周期問(wèn)題的示意圖數(shù)字化混沌系統(tǒng)的特性退化問(wèn)題2/28/202491一種改善混沌特性退化問(wèn)題的方案10進(jìn)制轉(zhuǎn)換為2進(jìn)制進(jìn)行混沌映射2進(jìn)制轉(zhuǎn)換為N進(jìn)制N進(jìn)制轉(zhuǎn)換為2進(jìn)制初值N進(jìn)制轉(zhuǎn)換為10進(jìn)制輸出一種改善特性退化問(wèn)題的思考2/28/202492

將混沌的映射區(qū)間按照從左到右的順序劃分為個(gè)-子域，并給-子域指定十進(jìn)制序數(shù)，將個(gè)-子域記為 ，根據(jù)混沌遍歷性可推出以下結(jié)論：

根據(jù)上式對(duì)混沌映射的輸出值進(jìn)行編碼，輸出得到驅(qū)動(dòng)序列

混沌驅(qū)動(dòng)序列的采樣和編碼2/28/202493碼本變換碼本變換部分的輸入是驅(qū)動(dòng)序列，輸出是密鑰流。驅(qū)動(dòng)序列在該部分查動(dòng)態(tài)變換的碼本得到密鑰流，同時(shí)對(duì)碼本進(jìn)行變換。碼本變換部分框圖2/28/202494

碼本由碼位和碼字兩部分組成，記為

。其中碼位為0，1，2，…，255。碼字為0，1，2，…，255的某一個(gè)排列{K0,K1,…,K254,K255}。由此構(gòu)成一個(gè)256元置換，所有這些256元置換構(gòu)成對(duì)稱群。碼本2/28/202495將驅(qū)動(dòng)序列的元素作為碼位，在當(dāng)前碼本中查得碼字，該碼字就是用來(lái)對(duì)明文進(jìn)行加密的密鑰。密鑰流的產(chǎn)生2/28/202496

碼本變換是一個(gè)彈洗操作和一個(gè)切牌操作的復(fù)合，該復(fù)合的集合稱為碼本變換（洗牌變換）操作集E?？梢宰C明本密碼系統(tǒng)中E是對(duì)稱群的一個(gè)生成系。

碼本變換（洗牌變換）2/28/202497輸出部分

將密鑰流在輸出部分和明文作異或運(yùn)算得到密文。密鑰序列＋明文(密文)序列密文(明文)序列加解密框圖2/28/202498理論分析驅(qū)動(dòng)部分的基本定理定理1.1單個(gè)混沌映射采樣編碼后得到的序列服從均勻分布。定理1.2單個(gè)混沌映射采樣編碼后得到的序列各元素之間相互獨(dú)立。定理1.3經(jīng)過(guò)變換順序后輸出的驅(qū)動(dòng)序列服從均勻分布。定理1.4經(jīng)過(guò)變換順序后輸出的驅(qū)動(dòng)序列各元素之間相互獨(dú)立。定理1.5驅(qū)動(dòng)序列出現(xiàn)周期的概率趨向于零。

2/28/202499碼本變換部分的基本定理定理2.1

如果給定的碼本變換操作集E是對(duì)稱群S的一個(gè)生成系且不是該對(duì)稱群的任何子群的陪集，那么經(jīng)過(guò)足夠多的碼本變換之后，n!個(gè)碼本狀態(tài)出現(xiàn)的概率是相等的。這意味著可以遍歷整個(gè)群，在n=256的情況下可用的碼本有256!個(gè)，這樣的碼本空間非常巨大，足以抵抗窮舉攻擊。2/28/2024100推論2.1

在定理2.1的前提下，碼本變換操作集可以更換、增加或刪除其中的某些操作，設(shè)計(jì)出新的碼本變換操作集。（根據(jù)對(duì)稱群的生成系的性質(zhì)，會(huì)有不同的碼本變換操作集。因此，本密碼系統(tǒng)的碼本變換操作集在滿足定理2.1的前提下，可以更換、增加或刪除其中的某些操作。）定理2.2

碼本序列出現(xiàn)周期的概率趨向于零。2/28/2024101密鑰流的基本定理定理3.1密鑰流在上0,1,…,254,255均勻分布。定理3.2密鑰流的各元素之間相互獨(dú)立。定理3.3密鑰流中出現(xiàn)周期的概率趨向于零。推論3.1有關(guān)密鑰流性質(zhì)的證明過(guò)程（定理3.1，3.2）并不涉及具體的碼本變換規(guī)則，只要求碼本變換操作集是對(duì)稱群的一個(gè)生成系且不是它的任何子群的陪集。這就意味著碼本變換的規(guī)則是可變的。本密碼系統(tǒng)也就可以衍生出很多變體2/28/2024102實(shí)驗(yàn)分析不同進(jìn)制下混沌系統(tǒng)的周期表

不同進(jìn)制下混沌系統(tǒng)的周期

進(jìn)制迭代次數(shù)周期進(jìn)入點(diǎn)1212億163,260,359161,108,4621412億401,792,765347,494,0023032億2,810,624,426116,120,2803134億1,960,831,597915,254,7519624億193,190,033261,541,91211224億190,000,641207,028,36912724億1,641,371,37813,546,54925524億197,150,322248,091,9872/28/2024103分?jǐn)?shù)維以下是對(duì)初值為0.5451254的8個(gè)不同進(jìn)制的迭代序列進(jìn)行檢測(cè)的結(jié)果。從對(duì)8種進(jìn)制進(jìn)行檢測(cè)的結(jié)果中可以看到，它們的分?jǐn)?shù)維與10進(jìn)制的大致相同（計(jì)算關(guān)聯(lián)維的算法存在5-10％的誤差）。進(jìn)制的不同對(duì)其復(fù)雜度不會(huì)有太明顯的影響。

表A2.2(a)10進(jìn)制分?jǐn)?shù)維

嵌入維10-110-22維0.901610.893853維0.962550.93517表A2.2(b)12，14進(jìn)制分?jǐn)?shù)維

嵌入維12-112-214-114-22維0.927660.929450.939370.915903維0.976050.981140.991290.985702/28/2024104表A2.2(c)30，31進(jìn)制分?jǐn)?shù)維

嵌入維30-130-231-131-22維0.908380.929180.916550.892803維0.969940.997220.971510.94080表A2.2(d)96，112進(jìn)制分?jǐn)?shù)維

嵌入維96-196-2112-1112-22維0.878820.938930.932860.897683維0.938800.905501.001240.95059表A2.2(e)127，255進(jìn)制分?jǐn)?shù)維

嵌入維127-1127-2255-1255-22維0.936660.910910.899360.923003維1.004640.971780.962770.975222/28/2024105自相關(guān)性對(duì)每個(gè)進(jìn)制的兩段分別取長(zhǎng)度為40,000的序列進(jìn)行檢測(cè)得到如下結(jié)果。從以下測(cè)試結(jié)果可以看出，它們的自相關(guān)函數(shù)近似沖激函數(shù)。

圖A2.1（a）12-1自相關(guān)特性

圖A2.1（b）12-2自相關(guān)特性

2/28/2024106圖A2.2（a）14-1自相關(guān)特性

圖A2.2（b）14-2自相關(guān)特性

自相關(guān)性續(xù)2/28/2024107自相關(guān)性續(xù)圖A2.3（b）30-2自相關(guān)特性

圖A2.3（a）30-1自相關(guān)特性

2/28/2024108自相關(guān)性續(xù)圖A2.4（a）31-1自相關(guān)特性

圖A2.4（b）31-2自相關(guān)特性

2/28/2024109自相關(guān)性續(xù)圖A2.5（a）96-1自相關(guān)特性

圖A2.5（b）96-2自相關(guān)特性

2/28/2024110自相關(guān)性續(xù)圖A2.6（a）112-1自相關(guān)特性

圖A2.6（b）112-2自相關(guān)特性

2/28/2024111自相關(guān)性續(xù)圖A2.7（a）127-1自相關(guān)特性

圖A2.7（b）127-2自相關(guān)特性

2/28/2024112自相關(guān)性續(xù)圖A2.8（a）255-1自相關(guān)特性

圖A2.8（b）255-2自相關(guān)特性

2/28/2024113互相關(guān)性對(duì)每個(gè)進(jìn)制的兩段分別取長(zhǎng)度為30,000的序列進(jìn)行檢測(cè)得到如下結(jié)果。從以下測(cè)試結(jié)果可以看出，它們的互相關(guān)函數(shù)近似為0。

圖A2.9（a）12-1與14-1的互相關(guān)函數(shù)

圖A2.9（b）12-2與14-2的互相關(guān)函數(shù)

2/28/2024114互相關(guān)性續(xù)圖A2.10（a）14-1與30-1的互相關(guān)函數(shù)

圖A2.10（b）14-2與30-2的互相關(guān)函數(shù)

2/28/2024115互相關(guān)性續(xù)圖A2.11（a）30-1與31-1的互相關(guān)函數(shù)

圖A2.11（b）30-2與31-2的互相關(guān)函數(shù)

2/28/2024116互相關(guān)性續(xù)圖A2.12（a）31-1與96-1的互相關(guān)函數(shù)

圖A2.12（b）31-2與96-2的互相關(guān)函數(shù)

2/28/2024117互相關(guān)性續(xù)圖A2.13（a）96-1與112-1的互相關(guān)函數(shù)

圖A2.13（b）96-2與112-2的互相關(guān)函數(shù)

2/28/2024118互相關(guān)性續(xù)圖A2.14（a）112-1與127-1的互相關(guān)函數(shù)

圖A2.14（b）112-2與127-2的互相關(guān)函數(shù)

2/28/2024119互相關(guān)性續(xù)圖A2.15（a）127-1與255-1的互相關(guān)函數(shù)

圖A2.15（b）127-2與255-2的互相關(guān)函數(shù)

2/28/2024120驅(qū)動(dòng)序列的0-1均勻性檢測(cè)驅(qū)動(dòng)序列的游程檢測(cè)驅(qū)動(dòng)部分輸出的數(shù)值分析2/28/2024121驅(qū)動(dòng)序列的自相關(guān)函數(shù)對(duì)長(zhǎng)度為40,000比特的驅(qū)動(dòng)序列進(jìn)行統(tǒng)計(jì)。測(cè)試結(jié)果如圖A14所示。

驅(qū)動(dòng)序列比特流的自相關(guān)函數(shù)近似于沖激函數(shù)，因此，驅(qū)動(dòng)序列比特流的自相關(guān)性小。圖A14驅(qū)動(dòng)序列比特流的自相關(guān)特性mean=0.00264838,max=0.0189104,min=1.13913e-7,std=0.00229726(mean,max,min,std為自相關(guān)函數(shù)在τ≠0時(shí),幅度絕對(duì)值的平均值,最大值,最小值及標(biāo)準(zhǔn)方差）2/28/2024122驅(qū)動(dòng)序列的游程統(tǒng)計(jì)在長(zhǎng)度為160萬(wàn)比特的驅(qū)動(dòng)序列中游程總數(shù)為800,890；其中1游程總數(shù)為400,445，0游程總數(shù)為400,445；1游程和0游程各占游程總數(shù)的一半。表A5驅(qū)動(dòng)序列游程統(tǒng)計(jì)

游程數(shù)

游程長(zhǎng)度1游程占1游程總數(shù)百分比%0游程占0游程總數(shù)百分比%理想百分比120023050.0019%20042650.05086%50%210028525.0434%1003425.0576%25%34981712.4404%4978712.4329%12.5%4250306.25055%250686.26004%6.25%5126893.16872%125013.12178%3.125%662201.55327%61521.53629%1.5625%731670.79087%30810.769394%0.78125%2/28/2024123

游程數(shù)

游程長(zhǎng)度1游程占1游程總數(shù)百分比%0游程占0游程總數(shù)百分比%理想百分比814940.373085%15230.380327%0.390625%97390.184545%7700.192286%0.195313%103950.0986403%3890.0971419%0.0976563%111980.049445%1890.0471975%0.0488281%12910.0227247%1240.0309656%0.0244141%13400.00998889%500.0124861%0.012207%14270.0067425%200.00499444%0.00610352%1580.00199778%80.00199778%0.00305176%1660.00149833%90.0022475%0.00152588%1740.000998889%50.001248615%0.000762939%1840.000998889%00.0%0.00038147%1910.000249722%00.0%0.00019074%2000.0%00.0%0.00009537%2100.0%10.000249722%0.00004768%驅(qū)動(dòng)序列的游程統(tǒng)計(jì)續(xù)2/28/2024124驅(qū)動(dòng)序列的游程統(tǒng)計(jì)續(xù)2/28/2024125驅(qū)動(dòng)序列的頻數(shù)統(tǒng)計(jì)對(duì)長(zhǎng)度為200,000的驅(qū)動(dòng)序列所做的頻數(shù)統(tǒng)計(jì)結(jié)果如圖A15所示。圖A15驅(qū)動(dòng)序列頻數(shù)統(tǒng)計(jì)表A6驅(qū)動(dòng)序列的分布特性(mean為每種驅(qū)動(dòng)平均出現(xiàn)的次數(shù)，max為出現(xiàn)頻數(shù)最大的驅(qū)動(dòng)所出現(xiàn)的次數(shù)，min為出現(xiàn)頻數(shù)最小的驅(qū)動(dòng)所出現(xiàn)的次數(shù)，std為在20萬(wàn)個(gè)0~255種驅(qū)動(dòng)中出現(xiàn)次數(shù)與平均次數(shù)的標(biāo)準(zhǔn)方差)meanmaxminstd781.2588070927.73612/28/2024126驅(qū)動(dòng)序列均勻性檢測(cè)2/28/2024127驅(qū)動(dòng)序列的參數(shù)檢驗(yàn)2/28/2024128驅(qū)動(dòng)序列的參數(shù)檢驗(yàn)續(xù)2/28/2024129驅(qū)動(dòng)序列的參數(shù)檢驗(yàn)續(xù)2/28/2024130驅(qū)動(dòng)序列的相關(guān)性分析2/28/2024131驅(qū)動(dòng)序列的自相關(guān)分析產(chǎn)生長(zhǎng)度為40,000的驅(qū)動(dòng)序列K1，序列K2的自相關(guān)函數(shù)如圖A16所示。

驅(qū)動(dòng)序列的自相關(guān)函數(shù)近似于沖激函數(shù)圖A16驅(qū)動(dòng)序列的自相關(guān)特性驅(qū)動(dòng)序列的自相關(guān)函數(shù)在t=0時(shí)幅度為1，t≠0時(shí)幅度絕對(duì)值的均值，最大值，最小值及標(biāo)準(zhǔn)方差如表A7所示表A7驅(qū)動(dòng)序列的自相關(guān)特性MeanMaxMinstd0.00265100.01710234.07025e-80.002327682/28/2024132驅(qū)動(dòng)序列的互相關(guān)分析用兩個(gè)不同的工作密鑰分別產(chǎn)生長(zhǎng)度為30,000的序列K2和K3，序列K2和K3的互相關(guān)函數(shù)如圖A17所示。驅(qū)動(dòng)序列互相關(guān)函數(shù)的幅度接近于0。

不同工作密鑰產(chǎn)生的驅(qū)動(dòng)序列之間的互相關(guān)函數(shù)的幅度都接近于0圖A17驅(qū)動(dòng)序列的互相關(guān)特性mean=0.00308977max=0.0199841min=2.66934e-007std=0.00269815

(mean,max,min,std表示互相關(guān)函數(shù)幅度絕對(duì)值的平均值、最大值、最小值和標(biāo)準(zhǔn)方差)2/28/2024133驅(qū)動(dòng)序列獨(dú)立性必要條件的檢驗(yàn)2/28/2024134驅(qū)動(dòng)獨(dú)立性必要條件的檢驗(yàn)續(xù)2/28/2024135驅(qū)動(dòng)序列的線性復(fù)雜度分析2/28/2024136驅(qū)動(dòng)的線性復(fù)雜性分析續(xù)2/28/2024137將長(zhǎng)度為100,000比特的驅(qū)動(dòng)序列均分為10段，計(jì)算每段序列的線性復(fù)雜度輪廓，其中第一個(gè)段序列的線性復(fù)雜度輪廓如圖A18和A19所示。在圖中，橫軸是序列長(zhǎng)度，縱軸是相應(yīng)序列的線性復(fù)雜度。圖A18驅(qū)動(dòng)序列的線性復(fù)雜度輪廓圖圖A19驅(qū)動(dòng)序列的線性復(fù)雜度輪廓圖的放大

該段序列的線性復(fù)雜度輪廓與直線y＝x/2接近驅(qū)動(dòng)的線性復(fù)雜性分析續(xù)2/28/2024138表A8為各段序列的線性復(fù)雜度。在表中，各段序列的線性復(fù)雜度接近序列長(zhǎng)度的一半。表A8驅(qū)動(dòng)序列的各序列段的線性復(fù)雜度序列段號(hào)12345678910線性復(fù)雜度4998500050005002500050015000500050014998驅(qū)動(dòng)的線性復(fù)雜性分析續(xù)2/28/2024139驅(qū)動(dòng)的序列相圖分析2/28/2024140我們用1,000個(gè)驅(qū)動(dòng)序列數(shù)據(jù)畫(huà)出了二維相圖，用600個(gè)驅(qū)動(dòng)序列數(shù)據(jù)畫(huà)出了三維相圖（如圖A20，A21所示）。

二維相圖與三維相圖的點(diǎn)均勻地充滿了可能的相空間，未顯示出任何結(jié)構(gòu)，說(shuō)明該系統(tǒng)是復(fù)雜的，難以對(duì)其進(jìn)行重構(gòu)分析圖A20驅(qū)動(dòng)序列的二維相圖圖A21驅(qū)動(dòng)序列的三維相圖驅(qū)動(dòng)序列的相圖分析續(xù)2/28/2024141驅(qū)動(dòng)序列的近似熵分析2/28/2024142檢驗(yàn)結(jié)果在l＝2，r=7.37663(序列標(biāo)準(zhǔn)方差×0.1)，N=20,000，基于混沌變碼本的流密碼系統(tǒng)產(chǎn)生的驅(qū)動(dòng)序列的近似熵R約為2.72108，遠(yuǎn)大于滿映射的Logistic序列的最大近似熵（約為0.693）。由近似熵分析可知，本密碼系統(tǒng)雖然基于一維Logistic映射，但其行為卻遠(yuǎn)比Logistic映射復(fù)雜，本系統(tǒng)所得到的驅(qū)動(dòng)序列的“隨機(jī)”性遠(yuǎn)大于Logistic映射所產(chǎn)生的混沌序列的“隨機(jī)”性。驅(qū)動(dòng)序列的近似熵分析續(xù)2/28/2024143驅(qū)動(dòng)序列的分?jǐn)?shù)維2/28/2024144密鑰流的性質(zhì)2/28/2024145密鑰序列的游程檢測(cè)

密鑰序列的0-1均勻性檢測(cè)2/28/2024146密鑰序列的游程檢測(cè)續(xù)對(duì)長(zhǎng)度為40,000比特的密鑰序列進(jìn)行統(tǒng)計(jì)，其結(jié)果如圖A22。

密鑰序列比特流的自相關(guān)函數(shù)近似沖激函數(shù)，因此，該比特流的自相關(guān)性小圖A22密鑰序列比特流的自相關(guān)特性mean=0.00266632,max=0.0176601,min=1.02401e-9,std=0.00232965(mean,max,min,std為自相關(guān)函數(shù)在τ≠0時(shí)，幅度絕對(duì)值的平均值，最大值，最小值及標(biāo)準(zhǔn)方差)密鑰序列的自相關(guān)函數(shù)2/28/2024147在長(zhǎng)度為120萬(wàn)比特的密鑰序列中游程總數(shù)為601093；其中1游程總數(shù)為300546，0游程總數(shù)為300547；1游程和0游程各占游程總數(shù)的一半。表A9密鑰序列游程統(tǒng)計(jì)密鑰序列的游程檢測(cè)續(xù)密鑰序列的游程統(tǒng)計(jì)2/28/2024148密鑰序列的游程檢測(cè)續(xù)2/28/2024149密鑰序列的游程檢測(cè)續(xù)2/28/2024150密鑰序列的頻數(shù)統(tǒng)計(jì)

對(duì)長(zhǎng)度為200,000的密鑰序列所做的頻數(shù)統(tǒng)計(jì)結(jié)果如圖A23所示。

圖A23密鑰序列頻數(shù)統(tǒng)計(jì)

其頻數(shù)統(tǒng)計(jì)分析的結(jié)果如表A10所示。

表A10密鑰序列的分布特性

meanmaxminstd781.25