数论与密码学报告.doc

《数论与密码学报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数论与密码学报告指导老师：宋军姓名：罗斌班级：192091-27学号：20091003757目录一、信息安全数学基础部分21、埃拉托斯散(Eratosthenes)素数筛法22、使用VC++编程语言设计实现一个算法程序库33、Euler素数验证8二、密码学部分91、大数运算库（代码见附录1）92、Kasiski测试法（代码见附录2）113、DES算法实现（代码见附录3）124、MD5算法实现（代码见附录4）135、AES算法实现（代码见附录5）146、SMS算法实现（代码见附录6）15附录：171、大数运算库1

2、72、Kasiski测试法283、DES加密算法304、MD5校验算法375、AES加密算法426、SMS4加密算法47数学基础与密码学实验一、信息安全数学基础部分1、埃拉托斯散(Eratosthenes)素数筛法关键程序代码：intprime(inta[],intn){inti,j,k,x,num;bool*b;n++;n/=2;b=newbool[(n+1)*2];a[0]=2;a[1]=3;num=2;memset(b,0,(n+1)*2);for(i=3;i<=n;i+=3)for(j=0;j<2;j+

3、+){x=2*(i+j)-1;while(b[x]==0){a[num++]=x;for(k=x;k<=2*n;k+=x)b[k]=1;}}returnnum;}运行截图：1、使用VC++编程语言设计实现一个算法程序库1）欧几里德算法求a，b的最大公倍数；/*欧几里得算法语法：intgcd(inta,intb)返回：最大公约数*/intgcd(inta,intb){if(b==0)returna;elsereturngcd(b,a%b);}2）扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax

4、+by的整数x和y；/*扩展欧几里得算法，求x、y;参数：a、b对应intgcd(a,b)=ax+by返回：最大公约数*/intext_euclid(inta,intb,int&x,int&y){intt,d;if(b==0){x=1;y=0;returna;}d=ext_euclid(b,a%b,x,y);t=x;x=y;y=t-a/b*y;returnd;}3）求解模线性方程ax≡b(modn)其中n>0；/*求模线性方程result＝modular_equation(inta,intb,intn);参数：

5、a、b、n：ax=b(modn)的对应参数*/voidmodular_equation(inta,intb,intn){inte,i,d;intx,y;d=ext_euclid(a,n,x,y);if(b%d>0)printf("Noanswer!");else{e=(x*(b/d))%n;for(i=0;i

6、sult=China(intB[],intW[],intk);参数：B[]、W[]：a=B[](modW[])的对应参数返回：a*/intChina(intB[],intW[],intk){inti;intd,x,y,a=0,m,n=1;for(i=0;i0)returna;elsereturn(a+n);}5）模取幂运算，计算abmo

7、dn（a,b>1032）；/*模取幂运算x=a^bmodn参数：a、b、n返回：x*/intmodular_exponent(inta,intb,intn){intret=1;for(;b;b>>=1,a=(int)((__int64)a)*a%n)if(b&1)ret=(int)((__int64)ret)*a%n;returnret;}6）Miller-Rabin随机性素数测试算法；/*Miller-Rabin随机性素数测试算法用法：输入N，可以测定2^32以内的数返回：判定结果*/intMiller_Ra

8、bin(intN){inttag=1;intt,m,s,b;__int64r0,r1;t=N-1;m=0;while(t%2==0){m++;t>>=1;}srand(N);for(inti=0;i<20;i++){b=rand()%N;if(b<2)b+=2;s=m;r0=1;for(intj=0;j

9、

10、r0