密码学基础知识.docx

密码学基础知识.docx

《密码学基础知识.docx》由会员分享，可在线阅读，更多相关《密码学基础知识.docx（37页珍藏版）》请在冰点文库上搜索。

密码学基础知识

【1】古典密码

1、置换密码

置换密码将明文中的字母顺序重新排列，但字母本身不变，由此形成密文。

换句话说，明文与密文所使用的字母相同，只是它们的排列顺序不同。

我们可以将明文按矩阵的方式逐行写出，然后再按列读出，并将它们排成一排作为

密文，列的阶就是该算法的密钥。

在实际应用中，人们常常用某一单词作为密钥，按照单词

中各字母在字母表中的出现顺序排序，用这个数字序列作为列的阶。

【例1】我们以coat作为密钥，则它们的出现顺序为2、3、1、4，对明文"attack

postoffice”的加密过程见图1:

密钥

C

0-

at

右

3

14

a

t

t&

C

Po

3

t

of

f

±

ie

图1对明文"attackpostoffice”的加密过程

按照阶数由小到大，逐列读出各字母，所得密文为：

tpocacsftktiaofe.

对于这种列变换类型的置换密码，密码分析很容易进行:

在矩阵中，并依次改变行的位置，然后按列读出，就可得到有意义的明文。

全性，可以按同样的方法执行多次置换。

例如对上述密文再执行一次置换,的二次置换密文:

ostftatapckocfie

还有一种置换密码采用周期性换位。

对于周期为r的置换密码，首先将明文分成若干组，每组含有r个元素，然后对每一组都按前述算法执行一次置换，最后得到密文。

【例2】一周期为4的换位密码，密钥及密文同上例，加密过程如图2：

iktn

亡0事u

uo•w

eoac

eoat

2314

：

314

2314

aEt«

ckpo

3tOf

f1c«

$za

peko

a-3?

f

ef1e

图2周期性换位密码

列变换类型的置换密码

算法步骤：

1、将明文按矩阵的方式逐行写出

2、根据密钥中各列阶的大小顺序，将明文矩阵的数据按列读出，得到的结果就是密文

列变换类型的置换密码

••示例••

密钥：

coat明文:

altackpostoftlce

mtn

CO1t

阶

2314

明文

*II*ckpostofficc

:

tpoaK：

iftktiaofe

2、替代密码

单表替代密码对明文中的所有字母都用一个固定的明文字母表到密文字母表的映射

fH->C/（nrr）5。

换句话说，对于明文（叫"叫』二叫［），相应的密文为

仇g…%1）」/血）』（叫）；」（叫［））。

下面介绍几种简单的替代密码。

1.加法密码

在加法密码中，映射规则可表示为/（mr）J（ilt）mDdrLO「已n,其中k

为密钥，加密算法就是（0（J+i）mwlno

例如，我们可以将英文的26个字母分别对应于整数

Q*'h2#3门4心5门6心7f8q9卩

0~25，贝Un=26，对应关系如表

世12鱼13*

皿血y匸z+心

22卩2%2如25^心

0门p~qjRp嗣和up¥卫皿1印16』讯⑻19*2S21*

【例1】取密钥k=9,明文为"attackpostoffice"，则转换为密文的过程如下：

首先将其转化为数字序列：

019190210151418191455824

然后每个数值加9,并做模26运算，得到以下序列：

92291119242312231414171113

再将其转化为英文字母，可得密文：

jccjltyxbcxoorln.

2.乘法密码

乘法密码的映射规则可表示为于（码）（"©mod/m）1,其中k为密钥，加密算法就是蜕①Ux上）111记no

【例2】密钥及明文同上例，采用乘法密码后的密文为：

appasmfwgpwttusk.

乘法密码有时也叫做采样密码。

3.仿射密码

同时运用加法密码和乘法密码，就构成了仿射密码。

可以表示为：

/（«i）=哼丿二（f沽+ifl）mDd吗（片周二卩＜妇＜»其中（kO,k1）为密钥，加密算法可表示为^（iXix^+^mdn

。

解密算法是加密算

法的逆变换，为几a）人x0打）™^專

例子从略。

4.多项式密码

仿照仿射密码，我们可以构造出更复杂的多项式密码：

鸟0二（4&+尸浊片+却）modn,

其中，阳）J1…仙讹卫

上述三种密码都可以看作是多项式密码的特例。

5.密钥短语密码

密钥短语密码是对上述各密码算法的改造，基本思想是任意选一短语作为密钥，去掉该

密钥中的重复字母，并将它们依次写在明文字母表下，然后将明文字母表中从未在密钥短语

中出现的字母依次写在该短语的后面，从而构造出一对明文、密文对应表。

【例3】取密钥短语为goodworker，去掉重复字母，得godwrke，构造明/密文对照表如下：

明文表：

abcdefghijklmnopqrstuvwxyz；

密文表：

godwrkeabcfhijlmnpqstuvxyz；

那么对于上例明文，其密文为：

gssgdfmlqslkkbdr。

由上例可以发现，采用以上方法，若密钥短语选择不合适，会造成大部分的密文字母与明文字母一致的现象，使得保密程度下降。

我们可以结合置换密码的思想予以改进。

【例4】密钥短语同上，我们可以构造矩阵：

godwrkeabcfhijlmnpqstuvxyz若按列读出，则可得明/密文对照表：

明文表：

abcdefghijklmnopqrstuvwxyz；

密文表：

galuobmvdcnxwfpyrhqzkisejt。

在单表替代密码中，对于多项式密码及其特例，由于它们的密钥量比较小，可以利用穷举攻击进行破译，尤其在计算机的帮助下，破译起来可以说是轻而易举。

而对于密钥短语替代密码，密文字母表本质上是明文字母表的一种排列，若字母表中有n个字母，可能的密文

字母表是n!

种。

若n较大，即使有计算机的帮助，穷举攻击也是不大现实的。

即便如此，密码分析者利用统计分析方法，仍能迅速地攻破。

下面我们简单地介绍一下统计分析攻击的

基本思路。

任何自然语言都有其固有的统计规律性，如果明文语言的统计规律在密文中有所反应，则密码分析者就可以通过分析明文和密文的统计规律而破译密码。

比如，人们分析了英语的单字母、双字母及三字母的统计特性：

1、英文字母频度分类：

极高频度字母：

e

次高频度字母：

taoinshr中等频度字母：

dlucm

低频度字母：

pfywgbv次低频度字母：

jkqxz

2、频度高的双字母组：

thheineranreedonesstenattonthandoueangasortiisetitartesehiof

3、频度高的三字母组：

theingandherereentthanthwasethfordthhatsheioninthissthersver

4、

当密码分析者要对截获的密文进行分析时，首先统计密文中的字母出现频率，并与明文

字母统计表比较。

例如在英文中，字母e的出现频率远远高于其它的字母，所以若一密文字

母出现频率极高，我们就可以断定该密文的对应明文是e。

进一步比较密文和明文的其它统

计数据及分布模式，就可以确定出密钥，进而攻破单表替代密码。

举例从略。

【2】对称密码

1、DES算法原理

1977年,DES成为一个标准，以后每五年进行一次再验证，这通常在12月份进行。

所有

的美国联邦机构和其他处理信息的组织为了各自的利益都必须使用DE（用于非机密文档）。

在非政府公司中，DES也得到了广泛的使用。

这个算法基于IBM的LUCIFER系统，该系统使

用128位的密钥。

通常，密钥越长，系统越安全。

DES使用64位密钥；但是其中8位用于

错误检测，因此实际上从安全性角度看DES是个56位的密钥系统。

由于该加密系统以64

位的二进制数据为一组进行加密，因此它也被称为分组密码。

DES的安全性取决于密钥的保

密，而不是算法的保密。

通过密钥的长度可以进一步增强安全性，因为存在着7亿亿

（70,000,000,000,000,000）种可能的密钥；因此推断密钥的可能性很小，足以保护大部分

分布式环境。

当然，随着普通PC的能力持续提高，连续搜索密钥和破译代码的能力也成比

例的提高。

该加密算法有三个阶段，在图1中进行了描述。

解密是通过逆序执行这三个阶段来实现的，包括逆序使用阶段2中所提到的密钥分组（从K16到K1）。

Phase1

DES阶段1:

初始置换

DES的第一阶段包括64位分组的置换，改变每个分组中位的顺序。

术语置换使用其严格的数学意义；只改变了顺序。

在下面的表格中具体给出了这个置换（参见DetailBox1.1）。

这64位数据现在被分成两半：

L0（左半部分）和R0（右半部分）。

下标0说明是原始的数

据。

在DES算法第二阶段的每次循环后，这些下标加

DetailBox1.1DES置换表1中描述了这个表格，DES标准使用这个表格来进行初始置换［NIST77］。

因此，在置换后的第1位是置换前的第58位。

在置换后的第2位是置换前的第50位。

置换后数据的最后一位在最初是明文中的第7个数据位。

表1DES初始置换［NIST77］

58

50

42

34

26

18

10

1

2

60

52

44

36

28

20

12

4

62

54

46

38

30

22

14

6

64

56

48

40

32

24

16

8

57

49

41

33

25

17

9

1

I

59

51

43

35

27

19

11

3

61

53

45

37

29

21

13

5

63

55

47

39

31

23

15

7

DES阶段2:

移位（重复16次）

第二阶段包括一种根据密钥，并且依赖于表格的算法。

这种操作通常被称为数据移位。

这个算法要重复16次，但由于每次移位都使用密钥的不同子分组，因此每次移位的操作各不相同。

密钥的子分组由另一组表格和表格的移位算法来确定。

在每次循环以后，L（左半部分）

和R（右半部分）的下标依次加一，用来表示每个阶段，如图1所示。

第16次循环的结果

被称为预输出，并传送到第3阶段。

［NIST77］中列有这些表格和各种算法。

DES阶段3:

逆序置换

DES的最后一个阶段包括64位分组的置换，改变每个分组中位的顺序，这与第1阶段的操

作类似，只是前后者使用不同的表格。

在下面的表格中具体给出了这个置换（参见DetailBox1.2）。

这次置换的输出结果就是密文。

DetailBox1.2DES逆序置换

表2中描述了这个表格，DES标准使用这个表格来进行最后的逆序置换［NIST77］。

因此，在

置换后的第1位是预输出的第40位。

在置换后的第2位是预输出的第8位。

而密文的最后一位是预输出的第25个数据位。

表2DES逆序置换[NIST77]

40

8

48

16

56

24

64

32

「39

r7

47

15

55

23

63

31

38

6

46

14

54

22

62

30

37

5

45

13

53

21

61

29

36

4

44

12

52

20

60

28

35

3

43

11

51

19

59

27

34

2

42

10

50

18

58

26

33

1

41

9

49

17

57

25

DES算法流程

2是它的算法粗框图。

其具体运

DES的算法是对称的，既可用于加密又可用于解密。

图算过程有如下七步。

r***

K（n

密钥扩展

密钥（ASCII）:

“Thisisatestkey”

比特流

01010100011010000110100101110011011010010111001101100001

循环16轮

O1O

O1OO

Ki,KirK3.K4,K5,K6.…，Kiz,Ki3,Ki4rK15,

加密

更文比特：

0*111O1Ol1O1ODDOl1mOOlU111DOHCXJ1tKMMMJ-O11O10O1O111（MH1

冒换选弹IF

Loroiioiiiioi

HllLil110Q1OQ11OOlOOlC

选择运畀E

I1IIMUhill

循环]6轮

OOCOOOOOOOQiailllllLllLOlOTlCOOOllOOOOl001010

KinmooooiononoiiicciiQaiwiiiooodooicxxxxxjii

I1t'MXPD

ILMJL1I

□miILMJ

miocriiiiiaii

蚤换运1FP

11OOOOOOl1101OCKMl1OOl11OOl1ClDAO

R]:

icn.ui1111cn.ocxjcji11Ocii.i

15种侯选算法中选出的

DES算法。

Rijndael

Rijmen和Daemen的名字得

2、AES算法原理

2000年10月，NIST（美国国家标准和技术协会）宣布通过从一项新的密钥加密标准。

新的标准将会代替密钥长度变的太短的旧的被选中成为将来的AESRijndael这个名字是从它的两个发明者来的。

这个加密体系是一种分组加密方法，因为信息的内容是以128位长度的分组为加密

单元的。

加密密钥长度有128，192或256位多种选择。

DES加密的分组长度是64比特，而

密钥长度只有64比特。

三重DES加密的分组长度通常是64比特，而密钥长度是112比特。

心施

图1:

AES迭代

图1描述了AES的操作模式。

首先密钥K0和待加密信息按位相与。

然后所有要加密的分组都用一个函数F进行迭代计算，计算用的子密钥是由一个密钥扩展函数产生的，初始

的密钥是主密钥。

对于AES函数F要迭代10次。

图2描述的是加密过程中函数F是如何被迭代的。

一个128位的分组转换成16个字

节，作为下面处理的输入。

首先，每一个字节分别经过替换函数S的处理，然后，用第二个

置换函数P对16个字节进行处理。

然后这个结果就和密钥扩展函数产生的子密钥进行位与。

密钥Ki是用密钥扩展函数从第K（i-1）轮的子密钥和第K0的密钥得到的。

图3描述了密钥扩展函数。

16个字节的被分成4组，每组4个字节，来进行处理。

最后的一组的4个字节由替换函数S（这个S和用F函数进行迭代处理时的S是一样的）来进行替换处理。

最初的4个字节的结果和a系数相加，这个系数是与轮数相关的，它是预

先定义的。

最后，为了得到Ki，把得到的4个字节的结果和K（i-1）子密钥的最初4个字节

按位相加，然后得到的结果又和K（i-1）子密钥的下面的4个字节按位相加，如此类推。

输A

128bbits

图2:

函数F

好了，现在我们简单地看看替换函数是怎么得到的，然后看看ai常数有什么作用。

为了简单的理由，一个字节应该是256个元素集（称为有限域）的一个元素，对于这些元素

只包含一些简单的操作（例如加法，乘法，反转）。

事实上，前面提到的替换函数S在那个

有限域里的反转。

置换函数S被定义为一个很简单的操作，以便能简单的实现。

ai系数是

和指数1（有限域的元素）成正比的。

这些考虑，使得AES实现起来非常有效。

因为AES仅仅在基于简单的位操作运算，这有两个主要的优点：

1.即使是纯粹的软件实现，AES也是很快的。

例如，用C++在奔腾200的电脑

上实现的AES的加密速度可达到70M位/秒；

2.AES并不依赖于S-Box的选择（根据NSA,DES里的S-Boxes可能包含后门），对分析算法抗击差分密码分析及线性密码分析具有抵抗能力。

图3:

密钥扩展例程

41A424CF

AC2tD801

33ED13C9

C2C9A3BA|

陶V9負理*丄1[

加密

明文（ASCII）:

"IamthetMtjucsMft"

20

65

眄

69

73

74

20

68

69

20

.54

20

腔

W3

63

63

63

閃

63

閃

AddRuundKey

63

D4

C5犖

63

63

63

63

FE

85

C5

h-lixC<>]uE[UL±i

63

63

63

閃

6D

65-

73

痣

61

6D

20

74

74

20

49

20

20

71

07

E7

83

72

58BB

83

R3

42FEFEDF

FE

63

63

63

【3】单项散列函数

单向函数

一个函数.'■-'■■称为严格单向函数，如果存在一个有效的算法（如多项式算

法）,使得对X中的任意元素x,都可计算f（x）,但不存在有效的算法使得对f（X）中的任意

元素y,都可计算出x满足f（x）=y.单向散列函数H（M）作用于一个任意长度的消息M,

返回一个固定长度的散列值h:

h=H（M）.

单向散列函数应具有的特性：

1.

给定M,很容易计算h;

2.

给定h,计算M使得H（M）=h非常困难；

3.

给定M,要找到另一个消息M'使得H（M'）=H（M）非常困难

在其它的一些应用中，仅有单向性是不够的，还需要称之为抗碰撞

（collision-resistanee）的条件:

要找出两个随机的消息M和M',使得H（M）=H（M'）非常困难.

要设计一个接收任意长度输入的函数不是一件容易的事，更不用说是单向的.在实

际中，单向散列函数建立在压缩函数的想法上•给定长度为m的输入，单向函数输出长度

为n的散列值.

将信息m分组为1-~'-1—L相应的散列值为1■--'f-，

''=是m或所有分组的散列值

1、MD5

MD5算法原理

MD5的全称是Message-DigestAlgorithm5（信息-摘要算法），在90年代初由MITLaboratoryforComputerScienee和RSADataSecurityInc的RonaldL.Rivest开发

出来，经MD2MD3和MD4发展而来。

它的作用是让大容量信息在用数字签名软件签署私人密匙前被”压缩”成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。

不管是MD2MD4还是MD5它们都需要获得一个随机长度的信息并产生一个128位的信息

摘要。

虽然这些算法的结构或多或少有些相似，但MD2的设计与MD4和MD5完全不同，那是

因为MD2是为8位机器做过设计优化的，而MD4和MD5却是面向32位的电脑。

这三个算法

的描述和C语言源代码在InternetRFCs1321中有详细的描述

http:

//www.ietf.org/rfc/rfc1321.txt），这是一份最权威的文档，由RonaidL.Rivest

在1992年8月向IEFT提交。

Rivest在1989年开发出MD2算法。

在这个算法中，首先对信息进行数据补位，使信息的字节长度是16的倍数。

然后，以一个16位的检验和追加到信息末尾。

并且根据这个

新产生的信息计算出散列值。

后来，Rogier和Chauvaud发现如果忽略了检验和将产生MD2

冲突。

MD2算法的加密后结果是唯一的--既没有重复。

为了加强算法的安全性，Rivest在1990年又开发出MD4算法。

MD4算法同样需要填补信息以确保信息的字节长度加上448后能被512整除（信息字节长度mod512=448）。

然

后，一个以64位二进制表示的信息的最初长度被添加进来。

信息被处理成512位

Damg?

rd/Merkle迭代结构的区块，而且每个区块要通过三个不同步骤的处理。

DenBoer和

Bosselaers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。

Dobbertin

向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版本中的冲突（这个冲

突实际上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后结果）。

毫

无疑问，MD4就此被淘汰掉了。

尽管MD4算法在安全上有个这么大的漏洞，但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。

除了MD5以外，其中比较有名的还有SHA-1、

RIPE-MD以及HAVAL等。

一年以后，即1991年，Rivest开发出技术上更为趋近成熟的MD5算法。

它在MD4勺基

础上增加了”安全-带子"（Safety-Belts）的概念。

虽然MD5比MD41微慢一些，但却更为安全。

这个算法很明显的由四个和MD4设计有少许不同的步骤组成。

在MD5算法中，信息-

摘要的大小和填充的必要条件与MD4完全相同。

DenBoer和Bosselaers曾发现MD5算法中

的假冲突（Pseudo-Collisions），但除此之外就没有其他被发现的加密后结果了。

VanOorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数（Brute-Force

HashFunction），而且他们猜测一个被设计专门用来搜索MD5冲突的机器（这台机器在1994

年的制造成本大约是一百万美元）可以平均每24天就找到一个冲突。

但单从1991年到2001

年这10年间，竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一点，我

们就可以看出这个瑕疵并没有太多的影响MD5的安全性。

上面所有这些都不足以成为MD5

的在实际应用中的问题。

并且，由于MD5算法的使用不需要支付任何版权费用的，所以在一

般的情况下（非绝密应用领域。

但即便是应用在绝密领域内，MD5也不失为一种非常优秀的

中间技术），MD5怎么都应该算得上是非