密碼學(xué)第四講密碼學(xué)基礎(chǔ)與應(yīng)用

尊浦多火學(xué)

第四講

密碼學(xué)基礎(chǔ)與應(yīng)用(1)

1

內(nèi)容提要

3.1密碼學(xué)的基本概念

3.2對稱密鑰密碼算法

3.3非對稱密鑰密碼算法

3.4單向散列函數(shù)

3.5數(shù)字簽名

3.6密鑰管理和公鑰基礎(chǔ)設(shè)施(PKI)

3.7OpenSSL簡介

2

內(nèi)容提要

3.1密碼學(xué)的基本概念

3.1.1密碼學(xué)的歷史

3.1.2密碼學(xué)的基本概念

3.1.3算法的分類

3.1.4密碼分析

3.1.5密碼技術(shù)的用途

3.2對稱密鑰密碼算法

3.3非對稱密鑰密碼算法

3.4單向散列函數(shù)

3.5數(shù)字簽名

3.6密鑰管理和公鑰基礎(chǔ)設(shè)施(PKI)

3.7OpenSSL簡介

3.1.1密碼學(xué)的歷史

?古羅馬：Caesar密碼

密碼本ABCDEFGHIGKLMNOPQRSTUVWXYZ

密文|DEFGHIGKLMN0PQRSTUVWXYZX13

明文Caesarwasagreatsoldier

密文Fdhvduzdvdjuhdwvroglhu

CAESAR密碼：c=(m+3)Mod264

3.L1密碼學(xué)的歷史（Cont.）

?美國南北戰(zhàn)爭

輸入方向

輸明文：

出CANY

方

向Canyouunderstand

0UUN

DERS

骷文:

TAND

codtaueanumynsd

5

3.1.1密碼學(xué)的歷史(Cont.)

轉(zhuǎn)輪密碼機(jī)ENIGMA,由

ArthurScherbius于1919年

發(fā)明，4輪ENIGMA在

1944年裝備德國海軍.

3.1.1密碼學(xué)的歷史(Cont.)

英國的TYPEX打字密碼機(jī)，是德國3輪ENIGMA的改進(jìn)型

密碼機(jī)。它在英國通信中使用廣泛，且在破譯密鑰后

幫助破解德國信號。

7

3.1.1密碼學(xué)的歷史(Cont.)

?圖靈(AlanMathisonTuring)

-AlanMathisonTuring,1912~1954.英國

數(shù)學(xué)家。一生對智能與機(jī)器之間的關(guān)系進(jìn)

行著不懈探索。

-1936年，24歲的圖靈提出“圖靈機(jī)”的設(shè)

想。二戰(zhàn)期間成功地破譯了納粹德國的密碼,

設(shè)計(jì)并制造了COLOSSUS,向現(xiàn)代計(jì)算機(jī)邁進(jìn)

了重要一步。

-1952年，圖靈遭到警方拘捕，原因是同性戀。

1954年6月8日,服毒自殺，年僅42歲。

-圖靈去世12年后，美國計(jì)算機(jī)協(xié)會以他的名

字命名了計(jì)算機(jī)領(lǐng)域的最高獎“圖靈獎”。

8

一個簡單的加密算法一異或

0?0=0x00=x

1?1=0x?x=0

_1

1十0=1X01=x

0?1=1X@x-1=1

9

一個簡單的加密算法一異或

?異或十

異或運(yùn)算（不帶進(jìn)位加法）：

明文：0011

加密：密鑰：⑦0101

密文：0110C=P十K

密

、

兀?oA1A1o

密

解

聞o1-1

明

、

兀o11

A-P=C十K

-已知明文、密文，怎樣求得密鑰？K=C十P

?只知道密文，如何求得密文和密鑰?

3.1.2密碼學(xué)的基本概念

?密碼學(xué)基本模型

Key

發(fā)plaintext接

送-----?收

方方

密碼分析

解密m=DK(C)

加密：c=EK(m)

(Cryptanalysis)

3.L2密碼學(xué)的基本概念(Cont.)

?密碼編碼：通過信息編碼使信息保密

?密碼分析：用分析方法解密信息

?基本術(shù)語

-明文(plaintext),密文(ciphertext)

-力口密(encrypt,encryption),解密(decrypt,decryption)

-密碼算法(Algorithm),密碼(Cipher):用來加密和解密的

數(shù)學(xué)函數(shù)

c=E(m),m=D(c),D(E(m)尸m

-密鑰(Key):算法中的一個變量

c=EKe(m),m=DKd(c),DKd(EKe(m))=m

12

3.1.3密碼算法的分類

?古典密碼算法和現(xiàn)代密碼算法

-按照算法和密鑰是否分開

?對稱密鑰密碼和非對稱密鑰密碼

-加密和解密是否使用相同的密鑰

?分組密碼和序列密碼

-每次操作的數(shù)據(jù)單元是否分塊

13

古典密碼和現(xiàn)代密碼

?古典密碼

-代替密碼(SubstitutionCipher)

-換位密碼(transpositionCipher)

-代替密碼與換位密碼的組合

?古典密碼(受限密碼)的缺陷

-密碼體制的安全性在于保持算法本身的保密性

-受限算法的缺陷

?不適合大規(guī)模生產(chǎn)

?不適合較大的或者人員變動較大的組織

?用戶無法了解算法的安全性

古典密碼和現(xiàn)代密碼（Cont.）

?現(xiàn)代密碼算法

-把算法和密鑰分開

-密碼算法可以公開，密鑰保密

-密碼系統(tǒng)的安全性在于保持密鑰的保密性

密鑰分配（秘密信道）

kk

發(fā)接

送m>m收

方方

密碼分析

15

對稱密碼算法和非對稱密碼算法

?對稱密鑰密碼算法，又稱傳統(tǒng)密碼算法、秘密密鑰

密碼算法

-加密和解密使用相同的密鑰Ke=Kd

-常用算法：DES,IDEA,Blowfish,RC2等

?優(yōu)點(diǎn)

-加密速度快，便于硬件實(shí)現(xiàn)和大規(guī)模生產(chǎn)

?缺點(diǎn)

-密鑰分配：必須通過保密的信道

-密鑰個數(shù)：n(n-1)/2

-無法用來簽名和抗抵賴(沒有第三方公證時)

16

對稱密碼和非對稱密碼(Cont.)

?非對稱密碼，又稱公開密鑰密碼算法

-加密和解密使用不同的密鑰(Kp,Ks),把加密密鑰公開，

解密密鑰保密：c=EKp(m),m=DKs(c)

-常用算法：RSA,DSA,背包算法，ElGamal,橢圓曲線等

?優(yōu)點(diǎn)：

-密鑰分配：不必保持信道的保密性

-密鑰個數(shù)：npair

-可以用來簽名和抗抵賴

?缺點(diǎn)

-加密速度慢，不便于硬件實(shí)現(xiàn)和大規(guī)模生產(chǎn)

17

分組密碼和序列密碼

?分組密碼(BlockCipher)

-一次加密或解密操作作用于一個數(shù)據(jù)塊，比如64位

?序列密碼(StreamCipher)

-一次加密或解密操作作用于一位或者一個字節(jié)

密鑰序列發(fā)生器-------Key------密鑰序列發(fā)生器

隨機(jī)序列????、-----丁-----------—------

p

Pi--------------------e-—sG—^3—i

隨機(jī)序列18

3.1.4密碼分析

?在未知密鑰的前提下，從密文恢復(fù)出明文、或者推

導(dǎo)出密鑰

?對密碼進(jìn)行分析的嘗試稱為攻擊

?攻擊方法分類（根據(jù)已知信息量的多少）

-唯密文攻擊

-已知明文攻擊

-選擇明文攻擊

-自適應(yīng)選擇明文攻擊

-選擇密文攻擊

-選擇密鑰攻擊

19

3.1.4密碼分析(Cont.)

?Successindealingwithunkownciphersis

measuredbythesefourthingsintheorder

named,perseverance^carefulmethodsof

analysis,intuition,luck.Theabilityatleastto

readthelanguageoftheoriginaltextisvery

desirablebutnotessential.

-ParkerHitt"軍事密碼破譯指南''的開場白

-毅力、審慎的分析方法、直覺、運(yùn)氣。

20

3.1.4密碼分析(Cont.)

?密碼算法的安全性

-如果破譯算法的代價(jià)大于加密數(shù)據(jù)本身的價(jià)值，

或者在信息的生命期內(nèi)無法破解，那么你的算法

可能是安全的。

-一個算法被稱為是計(jì)算上安全的，如果一個算法

用可得到的資源不能破解。

■處理復(fù)雜性：計(jì)算量，CPU時間

?數(shù)據(jù)復(fù)雜性：所需輸入數(shù)據(jù)量

?存儲復(fù)雜性：計(jì)算所需的存儲空間

21

3.1.4密碼技術(shù)的主要用途

?數(shù)據(jù)保密一數(shù)據(jù)加密/解密

-數(shù)據(jù)加密(存儲和傳輸)

?認(rèn)證技術(shù)

-實(shí)體身份認(rèn)證

-數(shù)據(jù)源發(fā)認(rèn)證

?信息完整性保護(hù)

-數(shù)據(jù)在傳輸過程中沒有被插入、篡改、重發(fā)；

?數(shù)字簽名和抗抵賴(Non-repudiation)

-源發(fā)抗抵賴

-交付抗抵賴

22

內(nèi)容提要

3.1密碼學(xué)的基本概念

3.2對稱密鑰密碼算法

321對稱密鑰算法簡介

3.2.2DES算法原理

323算法模式

3.2.4DES的安全性和速度

3.2.5其他對稱密碼算法簡介

3.3非對稱密鑰密碼算法

3.4單向散列函數(shù)

3.5數(shù)字簽名

3.6密鑰管理和公鑰基礎(chǔ)設(shè)施(PKI)

3.7OpenSSL簡介23

3.2.1對稱密鑰算法簡介

?加密和解密使用相同的密鑰：KE=KD

?密鑰必須使用秘密的信道分配

發(fā)

送接

方m-----am收

方

24

3.2.1對稱密鑰算法簡介(Cont.)

?常用對稱密鑰密碼算法

-DES(DataEncryptionStandard)及其各種變形

-IDEA(InternationalDataEncryptionAlgorithm)

-RC2,RC4,RC5,

-AES(AdvancedEncryptionStandard)

-CAST-128

-Blowfish

25

322DES算法原理

?IBM公司，70年代初提出，80年代成為國家

標(biāo)準(zhǔn)

?DES是一種對稱密鑰算法，密鑰長度為56bits

(加上奇偶校驗(yàn)，通常寫成64bits)

-是一種分組加密算法，64bits為一個分組

?基本思想：

-混亂(Confusion)和擴(kuò)散(Diffusion)

?使用標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算

26

DES加密過程

首先把明文0成以64bit為單位的塊m,對于

每個m,執(zhí)行如下操作

DES(m)=Ipi?T16-T15-..…0?0?IP(m)

-初始置換，IP

-16輪迭代，Ti9i=l,2,…16

-末置換，IP」

27

DES算法概要

初始換位(IP)

?初始換位(/尸)

585042342618102M=m1m2,……m62m639m64

605244362820124

625446383022146_1

645648403224168IP(M)

57494133251791

595143352719113

M-m58m50?……m23m15?m7

615345372921135

635547393123157

29

一輪迭代

32bits32bits

32bits32bits

擴(kuò)展置換(E)

?將Ri從32位擴(kuò)展到48位

?目的：輸入的一位影響下一步的兩個替換，使得輸

出對輸入的依賴性傳播得更快，密文的每一位都依

賴于明文的每一位

12345678

32

48

12345678

1234567891011121314.......464748

321234545678989....31321

s一盒置換

?將48比特壓縮成32比特

jRri(32bits)

E]

.S，.JISR

32

b)2b3b4b5b6

?輸入6比特：b]b2b3b4b5b6|||||

?輸出4比特：S(b]b6,b2b3b4b5)：S,

012345689101112131415

01441312151183106125907

10157414213110612119538

SI

24114813621115129731050

31512824917511314100613

01518146113497213120510

3

33

舉例：S1(100110)=1000

P-盒置換

?32比特輸入,32比特輸出

P-盒的輸出：

123456789303132

167202129122817115??????11425

34

子密鑰的生成

子密鑰生成

Ki

G+iD?+i

36

子密鑰生成

?拆分：56bits的密鑰分成兩部分，Q?Dj,各28bits

?循環(huán)左移：根據(jù)迭代的輪數(shù)，分別左移一位或兩位

12345678910111213141516

1122222212222221

?壓縮置換（置換選擇）：從56bits中選擇48bits

14171124153281562110

23191242681672720132

415231374755304051453348

444939563453464250362932*

末置換

?末置換?初始置換

408481656246432585042342618102

397471555236331605244362820124

386461454226230625446383022146

375451353216129645648403224168

36444125220602857494133251791

353431151195927595143352719113

342421050185826615345372921135

33141949175725635547393123157

IP-i(IP(M)尸M

38

?DES解密過程與加密過程完全相似，只不過

將16次迭代的子密鑰順序倒過來，即

1

m=DES】(c)=IP?T/T/..…T15?Tl6?IP(c)

?可以證明，

DES(DES1(m))=m

39

3.2.3DES的算法模式

?電子密碼本(EletronicCoodBook,ECB)

?密碼分組鏈(CipherBlockChaining,CBC)

?密文反饋(CipherFeedBack,CFB)

?輸出反饋(OutputFeedBack,OFB)

40

電子密碼本模式（ECB）

?基本的DES算法就是ECB模式

?相同的輸入永遠(yuǎn)產(chǎn)生相同的輸出

?相當(dāng)于加密、解密雙方各有一個密碼本，對于一個密鑰，密碼本

有264個表項(xiàng)

?存在重放（Replay）類型的攻擊，特別是對于結(jié)構(gòu)化的報(bào)文：

-攻擊者可以在不知道密鑰的情況下修改被加密過的消息

12345678910111213

接

時間發(fā)送受存款

銀

行儲戶姓名帳號

標(biāo)記銀行金額

41

密碼分組鏈模式（CBC）

IV

G=￡O

42

密碼分組鏈模式（CBC）（續(xù)）

E-\C^=E-（E（C-十月））=C-十月

?I=。Z「-1十C1—1?十？I=?I

43

3.2.4DES的安全性和速度

?弱密鑰

-產(chǎn)生的子密鑰相同,4個，如0000…00,1密11…同1,

0101010101...01,101010...10

?半弱密鑰

-用不同的密鑰加密產(chǎn)生相同的密文，即用一個密鑰加密

的信息可以用其他密鑰解開，12個

?密鑰的長度

-1976年，耗資2000萬美元的計(jì)算機(jī)，可以在一天中找到

密鑰。

-1993年，設(shè)計(jì)100萬美元的計(jì)算機(jī)，3.5小時用窮舉法找到

密鑰。

44

3.2.5DES的變形

?三重DES加密，密鑰長度為112比特,k=k]k2

k]k2k]k1k2瓦