密碼編碼學(xué)與網(wǎng)絡(luò)安全培訓(xùn)教材

密碼編碼學(xué)與網(wǎng)絡(luò)安全電子工業(yè)出版社2006

-

2007第一頁，共六十一頁。第3章對稱算法DES3.1

分組密碼算法原理3.2

DES算法3.3

DES強(qiáng)度↓↓↓3.4差分分析和線性分析↓3.5

分組密碼設(shè)計(jì)原理*

3.A

DES

in

/etc/passwd↓↓*

3.B

DES

in

OpenSSL↓第二頁，共六十一頁。密碼技術(shù)發(fā)展

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明文被分為固定長度的塊(即分組)，對每個(gè)分組用相同的算法和密鑰加解密分組一般為n＝64比特，或更長(Padding)密文分組和明文分組同樣長對某個(gè)密鑰可以構(gòu)造一個(gè)明密文對照表Codebook

(Substitution

Table)所以分組的長得至少64比特才好密鑰空間2^k<<可逆映射個(gè)數(shù)(2^n)!第四頁，共六十一頁。序列密碼算法(流密碼算法)流密碼算法Stream

Cipher每次可以加密一個(gè)比特適合比如遠(yuǎn)程終端輸入等應(yīng)用流密碼可用偽隨機(jī)數(shù)發(fā)生器實(shí)現(xiàn)密鑰做為隨機(jī)數(shù)種子，產(chǎn)生密鑰流keystream(不重復(fù),或極大周期)XOR

(plaintext，key-stream

)One-time

Pad第五頁，共六十一頁。比較基本區(qū)別粒度

8字節(jié)分組vs.

1比特或1字節(jié)各自適應(yīng)不同的應(yīng)用數(shù)據(jù)格式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乘積密碼：重復(fù)使用代替和置換，實(shí)現(xiàn)混亂和擴(kuò)散。第七頁，共六十一頁。Feistel(DES)加密框架明文分組的長n＝2w –分左右兩半L0

R0密鑰K產(chǎn)生子鑰：K→k1，k2，…，kr–r是輪數(shù)，比如16輪⊕是異或函數(shù)XOR–

p⊕x⊕x

=

p函數(shù)F是散列混亂函數(shù)–可以是手工精心構(gòu)造的查表函數(shù)第八頁，共六十一頁。Feistel網(wǎng)絡(luò)?第九頁，共六十一頁。Feistel解密?第十頁，共六十一頁。Feistel

–

‘for’

Loop加密計(jì)算序列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）解密計(jì)算第十一頁，共六十一頁。2輪解密舉例

假設(shè)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，每個(gè)長度為t密鑰k產(chǎn)生r個(gè)子密鑰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唯一的非線性結(jié)構(gòu)就是F可以重復(fù)使用兩個(gè)變量即可第十三頁，共六十一頁。Feistel參數(shù)特性分組大小密鑰大小循環(huán)次數(shù)一般僅幾輪是不夠的，得十幾輪才好，如16輪子鑰產(chǎn)生算法越復(fù)雜越好輪函數(shù)Round關(guān)鍵其他考慮速度（尤其是軟件實(shí)現(xiàn)的速度）便于分析（使用簡潔的結(jié)構(gòu)）第十四頁，共六十一頁。Feistel類算法舉例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel結(jié)構(gòu)的AES、IDEA*絕大數(shù)分組密碼屬于或類似Feistel結(jié)構(gòu)多輪每輪有XOR（或能恢復(fù)的操作）輪函數(shù)第十五頁，共六十一頁。3.2

DESData

Encryption

Standard1971

IBM

Horst

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

NBS，77

NIST

FIPS-46－NBS/NIST、IBM、NSA1994最后一次延長到1999年－AES取代之參數(shù)Feistel體制分組密碼分組大小64bit，密鑰大小56bit，輪數(shù)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，并同時(shí)左移第二十頁，共六十一頁。初始置換及逆置換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?第二十二頁，共六十一頁。擴(kuò)展置換Expansion

Permutation?32

1

2

3

4

545678

989101112

131213141516

171617181920

212021222324

252425262728

292829303132

1Ri的32bit

→48bit兩邊的是重復(fù)選中的6×8第二十三頁，共六十一頁。輪函數(shù)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第二十八頁，共六十一頁。一個(gè)DES計(jì)算實(shí)例p=0123456789ABCDEFk=133457799BBCDFF1?……??c=85E813540F0AB405第二十九頁，共六十一頁。3.3

DES安全強(qiáng)度對DES的爭議集中在密鑰空間太小

Key

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

Challenge

III,

22

hours

15

minutesS盒S-BoxesS盒的設(shè)計(jì)準(zhǔn)則？陷門？trapdoors

by

NSA(?)

“Form

surprise

to

suspicion”從驚喜(甚至能夠抵御很后來才發(fā)現(xiàn)的各種攻擊)

到懷疑(n年前就如此厲害的NSA現(xiàn)在究竟有多厲害)第三十一頁，共六十一頁。密鑰大小Key

Size第三十二頁，共六十一頁。窮舉(蠻力)攻擊Cost/Time表第三十三頁，共六十一頁?！癉eep

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第三十六頁，共六十一頁。蠻力攻擊對明文內(nèi)容的要求*問題：如何辨別出來？對給定的某個(gè)密文，任何一個(gè)密鑰都可以解密出一個(gè)可能的明文，但是其中應(yīng)該只有一個(gè)是正確的明文。必須事先知道明文的結(jié)構(gòu)，比如已經(jīng)知道這是文字文本、源程序（圖像、聲音、壓縮的？）如果有兩個(gè)密鑰，解密出來的兩個(gè)明文都有意義？可能性極小因?yàn)槊荑€空間2^k<<可逆映射個(gè)數(shù)(2^n)!One

time

pad就是讓對手分辨不出哪個(gè)更像正確明文第三十七頁，共六十一頁。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（兩個(gè)子密鑰，互為加解密）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（四個(gè)子密鑰）–…第四十頁，共六十一頁。3.4差分分析和線性分析蠻力攻擊計(jì)時(shí)攻擊差分分析線性分析–正面分析密碼算法的新技術(shù)，在很多算法上取得很好的效果第四十一頁，共六十一頁。差分分析Differential

CryptanalysisBiham,

Shamir

(‘S’)–

1991?

NSA,1974攻擊實(shí)例–對8輪DES，只需微機(jī)幾分鐘–對16輪DES，復(fù)雜度為2^47需這么多的選擇明文，使本方法只有理論意義Differential

Cryptanalysis

of

the

Full

16-round

DES第四十二頁，共六十一頁。線性分析Linear

Cryptanalysis第四十三頁，共六十一頁。DES其他DES肯定能破譯不單是RSA

challengeDES算法仍值得信賴但是關(guān)鍵場合不要用DES對一般個(gè)人用戶仍是安全的RSA

challenge反而給了信心DES還是AES，或者其他DES模塊仍廣泛存在，AES還沒有普及如果軟件實(shí)現(xiàn)，任何一個(gè)經(jīng)過考驗(yàn)的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/Open第四十四頁，共六十一頁。3.5分組密碼的設(shè)計(jì)原理DES

Design

Criteria設(shè)計(jì)準(zhǔn)則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第四十五頁，共六十一頁。分組密碼設(shè)計(jì)原理輪數(shù)輪函數(shù)FS盒雪崩效應(yīng)密鑰使用方法子鑰衍生方法雪崩效應(yīng)第四十六頁，共六十一頁。輪函數(shù)F及S盒的設(shè)計(jì)strict

avalanche

criterionbit

independence

criterion輪函數(shù)F雪崩效應(yīng)準(zhǔn)則獨(dú)立準(zhǔn)則S盒構(gòu)造方法隨機(jī)方法隨機(jī)加測試方法人工構(gòu)造方法數(shù)學(xué)構(gòu)造方法?第四十七頁，共六十一頁。查閱和學(xué)習(xí)第四十八頁，共六十一頁。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()函數(shù)crypt#define

_XOPEN_SOURCE#include

<unistd.h>char

*crypt(const

char

*key,

const

char

*salt);passwd

space–128-32-’7f’=95個(gè)可用字符–

95^nsalt兩個(gè)字符，每個(gè)可從[a-zA-Z0-9./]中選出來，即有

4096種不同取值抵制字典攻擊中的預(yù)算值第五十頁，共六十一頁。crypt()描述從passwd到keypadding形成8字符的組每組產(chǎn)生56bits＝8×7的密鑰如果多于1組，則XOR累計(jì)重復(fù)加密64比特0到25回–中間置換，受salt控制，計(jì)有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算法很復(fù)雜，實(shí)現(xiàn)起來非?，嵥椋谛阅芎鸵浦残陨弦搽y于友好，因此如果軟件實(shí)現(xiàn)提倡使用開放源碼的實(shí)現(xiàn)，如OpenSSL等。

OpenSSL是SSL/TLS協(xié)議的開放實(shí)現(xiàn)，其中也實(shí)現(xiàn)了幾十種密碼算法。

OpenSS