密码学--RSA

一、实验目的

1.随机生成明文和加密密钥

2.利用C语言实现素数选择（素性判断）的算法

3.利用C语言实现快速模幂运算的算法（模重复平方法）

4.利用孙子定理实现解密程序

5.利用C语言实现RSA算法

6.利用RSA算法进行数据加/解密

二、实验内容

1、题目内容描述

①实现快速模幂乘法计算ax mod m；

②实现Euclid算法计算gcd(a，b)；

③随机生成正整数，用Miller_Rabin算法进行素性判断，安全参数t=10，得到通过检验的两个素数p和q，计算出n，φ(n)，dp，dq和inv_p；

④实现扩展Euclid算法，当公钥e = 7时，计算出私钥d；

⑤随机生成明文数字，利用快速模幂乘法，计算出密文，利用孙子定理解密出明文。

2、关键代码的设计、实现与执行

设计思路：

先生成随机生成密钥以时间设置随机数生成器的种子，以确保每次运行程序时生成的随机数序列都是不同的。p大于 100确保p是一个足够大的素数；并调用最大公约数函数：gcd（），检查p-1和e的最大公约数为 1，即为了确保p和e是互质的；再调用primetest()函数，进行素性判断；rand()%Max是为了将随机生成的p，q控制在一定范围内，以免溢出int范围，关键代码如下：（此处只以p为例，在p生成后，以同样的方法生成q，只是换一个字母）

srand(time(NULL));//以时间为种子，以确保每次生成的随机数不同

do

{

if((p>100)&&(gcd(p-1,e)==1)&&(primetest(p,t)==1))//确保p足够大，且与e互质，并调用素性检验的函数，要求p为素数

break;//p满足上述条件则即可跳出循环

p=rand()%Max;//若p未满足上述条件则重新生成

}while(1);//只有在p到达条件成功生成后才会跳出循环

紧接着就是上面提到的计算最大公约数的函数，只要最大公约数为1，则证明两个数互质，关键代码如下：（也就是前面两个实验:仿射密码和希尔密码用到的求最大公约数的函数）

if(a<b)//交换数

{

temp=a;

a=b;

b=temp;

}

while(b!=0)

{

temp=a%b;

a=b;

b=temp;

}

return a;//得到最大公因数

然后是上面提到过的素性检验部分，t是实验题目中给出的安全参数，即实验t次，然后以r/2不断循环，在循环期间s++，r右移，再循环安全参数t次，检测传入的数x是否通过素性检测，这样检测q，p两个数，关键代码如下：

if(!(x&1))//检查 x 是否为偶数（只有偶数与1进行按位与操作结果才为0）。如果是偶数，函数返回 0，表示 x 不是质数

return 0;

while(!(r&1))// r 除以2的余数不为1。这意味着循环会一直执行直到 r 为奇数。

{

s++;

r>>=1;//在循环体内，首先 s 被增加1，然后 r 右移一位（相当于除以2）。这是在寻找 x 的位数。

}

for(i=0;i<t;i++)//安全参数t，则重复执行 t 次

{

a=rand()%(x-2)+2;//在循环体内，生成一个在[2, x-2] 范围内的随机整数并赋值给 a。

if(gcd(2,x)>1)//检查X是否数质数，2太小了，也排除在外

return 0;

int b=quickpower(a,r,x);//调用快速幂运算

if(b==1||b==x-1)//通过检测

continue;

for(j=0;j<s;j++)

{

b=b*b%x;

if(b==x-1)//通过检测

break;

}

if(j==s)//表示X不是质数

return 0;

}

return 1;

在已知当公钥e = 7时，计算出私钥d，上述已经得到了p，q，即可算出dn=（p-1）*（q-1），然后对计算出e模dn的逆元即是私钥d，关键代码如下：

int dn=(p-1)*(q-1);

int d=inverse_a(e,dn);

在加密解密的时候都运用了快速模幂算法，初始值为1，从指数二进制最低位开始，每步都把底数平方，遇到1就乘以底数，但是在快速模幂平方或者×原本的数的时候，由于p，q是两个大质数，所有有溢出风险，即再添加一个快速模乘的函数，代替快速模幂里面的乘法，关键代码如下：

快速模幂部分：

while(b)

{

if(b&1)//检查 b 的最后一位是否为 1；对于每一次循环，我们只对 b 的最后一位为 1 的情况进行处理，相当于每次只处理一个乘法结果。

ans=(ans+res)%c;

res=(res+res)%c;

b>>=1;//右移操作，将 b 的所有位向右移动一；在每次循环中处理的是 b 的下一位。

}

return (int)ans;//函数返回ans，即最终结果

快速模乘部分：

while(b!=0){

if((b&1)!=0)//检查 b 的最后一位是否为 1

    {

ans=quickmultiply(ans,base,c);

}

base=quickmultiply(base,base,c);// base 自乘并对 c 取模

b>>=1;//右移操作，将 b 的所有位向右移动一；在每次循环中处理的是 b 的下一位。

}

return ans;

为了操作方便且不溢出，解密过程还使用了孙子定理加速解密过程，由于p，q是两个大质数，所以它们的欧拉函数就是本身减1，于是用得到的欧拉函数调用快速模幂算法的函数，得到x1和x2，

再代入式子即可得到解密后的明文，关键代码部分如下：

int dp=d%(p-1);

int dq=d%(q-1);

if(dp<0)

dp=dp+p-1;

if(dq<0)

dq=dq+q-1;//求得p，q的欧拉函数

int inv_p=inverse_a(p,q);

int inv_q=(1-p*inv_p)/q;

int c1=c%p;

int c2=c%q;

int x1=quickpower(c1,dp,p);

int x2=quickpower(c2,dq,q);//快速模幂分别求得两个x1，x2

cout<<1;

cout<<"inv_p="<<inv_p<<endl;

cout<<"inv_q="<<inv_q<<endl;

cout<<"x1="<<x1<<endl;

cout<<"x2="<<x2<<endl;

int m=(x1*q*inv_q+x2*p*inv_p)%n;//代入计算

结果截图如下：

1. 实验结果分析

结果截图在上面过程中，可以看到每次生成的p，q都不同，且是大质数，，每次的明文也是随机生成的不同的数，可以看到过程，得到密文cipher，再经过一系列解密后得到解密后的明文，经观察可以看到，解密生成的密文与随机生成的明文是一致的，故可以得到加密解密过程正确。

三、实验思考

1、实验过程总结

相较于仿射密码和希尔密码，rsa密码算法更为复杂，虽然在这个实验中明文是数字而不是字母，需要转换，但是随机生成的p，q需要是大质数，无疑是增加了实验的难度。所以在随机生成了p，q后第一步要解决的难题就是素性检验的问题，根据理论知识，在安全参数为t的情况下，循环执行检查t次，每次随机生成范围内的数，看是否存在除1外的公因数；紧接着就是加密解密过程都涉及的快速模幂运算，将指数转换成二进制形式，从低位开始，不断平方右移，遇到1再乘底数，由于int类型的长度有限，所以在快速模幂运算中间的有两步乘法可能会出现溢出现象，可以将其改为加法，即快速模乘运算；最后的重点就是孙子定理，在解密中运用，加速解密，其中涉及到p，q的欧拉函数，将解密的式子分成两个式子减小运算量，最后再结合在一起，即得到加密过程。在前面两个实验的基础上，完成这个实验会较为轻松一点，无非就是多添了三个部分，但是此实验由于明文也是随机生成的，所以避免了文件操作。

1. 回答实验指导书最后提出的问题

思考题1：

在这个思考题中可以看到其实就是借用了rsa算法中的快速模幂算法，按题目中已给出的n=101*157=15857，e=7，s0=2，于是得到下面的结果：

当然也可以更换题目中给出的初始值，如下：

思考题2：

在这个思考题中可以看到就是没有了解密部分，将铭文空间里的每一个数进行加密计算，看得到的结果是否和明文一致，一致就是不动点，操作结果如下：