密码学与应用课程设计RSA算法加密解密

课 程 设 计 说 明 书课程名称： 密码学与应用 设计题目： RSA算法加密解密 院 部： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级： 指导教师： 2015年 6月目录一、 RSA算法的简介21、 RSA的由来22、 大数分解和素性检测23、 RSA密码体制的建立：24、 RSA算法实例:2二、 设计目的3三、 设计思路3四、 部分代码及功能4 1、candp函数.4 2、fun函数.5 3、prime函数.6 4、 欧拉数方法.6 5、选择加密还是解密.6五、 运行结果7六、总结.8一、 RSA算法的简介1、RSA的由来 RSA是Rivet，Shamir和Adleman于1978年在美国麻省理工学院研制出来的，它是一种比较典型的公开密钥加密算法。2、大数分解和素性检测 将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。 3、RSA密码体制的建立：(1)选择两个不同的大素数p和q；(2)计算乘积n=p*q和(n)=(p-1)(q-1)； (3)选择大于1小于(n)的随机整数e，使得gcd(e,(n)=1；(4)计算d使得de=1mod (n)；(5)对每一个密钥k=(n,p,q,d,e)，定义加密变换为Ek(x)=xemodn，解密变换为Dk(x)=ydmodn，这里x,yZn；(6)以e,n为公开密钥，p,q,d为私有密钥。4、RSA算法实例:下面用两个小素数7和17来建立一个简单的RSA算法：(1)选择两个素数p=7和q=17；(2)计算n=p*q=7*17=119，计算(n)=(p-1)(q-1)=6*16=96；(3)选择一个随机整数e=5，它小于(n)96并且于96互素；(4)求出d，使得de=1mod96且d96，此处求出d=77，因为77* 53854 *961；(5)输入明文M19，计算19模119的5次幂，Me19566 mod 119,传出密文C66；(6)接收密文66，计算66模119的77次幂；Cd=667719mod119得到明文19。二、 设计目的通过完成具有一定难度的题目，使自己能够将课本上的理论知识和具体问题有机地结合起来，锻炼自己分析问题、解决问题的能力，提高编程能力;完成一些需要查阅相关资料才能做的题目，提高自己的自学习能力和创新能力。同时，使自己对密码学以及RSA算法具有了深刻的认识和体会，能够认识到加密解密在当今社会的重要性。三、 设计思路（包括所用的函数） RSA的公钥、私钥的组成，以及加密、解密的公式可见于下表： 主函数实现求n的欧拉数, 由公钥求解私钥, 加密解密选择以及相应的密文明文输出。 candp 实现加密解密时的求幂取余运算 子函数 fun 实现e 与t 的互素判断，以验证e 是否符合要求 prime实现一个素数判断，以验证输入的数是否为素数 四、 部分代码及功能1、candp函数函数candp为数据处理函数，作用为实现幂的取余运算，通过while循环，判断b是不是等于1，%为取余符号。int candp(int a,int b,int c) int z;z=1;b=b+1;while(b!=1)z=z*a;z=z%c;b-;printf(%dn,z);return z;2、fun函数函数fun为实现e 与t 的互素判断，以验证e 是否符合要求int fun(int x,int y) int s;while(y)s=x;x=y;y=s%y;if(x = 1)return 0; /x 与y 互素时返回0elsereturn 1; /x 与y 不互素时返回13、prime函数prime函数为判断数m是不是一个素数，当m为1时，直接结束程序返回0，当m为一个素数时，返回1。n为m的平方根，使用for循环，依次增加i的值，然后相除判断。int prime(int m)int i;int n;if(m=1)return 0;n=(int)sqrt(m);for(i=2;i=n;i+)if(m%i=0)return 0;elsereturn 1; 4、欧拉数方法t=(p-1)*(q-1); 5、选择加密还是解密switch函数，通过判断r的数值是1还是2，来判断选择的是要加密还是解密。switch(r)case 1: printf(请输入明文m: ); /输入要加密的明文数字scanf(%d,&m);c=candp(m,e,n);printf(密文为%dn,c);break;case 2: printf(请输入密文c: ); /输入要解密的密文数字scanf(%d,&c);m=candp(c,d,n);printf(明文为%dn,m);break;五、 运行结果1、当P=43, q=59 时，对124 进行加密，运行结果如下：2、当P=7, q=19 时，对543 进行解密，运行结果如下：六、 总结 从对RSA算法的一无所知到现在运行处理的结果，中间经过查询各种资料，我的努力还是有收获的，运行结果基本上还令人满意。总的来说，这次的课程设计锻炼了我们分析问题、解决问题的能力，有助于提高自己的自学习能力和创新能力。同时在课程设计的过程中，我遇到了很多不懂的知识，但是通过我自己的努力查找资料，上网查阅相关信息，使我的知识面变宽了，所掌握的知识变的更加牢固了。七、 源代码#include #include#include /当用到数学函数时，加上头文件/以下为主函数void main() printf(如果想让程序运行，请输入66，结束请输入88n);int strn;scanf(%d,&strn);while(strn=66)int candp(int a,int b,int c);/candp函数声明int fun(int x,int y);/fun函数声明int prime(int m);/prime函数声明/以下为定义int型的变量int p;int q;int e;int d;int m;int n;int t;int c;int r;int str;int x;/输入框的设计/为了美观，我们可以添加一些*。printf();printf(*程序准备完毕，请按照以下步骤操作*);printf();printf(n);printf(n);printf(n);printf( );printf(请输入两个素数p,q，并以逗号隔开: n);printf( );printf(n);printf(n);printf( );printf();printf(*按照操作输入p和q*);printf();printf(n);/输入p,q并且接收scanf(%d,%d,&p,&q);for(;p0,q0;)/for循环判断p和q是否同时为素数if( (prime(p) & prime(q) ) /prime函数的调用，判断p,q是否为素数。break;elseprintf(输入有误，请重新输入：);scanf(%d,%d,&p,&q);n=p*q;printf(计算得n为%dn,n);/输出p和q的成绩nprintf(n);printf(n);t=(p-1)*(q-1);/求n 的欧拉数printf(计算得t为%dn,t);printf(n);printf(n);printf(请输入一个与t互素的数，即公钥e: );scanf(%d,&e);for(;e1,et;)if(e=t|fun(e,t)/判断e是否符合条件printf(n);printf(n);printf(e不合要求，请重新输入: ); /et 或e 与t /不互素时，重新输入scanf(%d,&e);elsebreak;d=1;while(e*d)%t)!=1)d+; /由公钥e 求出私钥dprintf(经计算d 为%dn,d); printf(n);printf(n);for(;)printf(加密请输入1n); printf(n);printf(n);printf(解密请输入2n);printf(n);printf(n);printf(结束请输入88n);/加密或解密选择scanf(%d,&r);if(r=1)printf(请输入明文m: ); scanf(%d,&m);printf(n);printf(n);/candp数据处理函数，实现幂的取余运算c=candp(m,e,n);/调用candp方法printf(n);printf(n);printf(密文为%dn,c);continue;elseif(r=2) printf(请输入密文c: ); scanf(%d,&c);printf(n);printf(n);m=candp(c,d,n);/调用candp方法printf(n);printf(n);printf(明文为%dn,m);continue;elsestrn=88;break;/主函数结束/数据处理函数，实现幂的取余运算int candp(int a,int b,int c) int z;z=1;b=b+1;while(b!=1)z=z*a;z=z%c;b-;printf(n);/printf(n);printf(%dn,z);return z;/公钥e 与t 的互素判断int fun(int x,int y) int s;while(y)s=x;x=y;y=s%y;if(x = 1)return 0; /x 与y 互素时返回0elsereturn 1; /x 与y 不互素时返回1/判断一个数是否为素数int prime(int m)int i;int n;if(m=1)return 0;n=(int)sqrt(m);/sqrt函数为求平方根/for循环判断是不是素数for(i=2;i n) return 1;19