現(xiàn)代密碼學(第二章)

第二章：流密碼一、流密碼的基本概念二、線性反饋移位寄存器序列三、非線性組合序列四、鐘控序列2024/7/171一、流密碼的基本概念有關的概念若m1的取值為0或1，則稱m1為一個比特（bit）。n個比特m1m2m3…mn

，稱為一個長度為n的比特串。無窮個比特m1m2m3…mnmn+1…

，稱為一個比特流。兩個比特流：m=m1m2m3…mnmn+1…

，k=k1k2k3…knkn+1…

，做運算得到如下一個新的比特流：c=c1c2c3…cncn+1…

，2024/7/172一、流密碼的基本概念其中cn=mn+kn(mod2)，n=1，2，3，…，稱比特流c是比特流m與比特流k的逐位模2加，或逐比特異或。記作c=m‘+’k注意：此時有m=c‘+’kk=m‘+’c2024/7/173一、流密碼的基本概念當（1）明文是比特流m，稱為明文流；（2）加密密鑰和解密密鑰相同，是比特流k，稱為密鑰流；（3）密文是比特流c，稱為密文流；（4）加密算法和解密算法相同，加密：c=m‘+’k；解密：m=c‘+’k。則稱這樣的加解密算法為流密碼，又稱其為序列密碼。2024/7/174一、流密碼的基本概念隨機性：密鑰流的理想情形假設密鑰流k是由完全隨機的方式生成的。因此從攻擊者的角度來看，密鑰流k應該是真正的隨機序列，滿足：k1，k2，

k3，

…，

kn

，

kn+1，

…都是具有等概率分布隨機變量，P(kl=0)=P(kl=1)=1/2，且它們相互獨立。2024/7/175一、流密碼的基本概念任意兩個不相重疊的密文段，它們所對應的密鑰段都是相互獨立的。換句話說，每一次加密都使用與以前的密鑰段完全無關的新密鑰段。再換句話說，此時的加密方式是一次一密的。因此，此時達到了最高的安全性標準：無條件安全（完善保密）。這樣的密鑰流k具有以下三條重要的性質：2024/7/176一、流密碼的基本概念（1）P(kl=0)=P(kl=1)=1/2。（1’）當n充分大時，k1k2k3…kn中0和1的個數(shù)各占約一半。（2）P(k1k2…kl=10…01)=P(k1k2…kl=01…10)=1/2l。（2’）當n充分大時，在k1k2k3…kn中，長度為l的比特串10…01（稱為0游程）的個數(shù)約有n/2l個；長度為l的比特串01…10（稱為1游程）的個數(shù)約有n/2l個。（3）若k>0，P(kl=kl+k)=P(kl≠kl+k)=1/2。（3’）若k>0，當n充分大時，以下的值（稱為異相自相關函數(shù)值）約為0。2024/7/177一、流密碼的基本概念2024/7/178一、流密碼的基本概念偽隨機性：密鑰流的實用情形實用的密鑰流k不可能由完全隨機的方式生成。出于商用目的和標準化要求，密鑰流k必須由確定的方式自動生成。不過從攻擊者的角度來看，密鑰流k很像真正的隨機序列，稱為偽隨機序列。偽隨機序列應該滿足前面提到的性質（1’）（2’）（3’）。這三條性質就是著名的Golomb隨機性假設。2024/7/179一、流密碼的基本概念兩個不相重疊的密文段，它們所對應的密鑰段可能不同，但未必沒有依賴關系。換句話說，此時的加密方式未必是一次一密的。因此，此時未必達到無條件安全。因此，偽隨機的密鑰流只能力爭做到計算安全。2024/7/1710一、流密碼的基本概念現(xiàn)在對流密碼進行已知明文攻擊。設攻擊者Eve在以往截獲了密文段c1c2c3…cn，并知道了對應的廢棄明文段m1m2m3…mn，因此計算出了對應的廢棄密鑰段k1k2k3…kn。希望：由k1k2k3…kn難以預測后續(xù)密鑰段kn+1kn+2…

。這種不可預測性又稱為偽隨機性。因此希望密鑰流k滿足Golomb隨機性假設（1’）（2’）（3’）。但這還不夠，還必須具有“很高的線性復雜度”。（將在以后介紹）2024/7/1711二、線性反饋移位寄存器序列線性反饋移位寄存器序列若比特流k由如下的方式生成：（1）選擇長度為n的比特串k1k2k3…kn；（2）當l>n后，kl=c1kl-1‘+’c2kl-2‘+’…‘+’cnkl-n。其中常數(shù)c1、c2、…、cn都是比特值，且cn=1。2024/7/1712二、線性反饋移位寄存器序列則稱比特流k為n階線性反饋移位寄存器序列，又稱為n階線性遞歸序列；稱常數(shù){c1、c2、…、cn}為抽頭系數(shù)；稱比特串k1k2k3…kn為初始狀態(tài)；稱f(x)=1‘+’c1x1

‘+’c2x2

‘+’…‘+’cnxn為此線性反饋移位寄存器序列的特征多項式。2024/7/1713線性反饋移位寄存器

(linearfeedbackshiftregister)

(LFSR)2024/7/1714二、線性反饋移位寄存器序列線性反饋移位寄存器序列的性質（不給出證明）設比特流k為n階線性反饋移位寄存器序列。（1）k是周期序列，最小周期不超過2n-1。（2）k由抽頭系數(shù){c1，c2，…，cn}和初始狀態(tài)k1k2k3…kn唯一確定。（3）如果k的最小周期達到了2n-1，此時稱k為n階m序列。m序列具有以下的特殊性質。（Golomb隨機性假設）2024/7/1715二、線性反饋移位寄存器序列（3.1）k在自己的一個最小周期內（即連續(xù)2n-1個比特內），0出現(xiàn)2n-1-1次，1出現(xiàn)2n-1次。（3.2）取定j，3≤j≤n，觀察k的連續(xù)2n-1個長l的比特串：klkl+1kl+2…kl+j-1，l=1,2,…,2n-1。10…01出現(xiàn)2n-l次；（長為l-2的0游程）01…10出現(xiàn)2n-l次。（長為l-2的1游程）觀察k的連續(xù)2n-1個長n+1的比特串：kl~kl+n，l=1~2n-1。10…01出現(xiàn)1次。（長為n-1的0游程）觀察k的連續(xù)2n-1個長n+2的比特串：kl~kl+n+1，l=1~2n-1。01…10出現(xiàn)1次。（長為n-1的0游程）2024/7/1716二、線性反饋移位寄存器序列（3.3）對任何1≤j≤2n-2

，下式為0。（自相關函數(shù)）2024/7/1717二、線性反饋移位寄存器序列從以上性質可以看出，n階m序列滿足Golomb隨機性假設。而且當n并不大時，通信伙伴生成n階m序列的復雜度很小，得到的最小周期2n-1卻極大。如此看來，m序列似乎非常適合用作密鑰流。其實不然。如果n階線性反饋移位寄存器序列用作密鑰流，攻擊者Eve截獲了密文段c1c2c3…c2n，并知道了對應的明文段m1m2m3…m2n，因此計算出了對應的廢棄密鑰段k1k2k3…k2n。則Eve獲得了關于抽頭系數(shù){c1、c2、…、cn}的以下方程組。2024/7/1718二、線性反饋移位寄存器序列kl=c1kl-1‘+’c2kl-2‘+’…‘+’cnkl-n，其中l(wèi)=n+1，n+2，…，2n。注意到這是在有限域GF(2)上的線性方程組，很容易解出抽頭系數(shù){c1、c2、…、cn}。實際上，當Eve獲得了n階線性反饋移位寄存器序列的任何一段的連續(xù)2n個比特kj+1kj+2kj+3…kj+2n，他就獲得了關于抽頭系數(shù){c1、c2、…、cn}的以下方程組。kl=c1kl-1‘+’c2kl-2‘+’…‘+’cnkl-n，其中l(wèi)=j+n+1，j+n+2，…，j+2n。2024/7/1719二、線性反饋移位寄存器序列2024/7/1720二、線性反饋移位寄存器序列以上方程組中的加法和乘法都是在域GF(2)上進行的（即(mod2)運算）。以上事實說明，當Eve獲得了n階線性反饋移位寄存器序列的任意連續(xù)2n個比特，Eve就獲得了整個密鑰流。實際上，對線性反饋移位寄存器序列還有更為有效的攻擊方法。當Eve不知道階數(shù)n時，他還可以進行測試。這種測試攻擊方法被稱為序列的綜合。2024/7/1721二、線性反饋移位寄存器序列線性反饋移位寄存器序列的綜合定理如果一個比特流是一個周期序列，則它一定是線性反饋移位寄存器序列。證明設比特流k的最小周期是N。則l>N后，kl=kl-N。因此比特流k為N階線性反饋移位寄存器序列，抽頭系數(shù)為

{c1、c2、…、cN}={0、0

、…0、1}（即極小多項式f(x)=1‘+’xN），初始狀態(tài)為k1k2k3…kN。2024/7/1722二、線性反饋移位寄存器序列定義一個周期序列作為一個線性反饋移位寄存器序列，它的最小階數(shù)稱為它的線性復雜度。對應于這個階的特征多項式稱為該序列的極小多項式.（注意一個周期序列作為一個線性反饋移位寄存器序列，可以有很多不同的階數(shù)，其中它的最小周期就是它的一個階數(shù)。因此，周期序列的線性復雜度一定不超過它的最小周期）所謂序列的綜合，就是尋找周期序列的線性復雜度n，并且求出極小多項式f(x)。序列的綜合的兩種最著名的算法是B-M算法和Games-Chan算法。2024/7/1723二、線性反饋移位寄存器序列B-M算法輸入：周期序列的一段長度為N的比特串sN=s0s1s2…sN-1。目的：求出比特串sN的最短的線性遞歸關系。當N≥周期序列的線性復雜度的2倍時，該線性遞歸關系的階數(shù)就是線性復雜度，該線性遞歸關系就給出了抽頭系數(shù)。2024/7/1724二、線性反饋移位寄存器序列步驟1：找n0使得當j=0~n0-1時，sj=0；當j=n0時，sj=1。取初始值對于j=0~n0-1，令dj=0；對于j=n0，令dj=sl；對于0≤j≤n0，令fj(x)=1，lj=0；再對于j=n0+1，令fj(x)=1‘+’dj-1xj，lj=j。2024/7/1725二、線性反饋移位寄存器序列步驟2：設{(fj(x),lj)；0≤j≤n}已經求出。如果n=N，則直接轉步驟3；否則計算dn=fn(E)sn（此處E是“時間延遲算子”。即：當fn(x)=a0‘+’a1x‘+’a2x2‘+’…‘+’atxt時，fn(E)sn=a0sn‘+’a1sn-1‘+’a2sn-2‘+’…‘+’atsn-t。）2024/7/1726二、線性反饋移位寄存器序列（1）如果dn=0，則令fn+1(x)=

fn(x)；ln+1=

ln；轉步驟2。（2）如果dn=1，則：找出m使得lm<lm+1=lm+2=…=

ln；令fn+1(x)=

fn(x)‘+’xn-mfm(x)；ln+1=max{ln,n+1-

ln}；轉步驟2。

2024/7/1727二、線性反饋移位寄存器序列步驟3：最后得到了(fN(x),lN)。（fN(x)的全體系數(shù)就是比特串sN的一個最短的齊次線性遞歸關系；該齊次線性遞歸關系的長度為lN。如果N不小于周期序列的線性復雜度的2倍，lN就是該周期序列的線性復雜度，fN(x)就是該周期序列的極小多項式?？梢钥闯觯珺-M算法簡單快速，攻擊線性復雜度小的序列極為有效。）2024/7/1728二、線性反饋移位寄存器序列Games-Chan算法定理比特流的最小周期為2的冪時，其線性復雜度大于其最小周期的一半。（不給出證明）設比特流的最小周期為N=2n。

輸入：周期序列的一個最小周期sN=s0s1s2…sN-1；令Lc=0；f(x)=1。2024/7/1729二、線性反饋移位寄存器序列步驟1：令L=(s0,s1,s2,…,sN/2-1)；R=(sN/2,sN/2+1,sN/2+2,…,sN-1)；計算B=L‘+’R。步驟2：如果B≠0，則令Lc=

Lc+N/2，f(x)=f(x)(1‘+’x)N/2，s=B，轉步驟3；如果B=0，則令s=L，轉步驟3。

步驟3：令N=N/2。步驟4：如果N=1，B≠0，則輸出(Lc,f(x))，停止；如果N=1，B=0，s≠0，則令Lc=Lc+1，f(x)=f(x)(1-x)，輸出(Lc,f(x))，停止；如果N≠1，則轉步驟1。

2024/7/1730二、線性反饋移位寄存器序列最后輸出的(Lc,f(x))是序列s的線性復雜度和極小多項式。注意到雖然序列的線性復雜度大于2n-1，用Games-Chan算法至多迭代n步就可求出，因此對此類大的線性復雜度，Games-Chan比B-M算法更加快速。由于需要序列的一個周期參加運算，存儲量巨大，故Games-Chan算法還不能算是一個有效的算法。

2024/7/1731二、線性反饋移位寄存器序列線性反饋移位寄存器序列的小結線性反饋移位寄存器序列能夠實現(xiàn)：小的計算量（n階線性遞歸生成，通常n不大）；極大的最小周期（對于m序列，最小周期為2n-1）；良好的偽隨機性（對于m序列，Golomb隨機性假設成立）。2024/7/1732二、線性反饋移位寄存器序列然而小的計算量得到小的線性復雜度（對于m序列，線性復雜度為n），很容易由短的一段（對于m序列，由長度為2n的一段）推斷出整個序列（用B-M算法）。因此，線性反饋移位寄存器序列不能作為密鑰流。（能否讓線性復雜度很大？不能）兼顧小的計算量和大的線性復雜度，需要使用非線性的生成方式。2024/7/1733三、非線性組合序列域GF(2)上的n維函數(shù)（n維布爾函數(shù)）n維布爾函數(shù)是這樣的函數(shù)y=g(x1,x2,…,xn)：n個自變量x1,x2,…,xn取值均為0和1；因變量y取值為0和1。2024/7/1734三、非線性組合序列n維布爾函數(shù)的代數(shù)正規(guī)型：y=g(x1,x2,…,xn)=a(0)‘+’a(1)x1‘+’a(2)x2‘+’…‘+’a(n)xn‘+’a(1,2)x1x2‘+’…‘+’a(n-1,n)xn-1xn‘+’a(1,2,3)x1x2x3‘+’…‘+’a(n-2,n-1,n)xn-2xn-1xn‘+’…‘+’a(1,…,n)x1…xn2024/7/1735三、非線性組合序列其中常數(shù){a(0)，a(1)~a(n)，a(1,2)~a(n-1,n)，a(1,2,3)~a(n-2,n-1,n)，…，a(1,…,n)}稱為系數(shù)，它們取0或1為值。使得系數(shù)不為0的項的最高次數(shù)稱為n維布爾函數(shù)的次數(shù)。（關于n維布爾函數(shù)的注解：x12≡x1，因此只有混合高次項；又因此最高次數(shù)不超過n；系數(shù)組{a(0)~a(1,…,n)}中一共有2n個系數(shù)；函數(shù)g(x1,x2,…,xn)與系數(shù)組相互唯一）2024/7/1736三、非線性組合序列當g(x1,x2,…,xn)只含有一次項時，稱g為線性函數(shù)；當g(x1,x2,…,xn)只含有0次項和一次項時，稱g為仿射函數(shù)；當g(x1,x2,…,xn)含有高次項時，稱g為非線性函數(shù)。2024/7/1737三、非線性組合序列非線性前饋序列若比特流k由如下的方式生成：（1）選擇n階m序列s=s1s2s3…，其極小多項式為f(x)，其初始狀態(tài)為s1s2s3…sn；（2）對每個l>0，kl=g(sl,sl+1,…,sl+n-1)。其中g(x1,x2,…,xn)為非線性的n維布爾函數(shù)。則稱比特流k為非線性前饋序列。稱m序列s為驅動序列。2024/7/1738三、非線性組合序列2024/7/1739三、非線性組合序列當非線性前饋序列用作密鑰流時，通常只有三個部分可能作為通信伙伴的原始密鑰：初始狀態(tài)，極小多項式，非線性布爾函數(shù)。有以下三種不同的用法：（1）原始密鑰是初始狀態(tài)，而將極小多項式和非線性布爾函數(shù)公開。此時原始密鑰最短，但需要精心設計非線性布爾函數(shù)。（2）原始密鑰是初始狀態(tài)和極小多項式，而將非線性布爾函數(shù)公開。此時原始密鑰長一些，但對非線性布爾函數(shù)的要求低一些。（3）原始密鑰是初始狀態(tài)、極小多項式、非線性布爾函數(shù)。此時原始密鑰最長，但對非線性布爾函數(shù)的要求最低。2024/7/1740三、非線性組合序列為什么g必須是非線性函數(shù)？如果g是線性函數(shù)，則前饋序列k還是n階m序列，并且與驅動序列s有相同的極小多項式（不給出證明）。如果g是仿射函數(shù)，則前饋序列k是n階m序列的補序列。希望：非線性前饋序列的線性復雜度極大，應該與2n具有相同的數(shù)量級。2024/7/1741三、非線性組合序列前饋序列k的偽隨機性如何？2n-1是前饋序列k的一個周期（容易證明）。換句話說，前饋序列k的最小周期必然是2n-1的因子。希望：前饋序列k的最小周期就是2n-1。希望：前饋序列k是0-1基本均衡的，即在一個最小周期內0和1的數(shù)量近似相等。這些都需要精心地設計非線性布爾函數(shù)g。前饋序列最難做到的是游程分布的偽隨機性和自相關的的偽隨機性。2024/7/1742三、非線性組合序列非線性組合序列若比特流k由如下的方式生成：（1）M個n階m序列s(j)=s(j)1s(j)2s(j)3…；j=1~M；（2）對每個l>0，kl=g(s(1)l,s(2)l,…,s(M)l)。其中g(x1,x2,…,xM)為非線性的M維布爾函數(shù)。則稱比特流k為非線性組合序列。稱M個n階m序列s(j)為驅動序列。2024/7/1743三、非線性組合序列2024/7/1744三、非線性組合序列J-K觸發(fā)器J和K分別表示兩個m序列，它們在任意時刻的輸出是J-K觸發(fā)器的輸入。這兩個輸入與J-K觸發(fā)器上一個時刻的內部狀態(tài)ql-1相結合，得到J-K觸發(fā)器本時刻的內部狀態(tài)ql，同時J-K觸發(fā)器在本時刻輸出該狀態(tài)ql。如下表所示。一般令q-1=0。J0011K0101本時刻的狀態(tài)及輸出：ql上一狀態(tài)：ql-101上一狀態(tài)取補：1-ql-12024/7/1745四、鐘控序列鐘控序列鐘控序列的種類很多，大體上采用如下的結構：（1）選擇2個同步的m序列s(j)=s(j)1s(j)2s(j)3…；j=1，2；（2）在任何一個時刻，根據s(1)的“當前情況”，決定是否輸出s(2)的“對應比特”；當輸出時，輸出s(2)的“哪些比特”。最終輸出的序列就是鐘控序列。稱s(1)為控制序列。稱s(2)為受控序列。請注意，鐘控序列與非線性前饋序列不同。鐘控序列并不是每個時刻都輸出一個比特。2024/7/1746四、鐘控序列2024/7/1747四、鐘控序列鐘控序列的的設計思想：對m序列進行適當?shù)摹白冃巍焙汀凹舨谩保沟迷揪€性復雜度很低的m序列變成線性復雜度級高的鐘控序列。設m序列的階為n。作為密鑰流，鐘控序列與非線性前饋序列相比，有以下的優(yōu)點和缺點（不給出證明）：（1）鐘控序列能夠更容易地使線性復雜度達到極大。（2）鐘控序列不是等間隔輸出，而是不定時的輸出，使得必須額外地進行時間同步，配備緩存器。（3）鐘控序列對m序列的某些比特跳過不輸出，造成了一定的浪費。2024/7/1748四、鐘控序列停-走生成器此工作屬于BethT.。所給出的停-走生成器如下。設GF(2)上兩個n級m-序列：控制序列a=a0a1a2…；受控序列b=b0b1b2…。記G(t)=a0+a1+a2+

…+at-1。（不是(mod2)加法）停-走序列u=u0u1u2…為：ut=bG(t)，t=0,1,2,…。

2024/7/1749四、鐘控序列縮減序列：互縮序列

此工作屬于DonCoppersmith。所給出的互縮序列如下。設GF(2)上兩個n級m-序列：控制序列a=a0a1a2…；受控序列b=b0b1b2…。當at=1時，輸出bt；當at=0時，放棄輸出。如此得到的輸出序列u=u0u1u2…稱為互縮序列。2024/7/1750四、鐘控序列縮減序列：廣義自縮序列

所給出的廣義自縮序列如下。設GF(2)上一個n級m-序列a=a0a1a2…。取G=(g0,g1,…,gn-1)∈GF(2)n。記vt=g0at‘+’g1at-1‘+’…‘+’gn-1at-n+1。當at=1時，輸出vt；當at=0時，放棄輸出。如此得到的輸出序列b=b0b1b2…稱為廣義自縮序列?？梢钥闯?，控制序列是a=a0a1a2…，受控序列是v=v0v1v2…，其中vt=g0at‘+’g1at-1‘+’…‘+’gn-1at-n+1。2024/7/1751四、鐘控序列注解一：關于受控序列v

當G=(g0,g1,…,gn-1)∈GF(2)n是全0向量時，受控序列v是全0序列；當G=(g0,g1,…,gn-1)∈GF(2)n是不為全0的向量時，受控序列v是控制序列a的平移序列。（即：v=v0v1v2…=akak+1ak+2…。這是m序列的一個基本結論，不給出證明。此時，控制序列a與受控序列v具有相同的極小多項式，僅僅初始狀態(tài)不同。這就是序列被稱為“廣義自縮序列”的理由）2024/7/1752四、鐘控序列注解二：關于廣義自縮序列的最小周期

控制序列a的最小周期是2n-1，在一個最小周期中，“1”出現(xiàn)2n-1次；當G=(g0,g1,…,gn-1)∈GF(2)n是不為全0的向量時，受控序列v的最小周期也是2n-1。這就是說，每當廣義自縮序列輸出了2n-1個比特后，再輸出就是重復這2n-1個比特。