《现代密码学基础》
课程设计指导书
杨柳 编
湖南科技大学计算机科学与工程学院
2014年12月
一、概述
本课程在简要复习数学基础知识之后，探讨了密码学研究的基本问题：通过不安全的通信媒介如何进行安全通信。也可以理解为关心任何希望限制不诚实者达到目的的问题，把度量和评价一个密码体制（协议）的安全性作为一个重点。就目前来说，密码学的研究领域已从消息加密扩大到了数字签名、消息认证、身份识别、抗欺骗协议等。无疑，在整个教学过程中非常重视密码学的基础，当然包括数学基础。并针对实际的密码体制（协议）强调设计与分析（攻击），对现代密码学的主要研究问题都进行了介绍。
对于密码学这样的课程，同学们一定要从理论、技术、应用三个方面进行学习与思考。密码体制（协议）无疑是我们的学习重点，密码体制（协议）也可以单纯地理解为计算机算法，从而有设计、分析、证明、实现的问题。实现密码体制（协议）就是我们经常讲的八个字：模型、算法、程序、测试。
二、课程设计步骤
课程设计步骤要求如下： 1. 模型
从数学的角度看，解决任何问题都要建立一个数学模型，对于密码学来说更是如此。我们还可以认为，数据结构中的存储结构也是模型。于是这一部分的任务就是建立起问题的逻辑结构和存储结构，为算法设计和编码实现打下基础。 2. 算法
这一部分对同学们的要求是能看懂书上的常用算法，并对其中的参数可以进行调整和设置，能实现和应用它们。 3. 程序
编码实现得到程序。 4. 测试
5. 提交课程设计报告
三、课程设计报告编写要求
课程设计报告开头标明课程设计题目、设计者的班级、姓名、学号和完成日期，内容包括：模型、算法、程序、测试四个部分。
四、设计要求
可以只做第7题，不做第7题的要做第1题-第6题。
五、课程设计题目
大整数运算包的设计与实现 1．问题描述
大整数运算是现代密码学算法实现的基础，重要性不言而喻。大整数我们指的是二进制位512、1024和2048的数，一般的语言不支持。 2．基本要求
以类库头文件的形式实现。 3．实现提示
在选择了大整数的存储结构之后，主要实现以下运算： ① 模加； ② 模减； ③ 模乘； ④ 模整除；
⑤ 模取余。这五种运算模拟手算实现。 ⑥ 幂模：利用“平方-乘法”算法实现。 ⑦ GCD：利用欧几里得算法实现。
⑧ 乘法逆: 利用扩展的欧几里得算法实现。
⑨ 素数判定与生成：概率性素数产生方法产生的数仅仅是伪素数，其缺点在于，
尽管其产生合数的可能性很小，但是这种可能性仍然存在:其优点是产生的伪素数没有规律性，而且产生的速度也比较快。此类方法是生成大素数的主要方法，其中较著名的算法有:Miller Rabin算法、Solovay-Strassen算法等。本文讨论Miller Rabin算法。
Miller Rabin素性测试法是在实际中应用非常广的一种素性测试方案，可以用来判定某随机数是否为素数。其定义如下:
设n>2是一个奇数，设n-1=2m，其中s是非负整数，m>0是奇数，设0
b≡－1(mod n)，
或者存在一个r,0≤r
2^r mm
s
≡－1(modn)
则称n通过以b为基的Miller-Rabin测试。
可以利用Miller-Rabin素性测试算法来随机生成大素数，随即生成一个奇数n>2，随即均匀的选取序列b1,b2...,bk∈{1,2,...,n-1}，对n进行k次Miller-Rabin素性测试，如果每次输出都为“n可能是素数”，则n是合数的概率小于 1/4当k足够大时，1/4是一个十分小的数。
同学们在具体实现时，为了提高速度最好以空间换时间，在主程序运行前先构造一个大素数表。
1．问题描述
MD5以512比特一块的方式处理输入的消息文本，每个块又划分为十六个32比特的子块。算法的输出由四个32比特的块组成，将它们级联成一个128比特的Hash值。
①首先填充消息使填充后的长度恰好为一个比512的倍数小64的数。填充方
k
k
的实现
法是附一个“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保存分析所得的明文。 ② 密文是通过
-1
ek(m)=am+b mod 28得到的，为了解密我们使用
dk(c)=a(c-b)mod 28。这里有一个函数要先实现： int gcd(int n,int m) {
int r,temp; if(n
while(m!=0) {r=n%m; n=m; m=r; } return n; }
③ 有了以上的准备工作，我们就可以编写程序的主要部分了，它是一个多 重循环：
for(a=2;a
{/*求a的乘法逆元p */ for(b=2;b
if ((a*b)%28==1){p=b;break;}; /* 用dk(c)=p(c-b) mod 28 */ for(b=0;b
{对数组C进行处理，输出k=(a,b)和M，M有意义程序结束，分析完成。} };
else continue;
1．问题描述
RSA密码系统可具体描述为：取两个大素数p和q，令n=pq,N=(p-1)(q-1),随机选择整数d,满足gcd(d,N)=1,ed=1 modN。
公开密钥：k1=(n,e) 私有密钥：k2=(p,q,d)
加密算法：对于待加密消息m，其对应的密文为c=E(m)=m(modn) 解密算法：D(c)=c(modn) 2．基本要求
p,q,d,e参数选取合理，程序要求界面友好，自动化程度高。 4． 实现提示
要实现一个真实的RSA密码系统，主要考虑对大整数的处理。P和q是1024位的，n取2048位。
d
e
密码系统的实现
1． 问题描述
为简化问题，我们取p=19,g=2,私钥x=9,则公钥y=2 mod 19=18。消息m的ELGamal签名为(r,s),其中r=g mod p,s=(h(m)-xr)k mod (p-1) 2．基本要求
考虑p取大素数的情况。 3． 实现提示
① 模n求逆amod n运算。 ② 模n的大数幂乘运算
Schnorr身份识别协议的实现 1．问题描述
Schnorr身份识别协议的身份识别过程提示如下：
(1) P任选一整数r∈[1,q-1],计算X=a mod p 并将X和证书CerP送给V。 (2) V验证CerP中TA的签名。如果成功，则任选一整数e∈[1,2-1],作为V对P
的“询问”，发送给P。
(3) P计算s=r+xe mod q ,s看成是P对V的“应答”，发送给V。 (4) V给证ay mod p =X是否成立，若成立，则V相信对方就是P。
其中p和q都是大素数，且q∣(p-1),a∈Zp,a=1 mod p。x∈Zq为P的私钥，公钥y=a mod p,t为安全参数。 2．基本要求
程序要求界面友好，能模拟P、V两方。 3． 实现提示
-x
*
q
s
e
t
r
-1
k
-1
9
数字签名方案的实现
① r、e的选取要有较好的随机性，可以使用语言提供的随机函数。 ② 模n的大数幂乘运算
安全系统设计与实现 1．问题描述
作为学生，我们关心能构造一个信息系统，在学习了数据库理论之后，我们会把信息系统的模式达到3NF。当然，学了现代密码学之后，我们应该能把信息系统改造为一个安全系统。 2．基本要求
程序要求界面友好。 2． 实现提示
在简单实现一个MIS之后，我们要完成以下功能： ① 数据库的加密存储（Hash,DES等）。 ② 可信机构与证书颁发。 ③ 强身份识别。
④ 密钥协商“加密密钥”。 ⑤ 数字签名。
⑥ 其他你认为重要的一些安全方法。
思考提高
1．利用SPIN等工具进行密码协议分析
SPIN是Bell实验室从1980年起开发的一套模型检测工具，开放其源代码，便于广大科研工作者和学生研究学习。获得了2001年度的ACM的System Software Award。
模型检测安全协议（密码协议、认证协议等）从上世纪90年代起已经成为了信息安全方面一个非常热门的课题。当然SPIN除了验证安全协议外，还可以验证程序及分布式软件系统的正确性。学习SPIN可以从以下三个方面入手：
1．下载和安装SPIN。
2．学习线性时序逻辑（Linear_time temporal logic,LTL）。 3．使用SPIN进行密码协议分析。
2．PGP—Pretty Good Privacy，它是一个基于RSA公匙加密体系的邮件加密软件。可以用它对你的邮件保密以防止非授权者阅读，它还能对你的邮件加上数字签名从而使收信人可以确信邮件是你发来的。它让你可以安全地和你从未见过的人们通讯，事先并不需要任何保密的渠道用来传递密匙。它采用了：审慎的密匙管理，一种RSA和传统加密的杂合算法，用于数字签名的邮件文摘算法，加密前压缩等，还有一个良好的人机工程设计。它的功能强大，有很快的速度。而且它的源代码是免费的。
五、主要参考资料
[1] 章照止主编.现代密码学基础.北京:北京邮电大学出版社,2004.
[2] 张小斌，严望佳编著.计算机网络安全工具.北京:清华大学出版社,1999. [3] http://spinroot.com
[4] Michael Huth and Mark Ryan.面向计算机科学的数理逻辑:系统建模与推理（英文版 第二版）. 北京:机械工业出版社,2005. [5] http://www.chinaitlab.com/www/special/pgp.asp [6] http://www.pgp.com/
六、附件
附件1：《密码学基础课程设计安排表》
附件1：
密码学基础课程设计安排表
1.班级分组及指导老师安排表
2．上机时间
2015年3月9日-2015年3月20日，第1、2周整天1-8节。
3.上机地点：专业实验室
4.学生自己独立完成课程设计任务请指导老师和学生注意把握进度。
11
《现代密码学基础》
课程设计指导书
杨柳 编
湖南科技大学计算机科学与工程学院
2014年12月
一、概述
本课程在简要复习数学基础知识之后，探讨了密码学研究的基本问题：通过不安全的通信媒介如何进行安全通信。也可以理解为关心任何希望限制不诚实者达到目的的问题，把度量和评价一个密码体制（协议）的安全性作为一个重点。就目前来说，密码学的研究领域已从消息加密扩大到了数字签名、消息认证、身份识别、抗欺骗协议等。无疑，在整个教学过程中非常重视密码学的基础，当然包括数学基础。并针对实际的密码体制（协议）强调设计与分析（攻击），对现代密码学的主要研究问题都进行了介绍。
对于密码学这样的课程，同学们一定要从理论、技术、应用三个方面进行学习与思考。密码体制（协议）无疑是我们的学习重点，密码体制（协议）也可以单纯地理解为计算机算法，从而有设计、分析、证明、实现的问题。实现密码体制（协议）就是我们经常讲的八个字：模型、算法、程序、测试。
二、课程设计步骤
课程设计步骤要求如下： 1. 模型
从数学的角度看，解决任何问题都要建立一个数学模型，对于密码学来说更是如此。我们还可以认为，数据结构中的存储结构也是模型。于是这一部分的任务就是建立起问题的逻辑结构和存储结构，为算法设计和编码实现打下基础。 2. 算法
这一部分对同学们的要求是能看懂书上的常用算法，并对其中的参数可以进行调整和设置，能实现和应用它们。 3. 程序
编码实现得到程序。 4. 测试
5. 提交课程设计报告
三、课程设计报告编写要求
课程设计报告开头标明课程设计题目、设计者的班级、姓名、学号和完成日期，内容包括：模型、算法、程序、测试四个部分。
四、设计要求
可以只做第7题，不做第7题的要做第1题-第6题。
五、课程设计题目
大整数运算包的设计与实现 1．问题描述
大整数运算是现代密码学算法实现的基础，重要性不言而喻。大整数我们指的是二进制位512、1024和2048的数，一般的语言不支持。 2．基本要求
以类库头文件的形式实现。 3．实现提示
在选择了大整数的存储结构之后，主要实现以下运算： ① 模加； ② 模减； ③ 模乘； ④ 模整除；
⑤ 模取余。这五种运算模拟手算实现。 ⑥ 幂模：利用“平方-乘法”算法实现。 ⑦ GCD：利用欧几里得算法实现。
⑧ 乘法逆: 利用扩展的欧几里得算法实现。
⑨ 素数判定与生成：概率性素数产生方法产生的数仅仅是伪素数，其缺点在于，
尽管其产生合数的可能性很小，但是这种可能性仍然存在:其优点是产生的伪素数没有规律性，而且产生的速度也比较快。此类方法是生成大素数的主要方法，其中较著名的算法有:Miller Rabin算法、Solovay-Strassen算法等。本文讨论Miller Rabin算法。
Miller Rabin素性测试法是在实际中应用非常广的一种素性测试方案，可以用来判定某随机数是否为素数。其定义如下:
设n>2是一个奇数，设n-1=2m，其中s是非负整数，m>0是奇数，设0
b≡－1(mod n)，
或者存在一个r,0≤r
2^r mm
s
≡－1(modn)
则称n通过以b为基的Miller-Rabin测试。
可以利用Miller-Rabin素性测试算法来随机生成大素数，随即生成一个奇数n>2，随即均匀的选取序列b1,b2...,bk∈{1,2,...,n-1}，对n进行k次Miller-Rabin素性测试，如果每次输出都为“n可能是素数”，则n是合数的概率小于 1/4当k足够大时，1/4是一个十分小的数。
同学们在具体实现时，为了提高速度最好以空间换时间，在主程序运行前先构造一个大素数表。
1．问题描述
MD5以512比特一块的方式处理输入的消息文本，每个块又划分为十六个32比特的子块。算法的输出由四个32比特的块组成，将它们级联成一个128比特的Hash值。
①首先填充消息使填充后的长度恰好为一个比512的倍数小64的数。填充方
k
k
的实现
法是附一个“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保存分析所得的明文。 ② 密文是通过
-1
ek(m)=am+b mod 28得到的，为了解密我们使用
dk(c)=a(c-b)mod 28。这里有一个函数要先实现： int gcd(int n,int m) {
int r,temp; if(n
while(m!=0) {r=n%m; n=m; m=r; } return n; }
③ 有了以上的准备工作，我们就可以编写程序的主要部分了，它是一个多 重循环：
for(a=2;a
{/*求a的乘法逆元p */ for(b=2;b
if ((a*b)%28==1){p=b;break;}; /* 用dk(c)=p(c-b) mod 28 */ for(b=0;b
{对数组C进行处理，输出k=(a,b)和M，M有意义程序结束，分析完成。} };
else continue;
1．问题描述
RSA密码系统可具体描述为：取两个大素数p和q，令n=pq,N=(p-1)(q-1),随机选择整数d,满足gcd(d,N)=1,ed=1 modN。
公开密钥：k1=(n,e) 私有密钥：k2=(p,q,d)
加密算法：对于待加密消息m，其对应的密文为c=E(m)=m(modn) 解密算法：D(c)=c(modn) 2．基本要求
p,q,d,e参数选取合理，程序要求界面友好，自动化程度高。 4． 实现提示
要实现一个真实的RSA密码系统，主要考虑对大整数的处理。P和q是1024位的，n取2048位。
d
e
密码系统的实现
1． 问题描述
为简化问题，我们取p=19,g=2,私钥x=9,则公钥y=2 mod 19=18。消息m的ELGamal签名为(r,s),其中r=g mod p,s=(h(m)-xr)k mod (p-1) 2．基本要求
考虑p取大素数的情况。 3． 实现提示
① 模n求逆amod n运算。 ② 模n的大数幂乘运算
Schnorr身份识别协议的实现 1．问题描述
Schnorr身份识别协议的身份识别过程提示如下：
(1) P任选一整数r∈[1,q-1],计算X=a mod p 并将X和证书CerP送给V。 (2) V验证CerP中TA的签名。如果成功，则任选一整数e∈[1,2-1],作为V对P
的“询问”，发送给P。
(3) P计算s=r+xe mod q ,s看成是P对V的“应答”，发送给V。 (4) V给证ay mod p =X是否成立，若成立，则V相信对方就是P。
其中p和q都是大素数，且q∣(p-1),a∈Zp,a=1 mod p。x∈Zq为P的私钥，公钥y=a mod p,t为安全参数。 2．基本要求
程序要求界面友好，能模拟P、V两方。 3． 实现提示
-x
*
q
s
e
t
r
-1
k
-1
9
数字签名方案的实现
① r、e的选取要有较好的随机性，可以使用语言提供的随机函数。 ② 模n的大数幂乘运算
安全系统设计与实现 1．问题描述
作为学生，我们关心能构造一个信息系统，在学习了数据库理论之后，我们会把信息系统的模式达到3NF。当然，学了现代密码学之后，我们应该能把信息系统改造为一个安全系统。 2．基本要求
程序要求界面友好。 2． 实现提示
在简单实现一个MIS之后，我们要完成以下功能： ① 数据库的加密存储（Hash,DES等）。 ② 可信机构与证书颁发。 ③ 强身份识别。
④ 密钥协商“加密密钥”。 ⑤ 数字签名。
⑥ 其他你认为重要的一些安全方法。
思考提高
1．利用SPIN等工具进行密码协议分析
SPIN是Bell实验室从1980年起开发的一套模型检测工具，开放其源代码，便于广大科研工作者和学生研究学习。获得了2001年度的ACM的System Software Award。
模型检测安全协议（密码协议、认证协议等）从上世纪90年代起已经成为了信息安全方面一个非常热门的课题。当然SPIN除了验证安全协议外，还可以验证程序及分布式软件系统的正确性。学习SPIN可以从以下三个方面入手：
1．下载和安装SPIN。
2．学习线性时序逻辑（Linear_time temporal logic,LTL）。 3．使用SPIN进行密码协议分析。
2．PGP—Pretty Good Privacy，它是一个基于RSA公匙加密体系的邮件加密软件。可以用它对你的邮件保密以防止非授权者阅读，它还能对你的邮件加上数字签名从而使收信人可以确信邮件是你发来的。它让你可以安全地和你从未见过的人们通讯，事先并不需要任何保密的渠道用来传递密匙。它采用了：审慎的密匙管理，一种RSA和传统加密的杂合算法，用于数字签名的邮件文摘算法，加密前压缩等，还有一个良好的人机工程设计。它的功能强大，有很快的速度。而且它的源代码是免费的。
五、主要参考资料
[1] 章照止主编.现代密码学基础.北京:北京邮电大学出版社,2004.
[2] 张小斌，严望佳编著.计算机网络安全工具.北京:清华大学出版社,1999. [3] http://spinroot.com
[4] Michael Huth and Mark Ryan.面向计算机科学的数理逻辑:系统建模与推理（英文版 第二版）. 北京:机械工业出版社,2005. [5] http://www.chinaitlab.com/www/special/pgp.asp [6] http://www.pgp.com/
六、附件
附件1：《密码学基础课程设计安排表》
附件1：
密码学基础课程设计安排表
1.班级分组及指导老师安排表
2．上机时间
2015年3月9日-2015年3月20日，第1、2周整天1-8节。
3.上机地点：专业实验室
4.学生自己独立完成课程设计任务请指导老师和学生注意把握进度。
11