現(xiàn)代密碼學(xué)第二講古典密碼學(xué)

1古典密碼學(xué)《現(xiàn)代密碼學(xué)》第二講上講內(nèi)容回顧密碼學(xué)分類密碼學(xué)與信息安全的關(guān)系A(chǔ)d

hoc攻擊方法和數(shù)學(xué)刻畫本章主要內(nèi)容代換密碼置換密碼Hill密碼轉(zhuǎn)輪密碼古典密碼的惟密文攻擊方法密碼分類

代換密碼（

substitution

）：代換是古典密碼中用到的最基本的處理技巧。所謂代換，就是將明文中的一個(gè)字母由其它字母、數(shù)字或符號替代的一種方法。凱撒密碼仿射密碼單表代換多表代換

置換密碼（permutation）：將明文字符按照某種規(guī)律重新排列而形成密文的過程。Hill密碼轉(zhuǎn)輪密碼In

this

section

and

the

next,

we

examine

a

sampling

of

what

might

be

called

classical

encryptiontechniques.

A

study

of

these

techniques

enables

us

to

illustrate

the

basic

approaches

to

symmetric

encryption

used

today

and

the

types

of

cryptanalytic

attacks

that

must

be

anticipated.The

two

basic

building

blocks

of

all

encryptiontechniques:

substitutionand

transposition.We

examine

these

in

the

next

two

sections.

Finally,

we

discuss

asystem

that

combine

bothsubstitution

and

transposition.凱撒密碼(caesar

cipher)已知最早的代換密碼，又稱移位密碼代換表（密鑰）：a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

zD

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C數(shù)學(xué)描述:用數(shù)字表示每個(gè)字母：a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

Z0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25c

=

E(p)

=

(p

+

k)

mod

(26)p

=

D(c)

=

(c

–

k)

mod

(26)明文p

∈Z

，密文c

∈Z

，密鑰k取[1,25]，只有25個(gè)26

26凱撒密碼例:使用其后的第三個(gè)字母代換該字母明文：meet

me

after

the

toga

party密文：PHHW

PH

DIWHU

WKH

WRJD

SDUWB愷撒密碼的攻擊

已知明文和密文、加密和解密算法，需要解同余方程，可以恢復(fù)密鑰k

=

(c-

p)

mod

(26)；窮舉攻擊：已知密文，且明文為有意義字符，至多嘗試25次，可以恢復(fù)明文.仿射密碼（Affine

Cipher）移位密碼的擴(kuò)展明文p

∈Z26，密文c

∈Z26

，密鑰k=(a,b)∈Z26×Z26,且gcd(a,26)=1.加密：c

=

E(p)

=

(a

×

p

+

b)

mod

26解密：p

=

D(c)

=

(c

–

b)

×

a-1mod

26例：令密鑰k=(7,3),且gcd(7,26)=1.明文hot=(7,14,19)加密：(7

×

7

+

3)

mod

26

=

0(7

×

14

+

3)

mod

26

=23(7

×

19

+

3)

mod

26

=6密文為(0,23,6)=(a,x,g)解密：7-1=15=-11

mod

26(0-

3)

×

15

mod

26

=

7(23-

3)

×

15

mod

26

=14(6-

3)

×

15

mod

26

=19明文為(7,14,19)=(h,o,t)仿射密碼仿射密碼練習(xí)：令密鑰k=(9,3),且gcd(5,26)=1.明文hot=(7,14,19)，求加解密過程。已知兩對明文和密文（p1,c1）和（p2,c2）、加密和解密算法，需要解2元同余方程組，可以恢復(fù)密鑰k=(a,b)；c1

=

(a

×

p1

+

b)

mod

26c2

=

(a

×

p2

+

b)

mod

26

窮舉攻擊：已知密文，明文為有意義字符，至多嘗試26*Φ(26)個(gè)，可以恢復(fù)明文.仿射密碼代換表是26個(gè)字母的任意置換例：加密函數(shù):anAN

obOB

pcPC單表qQdD

代RerE

換FfsS

密tTGg碼uHhU

ivIV

wJjW

XkxK

yYLl

zZmMDXzsuKHgmVTj（

adQMMokFwYnoaAleIlpBxpUhaJotObetWfcLiciRPh

CiEbGnphSvZrerCqyN）解密函數(shù):明文:

if

we

wish

to

replace

letters密文:

WI

RF

RWAJ

UH

YFTSDVF

SFUUFYA單表代換密碼練習(xí)：明文:nice

work，求密文。所有元素的全排列個(gè)數(shù)26！單表代換密碼

已知明文和密文，可以恢復(fù)部分加密函數(shù)（解密函數(shù)）；

窮舉攻擊：已知密文，明文為有意義字符，至多嘗試26!=4

x

1026個(gè)，可以恢復(fù)明文代換表的個(gè)數(shù)為26！多表代換密碼

(Polyalphabetic

Ciphers)加密明文消息時(shí)采用不同的單表代換，由密鑰具體決定采用哪個(gè)表代換消息，密鑰通常是一個(gè)詞的重復(fù)。

簡化的多表代換密碼----維吉尼亞密碼（Vigenère

Cipher

）：由26個(gè)類似caesar密碼的代換表組成多表代換密碼

維吉尼亞密碼：在長為m的密碼中，任何一個(gè)字母可被影射為26個(gè)字母中的一個(gè)明文p

∈(Z26)m，密文c

∈(Z26)m

，密鑰k

∈(Z26)m加密c=(p1+k1

,,p2+k2

,,…,pm+km)mod

26;解密p

=

(c1-k1

,,c2-k2

,,

…,

cm-km)

mod

26.多表代換密碼例多表代換密碼練習(xí)：明文:nice

work，密鑰：hot，求密文。多表代換密碼

已知m個(gè)連續(xù)的明文和密文，可以恢復(fù)維吉尼亞密碼的單表移位量（即密鑰）；

窮舉攻擊：已知密文，明文為有意義字符，至多嘗試26m

個(gè)，可以恢復(fù)明文密鑰空間大小是26^m置換密碼加密變換使得信息元素只有位置變化而形態(tài)不變，如此可以打破消息中的某些固定模式（結(jié)構(gòu)）明文p

∈(Z26)m，密文c

∈(Z26)m

，密鑰k

∈{∏|定義在1,2,…,m上的置換}加密c=

(p

∏

(1)

,,p

∏

(

2)

,,

…,

p

∏

(

m))

mod

26;解密p

=

(c

∏

-1

,

c

(2)

,

…,

c

(m))

mod

26.(1)

, ∏

-1

, ∏

-1置換密碼例密鑰明文：she

sells

sea

shells

by

the

sea

shore分組：shesel

lsseas

hellsb

ythese

ashore置換：ELSEHS

SSLASE

LBHSEL

HEYSTE

HEARSO思考：當(dāng)明文字符不是4的整數(shù)倍怎么辦？置換密碼練習(xí)：明文:nice

work求密文。X1234Pi(x)2413例子中，2對可以置換密碼

已知多對明文和密文，可以推導(dǎo)置換表（即密鑰）；

窮舉攻擊：已知密文，明文為有意義字符，至多嘗試m！個(gè)，可以恢復(fù)明文分組為m，至多有m！個(gè)置換希爾密碼（Hill

cipher）1929年，LesterS.Hill提出明文p

∈(Z26)m，密文c

∈(Z26)m

，密鑰K

∈{定義在Z26上m*m的可逆矩陣}加密c

=

p

*

K

mod

26解密p

=

c

*

K-1

mod

26擴(kuò)散希爾密碼例希爾密碼置換密碼可以看做是希爾密碼的特例。練習(xí)：設(shè)hill密碼的密鑰如下，求對應(yīng)置換密碼的置換表。希爾密碼

已知m組明文和密文、加密和解密算法，需要解m元同余方程組，可以恢復(fù)密鑰；窮舉攻擊：已知密文，明文為有意義字符，至多嘗試26m*m個(gè)，可以恢復(fù)明文轉(zhuǎn)輪密碼（Rotor

Machine）19世紀(jì)20年代，開始出現(xiàn)機(jī)械加解密設(shè)備，最典型的是轉(zhuǎn)輪密碼機(jī)1918年Arthur

Scherbius發(fā)明的EIGMA，瑞典

Haglin發(fā)明的Haglin，和日軍發(fā)明的“紫密

”和“蘭密”都屬于轉(zhuǎn)輪密碼機(jī)。轉(zhuǎn)輪密碼Enigma密碼機(jī)轉(zhuǎn)輪密碼窮舉搜索的復(fù)雜度------密鑰空間比較小，對于目前的計(jì)算能力來說，不夠安全，計(jì)算安全的實(shí)例。惟密文攻擊在攻擊者可以截獲（足夠）明密文的條件下，易于恢復(fù)用戶的密鑰；

當(dāng)攻擊者只能竊聽到密文時(shí)，若明文是有意義的（一段話等具有可讀性）字符時(shí)，利用窮舉搜索，可以通過密文解密出對應(yīng)明文，繼而恢復(fù)密鑰。（窮舉搜索的復(fù)雜度取決于密當(dāng)鑰攻空擊間者的只大能小竊，聽古到典密密文碼時(shí)體，制是的否密有鑰其空它間通常更比有較效小攻。擊）方法？？若明文是無意義的隨機(jī)字符時(shí)，攻擊者是否可以獲得明文或密鑰的相關(guān)信息？？惟密文攻擊人類的語言存在冗余，以英文文檔為例字母e

是使用頻率最高的其次是T,R,N,I,O,A,SZ,J,K,Q,X

很少使用

A、I、U很少用在詞尾，E、N、R常出現(xiàn)在詞尾。E、S、D作為字母結(jié)尾字母的單詞超過一半，T、A、S、W為起始字母的單詞約占一半。惟密文攻擊惟密文攻擊對于雙字母組合,三字母組合惟密文攻擊統(tǒng)計(jì)攻擊（頻率攻擊）假設(shè)：根據(jù)分析假設(shè)某些結(jié)論。推斷：在假設(shè)的前提下，推斷出一些結(jié)論。雙頻字母跟隨關(guān)系構(gòu)詞規(guī)則詞義

驗(yàn)證發(fā)展：填上破譯出的字母，根據(jù)詞義、構(gòu)詞規(guī)則不斷發(fā)展惟密文攻擊

移位密碼、仿射密碼和單表代換密碼都沒有破壞明文的頻率統(tǒng)計(jì)規(guī)律，可以直接用統(tǒng)計(jì)分析法例：截取一段仿射密碼的密文c=ap+b

mod

26字母頻率字母頻率字母頻率字母頻率A惟2

密文H

攻擊5

O1U2B■統(tǒng)計(jì)1

得到I

R(8)0,D(7)P,E,H,2K(5),VS,F,V4(4)C0J密文0出現(xiàn)字Q

母頻率0

統(tǒng)計(jì)W0D7K5R8X2E5L2S3Y1F4M2T0Z0G0N1統(tǒng)計(jì)第一為e，次之為t，令字符中統(tǒng)計(jì)比較多的依次為t惟密文攻擊令R=E(e)，D=E(t)，得到方程組a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

Z0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25解得a=6,b=19;其中g(shù)cd(6,26)=2>1，故猜測錯(cuò)誤。惟密文攻擊1、令R=E(e)，E=E(t)？a=132、R=E(e)，H=E(t)?a=83、R=E(e)，K=E(t),a=3,b=5,第3組解有效，則解密函數(shù)p=(c-5)*3-1=9c-19解密得明文：algorithms

are

quite

generaldefinitions

of

arithmetic

processes.惟密文攻擊

練習(xí)：已知用戶用移位密碼加密，密文為

“KHOOR,HYHUB

RQH”，用統(tǒng)計(jì)法求密鑰和對應(yīng)明文a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

Z0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25H(4),

O,R(2),

K(1),

Q(1),

Y(1),

U(1),

B(H------e,也就是e+x=h得4+x=7，密鑰為3解密：hello，every

one惟密文攻擊維吉尼亞密碼由m個(gè)移位密碼構(gòu)成，移位密碼不改變字符的分布，故若能確定m，則可以找到每個(gè)移位密碼的位移量k克思斯基測試（Kasiski

）

若用給定的m個(gè)密鑰表周期地對明文字母加密，則當(dāng)明文中有兩個(gè)相同字母組(長度大于3)在明文序列中間隔的字母數(shù)為m的倍數(shù)時(shí)，這兩個(gè)明文字母組對應(yīng)的密文字母組必相同。

但反過來，若密文中出現(xiàn)兩個(gè)相同的字母組，它們所對應(yīng)的明文字母組未必相同，但相同的可能性很大。

將密文中相同的字母組找出來，并對其相同字母數(shù)綜合研究，找出它們的相同字母數(shù)的最大公因子，就有可能提取出有關(guān)密鑰字的長度m的信息。惟密文攻擊例CHR出現(xiàn)5個(gè)位置：1,166,236,276,286距離差：165,235,275,285，gcd(165,235,275,285)=5猜測m=5惟密文攻擊重合指數(shù)法（Coincidence

Index）

完全隨機(jī)的文本CI=0.0385，一個(gè)有意義的英文文本CI=0.065單表代換密嗎的統(tǒng)計(jì)規(guī)律和自然語言（或隨機(jī)文本）的概率相似；多表代換則會(huì)發(fā)生很大變化惟密文攻擊實(shí)際使用CI的估計(jì)值CI’：L：密文長。fi：密文符號i發(fā)生的數(shù)目。作用：區(qū)分單表代換密碼和多表代換密碼確定兩段文本是否是同一種方法進(jìn)行加密確定維吉尼亞密碼的m值惟密文攻擊例CI’(C1)=0.0412CI’(C2)=0.0445同一加密方法惟密文攻擊1,對于不同的m,重新對密文m分組2,對不同的分組，分別求取重合指數(shù)當(dāng)m為5時(shí)，重合指數(shù)平均接近于0.065對于單表代換密碼(移位密碼,代換密碼)并沒有改變字符的統(tǒng)計(jì)規(guī)律，所以可以采用字符統(tǒng)計(jì)規(guī)律,確定E的位置，也可以采用擬重合指數(shù)法惟密文攻擊擬重合指數(shù)法自然語言的分布，如圖所示惟密文攻擊對于一個(gè)移位密碼惟密文攻擊惟密文攻擊CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEM

NDCMG

TSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWT

WDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWR

JGNMGJSGLXFEYPHAGNRBIEQJTAMRVL

CRREM