密码学实验RSA.docx

1、密码学实验RSA密码学实验RSA公钥密码体制实验姓名： 班级：学号：教师： 助教： 1. RSA算法参数实验（注：表格内容以截图形式给出，共测4组数据！）2. 各功能函数介绍与描述（1） ext_euclid函数介绍：A. 编程思想介绍：首先，我们在已知a,b的情况下需要求得最大公约数即gcd(a,b),因此，在编写这个函数之前首先完成功能函数int gcd(int a,int b)的实现，用于求找最大公约数；其次，利用扩展欧几里得算法由a,b,gcd(a,b)反解出x,y使得a*x+b*y=gcd(a,b)；B. 编程过程：事实上，求找x,y与gcd(a,b)没有必要联系，涵盖gcd(a,b

2、)函数是为了返回的内容更全面，介绍如下：先简单介绍gcd函数实现public static int gcd(int a,int b) int x=a,y=b; /采用辗转相除法 int r=1; /这里赋1没有太大意义（语法问题） while(r!=0) /显然，这是辗转相除结束的标志判断 r=x%y; /相除并取余数 x=y; /下一轮中，被除数是上一轮的除数 y=r; /下一轮中，除数是上一次的余数return x; /辗转相除结束后获得最大公约数接着是重点ext_euclid函数的实现public static int ext_euclid(int a,int b)/*入口参数即a,b，

3、返回一个数组（含三个元素）:第一个是最大公约数，第二个是x,第三个是y*/*这里的算法思想可以参见中文教材P81扩展Euclid算法的表格*/ int a0=a,b0=b; /参数传递 int xx=1,yy=0,r; /xx,yy为第一次逆运算赋初值 r=xx*a0+yy*b0; /由扩展算法d=rn=axn+byn决定 int x0=0,y0=1,q,v; int k;while(r!=0) /*这里r=0和原始Euclid算法中条件判断相对应*/ k=x0*a0+y0*b0; q=(xx*a0+yy*b0)/k; /取商舍余，int类型有此功能 v=x0; /*注：这里是保护x0值，因为

4、接下来变量要赋新值*/ x0=xx-q*x0; /这里就是求最大公约数算法的逆过程 xx=v; v=y0;/*注：这里是保护y0值，因为接下来变量要赋新值*/y0=yy-q*y0; yy=v; r=x0*a0+y0*b0; int result=new int3; result0=gcd(a,b);result1=xx;result2=yy; return result; /返回我们所期望的数组（2） modular_exponentitation函数介绍：A. 编程思想介绍：一开始，我认为指数模运算并不需要太多算法设计，但是如果是“老实地”使用循环语句“累乘”最后再来模运算，很显然，超过in

5、t的最大范围的情况是极易出现的。后来，想到每次累乘后都取模，而不是最后再取模，但是如果指数很大（比如10244092），虽然计算可行但是比较耗时和消耗系统资源，于是参看了书上的算法设计（中文版见P201）我是参看了表9.4得到了启发，其实就是把指数转成2进制来做！B. 编程过程： public static int modular_exponentitation(int a,int b,int n) String B=Integer.toBinaryString(b); /*java中有直接把任意整数（还可以指定进制）转成二进制字符串，这也是我喜欢用java的原因，库函数功能强大！*/ cha

6、r bi=B.toCharArray(); /字符串转字符数组，便于对每一位字符操作 int result=1;/*算法思想很简单，对于指数的对应的二进制位 bi ，如果为0，d(算法中为result)累乘 取模；如果为1，乘a(底数)并取模，整个运算由二进制数最高位到最低位进行*/ for(int i=0;ibi.length;i+) result=(result*result)%n; if(bii=1) result=(result*a)%n; return result;（3） 欧拉函数(n)函数Euler介绍：A. 编程思想介绍：这里我没有用更节省资源的算法，我单纯利用了定义了做，所谓

7、定义就是，(n)便是1到n-1内与n互素的整数个数，所以我直接遍历1到n-1并判断互素否（很简单，就用刚才的gcd函数就能办到）并计数即可。当然，这不是最简单最省资源的做法，它很依赖于计算机CPU的处理速度，不过，就目前计算机而言，n取10000000计算时间也不会超过10秒，不过n很大时，这种算法就比较耗时了！B. 编程过程：public static int Euler(int n) if(n=1) return 1; /欧拉函数指定(1)=1 else int count=0; for(int i=1;in;i+) if(gcd(i,n)=1) count+; /如果互素则计数+1 return count; 3. 功能函数测试数据结果截图（部分）