密码学实验RSA文档格式.docx
《密码学实验RSA文档格式.docx》由会员分享，可在线阅读，更多相关《密码学实验RSA文档格式.docx（9页珍藏版）》请在冰点文库上搜索。
（注：
表格内容以截图形式给出，共测4组数据！
）
2.各功能函数介绍与描述
（1）ext_euclid函数介绍：
A.编程思想介绍：
首先，我们在已知a,b的情况下需要求得最大公约数即gcd（a,b）,因此，在编写这个函数之前首先完成功能函数intgcd（inta,intb）的实现，用于求找最大公约数；
其次，利用扩展欧几里得算法由a,b,gcd（a,b）反解出x,y使得a*x+b*y=gcd（a,b）；
B.编程过程：
事实上，求找x,y与gcd（a,b）没有必要联系，涵盖gcd（a,b）函数是为了返回的内容更全面，介绍如下：
先简单介绍gcd函数实现——
publicstaticintgcd（inta,intb）{
intx=a,y=b;
//采用辗转相除法
intr=1;
//这里赋1没有太大意义（语法问题）
while（r!
=0）{//显然，这是辗转相除结束的标志判断
r=x%y;
//相除并取余数
x=y;
//下一轮中，被除数是上一轮的除数
y=r;
}//下一轮中，除数是上一次的余数
returnx;
//辗转相除结束后获得最大公约数
}
接着是重点——ext_euclid函数的实现
publicstaticint[]ext_euclid（inta,intb）{
/*入口参数即a,b，返回一个数组（含三个元素）:
第一个是最大公约数，第二个是x,第三个是y*/
/*这里的算法思想可以参见中文教材P81扩展Euclid算法的表格*/
inta0=a,b0=b;
//参数传递
intxx=1,yy=0,r;
//xx,yy为第一次逆运算赋初值
r=xx*a0+yy*b0;
//由扩展算法d=rn=axn+byn决定
intx0=0,y0=1,q,v;
intk;
while（r!
=0）{
/*这里r=0和原始Euclid算法中条件判断相对应*/
k=x0*a0+y0*b0;
q=（xx*a0+yy*b0）/k;
//取商舍余，int类型有此功能
v=x0;
/*注：
这里是保护x0值，因为接下来变量要赋新值*/
x0=xx-q*x0;
//这里就是求最大公约数算法的逆过程
xx=v;
v=y0;
这里是保护y0值，因为接下来变量要赋新值*/
y0=yy-q*y0;
yy=v;
r=x0*a0+y0*b0;
}
int[]result=newint[3];
result[0]=gcd（a,b）;
result[1]=xx;
result[2]=yy;
returnresult;
//返回我们所期望的数组
（2）modular_exponentitation函数介绍：
一开始，我认为指数模运算并不需要太多算法设计，但是如果是“老实地”使用循环语句“累乘”最后再来模运算，很显然，超过int的最大范围的情况是极易出现的。
后来，想到每次累乘后都取模，而不是最后再取模，但是如果指数很大（比如10244092），虽然计算可行但是比较耗时和消耗系统资源，于是参看了书上的算法设计（中文版见P201）
我是参看了表9.4得到了启发，其实就是把指数转成2进制来做！
publicstaticintmodular_exponentitation（inta,intb,intn）{
StringB=Integer.toBinaryString（b）;
/*java中有直接把任意整数（还可以指定进制）转成二进制字符串，这也是我喜欢用java的原因，库函数功能强大！
*/
char[]bi=B.toCharArray（）;
//字符串转字符数组，便于对每一位字符操作
intresult=1;
/*算法思想很简单，对于指数的对应的二进制位bi，如果为0，d（算法中为result）累乘
取模；
如果为1，乘a（底数）并取模，整个运算由二进制数最高位到最低位进行*/
for（inti=0;
i<
bi.length;
i++）{
result=（result*result）%n;
if（bi[i]=='
1'
result=（result*a）%n;
}
returnresult;
（3）欧拉函数Ø
（n）函数Euler介绍：
这里我没有用更节省资源的算法，我单纯利用了定义了做，所谓定义就是，Ø
（n）便是1到n-1内与n互素的整数个数，所以我直接遍历1到n-1并判断互素否（很简单，就用刚才的gcd函数就能办到）并计数即可。
当然，这不是最简单最省资源的做法，它很依赖于计算机CPU的处理速度，不过，就目前计算机而言，n取10000000计算时间也不会超过10秒，不过n很大时，这种算法就比较耗时了！
publicstaticintEuler（intn）{
if（n==1）return1;
//欧拉函数指定Ø
（1）=1
else{
intcount=0;
for（inti=1;
n;
if（gcd（i,n）==1）count++;
//如果互素则计数+1}
returncount;
}
3.功能函数测试数据结果截图（部分）
升级会员 