实验4 非对称密码算法RSA.docx
- 文档编号:16197758
- 上传时间:2023-07-11
- 格式:DOCX
- 页数:18
- 大小:41.71KB
实验4 非对称密码算法RSA.docx
《实验4 非对称密码算法RSA.docx》由会员分享,可在线阅读,更多相关《实验4 非对称密码算法RSA.docx(18页珍藏版)》请在冰点文库上搜索。
实验4非对称密码算法RSA
实验4非对称密码算法RSA(验证型)
一、实验目的
通过实际编程了解非对称密码算法RSA的加密和解密过程,加深对非对称密码算法的认识。
二、实验原理
对称密码算法要求通信双方通过交换密钥实现使用同一个密钥,这在密钥的管理、发布和安全性方面存在很多问题,而非对称密码算法解决了这个问题。
加密密钥和解密密钥是不同的,其中加密密钥是可以公开的,解密密钥是要求保密的,并且不能用其中的一个推导出另一个。
它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上,即将两个大素数相乘在计算上容易实现,而将该乘积分解为两个大素数因子的计算量相当大。
虽然它的安全性还未能得到理论证明,但经过30年的密码分析和攻击,迄今仍然被实践证明是安全的。
三、实验环境
运行Windows或者Linux操作系统的PC机,具有gcc(Linux)、VC(Windows)等C语言编译环境。
四、实验内容和步骤
1、为了加深对
算法的了解,根据已知参数:
,手工计算公私钥,并对明文进行加密,然后对密文进行解密。
2、编写
程序,加密一段文字,了解
算法原理。
尝试加密一大段文字,记录程序的运行时间。
使用DES算法加密相同的文字,比较两种算法加密的速度。
3、编写一个程序,随机选择3个较大的数
,计算
,记录程序运行时间。
查阅资料给出简单说明大数在计算机上是如何表示,如何进行运算。
4、查阅资料,找出目前实际可行的素数判定法则,并比较各自的优缺点。
五、实验步骤
1、p=3,q=11则n=pq=33,f(n)=20,选择e=7,则d=3
那么加密得c=29解密得m=2
2、打开VC++,编写程序如下:
#include
#include
#include
#include
//usingnamespacestd;
typedefstructRSA_PARAM_Tag
{//64位数
unsigned__int64p,q;//两个素数,不参与加密解密运算
unsigned__int64f;//f=(p-1)*(q-1),不参与加密解密运算
unsigned__int64n,e;//公匙,n=p*q,gcd(e,f)=1
unsigned__int64d;//私匙,e*d=1(modf),gcd(n,d)=1
unsigned__int64s;//块长,满足2^s<=n的最大的s,即log2(n)
}RSA_PARAM;//小素数表,用于素性测试前,用小素数来初步筛选素数.
conststaticunsigned__int64g_PrimeTable[]=
{
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
conststaticlongg_PrimeCount=sizeof(g_PrimeTable)/sizeof(long);
//乘数
constunsigned__int64multiplier=12747293821;
//加数
constunsigned__int64adder=1343545677842234541;
//随机数类
classRandNumber
{
private:
unsigned__int64randSeed;/**/
public:
RandNumber(unsigned__int64s=0);
unsigned__int64Random(unsigned__int64n);
};/**/
RandNumber:
:
RandNumber(unsigned__int64s)
{
if(!
s)
{
randSeed=(unsigned__int64)time(NULL);
}
else
{
randSeed=s;
}
}/*一个简单的随机数产生算法*/
unsigned__int64RandNumber:
:
Random(unsigned__int64n)
{
randSeed=multiplier*randSeed+adder;
returnrandSeed%n;
}
//定义了一个静态的类对象
staticRandNumberg_Rnd;/*
模乘运算,返回值x=a*bmodn
*/
inlineunsigned__int64MulMod(unsigned__int64a,unsigned__int64b,unsigned__int64n)
{
returna*b%n;
}/*
模幂运算,返回值x=base^powmodn
*/
unsigned__int64PowMod(unsigned__int64base,unsigned__int64pow,unsigned__int64n)
{unsigned__int64r=1;
pow=pow+1;
while(pow!
=1)//循环结果为pow(a,b)%c
{
r=r*base;
r=r%n;
pow--;
}
returnr;
}
/*
{unsigned__int64a=base,b=pow,c=1;
while(b)
{
while(!
(b&1))
{
b>>=1;//a=a*a%n;//函数看起来可以处理64位的整数,但由于这里a*a在a>=2^32时已经造成了溢出,因此实际处理范围没有64位
a=MulMod(a,a,n);
}
b--;//c=a*c%n;//这里也会溢出,若把64位整数拆为两个32位整数不知是否可以解决这个问题。
c=MulMod(a,c,n);
}
returnc;
}/*
Rabin-Miller素数测试,通过测试返回1,否则返回0。
n是待测素数。
注意:
通过测试并不一定就是素数,非素数通过测试的概率是1/4
*/
longRabinMillerKnl(unsigned__int64&n)
{
unsigned__int64b,m,s,z,r;
m=n-1;
s=0;//0、先计算出m、s,使得n-1=m*2^s,其中m是正奇数,s是非负整数
while(!
(m&1))
{
++s;
m>>=1;
}
//1、随机取一个b,2<=b b=2+g_Rnd.Random(n-3); //2、计算z=b^mmodn z=PowMod(b,m,n); //3、如果z==1,通过测试 if(z==1) { return1; } //4、令r=0 r=0; //5、如果z=n-1,通过测试 while(z! =n-1) { //6、如果i==l,非素数,结束 if(r==(s-1)) { return0; } //7、z=z^2modn,i=i+1 z=PowMod(z,2,n); ++r; //8、循环到5 } return1; }/* Rabin-Miller素数测试,循环调用核心loop次 全部通过返回1,否则返回0 */ longRabinMiller(unsigned__int64&n,longloop) { //先用小素数筛选一次,提高效率 for(longk=0;k { if(n%g_PrimeTable[k]==0) { return0; } }//循环调用Rabin-Miller测试loop次,使得非素数通过测试的概率降为(1/4)^loop for(longi=0;i { if(! RabinMillerKnl(n)) { return0; } }return1; }/* 随机生成一个bits位(二进制位)的大素数,最多32位 */ unsigned__int64RandomPrime(charbits) { unsigned__int64base; do { base=(unsignedlong)1<<(bits-1);//保证最高位是1 base+=g_Rnd.Random(base);//再加上一个随机数 base|=1;//保证最低位是1,即保证是奇数 } while(! RabinMiller(base,30));//进行拉宾-米勒测试30次 returnbase;//全部通过认为是素数 }/* 欧几里得除法求最大公约数 */ unsigned__int64EuclidGcd(unsigned__int64&p,unsigned__int64&q) { unsigned__int64a=p>q? p: q; unsigned__int64b=p p: q; unsigned__int64t; if(p==q) { returnp;//两数相等,最大公约数就是本身 } else { while(b)//辗转相除法,gcd(a,b)=gcd(b,a-qb) { a=a%b; t=a; a=b; b=t; }returna; } } //已知a、b,求x,满足a*x=1(modb)/ //相当于求解a*x-b*y=1的最小整数解 //*/ unsigned__int64Euclid(unsigned__int64&a,unsigned__int64&b) { unsigned__int64m,e,i,j,x,y; longxx,yy; m=b; e=a; x=0; y=1; xx=1; yy=1; while(e) { i=m/e; j=m%e; m=e; e=j; j=y; y*=i; if(xx==yy) { if(x>y) { y=x-y; } else { y-=x; yy=0; } } else { y+=x; xx=1-xx; yy=1-yy; }x=j; }if(xx==0) { x=b-x; }returnx; } /* 随机产生一个RSA加密参数 */ RSA_PARAMRsaGetParam(void) { RSA_PARAMRsa={0}; unsigned__int64t; Rsa.p=RandomPrime(16);//随机生成两个素数 //Rsa.p=11;Rsa.q=23; Rsa.q=RandomPrime(16); Rsa.n=Rsa.p*Rsa.q; Rsa.f=(Rsa.p-1)*(Rsa.q-1); do { Rsa.e=g_Rnd.Random(65536);//小于2^16,65536=2^16 Rsa.e|=1;//保证最低位是1,即保证是奇数,因f一定是偶数,要互素,只能是奇数 } while(EuclidGcd(Rsa.e,Rsa.f)! =1); //由de=1modf来求d; Rsa.d=Euclid(Rsa.e,Rsa.f); Rsa.s=0; t=Rsa.n>>1; while(t) { Rsa.s++;//s=log2(n) t>>=1; }returnRsa; }/* 拉宾-米勒测试,素性检测测试程序.非主要程序. */ //RSA加密解密 //*/ voidTestRSA(void) { RSA_PARAMr; //明文 //charpSrc[]="abcdefghijklmnopqrstuvwxyz"; intpSrc[2]={165,31}; //constunsignedlongLen=sizeof(pSrc); constunsignedlongLen=2; //密文信息 unsigned__int64pEnc[Len]; //unsignedchar*q,pDec[n]; unsigned__int64pDec[Len]; r=RsaGetParam(); printf("p=%I64u\n",r.p); printf("q=%I64u\n",r.q); printf("f=(p-1)(q-1)=%I64u\n",r.f); printf("n=p*q=%I64u\n",r.n); printf("e=%I64u\n",r.e); printf("d=%I64u\n",r.d); printf("s=%I64u\n",r.s); //cout<<"Source: "< //g=(unsigned__int64*)pSrc; cout<<"Encode: "< for(unsignedlongj=0;j { pEnc[j]=PowMod(pSrc[j],r.e,r.n); printf("%I64u\n",pEnc[j]); } cout<<"Decode: "< for(unsignedlongi=0;i { pDec[i]=PowMod(pEnc[i],r.d,r.n); //cout< printf("%I64u\n",pDec[i]); }cout< //cout<<(char*)pDec< }/**/ intmain(void) { clock_tstart,end; start=clock(); longtimes; TestRSA(); end=clock(); times=1000*(end-start); cout<<"花费的时间为: "< return0; } 调试程序,程序运行如下: 3、打开VC++,编写程序如下: #include #include #include #include #include #include #include //usingnamespacestd; intmain(){ clock_tstart,end; longtimes; longx,e,n; cout<<"随机产生3个大数: "< //x=1000*(rand()%11)+100*(rand()%11)+10*(rand()%11)+rand()%11; x=1000000*(rand()%11)+100000*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+ 100*(rand()%11)+10*(rand()%11)+rand()%11; e=1000000*(rand()%11)+100000*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+ 100*(rand()%11)+10*(rand()%11)+rand()%11; n=1000000*(rand()%11)+100000*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+ 100*(rand()%11)+10*(rand()%11)+rand()%11; cout<<"x="< start=clock(); cout< longanswer=(int)pow(x,e)%n;//指数运算 end=clock(); times=1000*(end-start); cout<<"花费的时间为: "< return0; } 调试运行如下: 计算机上大数表示方法: 将大数看作一个n进制数组,对于目前的32位系统而言,n可以取值为2的32次方,即0x10000000,假如将一个1024位的大数转化成0x10000000进制,它就变成了32位,而每一位的取值范围就不是0-1或0-9,而是0-0xfffffff.我们正好可以用一个无符号长整数来表示这一数值.所以1024位的大整数就是一个有32个元素的unsignedlong数组.而且0x10000000进制的数组排列与2进制流对于计算机来说,实际上是一回事,但是我们完全可以针对unsighedlong数组进行”竖式计算”,而循环规模被降低到了32次之内,并且算法很容易理解. 4、素性测试方法: 所谓素数,是指除了能补1和它本身整除而不能被其他任何数整除的数。 据此,只需用2到N-1去除N,如果都除不尽,则为素数 (1)flag=1,i=2 (2)Ifnmodi=0thenflag=1elsei=i+1 (3)Ifflag=0andi (2)else(4) (4)Ifflag=0thenwriteyeselseno 在最坏的情况下,即N为素数,算法需要执行N-2次,时间复杂性太大。 只需用2到根下N去除N,即可,于是上述算法改为 (3)Ifflag=0andi<=int(根N)then (2)else(4) 虽然快了不小,但有重复计算,如果用2去除N时若不尽,则用2的倍数去除N也除不尽,由此得 (1)for(i=2;int(根N);i++)mark[i]=0;//mark是标记其初值为0,只要它的因子除不尽其值变为1 (2)i=2,flag=0 (3)while(flag=0andi Ifmark[i]=0 Then{ Ifnmodi=0 Thenflag=1 S=i+i Whiles Mark[s]=1 S=s+i } } I=i+1 } (4)ifflag=0thenyeselseno
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验4 非对称密码算法RSA 实验 对称 密码 算法 RSA