现代密码学第二讲古典密码学

1古典密码学《现代密码学》第二讲上讲内容回顾密码学分类密码学与信息安全的关系Ad

hoc攻击方法和数学刻画本章主要内容代换密码置换密码Hill密码转轮密码古典密码的惟密文攻击方法密码分类

代换密码（

substitution

）：代换是古典密码中用到的最基本的处理技巧。所谓代换，就是将明文中的一个字母由其它字母、数字或符号替代的一种方法。凯撒密码仿射密码单表代换多表代换

置换密码（permutation）：将明文字符按照某种规律重新排列而形成密文的过程。Hill密码转轮密码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数学描述:用数字表示每个字母：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个26

26凯撒密码例:使用其后的第三个字母代换该字母明文：meet

me

after

the

toga

party密文：PHHW

PH

DIWHU

WKH

WRJD

SDUWB恺撒密码的攻击

已知明文和密文、加密和解密算法，需要解同余方程，可以恢复密钥k

=

(c-

p)

mod

(26)；穷举攻击：已知密文，且明文为有意义字符，至多尝试25次，可以恢复明文.仿射密码（Affine

Cipher）移位密码的扩展明文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)仿射密码仿射密码练习：令密钥k=(9,3),且gcd(5,26)=1.明文hot=(7,14,19)，求加解密过程。已知两对明文和密文（p1,c1）和（p2,c2）、加密和解密算法，需要解2元同余方程组，可以恢复密钥k=(a,b)；c1

=

(a

×

p1

+

b)

mod

26c2

=

(a

×

p2

+

b)

mod

26

穷举攻击：已知密文，明文为有意义字符，至多尝试26*Φ(26)个，可以恢复明文.仿射密码代换表是26个字母的任意置换例：加密函数:anAN

obOB

pcPC单表qQdD

代RerE

换FfsS

密tTGg码uHhU

ivIV

wJjW

XkxK

yYLl

zZmMDXzsuKHgmVTj（

adQMMokFwYnoaAleIlpBxpUhaJotObetWfcLiciRPh

CiEbGnphSvZrerCqyN）解密函数:明文:

if

we

wish

to

replace

letters密文:

WI

RF

RWAJ

UH

YFTSDVF

SFUUFYA单表代换密码练习：明文:nice

work，求密文。所有元素的全排列个数26！单表代换密码

已知明文和密文，可以恢复部分加密函数（解密函数）；

穷举攻击：已知密文，明文为有意义字符，至多尝试26!=4

x

1026个，可以恢复明文代换表的个数为26！多表代换密码

(Polyalphabetic

Ciphers)加密明文消息时采用不同的单表代换，由密钥具体决定采用哪个表代换消息，密钥通常是一个词的重复。

简化的多表代换密码----维吉尼亚密码（Vigenère

Cipher

）：由26个类似caesar密码的代换表组成多表代换密码

维吉尼亚密码：在长为m的密码中，任何一个字母可被影射为26个字母中的一个明文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.多表代换密码例多表代换密码练习：明文:nice

work，密钥：hot，求密文。多表代换密码

已知m个连续的明文和密文，可以恢复维吉尼亚密码的单表移位量（即密钥）；

穷举攻击：已知密文，明文为有意义字符，至多尝试26m

个，可以恢复明文密钥空间大小是26^m置换密码加密变换使得信息元素只有位置变化而形态不变，如此可以打破消息中的某些固定模式（结构）明文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思考：当明文字符不是4的整数倍怎么办？置换密码练习：明文:nice

work求密文。X1234Pi(x)2413例子中，2对可以置换密码

已知多对明文和密文，可以推导置换表（即密钥）；

穷举攻击：已知密文，明文为有意义字符，至多尝试m！个，可以恢复明文分组为m，至多有m！个置换希尔密码（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扩散希尔密码例希尔密码置换密码可以看做是希尔密码的特例。练习：设hill密码的密钥如下，求对应置换密码的置换表。希尔密码

已知m组明文和密文、加密和解密算法，需要解m元同余方程组，可以恢复密钥；穷举攻击：已知密文，明文为有意义字符，至多尝试26m*m个，可以恢复明文转轮密码（Rotor

Machine）19世纪20年代，开始出现机械加解密设备，最典型的是转轮密码机1918年Arthur

Scherbius发明的EIGMA，瑞典

Haglin发明的Haglin，和日军发明的“紫密

”和“兰密”都属于转轮密码机。转轮密码Enigma密码机转轮密码穷举搜索的复杂度------密钥空间比较小，对于目前的计算能力来说，不够安全，计算安全的实例。惟密文攻击在攻击者可以截获（足够）明密文的条件下，易于恢复用户的密钥；

当攻击者只能窃听到密文时，若明文是有意义的（一段话等具有可读性）字符时，利用穷举搜索，可以通过密文解密出对应明文，继而恢复密钥。（穷举搜索的复杂度取决于密当钥攻空击间者的只大能小窃，听古到典密密文码时体，制是的否密有钥其空它间通常更比有较效小攻。击）方法？？若明文是无意义的随机字符时，攻击者是否可以获得明文或密钥的相关信息？？惟密文攻击人类的语言存在冗余，以英文文档为例字母e

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

很少使用

A、I、U很少用在词尾，E、N、R常出现在词尾。E、S、D作为字母结尾字母的单词超过一半，T、A、S、W为起始字母的单词约占一半。惟密文攻击惟密文攻击对于双字母组合,三字母组合惟密文攻击统计攻击（频率攻击）假设：根据分析假设某些结论。推断：在假设的前提下，推断出一些结论。双频字母跟随关系构词规则词义

验证发展：填上破译出的字母，根据词义、构词规则不断发展惟密文攻击

移位密码、仿射密码和单表代换密码都没有破坏明文的频率统计规律，可以直接用统计分析法例：截取一段仿射密码的密文c=ap+b

mod

26字母频率字母频率字母频率字母频率A惟2

密文H

攻击5

O1U2B■统计1

得到I

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

母频率0

统计W0D7K5R8X2E5L2S3Y1F4M2T0Z0G0N1统计第一为e，次之为t，令字符中统计比较多的依次为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;其中gcd(6,26)=2>1，故猜测错误。惟密文攻击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组解有效，则解密函数p=(c-5)*3-1=9c-19解密得明文：algorithms

are

quite

generaldefinitions

of

arithmetic

processes.惟密文攻击

练习：已知用户用移位密码加密，密文为

“KHOOR,HYHUB

RQH”，用统计法求密钥和对应明文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个移位密码构成，移位密码不改变字符的分布，故若能确定m，则可以找到每个移位密码的位移量k克思斯基测试（Kasiski

）

若用给定的m个密钥表周期地对明文字母加密，则当明文中有两个相同字母组(长度大于3)在明文序列中间隔的字母数为m的倍数时，这两个明文字母组对应的密文字母组必相同。

但反过来，若密文中出现两个相同的字母组，它们所对应的明文字母组未必相同，但相同的可能性很大。

将密文中相同的字母组找出来，并对其相同字母数综合研究，找出它们的相同字母数的最大公因子，就有可能提取出有关密钥字的长度m的信息。惟密文攻击例CHR出现5个位置：1,166,236,276,286距离差：165,235,275,285，gcd(165,235,275,285)=5猜测m=5惟密文攻击重合指数法（Coincidence

Index）

完全随机的文本CI=0.0385，一个有意义的英文文本CI=0.065单表代换密吗的统计规律和自然语言（或随机文本）的概率相似；多表代换则会发生很大变化惟密文攻击实际使用CI的估计值CI’：L：密文长。fi：密文符号i发生的数目。作用：区分单表代换密码和多表代换密码确定两段文本是否是同一种方法进行加密确定维吉尼亚密码的m值惟密文攻击例CI’(C1)=0.0412CI’(C2)=0.0445同一加密方法惟密文攻击1,对于不同的m,重新对密文m分组2,对不同的分组，分别求取重合指数当m为5时，重合指数平均接近于0.065对于单表代换密码(移位密码,代换密码)并没有改变字符的统计规律，所以可以采用字符统计规律,确定E的位置，也可以采用拟重合指数法惟密文攻击拟重合指数法自然语言的分布，如图所示惟密文攻击对于一个移位密码惟密文攻击惟密文攻击CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEM

NDCMG

TSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWT

WDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWR

JGNMGJSGLXFEYPHAGNRBIEQJTAMRVL

CRREM