密码学第四讲密码学基础与应用

尊浦多火学

第四讲

密码学基础与应用(1)

1

内容提要

3.1密码学的基本概念

3.2对称密钥密码算法

3.3非对称密钥密码算法

3.4单向散列函数

3.5数字签名

3.6密钥管理和公钥基础设施(PKI)

3.7OpenSSL简介

2

内容提要

3.1密码学的基本概念

3.1.1密码学的历史

3.1.2密码学的基本概念

3.1.3算法的分类

3.1.4密码分析

3.1.5密码技术的用途

3.2对称密钥密码算法

3.3非对称密钥密码算法

3.4单向散列函数

3.5数字签名

3.6密钥管理和公钥基础设施(PKI)

3.7OpenSSL简介

3.1.1密码学的历史

•古罗马：Caesar密码

密码本ABCDEFGHIGKLMNOPQRSTUVWXYZ

密文|DEFGHIGKLMN0PQRSTUVWXYZX13

明文Caesarwasagreatsoldier

密文Fdhvduzdvdjuhdwvroglhu

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

3.L1密码学的历史（Cont.）

•美国南北战争

输入方向

输明文：

出CANY

方

向Canyouunderstand

0UUN

DERS

骷文:

TAND

codtaueanumynsd

5

3.1.1密码学的历史(Cont.)

转轮密码机ENIGMA,由

ArthurScherbius于1919年

发明，4轮ENIGMA在

1944年装备德国海军.

3.1.1密码学的历史(Cont.)

英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型

密码机。它在英国通信中使用广泛，且在破译密钥后

帮助破解德国信号。

7

3.1.1密码学的历史(Cont.)

•图灵(AlanMathisonTuring)

-AlanMathisonTuring,1912~1954.英国

数学家。一生对智能与机器之间的关系进

行着不懈探索。

-1936年，24岁的图灵提出“图灵机”的设

想。二战期间成功地破译了纳粹德国的密码,

设计并制造了COLOSSUS,向现代计算机迈进

了重要一步。

-1952年，图灵遭到警方拘捕，原因是同性恋。

1954年6月8日,服毒自杀，年仅42岁。

-图灵去世12年后，美国计算机协会以他的名

字命名了计算机领域的最高奖“图灵奖”。

8

一个简单的加密算法一异或

0©0=0x00=x

1©1=0x®x=0

_1

1㊉0=1X01=x

0©1=1X@x-1=1

9

一个简单的加密算法一异或

•异或㊉

异或运算（不带进位加法）：

明文：0011

加密：密钥：⑦0101

密文：0110C=P㊉K

密

、

兀©oA1A1o

密

解

闻o1-1

明

、

兀o11

A-P=C㊉K

­已知明文、密文，怎样求得密钥？K=C㊉P

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

3.1.2密码学的基本概念

•密码学基本模型

Key

发plaintext接

送-----►收

方方

密码分析

解密m=DK(C)

加密：c=EK(m)

(Cryptanalysis)

3.L2密码学的基本概念(Cont.)

•密码编码：通过信息编码使信息保密

•密码分析：用分析方法解密信息

•基本术语

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

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

-密码算法(Algorithm),密码(Cipher):用来加密和解密的

数学函数

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密码算法的分类

•古典密码算法和现代密码算法

-按照算法和密钥是否分开

・对称密钥密码和非对称密钥密码

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

•分组密码和序列密码

-每次操作的数据单元是否分块

13

古典密码和现代密码

・古典密码

-代替密码(SubstitutionCipher)

-换位密码(transpositionCipher)

-代替密码与换位密码的组合

•古典密码(受限密码)的缺陷

-密码体制的安全性在于保持算法本身的保密性

-受限算法的缺陷

・不适合大规模生产

・不适合较大的或者人员变动较大的组织

•用户无法了解算法的安全性

古典密码和现代密码（Cont.）

•现代密码算法

-把算法和密钥分开

-密码算法可以公开，密钥保密

-密码系统的安全性在于保持密钥的保密性

密钥分配（秘密信道）

kk

发接

送m>m收

方方

密码分析

15

对称密码算法和非对称密码算法

•对称密钥密码算法，又称传统密码算法、秘密密钥

密码算法

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

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

•优点

-加密速度快，便于硬件实现和大规模生产

•缺点

-密钥分配：必须通过保密的信道

-密钥个数：n(n-1)/2

-无法用来签名和抗抵赖(没有第三方公证时)

16

对称密码和非对称密码(Cont.)

•非对称密码，又称公开密钥密码算法

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

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

-常用算法：RSA,DSA,背包算法，ElGamal,椭圆曲线等

•优点：

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

-密钥个数：npair

-可以用来签名和抗抵赖

•缺点

-加密速度慢，不便于硬件实现和大规模生产

17

分组密码和序列密码

•分组密码(BlockCipher)

-一次加密或解密操作作用于一个数据块，比如64位

•序列密码(StreamCipher)

-一次加密或解密操作作用于一位或者一个字节

密钥序列发生器-------Key------密钥序列发生器

随机序列・・・・、-----丁-----------—------

p

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

随机序列18

3.1.4密码分析

•在未知密钥的前提下，从密文恢复出明文、或者推

导出密钥

•对密码进行分析的尝试称为攻击

•攻击方法分类（根据已知信息量的多少）

-唯密文攻击

-已知明文攻击

-选择明文攻击

-自适应选择明文攻击

-选择密文攻击

-选择密钥攻击

19

3.1.4密码分析(Cont.)

•Successindealingwithunkownciphersis

measuredbythesefourthingsintheorder

named,perseverance^carefulmethodsof

analysis,intuition,luck.Theabilityatleastto

readthelanguageoftheoriginaltextisvery

desirablebutnotessential.

-ParkerHitt"军事密码破译指南''的开场白

-毅力、审慎的分析方法、直觉、运气。

20

3.1.4密码分析(Cont.)

•密码算法的安全性

-如果破译算法的代价大于加密数据本身的价值，

或者在信息的生命期内无法破解，那么你的算法

可能是安全的。

-一个算法被称为是计算上安全的，如果一个算法

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

■处理复杂性：计算量，CPU时间

•数据复杂性：所需输入数据量

•存储复杂性：计算所需的存储空间

21

3.1.4密码技术的主要用途

•数据保密一数据加密/解密

-数据加密(存储和传输)

•认证技术

-实体身份认证

-数据源发认证

•信息完整性保护

-数据在传输过程中没有被插入、篡改、重发；

•数字签名和抗抵赖(Non-repudiation)

-源发抗抵赖

-交付抗抵赖

22

内容提要

3.1密码学的基本概念

3.2对称密钥密码算法

321对称密钥算法简介

3.2.2DES算法原理

323算法模式

3.2.4DES的安全性和速度

3.2.5其他对称密码算法简介

3.3非对称密钥密码算法

3.4单向散列函数

3.5数字签名

3.6密钥管理和公钥基础设施(PKI)

3.7OpenSSL简介23

3.2.1对称密钥算法简介

•加密和解密使用相同的密钥：KE=KD

•密钥必须使用秘密的信道分配

发

送接

方m-----am收

方

24

3.2.1对称密钥算法简介(Cont.)

•常用对称密钥密码算法

-DES(DataEncryptionStandard)及其各种变形

-IDEA(InternationalDataEncryptionAlgorithm)

-RC2,RC4,RC5,

-AES(AdvancedEncryptionStandard)

-CAST-128

-Blowfish

25

322DES算法原理

•IBM公司，70年代初提出，80年代成为国家

标准

•DES是一种对称密钥算法，密钥长度为56bits

(加上奇偶校验，通常写成64bits)

­是一种分组加密算法，64bits为一个分组

・基本思想：

-混乱(Confusion)和扩散(Diffusion)

•使用标准的算术和逻辑运算

26

DES加密过程

首先把明文0成以64bit为单位的块m,对于

每个m,执行如下操作

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

扩展置换(E)

•将Ri从32位扩展到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

•循环左移：根据迭代的轮数，分别左移一位或两位

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模式

•相同的输入永远产生相同的输出

•相当于加密、解密双方各有一个密码本，对于一个密钥，密码本

有264个表项

•存在重放（Replay）类型的攻击，特别是对于结构化的报文：

-攻击者可以在不知道密钥的情况下修改被加密过的消息

12345678910111213

接

时间发送受存款

银

行储户姓名帐号

标记银行金额

41

密码分组链模式（CBC）

IV

G=£O

42

密码分组链模式（CBC）（续）

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

?I=。Z「-1㊉C1—1।㊉？I=?I

43

3.2.4DES的安全性和速度

•弱密钥

-产生的子密钥相同,4个，如0000…00,1密11…同1,

0101010101...01,101010...10

•半弱密钥

-用不同的密钥加密产生相同的密文，即用一个密钥加密

的信息可以用其他密钥解开，12个

•密钥的长度

-1976年，耗资2000万美元的计算机，可以在一天中找到

密钥。

-1993年，设计100万美元的计算机，3.5小时用穷举法找到

密钥。

44

3.2.5DES的变形

・三重DES加密，密钥长度为112比特,k=k]k2

k]k2k]k1k2瓦