RSA加密解密的设计及其实现.docx

上海电力学院

《应用密码学》课程设计

题　　目：　 RSA加密解密设计和实现 　

院　　系：　 计算机科学和技术学院 　
专业年级：　 级
学生姓名：　 李正熹　　　学号：　 3273 　
指导老师：　　　 　　 　田秀霞　 　　

1月 8日
目录

目录
1. 设计要求
2. 开发环境和工具
3. 设计原理（算法工作原理）
4. 系统功效描述和软件模块划分
5. 设计关键代码
6. 参考文件
7. 设计结果及验证
8. 软件使用说明
9. 设计体会
附录

1. 设计要求

1 随机搜索大素数，随机生成公钥和私钥
2 用公钥对任意长度明文加密
3 用私钥对密文解密
4 界面简练、交互操作性强

2. 开发环境和工具

Windows XP操作系统
Microsoft Visual C++ 6.0

1. 创建rsa工程

2. 在rsa工程中创建3273 李正熹cpp文件

3. 设计原理

RSA算法介绍
公开密码算法和其它密码学完全不一样，它是基于数学函数而不是基于替换或置换。和使用一个密钥对称算法不一样，公开密钥算法是非对称，而且它使用是两个密钥，包含用于加密公钥和用于解密私钥。公开密钥算法有RSA、Elgamal等。
RSA公钥密码算法是由美国麻省理工学院(MIT)Rivest，Shamir和Adleman在1978年提出来，并以她们名字有字母命名。RSA是第一个安全、实用公钥密码算法，已经成为公钥密码国际标准，是现在应用广泛公钥密码体制。
RSA基础是数论Euler定理，其安全性基于二大整数因子分解问题困难性，公私钥是一对大素数函数。而且该算法已经经受住了多年深入密码分析，即使密码分析者既不能证实也不能否定RSA安全性，但这不恰恰说明该算法有其一定可信度。

4. 系统功效描述和软件模块划分

功效：
1. 进行加密

加密
第一步，随机两个素数p和q，并求出n = p*q，然后再求出n欧拉函数值phi。
第二步，在[e，phi]中选出一个和phi互素整数e，并依据e*d ≡1（mod phi），求出e乘法逆元。至此我们已经得到了公开密钥{e，n}和秘密密钥{d，n}。
第三步，让用户输入要进行加密小于n一组正整数（个数不超出MAXLENGTH），输入以-1为结束标志，实际个数存入size中，正整数以clear[MAXLENGTH]保留。
第四步，对第三步所得明文clear[MAXLENGTH]进行加密。遍历clear[size]，对每一个整数用以下算法进行加密,并将加密后密文保留在Ciphertext[MAXLENGTH]中。
第五步，输出密文Ciphertext[MAXLENGTH]

2. 进行解密

第一步，输入加密后密文Ciphertext1[MAXLENGTH]，输入以-1为结束标志
第二步，输入解密密钥[d,phi],对密文进行解密，结果保留在DecryptionText[MAXLENGTH]中。
第三步，输出解密后明文DecryptionText[MAXLENGTH]

生成随机素数： 先生成一个随机数 然后判定它是否为素数 从而输出
unsigned long foo() //生成随机数
int panduan(unsigned long b) //判定是否为素数
unsigned long tiqu(unsigned long &p,unsigned long &q) //从随机素数中选择两个为p和q

求e时需要用到e和phi互逆 所以在随机产生e同时需要作互逆判定 若互逆则输出随机e 不然重新生成e
int gcd(int x,int y) //判定两数是否为互素

在p、q、e全部准备就绪时候就能够进行加解密运算 因为考虑到溢出 所以3个一组进行加解密
void Encryption() //加密算法
void Decryption() //解密算法

5. 设计关键代码

unsigned long foo()
{
unsigned long random = 0;
srand((int)time(0));
random = rand() % 300;
return random;
}
srand函数是随机数发生器初始化函数
需要提供一个种子 这里使用time来获取系统目前时间
rand() % 300是随机0-299整数

//以下为加密算法
void Encryption()
{//加密算法
cout << "随机生成两个较大素数："<<endl ;
tiqu(p,q);
n = p * q;//求解 n，
phi = (p - 1) * ( q - 1 );//求解 n 欧拉函数值
cout << " n = " << n << ", phi = " << phi << endl;
cout << " 请从[0，" << phi - 1 << "]中选择一个和 " << phi << " 随机生成互素数 e：";
while(1)
{
e=foo();
if(gcd(e,phi)==1&&e>=100&&e<=300&&e!=q&&e!=p)
break;
}
cout<<e<<endl;
float d0;
for( int i = 1; ; i++)
{///求解乘法逆元 e * d ≡ 1 (mod phi)
d0 = (float)(phi*i+1) / e;
if( d0 - (int)d0 == 0 )
break;
}
d = (int)d0;
cout << endl;
cout << " e = " << e << ", d = " << d << endl;
cout << " 公开密钥 Pk = {e,n} = {" << e << "," << n << "}" << endl;
cout << " 秘密密钥 Sk = {d,n} = {" << d << "," << n << "}" <<"统计私钥"<< endl;
cout << endl;

cout << " 请3位一组输入要加密正整数（以-1结束）：" << endl;
cout << " 加密前明文为：";
for( i = 0; i < MAXLENGTH; i++)
Ciphertext[i] = 1;
int count;
for(int j = 0; j<MAXLENGTH; j++)
{
cin >> clear[j];
if( clear[j] == -1 )
break;
count = e;
while(count > 0)
{//对明文进行加密 Ciphertext =（clear）^ e mod n
Ciphertext[j] = (Ciphertext[j] * clear[j]) % n;
//加密算法
count-- ;
}
}
cout << " 密文为：" ;
size = j;//实际密文长度
for(int k=0; k<j; k ++)
cout << Ciphertext[k] << " ";
cout << endl ;
}

//以下为解密算法
void Decryption()
{//解密算法
int pp,kk;
for(int i = 0; i < MAXLENGTH; i++)
DecryptionText[i] = 1;
int count;
cout<<"请输入要解密密文（以-1结束）："<<endl;
for(int u = 0; u<MAXLENGTH; u++)
{
cin >> Ciphertext1[u];
if( Ciphertext1[u] == -1 )
break;
}
cout<<"输入密钥解密(d,n)"<<endl;
cin>>pp>>kk;
for(int j = 0; j < size; j++)
{
count = pp;
while(count > 0)
{//对密文进行解密 DecryptionText =（Ciphertext）^ d (mod n)
DecryptionText[j] = ((DecryptionText[j] * Ciphertext1[j]) %kk);
count-- ;
}
}
cout << " 解密后明文为：";
for( int k = 0; k < size; k ++)
cout << DecryptionText[k] << " ";
cout << endl ;
}

6. 参考文件

[1]赛迪网．RSA :云安全需紧迫处理安全隐患.旧金山：赛迪网，.
[2]赛迪网．RSA主席认为云安全成安全领域趋势.旧金山：赛迪网，.
[3]魏晨. 安全风向标：品味RSA 信息安全大会.旧金山：赛迪网，.
[4]四夕．新安全威胁而前需要新安全架构.旧金山：赛迪网，.
[5]王茜．倪建伟，一个基于RSA加密算法. 重庆大学学报，, 28 (1)：68-72.
[6]周升力．RSA密码算法研究和改善实现．现代计算机，：51-53．
[7]管占明. 邓亚娟．RSA加密算法研究及应用. 科技广场，：98- 99.
[8]胡向东，魏琴芳等．应用密码学．北京市：电子工业出版社，: 114-119．
[9]卢开澄．计算机密码学.北京市：清华大学出版社，: 73-77
[10]史予荣．软件加密技术从入门到精通，北京市：清华大学出版社．: 74-77.

7. 设计结果及验证
进行加密
得到公钥（113，11021）和私钥（2105，11021）
加密明文123 587 114 56 18 9
得到密文1453 385 7882 6329 4873 2744
输入密文 解密
得到先前加密明文123 587 114 56 18 9

8. 软件使用说明
1. 选择RSA加解密系统功效
1为加密 2为解密 0为退出 输入其它错误重新输入

2.输入1 进行加密过程

输入需要加密明文 3个一组 空格空开 -1结束

生成密文 而且返回主界面

2. 输入2进行解密

输入加密好密文 -1结束

输入密钥 d n

解密得到加密前明文
解密成功 返回主界面

9.设计体会

RSA课程设计中，包含了加解密过程，刚开始对做设计时候，认为对于RSA加解密只要套用公式就能够很方便地进行，实现并不是很困难。不过在真正实现时候还是碰到了不少问题，在随机产生素数时候，不一样实现方法会含有不一样复杂度，从而使得时间效率也有所不一样，若直接生成素数，系统需要很长一段时间来生成，而随机生成一个数后再判定是否为素数能够降低很多时间，效率也就提升了。
在加解密时候，起初使用是int型整形变量，不过发觉int型只有4位长度8字节，所以在计算时，数字一大就会产生溢出，所以使用了数组进行了加解密。而在大素数生成时，能够生成很大素数，不过在加密时，因为程序效率过于低以至于一天全部没有算出结果，所以在实现时使用了可进行运算和实现较大素数而并不是大素数。随机大素数进行RSA加解密程序还需要时间进行深入改善。需要深入调用大整数加减乘除算法，素数明文密文密钥公钥全部要使用数组才能加以实现，在此临时保留这个程序，将用更充足时间来实现。
总结这次课程设计，不可否定又是一次对于自己编程能力提升和团体合作加深，自己动手编程真是一个成就感，然而在这以外，我还发觉了自己会有部分突发奇想思绪，会发觉和挖掘实现试验时一些过程优化，而这些思绪又能够帮助自己来完成程序。这次课程设计不足是还没有完全完成课程设计所需要任务要求，写程序还是略微有点简单化了，可能自己能力还是有限，在静候时间里还需要愈加磨练才行。

附录

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXLENGTH 500 //明文最大长度，即所许可最大整数个数
int size = 0;//保留要进行加密正整数个数
unsigned long p, q; //两个大素数
int n, phi; //n = p * q，phi = (p-1) * (q-1) 是n欧拉函数值
int e; //{e, n}为公开密钥
int d; //{d, n}为秘密密钥
long clear[MAXLENGTH], Ciphertext[MAXLENGTH],Ciphertext1[MAXLENGTH];//分别用于存放加//密前明//文和加密后密文
long DecryptionText[MAXLENGTH];//存放解密后明文
////////////////////////////////////////////////////////////
unsigned long foo()
{
unsigned long random = 0;
srand((int)time(0));
random = rand() % 300;
return random;
}
int panduan(unsigned long b)
{
int flag=1;
if(flag)
{
for(unsigned long j=2;j<=sqrt(b);j++)
{
if(b%j==0)
{
flag=0;
//cout<<b<<"bu是素数!"<<endl;
}
}
}
if(flag)
{
return 1;
}
else return 0;
}
unsigned long tiqu(unsigned long &p,unsigned long &q)
{
label:
while(1)
{
p=foo();
if(panduan(p)&&p>100&&p<300)
{
//cout<<"p="<<p<<'\t';
break;
}
}
while(1)
{
q=foo();
if(panduan(q)&&q>100&&q<300)
{
//cout<<"q="<<q<<'\t';
break;
}
}
if(p!=q)
{
cout<<"p="<<p<<endl;
cout<<"q="<<q<<endl;
}
else goto label;
return 0;
}
int gcd(int x,int y)
{
int t;
while (y)
{
t=x;
x=y;
y=t%y;
}
return x;
}
//以下为加密算法
void Encryption()
{//加密算法
cout << "随机生成两个较大素数："<<endl ;
tiqu(p,q);
n = p * q;//求解 n，
phi = (p - 1) * ( q - 1 );//求解 n 欧拉函数值
cout << " n = " << n << ", phi = " << phi << endl;
cout << " 请从[0，" << phi - 1 << "]中选择一个和 " << phi << " 随机生成互素数 e：";
while(1)
{
e=foo();
if(gcd(e,phi)==1&&e>=100&&e<=300&&e!=q&&e!=p)
break;
}
cout<<e<<endl;
float d0;
for( int i = 1; ; i++)
{///求解乘法逆元 e * d ≡ 1 (mod phi)
d0 = (float)(phi*i+1) / e;
if( d0 - (int)d0 == 0 )
break;
}
d = (int)d0;
cout << endl;
cout << " e = " << e << ", d = " << d << endl;
cout << " 公开密钥 Pk = {e,n} = {" << e << "," << n << "}" << endl;
cout << " 秘密密钥 Sk = {d,n} = {" << d << "," << n << "}" <<"统计私钥"<< endl;
cout << endl;

cout << " 请3位一组输入要加密正整数（以-1结束）：" << endl;
cout << " 加密前明文为：";
for( i = 0; i < MAXLENGTH; i++)
Ciphertext[i] = 1;
int count;
for(int j = 0; j<MAXLENGTH; j++)
{
cin >> clear[j];
if( clear[j] == -1 )
break;
count = e;
while(count > 0)
{//对明文进行加密 Ciphertext =（clear）^ e mod n
Ciphertext[j] = (Ciphertext[j] * clear[j]) % n;
//加密算法
count-- ;
}
}
cout << " 密文为：" ;
size = j;//实际密文长度
for(int k=0; k<j; k ++)
cout << Ciphertext[k] << " ";
cout << endl ;
}
//////////////////////////////////////////////////////////////
//以下为解密算法
void Decryption()
{//解密算法
int pp,kk;
for(int i = 0; i < MAXLENGTH; i++)
DecryptionText[i] = 1;
int count;
cout<<"请输入要解密密文（以-1结束）："<<endl;
for(int u = 0; u<MAXLENGTH; u++)
{
cin >> Ciphertext1[u];
if( Ciphertext1[u] == -1 )
break;
}
cout<<"输入密钥解密(d,n)"<<endl;
cin>>pp>>kk;
for(int j = 0; j < size; j++)
{
count = pp;
while(count > 0)
{//对密文进行解密 DecryptionText =（Ciphertext）^ d (mod n)
DecryptionText[j] = ((DecryptionText[j] * Ciphertext1[j]) %kk);
count-- ;
}
}
cout << " 解密后明文为：";
for( int k = 0; k < size; k ++)
cout << DecryptionText[k] << " ";
cout << endl ;
}
void main()
{
int sign=1;
int chioce=0;
while(sign==1)
{
cout<<"——————————————————"<<endl;
cout<<" RSA加解密系统 "<<endl;
cout<<" 由 李正熹 李鑫 共同完成 "<<endl;
cout<<" 1.进行加密 "<<endl;
cout<<" 2.进行解密 "<<endl;
cout<<" 0.退出系统 "<<endl;
cout<<"——————————————————"<<endl;
cout<<"请输入!"<<endl;
int choice;
cin>>chioce;
switch(chioce)
{
case 1:
Encryption();
break;
case 2:
Decryption();
break;
case 0:
sign=0;
break;
default:
cout<<"输犯错误重新输入"<<endl;
}
}
}