中国矿业大学 密码学课程设计

中国矿业大学 信息安全 密码学课程设计

密码学

课程设计报告

张辰洋

信息安全08-3班 学号：08083703

2011年6月25日

中国矿业大学 信息安全 密码学课程设计

目 录

实验一 古典密码算法 ................................................................................................. 1

1.1 古典密码Hill .............................................................................................. 1

1.11 古典密码Hill概述................................................................................ 1

1.14 运行结果.................................................................................................. 2

1.15 密码安全性分析...................................................................................... 3

1.2 古典密码 Vignere ....................................................................................... 4

1.21 古典密码 Vignere概述......................................................................... 4

1.22 算法原理与设计思路.............................................................................. 4

1.23 关键算法分析.......................................................................................... 4

1.24 运行结果.................................................................................................. 5

1.25 密码安全性分析...................................................................................... 6

1.3古典密码Playfair ....................................................................................... 6

1.31 古典密码Playfair概述........................................................................ 6

1.32 算法原理与设计思路.............................................................................. 6

1.34 运行结果.................................................................................................. 8

1.35 密码安全性分析...................................................................................... 8

1.4古典密码Vernam ........................................................................................... 8

1.41 古典密码Vernam概述............................................................................ 8

1.42 算法原理与设计思想 .......................................................................... 9

1.43 关键代码分析.......................................................................................... 9

1.44 运行结果................................................................................................ 10

1.45 安全性分析............................................................................................ 10

实验二 分组密码DES加密解密 ............................................................................... 11

2.1 分组密码DES加密解密概述 ..................................................................... 11

2.2 算法原理与设计思想 ................................................................................. 11

2.3 DES加密解密主要算法分析 ...................................................................... 12

2.4 运行结果 ..................................................................................................... 13

2.5 密码安全性分析 ......................................................................................... 14

实验三 公钥密码算法RSA ........................................................................................ 15

3.1 公钥密码算法RSA概述 ............................................................................. 15

3.2 算法原理与设计思想 ................................................................................. 15

3.3 关键算法分析 ............................................................................................. 16

3.4 运行结果 ..................................................................................................... 17

3.5 密码安全性分析 ......................................................................................... 18

实验总结和体会.......................................................................................................... 19

中国矿业大学 信息安全 密码学课程设计

实验一 古典密码算法

1.1 古典密码Hill

1.11 古典密码Hill概述

Hill体制是1929年由Lester S.Hill发明的，它实际上就是利用了我们熟

知的线性变换方法，是在Z26上进行的。Hill体制的基本思想是将n个明文字

母通过线性变换转化为n个密文字母，解密时只需要做一次逆变换即可，密钥就

是变换矩阵。

1.12算法原理与设计思路

1.假设要加密的明文是由26个字母组成，其他字符省略。将每个字符与0-25

的一个数字一一对应起来。（例如：a/A—0，b/B—1，……z/Z—25）。

2.选择一个加密矩阵An n，其中矩阵A必须是可逆矩阵，例如

7

0

A 1

16

21 1123109135 1875 692 23210 72215 5

3.将明文字母分别依照次序每n个一组（如果最后一组不足n个的话，就将其补

成n个），依照字符与数字的对应关系得到明文矩阵minglen/n n。

4.通过加密矩阵A，利用矩阵乘法得到密文矩阵milen/n n= minglen/n n An nmod 26；

将密文矩阵的数字与字符对应起来，得到密文。

5.解密时利用加密矩阵的逆矩阵A 1和密文，可得到明文。

nn6. 设明文为m (m1 m2, ,mn) Z26,密文c (c1,c2,. ,cn) Z26，密钥为Z26

上的n*n阶可逆方阵K (kij)n n，则

加密：密文c mKmod26

解密：明文m cK 1mod26

1.13 关键算法分析

中国矿业大学 信息安全 密码学课程设计

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。

产生公约数的目的是为了下一步求逆矩阵和矩阵时方便运算。

这段代码是加密的过程，主要设计思想是输入的明文与矩阵做乘法，当明文

长度为矩阵阶数的倍数时，自动将明文变为列数与矩阵阶数相同，然后进行计算。

当明文长度不是矩阵阶数的倍数时，则会出现无关字符。

代码中的利用矩阵乘法得到的密文输出即可，而解密的过程只需要利用矩阵

的逆矩阵，也就是我们在做乘法的时候将矩阵换为它的逆矩阵即可得到明文。

1.14 运行结果

中国矿业大学 信息安全 密码学课程设计

1.15 密码安全性分析

经过算法分析和设计，我们可以知道它的安全强度（m是素数，模数为合数，

不是任意矩阵可逆） 为 26的m*m次方。例如，当m=5时，得出它的安全强度

为2的117次方。通过矩阵，将信息均匀分布到每个m长向量的每个分向量中，

具有比较好的随机性，相对于其他的古典密码来说，Hill是比较安全的。

但是在已知m组明文、密文和解密算法的情况下，我们需要解M组同余方程

组，因此，密钥是可以恢复的。关键是求得加密矩阵的逆—解密矩阵。只要分析

出两个明文向量（线性无关）与相应的密文向量。若有

b1 a1

A b 2 a2 b3 a3 A b4 a4 b1 b2b3 a1 A b4 a2a3 a4 b1A b2b3 a1 b4 a2a3 a4 1

如果甲方截获了一段密文：OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH

经分析这段密文是用HILL2密码编译的，且这段密文的字母 UCRS 依次代表

了字母 TACO，我们接着将要进行破译。

关系如下：

U

R 21 C 3 1 A 1 18 19 2 A 2 S 1 1 A 20 T 2 15 O 3 C 20A 13 21 15 318 19

计算矩阵的逆

det 1 2 2131819(mod26) 345(mod26) 7

中国矿业大学 信息安全 密码学课程设计

2118 1 19 18 2516

(mod26) (mod26) 15 3213 319 7

1 203 2118 A 115 319 1 1 017 9

破译

密文向量

15 23 9 0 24 21 9 5 2 21 18 9 12 8 1 13 12 10 15 5 8 161921121191131916211313161020 10 14 8

明文向量

3 9 20 14 19 15 14 20 22 19 20 3 21 20 25 14 9 4 5 1 20 12 14 15 9 7 9 7 15 9 9 1 15 14 18 9 13 4 12 5 19 20

明文：Clinton is going to visit a country in Middle East

1.2 古典密码 Vignere

1.21 古典密码 Vignere概述

1858年法国密码学家维吉尼亚提出一种以移位替换为基础的周期替换密

码。这种密码是多表替换密码的一种。是一系列（两个以上）替换表依次对明文

消息的字母进行替换的加密方法。

1.22 算法原理与设计思路

1.首先使用维吉尼亚方阵，它的基本方阵是26列26行。方阵的第一行是a到z

按正常顺序排列的字母表，第二行是第一行左移循环一位得到得，其他各行依次

类推。

2.加密时，按照密钥字的指示，决定采用哪一个单表。例如密钥字是bupt，加

密时，明文的第一个字母用与附加列上字母b相对应的密码表进行加密，明文的

第二个字母用与附加列的字母u相对应的密码表进行加密，依次类推。

3.令英文字母a,b,…,z对应于从0到25的整数。设明文是n个字母组成的字符

串，即 m=m1m2m3m4…mn

密钥字周期性地延伸就给出了明文加密所需的工作密钥

K=k1k2…kn,E（m）=C=c1c2…cn

加密：Ci=mi+kimod26

解密：mi=ci-kimod26,i=1,2,3,…,n

1.23 关键算法分析

中国矿业大学 信息安全 密码学课程设计

加密算法的关键是给出初始密钥，例如第一个密钥字母是e，对第一个明文

字母p进行加密时，选用左边附加列上的字母e对应的那一行作为代替密码表，

查处与p相对应的密文字母是T，依次类推即可得出明文。上述代码中的生成密

钥部分为核心代码，只有密钥更长，才能保证密码算法的可靠性。解密算法和加

密算法只需要减去密钥继续模26即可得到。

1.24 运行结果

中国矿业大学 信息安全 密码学课程设计

1.25密码安全性分析

首先，破译的第一步就是寻找密文中出现超过一次的字母。有两种情况可能

导致这样的重复发生。最有可能的是明文中同样的字母序列使用密钥中同样的字

母加了密；另外还有一种较小的可能性是明文中两个不同的字母序列通过密钥中

不同部分加了密，碰巧都变成了密文中完全一样的序列。假如我们限制在长序列

的范围内，那么第二种可能性可以很大程序地被排除，这种情况下，我们多数考

虑到4个字母或4个以上的重复序列。

其次，破译的第二步是确定密钥的长度，又看看这一段先： 密钥 F O R E S

T F O R E S T F O R E S T F O R E S T F O R 明 文 b e t t e r t o d o w

e l l t h a n t o s a y w e l l 密 文 G S K X W K Y C U S O X Q Z K L S

G Y C J E Q P J Z C 第一个YC出现后到第二个YC的结尾一共有12个字母（U

S O X Q Z K L S G Y C） 那么密钥的长度应是12的约数－－－1，2，3，4，6，

12之中的一个（其中，1可排除）。

第三， 破译的时候，可以从一下几个方面进行考虑。1.A－E段，U－Z段以

及O－T段的特征比较显著，可先从这些方面着手； 2.如果一些字符串出现的频

率较多，不妨猜猜，特别要注意THE，-ING等的出现；3.要留意那些图表中没有

出现的字母，很多时候也会是突破点，如X与Z的空缺；4.图表最好还是做一下，

毕竟比较直观，好看 。

因此，利用单纯的数学统计方法就可以攻破维吉尼亚密码，所以在使用这种

密码的过程中，我们尽量增加密钥的长度，只有密钥长度的足够长时，密码的使

用才会越安全。

1.3古典密码Playfair

1.31古典密码Playfair概述

Playfair密码最为著名的多字母加密密码．它将明文中的双字母组合作为

基于一个 5x5的字母矩阵．该矩阵通过一个关键词构造。从左到右、从上到下

填入该关键词的字母，并去除重复的字母(两个a只取一个)；其次。按照字母表

顺序将其余字母填入矩阵的剩余空问。字母I和J被算作一个字母，可以根据使

用者的意愿在形成密文时确定用I或L

1.32 算法原理与设计思路

密。这两个字母构成一对。其加密规则如下：

（1）一对明文字母如果是重复的，则在这对明文字母中间插入一个填充字符，

一个单元．并将这些单元转换为密文双字母的组合。Playfair算法 Playfair算法根据下列规则一次对明文的两个字母进行加

中国矿业大学 信息安全 密码学课程设计

如x。因此，单词session将被分割成：se ss si on.

(2)如果分割后的明文字母对在矩阵的同一行中都出现， E第一个字母代替。例如，on被加密成qo．而st被加密为tn。 则分别用矩阵中其右侧的字母代替．行的最后一个字母山行的

(3)如果分割后的明文字母对在矩阵的 一列中都出现， 第一个字母代替。例如，en被加密成nU．而aW被加密成ba。

(4)如果分割后的明文字母对既不在矩阵的同一列中都出 现也不在矩阵的同一

行中都出现．密文是这两个字母所在的长方形的另两个顶点。例如，8e被加密

成nk，而cu被加密成ix(或ix)。

(5)如果明文有奇数个字母，末尾加一个无效字母。

1.33关键算法分析

上述代码主要是用来填充矩阵，首先将明文矩阵进行填充，也就是第一张图

片所显示的，这是算法的关键，也是第一步所在。然后上面的算法中还有因为是

将明文两两分组，即每两个明文分为一组，那么当明文为奇数的时候，就需要添

加一个无关字符，使它可以达到偶数个，以方便分组。

则分别用矩阵中其下方的字母代替．列的最后一个字母由列的

中国矿业大学 信息安全 密码学课程设计

在算法设计过程中，我一共设计了两个函数，即decrypt()加密函数，encrypt()解密函数，main()主函数。主函数中调用加密函数和解密函数，使程序可以比较顺利的进行。

1.34运行结果

1.35 密码安全性分析

尽管Playfair密码被认为是比较安全的，它仍然是相对容易攻破的。普莱费尔密码隐藏了的频率，但是该体制仍可以用统计分析方法来破译。因为它的明 文仍然完整地保留了明文语言的结果。几百个字母的密文就足够我们分析出规律了。在英文中各种连字：th,he,an,in,re,es,…

因此，Playfair密码对抗穷举攻击的效果比较差。即有26*26=676个双字母，利用现代计算机来分析，很短时间内就可以将其破解。

1.4古典密码Vernam

1.41 古典密码Vernam概述

替换代码的密钥是一个随机且不重复的字符序列，这种密码则称为一次密密码，因为它的密钥只使用一次。该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报通信设计的一种密码，所以又称为Vernam密码。Vernam密码在对明文加密，前首先将明文编码为（0，1）序列，然后再进行加密变换。

中国矿业大学 信息安全 密码学课程设计

1.42 算法原理与设计思想 1.按递增顺序把每个明文字母作为一个数字,A=0,B=1等等。

2.对输入密文中每一个字母做相同的处理。

3.将明文中的每个字母与密钥中的相应字母相加。

4.如果得到的和大于26,则从中减去26。

5.将和转化为字母,从而得到密文。

6.设m=(m1 m2 m3 … mi …)为明文,k=(k1 k2 k3 … ki …)为密钥,其中mi,ki ∈(0,1), i≥1,

加密变换为：c=(c1 c2 c3 … ci …) ,其中ci ＝ mi Å ki , i≥1, 这里为模2加法（或异或运算）

解密变换为：m=(m1 m2 m3 … mi …) ,其中mi ＝ ci Å ki , i≥1,

1.43 关键代码分析

中国矿业大学 信息安全 密码学课程设计

这段代码是整个程序的核心代码，首先，将字母变换为数字，字母对应0-26个数字；这是将字母转化后为模26的除法做准备。其次，是加密运算过程，主要就是明文与密钥相加后模26即可得到密文，最后，解密过程中，用得到的密文减去密钥之后模26即可得到明文。这就是整个算法的核心。然后将得到的数字变换为字母，变换的时候，和第一步的过程是相同的。

1.44 运行结果

1.45 安全性分析 在应用Vernam密码时，如果对不同的明文使用不同的随机密钥，这时Vernam密码为一次一个密码。由于每一密钥序列都是等概率随机产生的，敌手没有任何信息用来对密文进行密码分析。香农（Claude Shannon）从信息论的角度证明了这种密码体制在理论上是不可破译的。但如果重复使用同一个密钥加密不同的明文，则这时的Vernam密码就较为容易破译。 若敌手获得了一个密文c=(c1 c2 c3 … ci …) 和对应明文m=(m1 m2 m3 … mi …) 时，就很容易得出密钥 k=(k1 k2 k3 … ki …) ，其中ki ＝ ci Å mi ，i≥1。 故若重复使用密钥，该密码体制就很不安全。 实际上Vernam密码属于序列密码，加密解密方法都使用模2加，这使软硬件实现都非常简单。但是，这种密码体制虽然理论上是不可破译的，然而

在实际应用中，真正的一次一密系统却受到很大的限制，其主要原因在于该

密码体制要求：

① 密钥是真正的随机序列；

② 密钥长度大于等于明文长度；

中国矿业大学 信息安全 密码学课程设计

③ 每个密钥只用一次（一次一密）。 这样，分发和存储这样的随机密钥序列，并确保密钥的安全都是很因难 的；另外，如何生成真正的随机序列也是一个现实问题。因此，人们转而寻求实际上不对攻破的密码系统。

实验二 分组密码DES加密解密

2.1 分组密码DES加密解密概述

DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位，产生最大 64 位的分组大小。这是一个迭代的分组密码，使用称为 Feistel 的技术，其中将加密的文本块分成两半。使用子密钥对其中一半应用循环功能，然后将输出与另一半进行“异或”运算；接着交换这两半，这一过程会继续下去，但最后一个循环不交换。DES 使用 16 个循环，使用异或，置换，代换，移位操作四种基本运算。

2.2 算法原理与设计思想

DES的加密过程可分为加密处理,加密变换和子密钥生成几个部分组成。

1.加密处理过程

(1)初始变换。加密处理首先要对64位的明文按表1所示的初始换位表IP进行变换。表中的数值表示输入位被置换后的新位置。例如输入的第58位,在输出的时候被置换到第1

位;输入的是第7位,在输出时被置换到第64位。

中国矿业大学 信息安全 密码学课程设计

(2)加密处理。上述换位处理的输出,中间要经过16轮加密变换。初始换位的64位的输出作为下一次的输入,将64位分为左、右两个32位,分别记为L0和R0,从L0、R0到L16、R16,共进行16轮加密变换。其中,经过n轮处理后的点左右32位分别为Ln和Rn,则可做如下定义:

Ln=Rn-1

Rn=Ln-1

其中,kn是向第n轮输入的48位的子密钥,Ln-1和Rn-1分别是第n-1轮的输出,f是Mangler函数。

(3)最后换位。进行16轮的加密变换之后,将L16和R16合成64位的数据,再按照表2所示的最后换位表进行IP-1的换位,得到64位的密文,这就是DES算法加密的结果。

2.加密变换过程

通过重复某些位将32位的右半部分按照扩展表3扩展换位表扩展为48位,而56位的密钥先移位然后通过选择其中的某些位减少至48位,48位的右半部分通过异或操作和48位的密钥结合,并分成6位的8个分组,通过8个S-盒将这48位替代成新的32位数据,再将其置换一次。这些S-盒输入6位,输出4位。

3.子密钥生成过程

钥通常表示为64位的自然数,首先通过压缩换位PC-1去掉每个字节的第8位,用作奇偶校验,因此,密钥去掉第8、16、24……64位减至56位,所以实际密钥长度为56位,而每轮要生成48位的子密钥。

4.解密处理过程

从密文到明文的解密过程可采用与加密完全相同的算法。不过解密要用加密的逆变换,就是把上面的最后换位表和初始换位表完全倒过来变换。这里不再赘述。

2.3 DES加密解密主要算法分析

中国矿业大学 信息安全 密码学课程设计

上述是我做程序中主要用到的函数和算法，DES_Run()主要功能就是涉及到S盒的变换,即将S盒的内容包含在里面。DES_SetKey()的功能是设置密钥,main()函数调用上面的主要方法和步骤，完成实验算法。而接下来的16轮子密钥的功能就是方便下面的与子密钥进行异或时使用。

与子密钥异或得到48位，每6比特一组，共分成8组，分别作为8个S盒的输入；每一个分组将对应于一个S盒进行变换运算：分组1由S盒1进行变换操作，分组2由S盒2操作…而且8个S盒所表示的变换也是不同的。

这段代码的作用是设置密钥，DES算法共需16轮迭代运算，每轮迭代运算使用一个子密钥，共需要16个子密钥。子密钥是从用户输入的初始密钥（或称为种子密钥）产生的，用户输入的初始密钥K为64位，其中有8为用于奇偶校验，分别位于第8,16,24,32,40,48,56,64。奇偶校验位用于检查密钥K在产生和分配以及存储过程中可能发生的错误，这样DES的密钥实际上只有56位。

2.4 运行结果

中国矿业大学 信息安全 密码学课程设计

接下来我将其封装为可视化界面，将程序封装到里面。

2.5 密码安全性分析

DES是对称的分组密码算法。对称的分组密码算法最主要的问题是：由于加解密双方都要使用相同的密钥，因此在发送、接收数据之前，必须完成密钥的分发。因而，密钥的分发便成了该加密体系中的最薄弱、风险最大的环节，各种基本的手段均很难保障安全地完成此项工作，从而使密钥更新的周期加长，给他人破译密钥提供了机会。

其次，由于算法各轮的子密钥是通过改变初始密钥这种方式得到的,因此有些初始密钥成了弱密钥(weakkey)。初始密钥分成两部分,每部分各自独立的移动。如果每一部分的所有位都是0或1,那么算法的任意一个周期的密钥都是相同的。当密钥是全1、全0、或者一半全1、一半全0时,会发生这种情况。下面以十六进制编码的方式给出了四种弱密钥。

弱密钥值( 带奇偶校验位) 真实密钥

0101 0101 0101 0101 0000000 0000000

1F1F 1F1F E0E0 E0E0 0000000 FFFFFFF

E0E0 E0E0 1F1F 1F1F FFFFFFF 0000000

FEFE FEFE FEFE FEFE FFFFFFF FFFFFFF

但是DES仅有56位二进制未免太短,许多密码学专家力荐使用更长的密钥,理由是穷举攻击的可能性。设已知一段密码文C及与它对应的明码文M,用一切可能的密钥K加密M,直到得到E(M)=C,这时所用的密钥K

即为要破译的密码的密

中国矿业大学 信息安全 密码学课程设计

钥。穷举法的时间复杂性是T=O(n),空间复杂性是S=O(1)。

对于DES密码,n=256≈7×106,即使使用每秒种可以计算一百万个密钥的大型计算机,也需要算106天才能求得所使用的密钥,因此看来是很安全的。但是密码专家Diffie和Hellman指出,如果设计一种一微秒可以核算一个密钥的超大规模集成片,那么它在一天内可以核算8.64×1010个密钥。如果由一个百万个这样的集成片构成专用机,他们当时估计:这种专用机的造价约为两千万美元。在五年内分期偿还,平均每天约需付一万美元。由于用穷举法破译平均只需要计算半个密钥空间,因此获得解的平均时间为半天。

这样,破译每个DES密码的花销只是五千美元。后来,Diffie在1981年又修改了他们的估计,认为以1980年的技术而论,用造价为五千万美元的专用机破译DES密码平均要花两天时间。但是他与Hellman都预计:1990年时,破译DES密码的专用机的造价将大幅度下降。同时,DES的硬件实现方法逐步接近Diffie和Hellman的专用机所要求每秒百万次的速度。在1993年,MuchaelWiener设计了一个一百万美元的机器,它能在平均3.5小时内,完成DES的穷举攻击,到1990年时,DES是完全不安全的。

实验三 公钥密码算法RSA

3.1 公钥密码算法RSA概述

RSA密码体制是美国麻省理工学院（MIT）Rivest、Shami和Adleman于1978年提出来的，它是第一个理论上最为成功的公开密钥密码体制，它的安全性基于数论中的Euler定理和计算复杂性理论中的下述论断：求两个大素数的乘积是很容易计算的，但要分解两个大素数的乘积，求出它们的素数因子却是非常困难的，它属于NP—完全类，是一种幂模运算的加密体制。除了用于加密外，它还能用于数字签字和身份认证。下面将从各个方面来详细对RSA公钥体制进行研究。

3.2 算法原理与设计思想

RSA算法的过程

首先产生密钥，过程如下：

(1) 随机产生两个长度为K/2位的素数P 和 Q

(2) 计算公钥 publicKey=P*Q;(publicKey 是k位的长度)

(3) 随机产生一个加密密钥 keyE, 2<=keyE<=Φ(n)-1其中GCD(keyE, Φ(n))=1; 注意这是保证解密密钥keyE *keyD mod Φ(n)=1 有解的充要条件， Φ(n)称为n的欧拉函数,值为: Φ(n)=(P-1)*(Q-1)

(4) 求解解密密钥keyD=keyE-1 mod (n) ,keyE-1为解密密钥keyD的逆元 ，此公式原方程为(keyE*keyD mod (n)=1)

中国矿业大学 信息安全 密码学课程设计

由此公钥，加密密钥，解密密钥全部产生。

其次 对明文加密或对密文进行解密,过程如下:

(1) 加密: C = M

算法流程图：

图2 总的流程图

图1为加密或解密流程图 keyE mod publicKey;其中M表示明文,C表示密文 (2) 解密: M = CkeyD mod publicKey. 其中M表示明文,C表示密文

图3 产生密钥流程图

3.3 关键算法分析

该算法是主要生成大素数的，大素数的产生是算法实现的关键。因此，我没有使用素数生成头文件或者类，而是采取用小素数生成大素数的方法，先找到一些随机素数，然后由随机素数生成大素数。

中国矿业大学 信息安全 密码学课程设计

当算法产生了大素数后，接着就是生成公钥和私钥了，求解密密钥实际上是如何去解一次同余方程 ax ≡ 1 mod n。根据费马定理与欧拉定理给出了同余方程的解为:

x=a(Φ(n)-1) mod n

由此可得出iKeyD*iKeyE≡ 1 mod Φ(n)

即iKeyD=iKeyE(Φ(Φ(n))-1) mod Φ(n)

3.4 运行结果

本文来源：https://www.bwwdw.com/article/axyh.html