密码学基础课程设计指导书

《现代密码学基础》

课程设计指导书

杨柳编

湖南科技大学计算机科学与工程学院

2014年12月

一、概述

本课程在简要复习数学基础知识之后，探讨了密码学研究的基本问题：通过不安全的通信媒介如何进行安全通信。也可以理解为关心任何希望限制不诚实者达到目的的问题，把度量和评价一个密码体制（协议）的安全性作为一个重点。就目前来说，密码学的研究领域已从消息加密扩大到了数字签名、消息认证、身份识别、抗欺骗协议等。无疑，在整个教学过程中非常重视密码学的基础，当然包括数学基础。并针对实际的密码体制（协议）强调设计与分析（攻击），对现代密码学的主要研究问题都进行了介绍。

对于密码学这样的课程，同学们一定要从理论、技术、应用三个方面进行学习与思考。密码体制（协议）无疑是我们的学习重点，密码体制（协议）也可以单纯地理解为计算机算法，从而有设计、分析、证明、实现的问题。实现密码体制（协议）就是我们经常讲的八个字：模型、算法、程序、测试。

二、课程设计步骤

课程设计步骤要求如下：

模型

从数学的角度看，解决任何问题都要建立一个数学模型，对于密码学来说更是如此。我们还可以认为，数据结构中的存储结构也是模型。于是这一部分的任务就是建立起问题的逻辑结构和存储结构，为算法设计和编码实现打下基础。

算法

这一部分对同学们的要求是能看懂书上的常用算法，并对其中的参数可以进行调整和设置，能实现和应用它们。

程序

编码实现得到程序。

4. 测试

5. 提交课程设计报告

三、课程设计报告编写要求

课程设计报告开头标明课程设计题目、设计者的班级、姓名、学号和完成日期，内容包括：模型、算法、程序、测试四个部分。

四、设计要求

可以只做第7题，不做第7题的要做第1题-第6题。

五、课程设计题目

题目1 大整数运算包的设计与实现

1．问题描述

大整数运算是现代密码学算法实现的基础，重要性不言而喻。大整数我们指的是二进制位512、1024和2048的数，一般的语言不支持。

2．基本要求

以类库头文件的形式实现。

3．实现提示

在选择了大整数的存储结构之后，主要实现以下运算：

模加；

模减；

模乘；

模整除；

模取余。这五种运算模拟手算实现。

幂模：利用“平方-乘法”算法实现。

GCD：利用欧几里得算法实现。

乘法逆: 利用扩展的欧几里得算法实现。

素数判定与生成：概率性素数产生方法产生的数仅仅是伪素数，其缺点在于，尽管其产生合数的可能性很小，但是这种可能性仍然存在:其优点是产生的伪素数没有规律性，而且产生的速度也比较快。此类方法是生成大素数的主要方法，其中较著名的算法有:Miller Rabin算法、Solovay-Strassen算法等。本文讨论Miller Rabin算法。

Miller Rabin素性测试法是在实际中应用非常广的一种素性测试方案，可以用来判定某随机数是否为素数。其定义如下:

设n>2是一个奇数，设n-1=2sm，其中s是非负整数，m>0是奇数，设0

bm≡－1(mod n)，

或者存在一个r,0≤r

b 2^r m≡－1(modn)

则称n通过以b为基的Miller-Rabin测试。

可以利用Miller-Rabin素性测试算法来随机生成大素数，随即生成一个奇数n>2，随即均匀的选取序列b1,b2...,bk∈{1,2,...,n-1}，对n进行k次Miller-Rabin素性测试，如果每次输出都为“n可能是素数”，则n是合数的概率小于1/4k当k足够大时，1/4k是一个十分小的数。同学们在具体实现时，为了提高速度最好以空间换时间，在主程序运行前先构造一个大素数表。

题目2 MD5的实现

1．问题描述

MD5以512比特一块的方式处理输入的消息文本，每个块又划分为十六个32比特的子块。算法的输出由四个32比特的块组成，将它们级联成一个128比特的Hash值。

①首先填充消息使填充后的长度恰好为一个比512的倍数小64的数。填充方法是附一个“1”在消息后面，再补多个“0”。然后，在其后附上64比特的消息长度（填充前）的二进制表示。算法中使用了四个32比特的变量A、B、C、D，先把这四个变量初始化为：

A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210

称它们为链接变量。

接着进行算法的主循环，循环的次数是消息中512比特的块的数目。

将上面四个变量复制到另外的变量中：A到AA，B到BB，C到CC，D到DD。

主循环有四轮，每一轮由16次操作组成。F、G、H、I函数，FF、GG、HH、II四种操作详见教材各密码学参考书。所有这些步骤进行完之后，将A、B、C、D分别加上AA、BB、CC、DD，然后用下一块数据继续进行算法。

③最后的输出是A、B、C、D的级联。

2．基本要求

以MD5(x)的形式实现，x为01串。

实现提示

注意消息文本、各种变量的类型及其类型转换。

题目3 仿射密码的攻击

1．问题描述

仿射密码系统用五元组（P，C，K，E，D）表示，设P=C={计算机学院网络工程信息安全，我们热爱中华人民共和国。大家…}.现在截获了一段密文“和院程安我爱计”。请编程分析出明文。

2．基本要求

程序要求界面友好，自动分析程度高，能输出加密所用的密钥和明文。

3．实现提示

申请三个字符数组Z，C，M。

Z={计算机学院网络工程信息安全，我们热爱中华人民共和国。大家}，

C=“和院程安我爱计”，

M保存分析所得的明文。

密文是通过ek(m)=am+b mod 28得到的，为了解密我们使用dk(c)=a-1(c-b)mod 28。这里有一个函数要先实现：

int gcd(int n,int m)

{

int r,temp;

if(n

{temp=n;

n=m;

m=temp;

}

while(m!=0)

{r=n%m;

n=m;

m=r;

}

return n;

}

有了以上的准备工作，我们就可以编写程序的主要部分了，它是一个多

重循环：

for(a=2;a<28;a++)

if (gcd(a,28)==1)

{/*求a的乘法逆元p */

for(b=2;b<28;b++)

if ((a*b)%28==1){p=b;break;};

/* 用dk(c)=p(c-b) mod 28 */

for(b=0;b<28;b++)

{对数组C进行处理，输出k=(a,b)和M，M有意义程序结束，分析完成。}

};

else continue;

题目4 RSA密码系统的实现

1．问题描述

RSA密码系统可具体描述为：取两个大素数p和q，令n=pq,N=(p-1)(q-1),随机选择整数d,满