教學培訓課件第14-15講數(shù)據(jù)加密技術(序列加密)

密碼學序列密碼xxx魯東大學計算機學院1ppt課件密碼學1ppt課件一、序列密碼的基本概念

①明文、密文、密鑰以位（字符）為單位加解密；②模型

密鑰序列產生器種子密鑰密鑰序列：k1,k2,…

密文:c1,c2,…

明文:m1,m2,…Ci=mi⊕ki2ppt課件一、序列密碼的基本概念①明文、密文、密鑰以位（字符）為單位一、序列密碼的基本概念③人們用序列密碼模仿“一次一密”密碼；④加密運算最簡單，而且是對合運算；⑤安全取決于密鑰序列產生算法；⑥理論和技術都十分成熟；3ppt課件一、序列密碼的基本概念③人們用序列密碼模仿“一次一密”一、序列密碼的基本概念1、序列密碼的分類①同步序列密碼（SynchronousStreamCipher）軍方稱為密鑰自動密鑰。密鑰序列產生算法與明文無關，所產生的密鑰序列也與明文無關。一位一位“吐出”密鑰。在通信過程中，通信的雙方必須保持精確的同步，收方才能正確解密，如果失步收方將不能正確解密。例如，如果通信中丟失或增加了一個密文字符，則收方的解密將一直錯誤。4ppt課件一、序列密碼的基本概念1、序列密碼的分類4ppt課件一、序列密碼的基本概念①同步序列密碼設密文失步

c=

c1,c3,c4,…cn-1,cn（c2丟失）

⊕

k=k1,k2,k3,…kn-1,kn（密鑰正確）m=m1,×,×,…×,×（m1后的明文全錯）密鑰序列產生算法密鑰序列產生算法m1,m2,…

m1,m2,…c1,c2,…

k1,k2,…k1,k2,…Ci=mi⊕ki種子密鑰k種子密鑰k5ppt課件一、序列密碼的基本概念①同步序列密碼密鑰序列密鑰序列m1,m一、序列密碼的基本概念①同步序列密碼對失步的敏感性，使我們能夠容易檢測插入、刪除、重播等主動攻擊。另一個優(yōu)點是沒有錯誤傳播，當通信中某些密文字符產生了錯誤（不是插入和刪除），只影響相應字符的解密，不影響其它字符。注意：錯誤與失步是不同的概念！設密文錯誤c=

c1,c2,c3,…cn-1,cn（c2錯）

⊕k=k1,k2,k3,…kn-1,kn（密鑰正確）

m=m1,×,m3,…mn-1,mn（僅m2錯）6ppt課件一、序列密碼的基本概念①同步序列密碼6ppt課件一、序列密碼的基本概念②自同步序列密碼（Self-SynchronousStreamCipher）密鑰流的每一位是前面固定數(shù)量密文位的函數(shù)。軍方稱為密文自動密鑰密鑰序列產生算法與明文（密文）相關，則所產生的密鑰序列與明文（密文）相關。設密鑰序列產生器具有n位存儲，則加密時一位密文錯誤將影響后面連續(xù)n個密文錯誤。在此之后恢復正確。解密時一位密文錯誤也將影響后面連續(xù)n個明文錯。在此之后恢復正確。加解密會造成錯誤傳播。在錯誤過去之后恢復正確。7ppt課件一、序列密碼的基本概念②自同步序列密碼（Self-Syn一、序列密碼的基本概念②自同步序列密碼密鑰序列產生算法n位存儲密鑰序列產生算法n位存儲m1,m2,…

m1,m2,…

c1,c2,…

k1,k2,…

k1,k2,…

Ci的錯誤將影響n位種子密鑰k種子密鑰k8ppt課件一、序列密碼的基本概念②自同步序列密碼密鑰序列密鑰序列m1,二、線性移位寄存器序列密碼1、線性移位寄存器（LinearSiftRegistor）例1例2增加反饋S0S1Sn-2Sn－1輸入輸出移位脈沖S0S1Sn-2Sn－1輸入輸出移位脈沖9ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器（Linear二、線性移位寄存器序列密碼1、線性移位寄存器（LinearSiftRegistor）例3增加運算S0S1Sn-2Sn－1輸入輸出移位脈沖⊕10ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器（Linear二、線性移位寄存器序列密碼1、線性移位寄存器（LinearSiftRegistor）一般模型F(s0,s1,…,sn－1)S0S1Sn-2Sn－1輸出11ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器（Linear二、線性移位寄存器序列密碼1、線性移位寄存器（LinearSiftRegistor）圖中s0，s1，...，sn-1組成左移移位寄存器，并稱每一時刻移位寄存器的取值為一個狀態(tài)。移位寄存器的輸出同時要送入sn-1，其值要通過函數(shù)F(s0,s1,...,sn-1)計算產生。稱函數(shù)F(s0,s1,...,sn-1)為反饋函數(shù)。如果反饋函數(shù)F(s0,s1,...,sn-1)是s0,s1,...,sn-1

的線性函數(shù)，則稱為線性移位寄存器，否則稱為非線性移位寄存器。12ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器（Linear二、線性移位寄存器序列密碼1、線性移位寄存器設F(s0,s1,...,sn-1)為線性函數(shù)，則可寫成

F(s0,s1,...,sn-1)=g0s0+g1s1+,...,+gn-1sn-1

其中，g0,g1,...,gn-1為反饋系數(shù)。在二進制的情況下，式中的+即為⊕，反饋系數(shù)gi∈GF(2)，如果gi=0，則表示式中的gisi項不存在，因此表示si不連接。同理，gi=1表示si連接。故gi的作用相當于一個開關。13ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器13ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器形式地，用xi與si相對應，則根據(jù)反饋函數(shù)可導出一個文字x的多項式：

g(x)=gnxn+gn-1xn-1+,...,+g1x+g0

稱g(x)為線性移位寄存器的連接多項式。與下圖對照可知，gn=g0=1。否則，若gn=0則輸出不反饋到sn-1，若g0=0則s0不起作用，應將其去掉。14ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器14ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器S0S1Sn－1Sn－2gn=1gn-1g2g1g0=115ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器S0S1Sn－1二、線性移位寄存器序列密碼1、線性移位寄存器n級線性移位寄存器最多有2n個不同的狀態(tài)。若其初始狀態(tài)為零，則其后續(xù)狀態(tài)恒為零。若其初始狀態(tài)不為零，則其后續(xù)狀態(tài)也不為零。因此，n級線性移位寄存器的狀態(tài)周期≤2n

–1，其輸出序列的周期≤2n

–1。只要選擇合適的連接多項式便可使線性移位寄存器的輸出序列周期達到最大值2n–1，并稱此時的輸出序列為最大長度線性移位寄存器輸出序列，簡稱為m序列。16ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器16ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器僅當連接多項式g(x)為本原多項式時，其線性移位寄存器的輸出序列為m序列。設f(x)為GF（2）上的多項式，使f(x)|

x

p－1的最小正整數(shù)p稱為f(x)的周期。如果f(x)的次數(shù)為n，且其周期為2

n－1，則稱f(x)為本原多項式。已經證明，對于任意的正整數(shù)n，至少存在一個n次本原多項式。而且有有效的產生算法。17ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器17ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器舉例：設g(x)=x4+x+1，

g(x)為本原多項式，以其為連接多項式的線性移位寄存器的輸出序列為100110101111000···，它是周期為2

4-1=15的m序列。S0S1S2S3g4=1g3=0g2=0g1=1g0=100010101001010110100011110011111001111100110110011011000101018ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器S0S1S2S3二、線性移位寄存器序列密碼1、線性移位寄存器m序列具有良好的隨機性：

游程：稱序列中連續(xù)的i個1為長度等于i的1游程，同樣，稱序列中連續(xù)的i個0為長度等于i的0游程。①在一個周期內，0和1出現(xiàn)的次數(shù)接近相等，即0出現(xiàn)的次數(shù)為2n-1-1，1出現(xiàn)的次數(shù)為2n-1；19ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器19ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器

②將序列的一個周期首尾相接，其游程總數(shù)N=2n-1。③其中1游程和0游程的數(shù)目各占一半。當n>2時，游程分布如下（1≤i≤n-2）：長為i的1游程有N/2i+1個；長為i的0游程有N/2i+1個；長為n-1的0游程有1個；長為n的1游程有1個.20ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器20ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器

④自相關函數(shù)

定義：設{ki}是周期為p的序列，k0,k1,…,kp-1是其中一個周期子段，則k0+τ,k1+τ,…,kp-1+τ也是一個周期子段。記這兩個子段中相同的位數(shù)為A，不相同的位數(shù)為D，則自相關函數(shù)定義為：A-DP自相關函數(shù)反映一個周期內平均每位的相同程度。

R(j)=21ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器R(j)=21p二、線性移位寄存器序列密碼1、線性移位寄存器

④自相關函數(shù)1

,τ=0

-1/P，0<τ≤P-1

例：

100110101111000001101011110001R(τ)=m序列的自相關函數(shù)達到最佳值。A＝7D＝8R(τ)=-1/1522ppt課件二、線性移位寄存器序列密碼1、線性移位寄存器R(τ)=m序列二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼（第二次開課始處）m序列具有良好的隨機性；50年代開始用作密鑰序列，并用于軍用。60年代發(fā)現(xiàn)其是不安全的。23ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼（第二次二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼設m序列線性移位寄存器的狀態(tài)為

S=（s0,s1,...,sn-1）T，下一狀態(tài)為S’=（s’0,s’1,...,s’n-1）T，其中

s’0=

s1

s’1=

s2

...

s’n-2=

sn-1

s’n-1=

g0s0+g1s1+,...,+gn-1sn-124ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼24pp二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼寫成矩陣形式：S’=HSmod2010...0s’0s0

001...0s’1s1

000...0H=...S’=S=000...1

g0

g1...gn-1s’n-1sn-1矩陣H稱為連接多項式的伴侶矩陣。25ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼25pp二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼進一步假設攻擊者知道了一段長2n位的明密文對，即已知：

M=

m1,m2,...,m2n

C=

c1,c2,...,c2n于是可求出一段長2n位的密鑰序列，

K=

k1,k2,...,k2n，其中

ki=mi⊕ci=mi

⊕(mi⊕ki)。26ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼26pp二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼

由此可以推出線性移位寄存器連續(xù)n+1個狀態(tài)：

S1

=（k1,k2,...,kn）T

S2

=（k2,k3,...,kn+1）T…

Sn+1

=（kn+1,kn+2,...,k2n）T作矩陣

X

=（S1,S2,...,Sn）T

Y

=（S2,S3,...,Sn+1）T27ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼27pp二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼根據(jù)S’=HSmod2，有

S2=HS1

S3=HS2

...

Sn+1=HSn于是，

Y=HXmod228ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼28pp二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼因為m序列的線性移位寄存器連續(xù)n個狀態(tài)向量彼此線性無關，因此X矩陣為滿秩矩陣，故存在逆矩陣X

-1，于是

H=YX

-1mod2求出H矩陣，便確定出連接多項式g(x)，從而完全確定線性移位寄存器的結構。

例：m序列100110101111000

連續(xù)4個狀態(tài)

1001，0011，0110，1101線性無關29ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼29pp二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼求逆矩陣X-1的計算復雜度為O（n3）。一般，對于n=1000的線性移位寄存器序列密碼，用每秒100萬次的計算機，一天之內便可破譯。30ppt課件二、線性移位寄存器序列密碼2、線性移位寄存器序列密碼30pp三、非線性序列密碼線性移位寄存器序列密碼在已知明文攻擊下是可破譯的，可破譯的根本原因在于線性移位寄存器序列是線性的，這一事實促使人們向非線性領域探索。目前研究得比較充分的方法：①非線性移位寄存器序列

②對線性移位寄存器序列進行非線性組合③利用非線性分組碼產生非線性序列31ppt課件三、非線性序列密碼線性移位寄存器序列密碼在已知明文攻擊下是可三、非線性序列密碼①非線性移位寄存器序列

令反饋函數(shù)f(s0,s1,...,sn-1)為非線性函數(shù)便構成非線性移位寄存器，其輸出序列為非線性序列。稱輸出序列的周期達到最大值2n的非線性移位寄存器序列為M序列。M序列的0，1分布和游分布是均勻的，而且周期最大。32ppt課件三、非線性序列密碼①非線性移位寄存器序列32ppt課件三、非線性序列密碼①非線性移位寄存器序列非線性移位寄存器反饋函數(shù)的數(shù)量極大

GF（2）上的n級移位寄存器共有2n個狀態(tài)，因此共有種不同的反饋函數(shù)，其中線性反饋函數(shù)只有2n-1種，其余均為非線性。顯然，非線性移位寄存器的空間極大！

2n

233ppt課件三、非線性序列密碼①非線性移位寄存器序列33ppt課件三、非線性序列密碼①非線性移位寄存器序列例：令n=3，f(s0,s1,s2)=s0⊕s2⊕1⊕s1

s2，由于與運算為非線性運算，故反饋函數(shù)為非線性反饋函數(shù)，其輸出序列為10110100...，為M序列。s0s1s2

輸出34ppt課件三、非線性序列密碼①非線性移位寄存器序列s0s1s2輸出3三、非線性序列密碼②對線性移位寄存器序列進行非線性組合

非線性移位寄存器序列的研究比較困難，但人們對線性移位寄存器序列的研究卻比較充分和深入。于是人們想到，利用線性移位寄存器序列設計容易、隨機性好等優(yōu)點，對一個或多個線性移位寄存器序列進行非線性組合可以獲得良好的非線性序列。35ppt課件三、非線性序列密碼②對線性移位寄存器序列進行非線性組合35p三、非線性序列密碼②對線性移位寄存器序列進行非線性組合對一個LSR進行非線性組合在這里用線性移位寄存器作為驅動源來驅動非線性電路產生非線性序列。其中用線性移位寄存器序列來確保所產生序列的長周期和均勻性，用非非線性電路來確保輸出序列的非線性和其它密碼性質。通常稱這里的非線性電路為前饋電路，稱這種輸出序列為前饋序列。對多個LSR進行非線性組合36ppt課件三、非線性序列密碼②對線性移位寄存器序列進行非線性組合36p三、非線性序列密碼②對線性移位寄存器序列進行非線性組合對一個LSR進行非線性組合非線性組合線性移位寄存器輸出37ppt課件三、非線性序列密碼②對線性移位寄存器序列進行非線性組合非線性三、非線性序列密碼②對線性移位寄存器序列進行非線性組合對多個LSR進行非線性組合線性移位寄存器1輸出線性移位寄存器2線性移位寄存器n非線性組合38ppt課件三、非線性序列密碼②對線性移位寄存器序列進行非線性組合線性移四、RC4序列密碼

RC4序列密碼是美國RSA數(shù)據(jù)安全公司設計的一種序列密碼。RSA數(shù)據(jù)安全公司將其收集在加密工具軟件BSAFE中。最初并沒有公布RC4的算法。人們通過對軟件進行逆向分析得到了算法。

在這種情況下RSA數(shù)據(jù)安全公司于1997年公布了RC4密碼算法。

密鑰40位的RC4，通過Internet32小時攻破。39ppt課件四、RC4序列密碼RC4序列密碼是美國RSA數(shù)據(jù)安全四、RC4序列密碼RC4密碼與基于移位寄存器的序列密碼不同。它是一種基于非線性數(shù)據(jù)表變換的序列密碼。它以一個足夠大的數(shù)據(jù)表為基礎，對表進行非線性變換，產生非線性的密鑰序列。40ppt課件四、RC4序列密碼RC4密碼與基于移位寄存器的序列密碼不同。四、RC4序列密碼RC4使用256個字節(jié)的S表和兩個指針（I和J）。S表的值S0,S1,…，S255是0,1,…，255的一個排列。I和J的初值為0。我們把RC4算法看成一個有限狀態(tài)自動機。把S表和I、J指針的具體取值稱為RC4的一個狀態(tài)：

T=<S0,S1，…，S255,I,J>對狀態(tài)T進行非線性變換，產生出新的狀態(tài)

，并輸出密鑰序列中一個字節(jié)k

。41ppt課件四、RC4序列密碼RC4使用256個字節(jié)的S表和兩個指針（I四、RC4序列密碼RC4的下一狀態(tài)函數(shù)定義如下：⑴I＝0，J＝0;⑵I=I+1mod256;⑶J=J+S[I]mod256;⑷交換S[I]和S[J]

。RC4的輸出函數(shù)定義如下：⑴h=S[I]

+S[J]mod256;⑵