数论与密码学报告

数论与密码学报告 指导老师：宋 军      姓名：罗 斌      班级：192091-27  学号：20091003757 目录 一、信息安全数学基础部分    2 1、 埃拉托斯散(Eratosthenes)素数筛法    2 2、 使用VC++编程语言实现一个算法程序库    3 3、Euler素数验证    8 二、密码学部分    9 1、 大数运算库（代码见附录1）    9 2、 Kasiski测试法（代码见附录2）    11 3、 DES算法实现（代码见附录3）    12 4、 MD5算法实现（代码见附录4）    13 5、 AES算法实现（代码见附录5）    14 6、 SMS算法实现（代码见附录6）    15 附录：    17 1、 大数运算库    17 2、 Kasiski测试法    28 3、 DES加密算法    30 4、 MD5校验算法    37 5、 AES加密算法    42 6、 SMS4加密算法    47 数学基础与密码学实验 一、信息安全数学基础部分 1、埃拉托斯散(Eratosthenes)素数筛法 关键程序代码： int prime(int a[],int n) { int i,j,k,x,num; bool *b; n++; n/=2; b=new bool[(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++){ x=2*(i+j)-1; while(b[x]==0){ a[num++]=x; for(k=x;k<=2*n;k+=x) b[k]=1; } } return num; } 运行截图： 2、使用VC++编程语言设计实现一个算法程序库 1）欧几里德算法求a，b的最大公倍数； /*欧几里得算法 语法：int gcd(int a,int b) 返回：最大公约数*/ int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } 2）扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y； /*扩展欧几里得算法，求x、y; 参数：a、b对应int gcd(a,b)=ax+by 返回：最大公约数*/ int ext_euclid(int a,int b,int &x,int &y) { int t,d; if (b==0) {x=1;y=0;return a;} d=ext_euclid(b,a %b,x,y); t=x; x=y; y=t-a/b*y; return d; } 3）求解模线性方程 ax ≡ b (mod n) 其中n>0； /*求模线性方程 result＝modular_equation(int a,int b,int n); 参数：a、b、n：ax=b (mod n) 的对应参数*/ void modular_equation(int a,int b,int n) { int e,i,d; int x,y; d=ext_euclid(a,n,x,y); if (b%d>0) printf("No answer!\n"); else { e=(x*(b/d))%n; for (i=0;i0) return a; else return(a+n); } 5）模取幂运算，计算ab mod n （a,b>1032）； /*模取幂运算x = a^b mod n 参数：a、b、n 返回：x*/ int modular_exponent(int a,int b,int n) { int ret=1; for (;b;b>>=1,a=(int)((__int64)a)*a%n) if (b&1) ret=(int)((__int64)ret)*a%n; return ret; } 6）Miller-Rabin随机性素数测试算法； /*Miller-Rabin随机性素数测试算法 用法：输入N，可以测定2^32以内的数 返回：判定结果*/ int Miller_Rabin(int N) { int tag=1; int t,m,s,b; __int64 r0,r1; t=N-1;m=0; while(t%2==0){ m++; t>>=1; }  srand(N); for(int i=0;i<20;i++){ b=rand()%N; if(b<2) b+=2;    s=m;r0=1; for(int j=0;j0) continue; else if(r0%N==1) continue; else{ tag=0;break;} } return tag; } 运行截图 3、Euler素数验证 令f(n)=n2+n+41，使用Miller Rabin素性检测方法验证，当n=0,1,…,39时，f(n)都是素数，但f(40)是合数。程序运行结果如下所示，其中f(40)和f(41)均为合数。 二、密码学部分 1、大数运算库（代码见附录1） 大整数类 class CBigInt { public:    unsigned m_nLength;//大数在0x100000000进制下的长度 unsigned long m_ulValue[BI_MAXLEN];//用数组记录大数在0x100000000进制下每一位的值 CBigInt(); ~CBigInt(); void Mov(unsigned __int64 A); void Mov(CBigInt& A);  //赋值 CBigInt Add(CBigInt& A);//加法 CBigInt And(CBigInt& A);//与运算 CBigInt Sub(CBigInt& A);//减法 CBigInt Mul(CBigInt& A);//乘法 CBigInt Div(CBigInt& A);//除法 CBigInt Mod(CBigInt& A);//求模 CBigInt Or(CBigInt& A);//或运算 CBigInt Xor(CBigInt& A);//异或 CBigInt Rev();    //求反 CBigInt Add(unsigned long A); CBigInt Sub(unsigned long A); CBigInt Mul(unsigned long A); CBigInt Div(unsigned long A); CBigInt Gcd(CBigInt &A,CBigInt &B);//求最大公约数 unsigned long And(unsigned long A); unsigned long Mod(unsigned long A); int Cmp(CBigInt& A); //比较大小 /***************************************************************** 输入输出 Get，从字符串按10进制或16进制格式输入到大数 Put，将大数按10进制或16进制格式输出到字符串 *****************************************************************/ void Get(CString& str, unsigned int system=DEC); void Put(CString& str, unsigned int system=DEC); /***************************************************************** Rab，拉宾米勒算法进行素数测试 Euc，欧几里德算法求解同余方程 RsaTrans，反复平方算法进行幂模运算