密碼編碼學與網絡安全電子工業出版社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