数学基础与密码学部分实验重要内容

1/30数学基础与密码学部分实验内容2/30一、信息安全数学基础实验部分题目：定理：设n是一个正整数，如果对所有的素数p≤,都有płn,则n一定是素数。注：古希腊数学家埃拉托斯散(Eratosthenes，公元前275—公元前194)发明了求比某给定数小的素数的筛法技巧。方法如下：对于任意给定的正整数N，要求出所有不超过N的素数。我们列出N个整数，从中删除小于等于的所有素数p1,…,pk的倍数。然后依次删除，p1的倍数：2p1,…,p1。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。pk的倍数：2pk,…,pk余下的整数（不包括1）就是所要求的不超过N的素数。使用VC++编程语言编写一个可测定不超过1，000，000的素数判定程序。1、程序设计思想：有题目所给定的定理我们可以采用：首先将整数N下对应的小于所有的素数尽，则通过的倍数比不为素数，并将此种类型的整数提出后，最终只剩下素数输出到屏幕上。2、程序流程图：3、程序源代码：#includestdio.hintprime(intm){intn,i;n=m/2;for(i=2;i=n;i++)if(m%i==0)return0;return1;}3/30intmain(void){intk;for(k=2;k=1000000;k++)if(prime(k))printf(%d,k);return0;}程序运行截图：4/30题目二：使用VC++编程语言设计实现一个算法程序库，要求包括以下部分：1）欧几里德算法求a，b的最大公倍数；2）扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y；3）求解模线性方程ax≡b(modn)其中n0；4）求解模线性方程组(中国余数定理)；5）模取幂运算，计算abmodn（a,b1032）；6）Miller-Rabin随机性素数测试算法（要求判定n1016）；1）欧几里德算法求a，b的最小公倍数；程序设计思想：采用欧几里得思想的推论，两个整数的积相乘并除以他们的最大公约数可以求出这两个整数的最小公倍数。程序流程图：程序源代码：#includestdio.hintmain(){inta,b,c;printf(请依次输入两个数：\n);scanf(%d%d,&a,&b);inta_cup,b_cup,res;/*被除数,除数,余数*/if(a0&&b0){a_cup=a;b_cup=b;res=a_cup%b_cup;while(res!=0){a_cup=b_cup;b_cup=res;res=a_cup%b_cup;}5/30c=a*b/b_cup;}printf(%d\n,c);return0;}运行结果：2）扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y；#includestdio.hintx,y,q;voidextend_Eulid(inta,intb){if(b==0){x=1;y=0;q=a;}else{extend_Eulid(b,a%b);6/30inttemp=x;x=y;y=temp-a/b*y;}}intmain(){inta,b;printf(Pleaseinputtwonumbers:);scanf(%d%d,&a,&b);if(ab){intm=a;a=b;b=m;}elseextend_Eulid(a,b);printf(%d=(%d)*%d+(%d)*%d\n,q,x,a,y,b);return0;}3）求解模线性方程ax≡b(modn)其中n0；源代码：#includeiostream#includestring#includetime.husingnamespacestd;#includeBigNum.hBigNumgcd(BigNumx,BigNumy)//递归法求最大公约数{BigNumz;z=0;if(y==z)7/30returnx;//递归出口elsereturngcd(y,x%y);//递归调用}BigNumQiuNi(BigNuma,BigNumm)//求逆{BigNumr0,r1,r2,s0,s1,s2,t0,t1,t2,q,x,y;x=0;y=1;r0=a,r1=m;s0=1,t1=1,s1=0,t0=0;while(r1!=x){q=r0/r1;r2=r0%r1;s2=s0-q*s1;t2=t0-q*t1;s0=s1,s1=s2;t0=t1,t1=t2;r0=r1,r1=r2;}if(r0==y){if(!a.s&&s0.s){s0=m+s0;returns0;}elseif(!a.s&&!s0.s)returns0;elseif(a.s&&s0.s){returns0;}elseif(a.s&&!s0.s){s0=s0-m;returns0;}}elsereturnx;}voidmain(){BigNuma,b,m,p,q,s,t;8/30charx[100],y[100],z[100];while(1)//控制多次输入{coutinputa,b,m:endl;cinxyz;s=0;t=1;a=x;b=y;m=z;p=gcd(a,m);//求（a,m）q=QiuNi(a/(p),m/(p));//求（a/((a,m))）的逆(a/((a,m)))^(-1)if(b%p==s)//判断是否有解，有解输出解的情况{cout解得：endl;coutx≡;((b/p*q)%(m/p)).CoutBigNum();cout+;(m/p).CoutBigNum();coutt(mod;m.CoutBigNum();cout)t=0,...,;(p-t).CoutBigNum();cout.endl;}elsecout无解!endl;//无解显示说明}}运行结果：结果为有解和无解两种情况5）模取幂运算，计算abmodn（a,b1032）；源代码：9/30#includeiostream#includestring.h#includetime.husingnamespacestd;#includeBigNum.h#defineMAX100main(){BigNumf,r,s,b2,c1,c2,b1[500],c3,c4;chara[MAX]={'\0'},b[MAX]={'\0'},m[MAX]={'\0'};inti=0,j=0,t=0;while(1){coutinputa,b:endl;cinab;coutinputn:endl;cinm;b2=b;s=m;f=1;c1=2;c2=0;c4=1;r=a;for(i=0;i500;i++)b1[i]=0;//十进制转换成二进制i=0;while(b2!=c2){b1[i]=b2%c1;b2=b2/c1;i++;}t=i;for(j=0;j(t-1)/2;j++){c3=b1[j];b1[j]=b1[t-1-j];b1[t-1-j]=c3;}for(i=0;it;i++)//求余{f=(f*f)%s;if(b1[i]==c4){f=(f*r)%s;}}coutf=;f.CoutBigNum();}10/30}运行结果：2的3次模6等于26）Miller-Rabin随机性素数测试算法（要求判定n1016）；源代码：#includeiostream.h#includetime.h#includestdlib.h#includemath.hclassjudge_prime{private:public:intBtest(inta,intn);intMillRab(intn);intRepeatMillRab(intn,intk);};intjudge_prime::Btest(inta,intn){ints=0;intt=n-1;11/30inti=1;intx=1;inty;do{s++;t=t/2;}while((t%2)!=1);while(i=t){x=(x*a)%n;i++;}if((x==1)||(x==n-1))return1;for(intj=1;j=s-1;j++){y=1;for(intk=1;k=j;k++){y=2*y;}i=1;x=1;while(i=(y*t)){x=(x*a)%n;i++;}if(x==n-1)return1;}12/30return0;}intjudge_prime::MillRab(intn){inta;srand((unsigned)time(0));a=rand()%(n-3)+2;returnBtest(a,n);}intjudge_prime::RepeatMillRab(intn,intk){inti;for(i=1;i=k;i++){if(MillRab(n)==0)return0;}return1;}intmain(){inti;intn=10000;intresult=0;cout23;for(i=5;i=n;){judge_primeP;if(P.RepeatMillRab(i,(int)log10(i)))couti;i=i+2;13/30}return0;}测试结果：二、密码学基础实验部分一、使用VC++编程语言设计实现一个200位以上十进制数运算的程序库：能够完成大整数加、减、乘、除、求模、与、或、非、异或等运算。二、使用VC++编程语言编写一个程序，实现DES算法，包括以下环节，密钥通过随机函数产生，并应用密文反馈（CFB）工作模式和输出反馈（OFB）工作模式进行加密、解密和输出。源代码：#includestdio.h14/30#includememory.h#includetime.h#includestdlib.h#definePLAIN_FILE_OPEN_ERROR-1#defineKEY_FILE_OPEN_ERROR-2#defineCIPHER_FILE_OPEN_ERROR-3#defineOK1typedefcharElemType;//下面是变量的声明//初始置换表IPintIP_Table[64]={57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,56,48,40,32,24,16,8,0,58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,62,54,46,38,30,22,14,6};//逆初始置换表IP^-1intIP_1_Table[64]={39,7,47,15,55,23,63,31,38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,34,2,42,10,50,18,58,26,33,1,41,9,49,17,57,25,15/3032,0,40,8,48,16,56,24};//扩充置换表EintE_Table[48]={31,0,1,2,3,4,3,4,5,6,7,8,7,8,9,10,11,12,11,12,13,14,15,16,15,16,17,18,19,20,19,20,21,22,23,24,23,24,25,26,27,28,27,28,29,30,31,0};//置换函数PintP_Table[32]={15,6,19,20,28,11,27,16,0,14,22,25,4,17,30,9,1,7,23,13,31,26,2,8,18,12,29,5,21,10,3,24};//S盒intS[8][4][16]=//S1{{{14,4,13