計(jì)算機(jī)安全技術(shù)第八講信息保密技術(shù)

第裕信息保密枝木(2)

分組密碼的分析方法（續(xù)）

■一種攻擊的復(fù)雜度可以分為兩部分：數(shù)據(jù)復(fù)雜

度和處理復(fù)雜度。

-數(shù)據(jù)復(fù)雜度是實(shí)施該攻擊所需輸入的數(shù)據(jù)量。

-處理復(fù)雜度是處理這些數(shù)據(jù)所需的計(jì)算量。

■對(duì)某一攻擊通常是以這兩個(gè)方面的某一方面為

主要因素，來(lái)刻畫(huà)攻擊復(fù)雜度O

【例如】

-窮舉攻擊的復(fù)雜度實(shí)際就是考慮處理復(fù)雜度；

.差分密碼分析其復(fù)雜度主要是由該攻擊所需的明密

文對(duì)的數(shù)量來(lái)確定。

幾種常見(jiàn)的攻擊方法

1,強(qiáng)力攻擊

強(qiáng)力攻擊可用于任何分組密碼，且攻擊的復(fù)雜度

只依賴于分組長(zhǎng)度和密鑰長(zhǎng)度，嚴(yán)格地講攻擊所

需的時(shí)間復(fù)雜度依賴于分組密碼的工作效率（包

括加解密速度、密鑰擴(kuò)散速度以及存儲(chǔ)空間

等）。

強(qiáng)力攻擊常見(jiàn)的有：窮舉密鑰搜索攻擊、

字典攻擊、查表攻擊和時(shí)間-存儲(chǔ)權(quán)衡攻擊等。

幾種常見(jiàn)的攻擊方法（續(xù)）

2,線性密碼分析

本質(zhì)：一種已知明文攻擊方法。

基本思想：通過(guò)尋找一個(gè)給定密碼算法的有效的

線性近似表達(dá)式來(lái)破譯密碼系統(tǒng)。

對(duì)已知明文密文和特定密鑰，尋求線性表示式

（Q.x）十（6.y）=（d?x）

式中，（。也"層攻擊參數(shù)。對(duì)所有可能密鑰，此表

達(dá)式以概率5=1/2成立。對(duì)給定的密碼算法，

使|2-1/2|極大化。為此對(duì)每一盒的輸入和輸

出構(gòu)造統(tǒng)計(jì)線性路線，并最終擴(kuò)展到整個(gè)算法。

分組密碼的工作模式

-常用的分組密碼工作模式有4種:

L電子密碼本即ECB模式

2.密碼分組連接模式(CBC)模式

3.密碼反饋模式(CFB)模式

4.輸出反饋模式(OFB)模式。

ECBfElectronicCodeBook)

加密過(guò)程

解密過(guò)程

CBC(CipherBlockChaining)

Pn

I]

IV----?十4.十

]

|?|k—?|DES|I?|

C2C“

加密過(guò)程

c”

?|DES|k-?|DES|

—^1DESI

I

IV----?十A十---?十

IJ

PlP2Pn

解密過(guò)程

CFB(CipherFeedBack)

加密過(guò)程

解密過(guò)程

OFB(OutputFeedBack)

加密過(guò)程

解密過(guò)程

2.3公鑰加密技術(shù)

■本節(jié)提示

2.3.1基本概念

2.3.2RSA公鑰密鑰算法

2.3.3EIGamal算法

2.3,4橢圓曲線算法

2.3.1基本概念

■1976年，W.Diffie和MEHellman發(fā)表了“密碼學(xué)的新

方向(NewDirectionsinCryptography)”一文，提由了

公栩密碼學(xué)(Public-keycryptography)的思想，在公

鑰密碼體制(Public-keycryptosystem)中加密密朝和

解密密鑰是不同的，加密密鑰可以公開(kāi)傳播而不會(huì)危

及密碼體制的安全性。

-通信的一方利用某種數(shù)學(xué)方法可以產(chǎn)生一個(gè)密鑰對(duì)，

一個(gè)稱為公轉(zhuǎn)(Public-key),另外一個(gè)稱為私鑰

(Private-key)o該密鑰對(duì)申的公鑰與私鑰是不同的，

但又是相互對(duì)應(yīng)的，并且由公鑰不能推導(dǎo)出對(duì)應(yīng)的私

鑰。選擇某種算法(可以公開(kāi))能做到：用公鑰加密

的數(shù)據(jù)只有使用與該公鑰配對(duì)的私鑰才能解密。

基本概念（續(xù)）

■公鑰加密算法的核心——單向陷門函數(shù)，即從

一個(gè)方向求值是容易的。但再逆向計(jì)算卻很困

難，從而在實(shí)際上成為不可行。

■定義L設(shè)/是一個(gè)函數(shù)，如果對(duì)任意給定的工,

計(jì)算y，使得》=/（、）是容易計(jì)算的，但對(duì)于任意

給定的y，計(jì)算x，使得工二廠（丁屋難解的，

即求/的逆函數(shù)是難解的，則稱/是一個(gè)單向

函數(shù)。

基本概念（續(xù)）

■定義2.設(shè)/是一個(gè)函數(shù)，t是與/有關(guān)的

一個(gè)參數(shù)。對(duì)于任意給定的x,計(jì)算y,

使得y='是容易的。如果當(dāng)不知參數(shù)/

時(shí)，計(jì)算/的逆函數(shù)是難解的，但當(dāng)知

道參數(shù)，時(shí)，計(jì)算函數(shù)/的逆函數(shù)是容

易的，則稱/是一個(gè)單向陷門函數(shù)，參

數(shù),稱為陷門。

2.3.2RSA公鑰密碼算法

■RSA是Rivet,Shamir和Adleman于1978年在美

國(guó)麻省理工學(xué)院研制出來(lái)的，它是一種比較典

型的公開(kāi)密鑰加密算法。

■基礎(chǔ)

大數(shù)分解和素性檢測(cè)——將兩個(gè)大素?cái)?shù)相乘在

計(jì)算上很容易實(shí)現(xiàn)，但將該乘積分解為兩個(gè)大

素?cái)?shù)因子的計(jì)算量是相當(dāng)巨大的，以至于在實(shí)

際計(jì)算中是不能實(shí)現(xiàn)的。

RSA公鑰密碼算法(續(xù))

■算法內(nèi)容

⑴公鑰

選擇兩個(gè)互異的大質(zhì)數(shù)p和q，使〃=夕?，可〃)=(p-1)(9-1)0(〃)是

歐拉函數(shù)，選擇一個(gè)正數(shù)e，使其滿足(自押1,

貝IJ將K°=(〃,e)(乍為公鑰。

(2)私鑰

求出正數(shù)d使其滿足e*d=1mod0卜7)d)>1，則將

酌=(。，)，夕)作為私鑰。

(3)加密變換

府明文河作變換，使C=￡K,,(M)=〃emod〃，從而得到密文C。

(4)解密變換「

將密文C作變換，使M=OKs(C)=C，mod”，從而得到明文

RSA公鑰密碼算法（續(xù)）

■如果A要發(fā)送信息M給B,A和B之間用以

下方式進(jìn)行通信：

計(jì)算密文C=一發(fā)送C給B-從A

接收C-計(jì)算明文M=OK￡C）.

■一般要求p,q為安全質(zhì)數(shù)，現(xiàn)在商用的

安全要求為n的長(zhǎng)度不少于1024位。

■應(yīng)用：PEM,PGP

RSA公鑰密碼算法(續(xù))

-算法的安全性分析

1.如果密碼分析者能分解〃的因子夕和q,他就可以

求出。(〃)和解密的密鑰d,從而能破譯RSA,因此破

譯RSA不可能比因子分解難題更困難。

2.如果密碼分析者能夠不對(duì)〃進(jìn)行因子分解而求得，則

可以根據(jù)de=1mod0(H)

求得解密密鑰d,從而破甲R(shí)SA。因?yàn)?/p>

P+q=n-。⑺+1p_q=/p+q)2—4孔

所以知道。⑺和〃就可以容嘉地表得,和9，從而成

功分解〃，因此，不對(duì)〃進(jìn)行因子分解而直接計(jì)算

。(〃)并不比對(duì)〃進(jìn)行因子分解更容易。

RSA公鑰密碼算法（續(xù)）

3.如果密碼分析者既不能對(duì)n進(jìn)行因子分解，也不

能求放⑺而直接求得第甯密鑰d，則他就可以

計(jì)算是的倍數(shù)。而且利用

M的倍數(shù)可以容易地分解出n的因子。因此

直接計(jì)算解密密鑰d并不比對(duì)n進(jìn)行因子分解

更容易。

■注意問(wèn)題

■p和q的長(zhǎng)度相差不能太多.

■p-1和q-1都應(yīng)該包含大的素因子。

■p-1和q-1的最大公因子要盡可能小。

2.4流密碼技術(shù)

-本節(jié)友情提示

2.4.1流密碼基本原理

2.4.2二元加法流密碼

2.4.3幾種常見(jiàn)的流密碼算法

2.4流密碼技術(shù)

■在單鑰密碼體制中，按照加密時(shí)對(duì)明文處理方

式的不同，可分為分組密碼和流密碼。

■流密碼亦稱為序列密碼，是將待加密的明文分

成連續(xù)的字符或比特，然后用相應(yīng)的密鑰流對(duì)

之進(jìn)行加密，密鑰流由種子密鑰通過(guò)密鑰流生

成器產(chǎn)生。

■密鑰流可以方便地利用以移位寄存器為基礎(chǔ)的

電路來(lái)產(chǎn)生。

-特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，加密速度快，錯(cuò)誤傳播低。

2.4.1流密碼基本原理

■原理

通過(guò)隨機(jī)數(shù)發(fā)生器產(chǎn)種子密鑰K

生性能優(yōu)良的偽隨機(jī)

序列（密鑰流），使隨機(jī)數(shù)發(fā)生器

用該序列加密信息流

（逐比特加密），得密鑰流Ki

到密文序列。

明文流777/>加密變換一密文流Ci

2.4.2二元加法流密碼

符號(hào)描述與示例

加密操作：黑?操作：

密'鑰流：k］,k2,■■■-笛鑰流:k],k2,k2,■■■

十十十十十十

密?文流：C],C2,C3,???

明文流：nipm2,m3,...

([(

光?又VIL：5,c?,c2,■■■明文流：m15m2,m3,...

［例］電報(bào)內(nèi)容“專列下午2點(diǎn)到達(dá)。”的加密過(guò)程如下：

密鑰流：78,35,02,E4,B2…

十十十十十

明文流：D7,A8,CLD0,CF,C2,CE,E7,32,B5E3,B5,BD,B4,EEALA3

密文流：A^9D,C3,34,7D…

元加法流密碼（續(xù)）

-隨機(jī)性假設(shè)：

■在序列的一個(gè)周期內(nèi)，。與1的個(gè)數(shù)相差至多

為1;

■在序列的一個(gè)周期圈內(nèi)，長(zhǎng)為1的妙數(shù)占

總游程數(shù)的1/2,長(zhǎng)為2的游程數(shù)?占總游程數(shù)

的，…，長(zhǎng)為的游程數(shù)占總游程數(shù)的

且在等長(zhǎng)的游程中0,1游程各占一半；

■序列的異相自相關(guān)系數(shù)為一個(gè)常數(shù)。

■滿足隨機(jī)性假設(shè)的序列稱為偽隨機(jī)序列。

元加法流密碼(續(xù))

■流密碼的設(shè)計(jì)最核心的問(wèn)題是密鑰流生成器的

設(shè)計(jì)。

■密鑰流生成器一般由線性反饋移位寄存器

(LinearFeedbackShiftRegisterLFSR)和一個(gè)

非線性組合函數(shù)兩部分構(gòu)成，其中，線性反饋

移位寄存器部分稱為驅(qū)動(dòng)部分，另一部分稱為

非線性組合部分。

驅(qū)動(dòng)部分---------------?非線性______密鑰流左

(LFSR)---------------?組合部分

二元加法流密碼(續(xù))

■反饋移位寄存器(feedbackshiftregister)

1.組成結(jié)構(gòu)

反饋移位寄存器由n位的寄存器(稱為n-級(jí)移位寄存

器)和反饋函數(shù)(feedbackfunction)組成。移位寄

存器序列的理論由挪威政府的首席密碼學(xué)家Ernst

Selmer于1965年提出。

反饋函數(shù)和〃“j

元加法流密碼(續(xù))

■2.工作原理

移位寄存器中所有位右移一位，最

右邊移出的位是輸出位，最左端的一位

由反饋函數(shù)的輸出填充，此過(guò)程稱為進(jìn)

動(dòng)一拍。反饋函數(shù)f(b1,…,bn)是n元

(bl,…,bn)的布爾函數(shù)。移位寄存器根

據(jù)需要不斷地進(jìn)動(dòng)m拍，便有m位的輸

出，形成輸出序列Ol02…OITI。

元加法流密碼(續(xù))

■［例1］如圖所示為一個(gè)3-級(jí)反饋移位寄存器，反饋函數(shù)

f(x)=b3。b2,初態(tài)為：100o輸出序列生成過(guò)程如下:

■狀態(tài)輸出位一一一

100一0

110一0

011一1

101一1

110一0(a)移位寄存器結(jié)構(gòu)圖

011一1、

101一1初態(tài)(011)

因此，對(duì)應(yīng)初態(tài)(100)的輸出序列為：⑴。)一(1°1)

011011...(周期為3)(b)狀態(tài)轉(zhuǎn)移圖

元加法流密碼（續(xù)）

3.輸出序列的周期

移位寄存器的周期是指輸出序列中連續(xù)且重復(fù)出現(xiàn)部分的長(zhǎng)度

（位數(shù)）。

如［例1］輸出序列中連續(xù)且重復(fù)出現(xiàn)的序列為：011,則其周期

為3。其輸出序列可表示為：0（011）8。將其用圖的方式表示出來(lái)

稱為“序列圈”，如圖（c）所示。

4.狀態(tài)

某一時(shí)刻移位寄存器中所有位的值稱為一個(gè)狀態(tài)。n-級(jí)的

FSR共有2rl個(gè)狀態(tài)。

3-級(jí)移位寄存器的狀態(tài)共有23=8個(gè)，它們分別是：

000,001,010,011,100,101,110,1110

但是，并非所有的狀態(tài)都被用到。如［例1］除初始狀態(tài)以外，僅有

三個(gè)狀態(tài)周期性地參與了輸出序列的產(chǎn)生。

元加法流密碼（續(xù)）

■當(dāng)反饋移位寄存器的反饋函數(shù)是異或變

換時(shí)，這樣的反饋移位寄存器叫線性反

饋移位寄存器，如圖所示：

元加法流密碼（續(xù)）

?移位寄存器中存儲(chǔ)器的個(gè)數(shù)稱為移位寄存器的

級(jí)數(shù)，移位寄存器存儲(chǔ)的數(shù)據(jù)為寄存器的狀態(tài),

狀態(tài)的順序從左到佑依次為從最高位到最低位。

?在所有狀態(tài)中…叫初態(tài)，并且從左到

右依次稱為第一級(jí)、第二級(jí)、??.、第n級(jí)，亦

稱為抽頭1、抽頭2、抽頭3、..??、插頭n。n級(jí)

線性反饋移位寄存器的有效狀態(tài)為？小個(gè)。它

主要是用來(lái)產(chǎn)生周期大，統(tǒng)計(jì)性能分的序列。

元加法流密碼（續(xù)）

■非線性組合部分主要是增加密鑰流的復(fù)雜程度,

使密鑰流能夠抵抗各種攻擊（對(duì)流密碼的攻擊

手段主要是對(duì)密鑰流進(jìn)行攻擊）。

■以線性反饋移位寄存器產(chǎn)生的序列為基序列，

經(jīng)過(guò)不規(guī)則采樣、函數(shù)變換等（即非線性變

換），就可以得到實(shí)用安全的密鑰流。

■不規(guī)則采樣是在控制序列下，對(duì)被罡樣序列進(jìn)

行采樣輸出，得到的序列稱為輸出序列。

■控制序列的控制方式有鐘控方式、抽取方式等,

函數(shù)變換有前饋?zhàn)儞Q、有記憶變換等。

元加法流密碼（續(xù)）

■代表性的序列模型

1、鐘控模型

當(dāng)LFSR-1輸出1時(shí)，時(shí)鐘信號(hào)被采樣，即能通

過(guò)“與門”驅(qū)動(dòng)LFSR-2進(jìn)動(dòng)一拍；當(dāng)LFSR-1為

。時(shí)，時(shí)鐘信號(hào)不被采樣，即不能通過(guò)“與

門”，此時(shí)LFSR-2不進(jìn)動(dòng)，重復(fù)輸出前一位。

鐘控發(fā)生器的示意圖如下：

■2、前饋模型

Geffe發(fā)生器是前饋序列的典型模型，其前饋函

數(shù)g(x)=(xlx2)十(x2x3)為非線性函數(shù)，即當(dāng)

LFSR-2輸出1時(shí)，g(x)輸出位是LFSR-1的輸出位;

當(dāng)LFSR-2輸出0時(shí)，g(x)輸出位是LFSR-3的輸出

位。Geffe發(fā)生器示意圖如下：

2.4.3幾種常見(jiàn)的流密碼算法

1.A5算法

-法國(guó)，歐洲數(shù)字蜂窩移動(dòng)電話系統(tǒng)（GSM）中使用的序列密碼加密

算法

■3個(gè)LFSR,移位寄存器的長(zhǎng)度分別是19、22和23,但抽頭都較少

2.Rambutan算法

■英國(guó)的算法，由通信電子安全組織設(shè)計(jì)

-5個(gè)LFSR組成，每個(gè)LFSR長(zhǎng)度大約為80-級(jí)，而且有10個(gè)抽頭。

3.RC4算法

-由RonRivest