实验4 非对称密码算法RSA
一、 实验目的
通过实际编程了解非对称密码算法RSA的加密和解密过程，加深对非对称密码算法的认识。
二、 实验原理
1、算法原理
步骤如下（这里设B为是实现者）
（1）B寻找出两个大素数p和q。
（2）B计算出n=p*q和
（n）=）（p-1）*（q-1）。
（3）B选择一个随机数e（0<e<(n)）,满足（e,(n))=1 (即e与欧拉函数互素（n）)。
（4）B使用欧几里得算法计算e的模余（n）的乘法逆元素d。
（5）B在目录中公开n和e作为他的公开密钥，保密p、q和d。
加密时，对每一明文m计算密文
cΞme（modn）
解密时，对每一密文c计算明文
mΞcd（modn）
三、 实验环境
运行Windows或者Linux操作系统的PC机，具有gcc（Linux）、VC（Windows）等C语言编译环境。
四、 实验内容
1、为了加深对
算法的了解，根据输入的参数p，q，M，手工计算公私钥，并对明文进行加密，然后对密文进行解密。
2、编写程序，加密一段文字，了解算法原理。尝试加密一大段文字，记录程序的运行时间。使用DES算法加密相同的文字，比较两种算法加密的速度。
3、编写一个程序，随机选择3个 较大的数
，计算
，记录 程序运行时间。
查阅资料给出简单说明大数在计算机上是如何表示，如何进行运算。
4、查阅资料，找出目前实际可行的素数判定法则，并比较各自的优缺点。
五、实验步骤
1、主要函数说明
（1）判断一个数是否为素数函数
bool prime(int n)
{
int m=sqrt(n);
for(int i=2;i<m;i++)
{
if(n%i==0)
break;
}
if(i>=m)
return 1;
else return 0;
}
（2）模幂算法 (这里以明文m为一个为例)
①令f=1；
②用for循环遍历从i=1到i=b，令f=(f*a)%n
③输出f，f的值即为模幂的结果。
int multiplication(int a,int b,int n)
{
int f=1;
for(int i=1;i<=b;i++)
{
f=(f*a)%n;
}
return f;
}
（3）扩展欧几里得算法
由扩展欧几里得算法可以计算整数s和t ，使得s*e+t*N=（e,N）=1,则e的乘法逆元等价于s mod N。
①定义变量 x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
②令 x1 = y2 = 1; x2 = y1 = 0;
③计算q = x3/y3; t1 = x1 - q*y1;
t2 = x2 - q*y2; t3 = x3 - q*y3;
④ x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;
⑤当 y3 =1时，*result = y2; result 的结果即为所求乘法逆元；如果y3 ！=1，则返回顺序执行③、④步直到满足 y3 =1
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
if(f>=d)
{
x3=f;
y3=d;
}
else
{
x3=d;
y3=f;
}
while( 1 )
{
if ( y3 == 1 )
{
*result = y2; /* 两个数互素则resutl为其乘法逆元，此时返回值为1 */
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
（4）主函数
①输入两个数字判断是否为素数，当不为素数时重新输入。如输入 17 11
②输入e，得到公钥。如输入e为7
③调用ExtendedEuclid(e,N,&d)函数，得到d，和私钥。如d=23
④输入明文长度。如输入 5 如输入明文为 56 88 78 12 23
⑤开始加密，调用加密函数 Encryption()。 则输入密文为 78 11 56 177 133
⑥开始解密，调用解密函数 Decipher()。 则解密后明文为 56 88 78 12 23
2、打开VC++，编写程序如下：
#include<iostream.h>
#include<math.h>
int p,q,n,e,d,N,m1[100],m2[100],len;
//判断一个数是否为素数，为素数返回1，否则返回0
bool prime(int n)
{
int m=sqrt(n);
for(int i=2;i<m;i++)
{
if(n%i==0)
break;
}
if(i>=m)
return 1;
else return 0;
}
//扩展欧几里得算法求乘法逆元,两数互素返回1
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
if(f>=d)
{
x3=f;
y3=d;
}
else
{
x3=d;
y3=f;
}
while( 1 )
{
if ( y3 == 1 )
{
*result = y2; /* 两个数互素则resutl为其乘法逆元，此时返回值为1 */
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
//将十进制数据转化为二进制数组
void to_bit(int b,int bit[32])
{
int n=0;
while(b>0)
{
bit[n]=b%2;
n++;
b/=2;
}
}
//模幂算法
int multiplication(int a,int b,int n)
{
int f=1;
for(int i=1;i<=b;i++)
{
f=(f*a)%n;
}
return f;
}
//加密函数
void Encryption()
{
cout<<"******************开始加密*****************"<<endl;
int i;
cout<<"请输入明文：";
for(i=0;i<len;i++)
cin>>m1[i];
for(i=0;i<len;i++)
m2[i]=multiplication(m1[i],e,n);
cout<<"加密后的密文为：";
for(i=0;i<len;i++)
cout<<m2[i]<<" ";
cout<<endl;
}
//解密函数
void Decipher()
{
int i;
cout<<"*************开始解密*************"<<endl;
for(i=0;i<len;i++)
m2[i]=multiplication(m2[i],d,n);
cout<<"解密后的明文为：";
for(i=0;i<len;i++)
cout<<m2[i]<<" ";
cout<<endl;
}
void main()
{
cout<<"输入两个素数p和q:\n";
while(1)
{
cin>>p;
if(prime(p))
{
cout<<p<<"是素数"<<endl;
break;
}
else
{
cout<<p<<"不是素数"<<endl;
continue;
}
}
while(1)
{
cin>>q;
if(prime(q))
{
cout<<q<<"是素数"<<endl;
break;
}
else
{
cout<<q<<"不是素数"<<endl;
continue;
}
}
cout<<"两个素数为："<<p<<","<<q<<endl;
n=p*q;
N=(p-1)*(q-1);
for(int i=2;i<N;i++)
{
if(N%i==0)
{
cout<<i<<" ";
}
}
cout<<endl;
cout<<"请输入一个随机数，该数不等于上面的任何一个数！"<<endl;
cin>>e;
cout<<"公钥为<"<<e<<","<<n<<">"<<endl;
if(ExtendedEuclid(e,N,&d))
cout<<e<<"的乘法逆元是："<<d<<endl;
cout<<"私钥为<"<<d<<","<<n<<">"<<endl;
cout<<"请输入明文长度: ";
cin>>len;
Encryption();
Decipher();
}
调试程序，程序运行如下：
六、实验心得和总结
我是这次试验主要负责人， 因为实验要分组做，每个人都要负责一个项目，在我们组前两次实验中，我主要负责编写代码，像写报告、做PPT我几乎没有参与。但这次不一样了，所以的工作自己都要操起心来，比同组的同学多做一些工作，多分担一些，但是组员也很给力，实验的时候给了我很多建议与指导，制作PPT时给了我很多建议和帮助，有了团队精神所以效率提高了很多。所以这次试验下来感觉自己比以前做实验多学了好多东西，因为什么都要动手做，不懂得东西要查询清楚。
我感觉做实验对学生真正掌握知识很重要。上课的时候只是听老师讲RSA算法顶多就是学会理论知识，而真正实践动手做的时候就会发现自己漏洞百出，因为考虑问题不周全，编写代码的时候总是出错，编写的不完善，算法的功能没有全部体现，最后又翻看了课本、大一的时候学的C++课本、大二学的密码学基础课本和信息安全概论课本。巩固了一些已经忘记了的基础知识，有不太理解的算法实现方法就通过上网查询以及与同学讨论来解决。这次写代码是我参与编写过的比较长的代码，RSA算法的算法原理我理解的比较清楚，所以对算法如何实现有一定的认识，编写起来也比较轻松一点。RSA算法用到了数论的知识，这次实验对我来说最难理解的就是扩展欧几里得算法，虽然在大二时学过了理论但实际编写还是有点难度的，通过查阅书籍及网上搜寻资料最终写出来扩展欧几里得算法实现函数。实在不容易啊。。。经过这次试验，我认识到了我编写代码的能力确实需要提升，需要平时更多的努力，相信以后在与组员以及其他同学的合作下，我能够学到更多知识。
3、打开VC++，编写程序如下：（此程序错误，因为数值过大产生溢出，请改之）
#include<iostream.h>
#include <ctime>
#include<cstdlib>
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include <math.h>
//using namespace std;
int main(){
clock_t start,end;
long times;
long x,e,n;
cout<<"随机产生3个大数:"<<endl;
//x=1000*(rand()%11)+100*(rand()%11)+10*(rand()%11)+rand()%11;
x=1000000*(rand()%11)+100000*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+
100*(rand()%11)+10*(rand()%11)+rand()%11;
e=1000000*(rand()%11)+100000*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+
100*(rand()%11)+10*(rand()%11)+rand()%11;
n=1000000*(rand()%11)+100000*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+
100*(rand()%11)+10*(rand()%11)+rand()%11;
cout<<"x="<<x<<" e="<<e<<" n="<<n<<endl;
start=clock();
cout<<pow(x,e)<<endl;
long answer=(int)pow(x,e)%n; //指数运算
end=clock();
times=1000*(end-start);
cout<<"花费的时间为:"<<times<<endl;
return 0;
}
调试运行如下：
计算机上大数表示方法：
将大数看作一个n进制数组,对于目前的32位系统而言,n可以取值为2的32次方,即0x10000000,假如将一个1024位的大数转化成0x10000000进制,它就变成了32位,而每一位的取值范围就不是0-1或0-9,而是0-0xfffffff.我们正好可以用一个无符号长整数来表示这一数值.所以1024位的大整数就是一个有32个元素的unsigned long数组.而且0x10000000进制的数组排列与2进制流对于计算机来说,实际上是一回事,但是我们完全可以针对unsighed long数组进行”竖式计算”,而循环规模被降低到了32次之内,并且算法很容易理解.
4、素性测试方法：
所谓素数，是指除了能被1和它本身整除而不能被其他任何数整除的数。据此，只需用2到N-1去除N，如果都除不尽，则为素数
（1）flag=1,i=2
(2)If n mod i=0 then flag=1 else i=i+1
(3)If flag=0 and i<n-1 then(2) else (4)
(4)If flag=0 then write yes else no
在最坏的情况下，即N为素数，算法需要执行N-2次，时间复杂性太大。
只需用2到根下N去除N，即可，于是上述算法改为
（3）If flag=0 and i<=int(根N) then(2) else (4)
虽然快了不小，但有重复计算，如果用2去除N时若不尽，则用2的倍数去除N也除不尽，由此得
(1)for(i=2;int(根N);i++) mark[i]=0;//mark是标记其初值为0，只要它的因子除不尽其值变为1
(2)i=2,flag=0
(3)while(flag=0 and i<int(根N)){
If mark[i]=0
Then{
If n mod i=0
Then flag=1
S=i+i
While s<int(根N){
Mark[s]=1
S=s+i
}
}
I=i+1
}
(4)if flag=0 then yes else no