密码编码学与网络安全培训教材

密码编码学与网络安全电子工业出版社2006

-

2007第一页，共六十一页。第3章对称算法DES3.1

分组密码算法原理3.2

DES算法3.3

DES强度↓↓↓3.4差分分析和线性分析↓3.5

分组密码设计原理*

3.A

DES

in

/etc/passwd↓↓*

3.B

DES

in

OpenSSL↓第二页，共六十一页。密码技术发展

1918，William

F.

Friedman，The

Index

of

Coincidenceand

Its

Applications

in

Cryptography

1949，Claude

Shannon，The

Communication

Theoryof

Secrecy

Systems1967，David

Kahn，The

Codebreakers1970s，NBS/NIST，DES

（90s,

AES）1976，Diffie,

Hellman，New

Directory

in

Cryptography

1984，C.H.

Bennett，Quantum

Cryptography:

PublicKey

Distribution

and

Coin

Tossing1985，N.

Koblitz，Elliptic

Curve

Cryptosystem2000，AES第三页，共六十一页。3.1分组密码算法原理分组密码算法Block

Cipher明文被分为固定长度的块(即分组)，对每个分组用相同的算法和密钥加解密分组一般为n＝64比特，或更长(Padding)密文分组和明文分组同样长对某个密钥可以构造一个明密文对照表Codebook

(Substitution

Table)所以分组的长得至少64比特才好密钥空间2^k<<可逆映射个数(2^n)!第四页，共六十一页。序列密码算法(流密码算法)流密码算法Stream

Cipher每次可以加密一个比特适合比如远程终端输入等应用流密码可用伪随机数发生器实现密钥做为随机数种子，产生密钥流keystream(不重复,或极大周期)XOR

(plaintext，key-stream

)One-time

Pad第五页，共六十一页。比较基本区别粒度

8字节分组vs.

1比特或1字节各自适应不同的应用数据格式Padding对相同的明文分组，总是输出相同的密文分组；而流密码却输出不同的密文比特流密码一般快很多分组密码多些，是主流分组密码也可以用作流模式安全性对比第六页，共六十一页。Block

Cipher

Principles0000

11100001

01000010

11010011

00010100

00100101

11110110

10110111

10001000

00111001

10101010

01101011

11001100

01011101

10011110

00001111

01110000

11100001

00110010

01000011

10000100

00010101

11000110

10100111

11111000

01111001

11011010

10011011

01101100

10111101

00101110

0000乘积密码：重复使用代替和置换，实现混乱和扩散。第七页，共六十一页。Feistel(DES)加密框架明文分组的长n＝2w –分左右两半L0

R0密钥K产生子钥：K→k1，k2，…，kr–r是轮数，比如16轮⊕是异或函数XOR–

p⊕x⊕x

=

p函数F是散列混乱函数–可以是手工精心构造的查表函数第八页，共六十一页。Feistel网络•第九页，共六十一页。Feistel解密•第十页，共六十一页。Feistel

–

‘for’

Loop加密计算序列L0＝左半L1＝R0R0＝右半R1＝L0⊕F(k1,R0)L2＝R1

R2＝L1⊕F(k2,R1)L3＝R3

R3＝L2⊕F(k3,R2)…Ri＝Li-1⊕F(ki,Ri-1)Li＝Ri-1…Ln＝Rn-1Rn＝Ln-1⊕F(kn,Rn-1)密文即（Ln，Rn）解密计算第十一页，共六十一页。2轮解密举例

假设n＝2轮，C

＝（L2，R2）加密明文＝半＋半＝L0+R0L1＝R0

R1＝L0⊕F(k1,R0)L2＝R1

R2＝L1⊕F(k2,R1)解密密文＝半＋半＝L2＋R2R1＝L2

L1＝R2⊕F(k2,R1)R0＝L1

L0＝R1⊕F(k1,R0)明文＝L0＋R0L1＝R2⊕F(k2,R1)＝L1⊕F(k2,R1)⊕F(k2,R1)＝L1L0＝R1⊕F(k1,R0)＝L0⊕F(k1,R0)⊕F(k1,R0)＝L0第十二页，共六十一页。Feistel伪代码m：0,

1i,

i+1

<-

kir,

r+1

<-

kr明文m长度n＝2t，记为m0m1，每个长度为t密钥k产生r个子密钥k1,k2

,...,kr加密Efor

i=2

to

r+1

domi＝mi-2

XOR

f(mi-1,

ki-1)得密文（mr，mr+1）解密Dfor

i=r

to

1

domi-1＝mi+1

XOR

f(mi,

ki)或for

i=r-1

to

0

domi＝mi+2

XOR

f(mi+1,

ki+1)＝mi

XOR

f(mi+1,

ki+1)

XOR

f(mi+1,

ki+1)＝mi唯一的非线性结构就是F可以重复使用两个变量即可第十三页，共六十一页。Feistel参数特性分组大小密钥大小循环次数一般仅几轮是不够的，得十几轮才好，如16轮子钥产生算法越复杂越好轮函数Round关键其他考虑速度（尤其是软件实现的速度）便于分析（使用简洁的结构）第十四页，共六十一页。Feistel类算法举例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel结构的AES、IDEA*绝大数分组密码属于或类似Feistel结构多轮每轮有XOR（或能恢复的操作）轮函数第十五页，共六十一页。3.2

DESData

Encryption

Standard1971

IBM

Horst

Feistel—Lucifer→DES，key由128bit→56bit1973

NBS，77

NIST

FIPS-46－NBS/NIST、IBM、NSA1994最后一次延长到1999年－AES取代之参数Feistel体制分组密码分组大小64bit，密钥大小56bit，轮数16轮S-Boxes

*第十六页，共六十一页。DES•第十七页，共六十一页。密钥置换选择-1Key

Permuted

Choice

One

(PC-1)57

49

41

33

25

17

9

81

58

50

42

34

26

18

1610

2

59

51

43

35

27

2419

11 3

60

52

44

36

327×8K的56比特重新排列，成为C0D01 2

3

4

5

6

7

89

10

11

12

13

14

15

1617

18

19

20

21

22

23

2425

26

27

28

29

30

31

3233

34

35

36

37

38

39

4063

55

47

39

31

23

15

4041

42

43

44

45

46

47

487

62

54

46

38

30

22

4849

50

51

52

53

54

55

5614

6

61

53

45

37

29

5657

58

59

60

61

62

63

6421

135

28

20

124

64第十八页，共六十一页。Keyi

(48bit)C0D0…C15D15第十九页，共六十一页。PC-2141711241

5

3

28156211023

19

12

426816727

20

13

24152313747

55

30

408×6未入选的：9、18、22等51

45

33

48

44

49

39

5634

53

46

42

50

36

29

32Round

number

1

2

3

4

5

67

8910111213141516Bits

rotated

1

1

2

2

22

22

1

2

2

2

2

2

21每轮从56比特中选取48比特即为Ki，并同时左移第二十页，共六十一页。初始置换及逆置换Initial

Permutation

（IP/IP-1）63

55

47

39

31

23

15

758

50

42

34

26

18

10240848

16

56

24

64

3260

52

44

36

28

20

12439747

15

55

23

63

3162

54

46

38

30

22

14

638646

14

54

22

62

3064

564840322416837545135321612957

49413325179136444125220602859

514335271911335343115119592761

534537292113534242105018582633

1

41

9

49

17

57

25初始明文按照IP重排；16轮后的密文按照IP-1重排即为最后密文oddeven第二十一页，共六十一页。轮One

Round•第二十二页，共六十一页。扩展置换Expansion

Permutation•32

1

2

3

4

545678

989101112

131213141516

171617181920

212021222324

252425262728

292829303132

1Ri的32bit

→48bit两边的是重复选中的6×8第二十三页，共六十一页。轮函数Round

Function•第二十四页，共六十一页。S盒S-Boxes：1/4两边2比特选择行号中间4比特选择列号第二十五页，共六十一页。S-Boxes：5-8第二十六页，共六十一页。从S盒出来后重排：Permutation

FunctionP

8×416 7

20

21

29

12

28

171 15

23

26 5

18

31

102 8

24

14

32

27

3

919

13

30 6

22

11 4

25第二十七页，共六十一页。DESReview第二十八页，共六十一页。一个DES计算实例p=0123456789ABCDEFk=133457799BBCDFF1•……••c=85E813540F0AB405第二十九页，共六十一页。3.3

DES安全强度对DES的争议集中在密钥空间太小

Key

space从Lucifer的2^128降到DES的2^56DES

Challenge

III,

22

hours

15

minutesS盒S-BoxesS盒的设计准则？陷门？trapdoors

by

NSA(?)

“Form

surprise

to

suspicion”从惊喜(甚至能够抵御很后来才发现的各种攻击)

到怀疑(n年前就如此厉害的NSA现在究竟有多厉害)第三十一页，共六十一页。密钥大小Key

Size第三十二页，共六十一页。穷举(蛮力)攻击Cost/Time表第三十三页，共六十一页。“Deep

Crack”

Hardware

CrackerDeveloped

by

theElectronic

Frontier

FoundationCost

US$210,000–

$80,000

design–

$210,000

materials

(chips,

boards,

chassis

etc)第三十四页，共六十一页。VLSI

Chip

Developed

by

AdvancedWireless

Technologies24

search

units

per

chip40

MHz16

cycles

per

encryption2.5

million

keys/sBoard

contains

64

chips6

cabinets

holding

29

boards第三十五页，共六十一页。Deep

Crack

System90

billion

keys/s37,000

search

unitsc.f.

Distributed

Net’s

34

billion

keys/sControlled

by

PCchecks

possible

all

ASCII

candidate

solutionsfrom

the

search

unitsSolved

RSA’s

DES-III

in

22

hoursJan

18,

1999第三十六页，共六十一页。蛮力攻击对明文内容的要求*问题：如何辨别出来？对给定的某个密文，任何一个密钥都可以解密出一个可能的明文，但是其中应该只有一个是正确的明文。必须事先知道明文的结构，比如已经知道这是文字文本、源程序（图像、声音、压缩的？）如果有两个密钥，解密出来的两个明文都有意义？可能性极小因为密钥空间2^k<<可逆映射个数(2^n)!One

time

pad就是让对手分辨不出哪个更像正确明文第三十七页，共六十一页。S盒特性SizeInput

N

×

output

M8×32，but

DES

6×42^N

→

M

bitsin

contrast

to

DES’s

2^2×2^4→4NonlinearBent

functionS-boxes’

evolutionBlowfish,

but

DES’s

is

man-madeavoid

analyze

in

advance第三十八页，共六十一页。AvalancheEffect

in

DES(A)P1：00000…0

(64bit)P2：10000…0(相差1bit)K

：0000001

10010110100100

11000100011100

00110000011100

0110010(B)K1：…(56bit)K2：…(相差1bit)P

：…(64bit)第三十九页，共六十一页。DES弱密钥DES弱密钥：4(子密钥相同)0101

0101

0101

01011F1F

1F1F

E0E0

E0E0E0E0

E0E0

1F1F

1F1FFEFE

FEFE

FEFE

FEFE0000000

0000000eq 0000000

FFFFFFFFFFFFFF

0000000FFFFFFF

FFFFFFFDES 半弱密钥：12（两个子密钥，互为加解密）01FE

01FE

01FE

01FE1FE0

1FE0

0EF1

0EF101E0

01E0

01F1

01F1FE01

FE01

FE01

FE01E01F

E01F

F10E

F10Evs E001

E001

F101

F1011FFE1FFE0EFE0EFEFE1FFE1F

FE0E

FE0E011F011F010E010E1F011F01

0E01

0E01E0FE

E0FE

F1FE

F1FEFEE0

FEE0

FEF1

FEF1DES可能的弱密钥：24（四个子密钥）–…第四十页，共六十一页。3.4差分分析和线性分析蛮力攻击计时攻击差分分析线性分析–正面分析密码算法的新技术，在很多算法上取得很好的效果第四十一页，共六十一页。差分分析Differential

CryptanalysisBiham,

Shamir

(‘S’)–

1991»

NSA,1974攻击实例–对8轮DES，只需微机几分钟–对16轮DES，复杂度为2^47需这么多的选择明文，使本方法只有理论意义Differential

Cryptanalysis

of

the

Full

16-round

DES第四十二页，共六十一页。线性分析Linear

Cryptanalysis第四十三页，共六十一页。DES其他DES肯定能破译不单是RSA

challengeDES算法仍值得信赖但是关键场合不要用DES对一般个人用户仍是安全的RSA

challenge反而给了信心DES还是AES，或者其他DES模块仍广泛存在，AES还没有普及如果软件实现，任何一个经过考验的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/Open第四十四页，共六十一页。3.5分组密码的设计原理DES

Design

Criteria设计准则as

reported

by

Coppersmith

in

[COPP94]7

criteria

for

S-boxes

provide

fornon-linearityresistance

to

differential

cryptanalysisgood

confusion3

criteria

for

permutation

P

provide

forincreased

diffusion第四十五页，共六十一页。分组密码设计原理轮数轮函数FS盒雪崩效应密钥使用方法子钥衍生方法雪崩效应第四十六页，共六十一页。轮函数F及S盒的设计strict

avalanche

criterionbit

independence

criterion轮函数F雪崩效应准则独立准则S盒构造方法随机方法随机加测试方法人工构造方法数学构造方法•第四十七页，共六十一页。查阅和学习第四十八页，共六十一页。3.A

DES

in

/etc/passwdfile

‘passwd’

formatusername:passwd:UID:GID:full_name:directory:shell{From

Shadow-Password-HOWTO}account:password:UID:GID:GECOS:directory:shell{From

RH8}shadow/etc/passwd

passwd

--->

*/etc/shadow

passwdusername:passwd:last:may:must:warn:expire:disable:reservedsampleusername:Npge08pfz4wuk:503:100:FN:/home/username:/bin/shusername:x:503:100:FN:/home/username:/bin/shusername:Npge08pfz4wuk:9479:0:10000::::1/22/2第四十九页，共六十一页。crypt()函数crypt#define

_XOPEN_SOURCE#include

<unistd.h>char

*crypt(const

char

*key,

const

char

*salt);passwd

space–128-32-’7f’=95个可用字符–

95^nsalt两个字符，每个可从[a-zA-Z0-9./]中选出来，即有

4096种不同取值抵制字典攻击中的预算值第五十页，共六十一页。crypt()描述从passwd到keypadding形成8字符的组每组产生56bits＝8×7的密钥如果多于1组，则XOR累计重复加密64比特0到25回–中间置换，受salt控制，计有4096种不同的置换输出2＋1字符2字符是明码salt11字符是编码后的DES的64bits输出密文第五十一页，共六十一页。crypt()

Fig•第五十二页，共六十一页。Passwd

Cracker第五十三页，共六十一页。Zip

cracker

sampleAdvanced

ZIP

Password

Recovery

statistics:Encrypted

ZIP-file:

sdjfks.zipTotal

passwords:

2,091,362,752Total

time:

6m

58s

725msAverage

speed

(passwords/s):

4,994,597Password

for

this

file:

7uee23Password

in

HEX:

37

75

65

65

32

33第五十四页，共六十一页。3.B

DES

in

OpenSSL

DES算法很复杂，实现起来非常琐碎，在性能和移植性上也难于友好，因此如果软件实现提倡使用开放源码的实现，如OpenSSL等。

OpenSSL是SSL/TLS协议的开放实现，其中也实现了几十种密码算法。

OpenSS