3-2信息安全与密码

1高中数学选修课程专题研究3-2信息安全与密码前

言2012年8月2信息安全与密码密码的历史极为久远，其起源可以追溯到几千年以前，人类有记载的通信密码始于公元前405年。YHPARGCRYPTO给定消息cryptography（密码学）CGRRYAPPTHOY2012年8月3信息安全与密码前言2012年8月4信息安全与密码第一次世界大战是化学家的战争，第二次世界大战是物理学家的战争，如果未来发生战争将是数学家的战争，其核心是信息战中的军事密码学问题。生活中常见的密码2012年8月5信息安全与密码早期生活中的密码2012年8月6信息安全与密码文学作品中的密码2012年8月7信息安全与密码2012年8月8信息安全与密码信息安全、密码

防止信息被非授权地访问、使用、泄露、分解、修改和毁坏，以求保证信息的保密性、完整性、可用性和可追责性，使信息保障能正确实施、信息系统能如意运行、信息服务能满足要求。目前新出现的定义又增加信息有效性和占有性之类的概念（后者与偷窃、欺诈和舞弊相对应）网络经济当然增加了电子交易信用和责任的需要。

按特定法则编成，用以对通信双方的信息进行明密变换的符号。2012年8月9信息安全与密码《课程标准》系列3-2：信息安全与密码内容与要求2012年8月10信息安全与密码初等数论的有关知识

⑴了解整除和同余，模的完全同余系和简化剩余系，欧拉定理和费马小定理，大数分解问题。

⑵了解欧拉函数的定义和计算公式，威尔逊定理及在素数判别中的应用，原根与指数，模的原根存在性，离散对数问题。《课程标准》系列3-2：信息安全与密码内容与要求2012年8月11信息安全与密码数论在信息安全中的应用

⑴了解通讯安全中的有关概念（如明文、密文、密钥）和通讯安全中的基本问题（如保密、数字签名、密钥管理、分配和共享）。

⑵了解古典密码的一个例子：流密码（利用模同余方式）。

⑶理解公钥体制（单项函数概念），以及加密和数字签名的方法（基于大数分解的RS

A方案）。

⑷理解离散对数在密钥交换和分配中的应用——棣弗-赫尔曼方案。

⑸理解离散对数在加密和数字签名中的应用——盖莫尔算法。

⑹了解拉格朗日插值公式在密钥共享中的应用。知识框架图凯撒密码体制维吉尼亚密码体制流密码体制—M序列公钥密码体制的思想RSA公钥方案离散对数方案保密通讯的基本常识公钥密码体制古2012年8月12信息安全与密码典密码体制密码管理保密通讯的基本常识人类使用密码的历史，从今天已知的，最早可以一直追溯到古巴比伦人的泥板文字。古埃及人，古罗马人，古阿拉伯人⋯⋯几乎世界历史上所有文明都使用过密码。军事和外交一直是密码应用的最重要的领域。2012年8月13信息安全与密码保密通讯的基本常识密码体制发展简史原始的密码体制2012年8月14信息安全与密码古典

密码体制近代

密码体制保密通讯的基本常识明文与密文在通讯过程中，当甲方通过公共通道向乙方传递信息时，为了不被窃取或修改，往往可将信息改变为秘密形式，这时将原信息称为明文，明文的秘密形式称为密文。明文密文加

密解

密2012年8月15信息安全与密码保密通讯的基本常识保密通讯的基本模型兄妹好朋友小明小虹小强2012年8月16信息安全与密码保密通讯的基本常识保密通讯的基本模型甲方乙方密文解密明文加密第三方密文2012年8月17信息安全与密码保密通讯的基本常识密码体制评价标准2012年8月18信息安全与密码

⑴敌方难于破译收发双方使用的密钥

⑵有足够多的密钥供收发双方选择使用

⑶加密解密的运算较为容易操作，不会误译古典密码体制2012年8月19信息安全与密码古典密码学是现代密码学的渊源，这些密码大多比较简单，用手工或机械操作即可实现。加密和解密的方式千差万别，但任何密码体制本质上都是采用了不同的数学模型。换位加密术——栅栏加密法2012年8月20信息安全与密码ZQI

HXTGN明文ME

ET

ME

TONIGHTE

M

TE

T

E

OMMEMTNGTXETEOIHQZ替换加密术——猪圈加密法ZYXWPSVORUNQTMLKJCFIBEHADG2012年8月21信息安全与密码原文CRYPTOGRAP

HY2012年8月22信息安全与密码古典密码体制2012年8月23信息安全与密码恺撒密码体制加密方法：取一个整数k

1

k

25

，然后将明文中每个英文字母改用在它k

位之后的那个字母来代替。例如，取k=10，而明文为“ba

t

t

l

e”。这时，字母b改成它10位之后的字母l。abcdefghijklmo

npqrstuvwxyz12345678910注意英文中最后一个字母z向后又回到字母a252012年8月24信息安全与密码ba

ttle古典密码体制2012年8月25信息安全与密码恺撒密码体制经过这个字母代换方式,上述明文就成为密文

“lkddvo

”。其中k=1

0即是加密密钥。古典密码体制恺撒密码体制采用同余符号，则上述密码体制的加密运算为y

E

x

x10

mod

26

Y≡x+10mod26明文battleontuesdayX101919114141319204183024？111033211424233414213108密文LKDDVOYXDEOCNKI字母数字对应表2012年8月26信息安全与密码古典密码体制恺撒密码体制为方便起见，我们用英文来介绍这种密码体制即将a,b,c,⋯,y,z依次用数字0，1，⋯，24，25表示abcdefghijklm0123456789101112nopqrstuvwxyz131415161718192021222324252012年8月27信息安全与密码补充同余的概念设m和n都是整数，如果有一个整数k，使得n=km，就说n是m的倍数，也说m是n的因数，也说m整除n，设m是正整数，a和b是整数，如果如果不成立，就说n记作mm

a

b

就说a和b同余模m，记作a

b

mod

m

a

b(mod

m)2012年8月28信息安全与密码古典密码体制2012年8月29信息安全与密码恺撒密码体制课堂练习

取k=6，试将明文ma

th进行加密。s

g

znabcdefghijklm0123456789101112nopqrstuvwxyz13141516171819202122232425古典密码体制密文LKDDVOYXDEOCNKIY111033211424233414213108Y+16272619193730403919203018292624X≡Y+16mod26101919114141319104183024明文battleontuesday加密规则与解密规则互为逆运算，由于事先约定好运算规则，并且高度保密，所以这一对运算分别被称为加密密钥、解密密钥，统称为密钥。恺撒密码体制解密运算x

D

y

y

106

mod

26

2012年8月30信息安全与密码古典密码体制2012年8月31信息安全与密码恺撒密码体制课堂练习取k=6,试将密文s

gznks

gzoiy进行解密ma

the

ma

tic

sabcdefghijklm0123456789101112nopqrstuvwxyz13141516171819202122232425古典密码体制2012年8月32信息安全与密码恺撒密码体制缺点：是密钥量太小，只有25个。如果知道密码体制，可以逐个试k的值，很容易就恢复成明文。这种体制在公元9世纪才被阿拉伯人找到破译方法，在阿拉伯科学家阿尔▲金迪《关于破译加密信息》的手稿中有详细的描述。破译的方法是频率统计分析。古典密码体制恺撒密码体

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z2012年8月33信息安全与密码思考2012年8月34信息安全与密码恺撒密码体制中是用“+”进行加密，是否能够对其进行改造，用“×”进行加密？如果可行，解密的过程应该如何？深入探究恺撒密码体制加密方法：取一个整数k

1

k

25

，然后将明文中每个英文字母改用在它k位之后的那个字母来代替。y

x

k

mod

26

2012年8月35信息安全与密码深入探究思

考能否用乘法运算来“改造”恺撒密码体制呢y

kx

mod

26

2012年8月36信息安全与密码深入探究比如：取k=3(1≤k≤25

）明文math对应数字1201973

x3605721y≡3

x(mod

26

)100521密文kafv2012年8月37信息安全与密码深入探究如何将密文“ka

fv”还原为明文“ma

th”呢？恺撒密码体制加密钥匙8解密钥匙

188

18

0(mod

26)同余意义下的互为相反数“改造”后的体制加密钥匙3解密钥匙？？？3k

1(mod

26)同余意义下的互为倒数2012年8月38信息安全与密码深入探究寻找k=3在模26意义下的倒数！3×

？（正整数）

≡92012年8月39信息安全与密码3

2???

?1

（mod26

）11?密文kafv对应数字1005219

y90045189x≡9

y(mod

26

)120197明文math解密钥匙：k`=9；解密运算深应入该是探9

y还究是y/9呢？2012年8月40信息安全与密码深入探究课堂练习自行选择下列中一个k值，将单词ma

t

h进行加密和解密。k=4k=5k=6k=72012年8月41信息安全与密码深入探究取k=4时，找不到正整数k`，使得4×k`（正整数）≡1

（mod26

）?

?

?4×整数＝偶数，而被26除余数为1的数必为奇数，故k不能取偶数2012年8月42信息安全与密码深入探究2012年8月43信息安全与密码模26的倒数表a1357911151719212325a

-11921153197231151725深入探究恺撒密码体制方法一方法二改造后的体制+y

H

ikllx密

码b(体mo制d

26)y

x

k(mod26)y

kx(mod

26)2012年8月44信息安全与密码补充⑴⑵⑶a

a

mod

m

;如果a

b

mod

m

,那么b

a

mod

m

如果a

b

mod

m

和b

c

mod

m

,那么a

c

modm

如果a

b

mod

m

和c

d

mod

m

,那么a

c

b

d

mod

m

,a

c

b

d

mod

m

和a

c

bd

mod

m

2012年8月45信息安全与密码如果nanb

mod

m

,而n与m互素，那么a

b

mod

m

同余的性质同余的性质如果a

b和b

c,那么a

c;a

a;如果a

b,那么b

a如果a

b和c

d,那么a

c

b

d,a

cb

d和a

c

bd维吉尼亚密码体制2012年8月46信息安全与密码1586年，法国外交家维吉尼亚把恺撒密码的模型作另一种改进。恺撒密码的密钥是用同一个数字k=10简单地重复成序列10，10，10，⋯与明文逐位模26相加。维吉尼亚则增加密钥的长度。对于维吉尼亚密码，密钥是一个字序k

k1

,k2

,,km

，其中m为任意正整数。因此，在原理上存在无限多个密钥。维吉尼亚密码体制以f

i

nger作为密钥,对“ba

t

t

l

eonTue

s

day”加密过程可表示如下：明文battleontuesdayx101919114141319204183024密钥序列58136417581364175813Y=E(x)686251521192160898811密文GIGZPVTVGAIJIIL2012年8月47信息安全与密码维吉尼亚密码体制2012年8月48信息安全与密码这种密码体制克服了恺撒体制的缺点，明文中前两个字母t被加密成不同的字母G和Z，而密文中前两个G也来自明文中不同的字母b和t，所以加密性能比恺撒体制要好。维吉尼亚密码体制2012年8月49信息安全与密码课堂练习以finge

r作为密钥，试将明文Ma

the

ma

tics进行加密r

i

gni

df

bvi

w维吉尼亚密码体制2012年8月50信息安全与密码解密过程密文gigzpvtvgaijiilY686251521192160898811密钥序列-521-816-1313-620-422-17921181320229211813X=D(y)101919114141319204183024明文battleontuesday维吉尼亚密码体制2012年8月51信息安全与密码课堂练习以finge

r作为密钥，试将密文rignidfbviw进行解密mat

he

mat

i

cs维吉尼亚密码直到二百年后才找到破译方法，破译者是英国人巴比奇（1854年）和德国人卡西斯基（1863年）。破译手段是采用更精细的数学统计方法，关键是首先设法决定密钥的周期长度。密文维出现周吉期性尼变化亚，敌密方找码到k值体，便制容易破译2012年8月52信息安全与密码Hill密码体制假设甲方要将信息“HELP”（明文）发送给乙方，则发送者事先与接受者约定某个二维函数，假如设（※）y1

3

x1

3

x

2y

2

2

x1

5

x

22012年8月53信息安全与密码然后将HELP分为两组（H,E）和（L,P），按上面的编码方法得：H⋯7⋯

E⋯4⋯Hill密码体制x1x2L⋯11⋯

x1P⋯15⋯

x2用前面的函数（※）作用后，得y1

3x1

3x2

37

34

33

7mod

26

y2

2x1

5x2

27

54

34

8

mod

26

2012年8月54信息安全与密码Hill密码体制y1

33

7

mod26

7Hy2

34

8

mod26

8Iy1

78

0

mod

26

0

Ay2

97

19

mod

26

19T从而将明文转化为密文“HI

AT”，这一过程称为加密。2012年8月55信息安全与密码Hill密码体制然后甲方将“HI

AT”发送给乙方，乙方得到密文之后，仍将密文分成两组H

7

y

1

A

0

y

1I

8

y

2

T

19

y

2并由（※）解出x1

15

y1

17

y2x2

20

y1

9

y22012年8月56信息安全与密码Hill密码体制如何用Hill密码体制进行解密？y1

3

x1

3

x

2y

2

2

x1

5

x

2392

119

35x2

y1

y2x1

y1

y22012年8月57信息安全与密码Hill密码体制2012年8月58信息安全与密码补充知识对于一个n阶方阵A，若存在一个n阶方阵B，使得AB=BA=E(mod

m)，称A为模m可逆，B为A的逆矩阵，记为B=A-1

(mod

m)。可验证：

mod

26

1

c

ab

1

dA

a

d

bc

Hill密码体制2012年8月59信息安全与密码模26的倒数表a1357911151719212325a

-11921153197231151725上述例子也可用矩阵运算表示如下：明文HELP的加密过程为：Hill密码体制

20

9

15 17

2

3

3

5

,

DyEx37

34

33

7

mod26

211515

97

19

mod26

T

HAIT

（密文）2012年8月60信息安全与密码

I

H

A

E

H L

15

8 19

11

7 0

5

415

2P

Ex

4

7 11

3

3

7Hill密码体制反过来，解密过程可计算如下：什么是矩阵？2012年8月61信息安全与密码11(明文)P

HELP

E

H L

19

4 15

0

79

8

19

20

T

Dy

8

I

H

A

7 0

15 17

7Hill密码体制y1

3

x1

3

x

2y

2

2

x1

5

x

29

x1

5

y1

3

y

2

①9

x

2

2

y1

3

y

2

②①

3

27

x1

15

y1

9

y2②

3

27

x2

6

y1

9

y227

1

mod

26

15

15

mod

26

9

17

mod

26

9

9

mod

26

x1

15

y1

17

y

2x

2

20

y1

9

y

22012年8月62信息安全与密码Hill密码体制练

习试将HIAT进行解密x1

15

y1

17

y2

15

7

17

8

2417mod

26x2

20

y1

9

y220

7

9

8

2124mod

26x1

15

y1

17

y2

15

0

17

19

323

11mod

26x2

20

y1

9

y2

20

0

9

19

171

15mod

262012年8月63信息安全与密码Hill密码体制从而得到明文“HELP”，这一过程称为解密。再将y1

,y2代入得到x

1

7

H

x

1

11

Lx

2

4

E

x

2

15

P2012年8月64信息安全与密码简单的机械加密2012年8月65信息安全与密码普通的打字机可以提供多种简单的替换加密方法。例如，不要击打表示正确字母的那个键，而是击打它上头偏左的键；也可以选择击打它的右旁键，或击打上头偏右的键。如果你选择击打上头偏左键的方案，那么I

LOVE

YOU打字后成了：8

O9

F

3

697而如果选择击打右旁键的方案，那又成了O

:PBR

UPI流密码体制——M序列密码体制在第一次世界大战后又有了新的突破，这种新体制被称为流密码,在技术上依托于一种新的基本元件，称为移位寄存器。2012年8月66信息安全与密码流密码体制——M序列2012年8月67信息安全与密码一个n级的移位寄存器由两部分组成：移位寄存部分计算反馈部分流密码体制——M序列2012年8月68信息安全与密码移位寄存部分：状态，其中每个字母取值可为0或1。n可存放n个数字

a

1

,

a

，这n个数字组成一个2

,

,

a流密码体制——M序列计算反馈部分：位移寄存器的工作过程可用下图表示a1

,

a

2

,输出x1

x2

x

n-1

x

na

1a

2⋯a

n-1a

na

1a

2⋯a

n-1a

n反馈2012年8月69信息安全与密码流密码体制——M序列2012年8月70信息安全与密码例如：在一个3元移位寄存器中，取f

x

1

,

x

2

,

x

3

1

x

1

x

2

x

2

x

3当取初始状态为

a

1

,

a

2

,

a

3

1

,1

,1

时，a

4

f

a

1

,

a

2

,

a

3

1

1

1

1

4

0

mod

2

将

a

1

1

输出，初始状态

1,1,1

变成

a

2

,

a

3

,

a

4

1

,1

,

0

如此类推，下一个状态

a

3

,a

4

,a

5

1,0,1

a

4

,

a

5

,

a

6

0

,1

,

0

⋯流密码体制——M序列2012年8月71信息安全与密