RSA加密算法设计说明

《RSA加密算法设计说明》由会员分享，可在线阅读，更多相关《RSA加密算法设计说明（22页珍藏版）》请在装配图网上搜索。

1、. . . . 网络安全作业题 目 RSA 加 密 算 法学 号专业与班级 网络工程0902班姓 名日 期 2012.04.14 一、 RSA简介：RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。二、 RSA算法描述：RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。 RSA的算法涉与三个参数，n、e1、e2。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。 e1和e2是一对相关的值，e1可以任意取，

2、但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod(p-1)*(q-1)=1。 (n与e1),(n与e2)就是密钥对。 RSA加解密的算法完全一样,设A为明文，B为密文，则：A=Be1 mod n；B=Ae2 mod n； e1和e2可以互换使用，即： A=Be2 mod n；B=Ae1 mod n;三、 实现代码：1.实现RSA算法类的定义：class CRsaA : public CCmdTargetDECLARE_DYNCREATE(CRsaA)CRsaA(); / protected constructor used by dynamic creation/

3、成员函数private:void InitInt(void); /基本数据常量的初始化int IntValid(byteint validtemp); /返回大validtemp的非零位的个数int IntCmp(byteint A,byteint B); /比较大数A和B是否相等/自定义类型的基本运算void Plus(byteint A,byteint B,byteint C); /C=A+Bvoid Substract(byteint SA,byteint SB,byteint SC); /SC=SA-SBvoid Multiply(byteint A,byteint B,byteint

4、 C); /C=A*Bvoid SetMode(byteint A,byteint B,byteint C,byteint D);/C=A%Bint PowerMode(byteint A,byteint C,byteint D,signed char flag400);/computing AB mod C-Dvoid IntRandom(byteint RandomA,int num); /随机产生一个大数void LoadInt(byteint A,mtype B); /将质数类型转换为大数类型void TransBi(byteint B,signed char flag400) 将大数

5、B转换为二进制形式void Mdata(); 产生用于生成质数中进行比较的数int Prime(byteint Prm); /产生一个长度为MLENGTH的质数int ComputingPK(byteint Rvalue,byteint SK,byteint PK);/计算公钥PKvoid ComputingR(byteint p,byteint q,byteint R); /计算模值Rvoid ComputingRvalue(byteint p,byteint q,byteint Rvalue); /计算$(r)void IntCpy(byteint A1,byteint B1); /将大数

6、B1的值拷贝到大数A1中void SetZero(byteint A); /将大数A清零CString PrtInt(byteint A); /将一个大数类型转换为一个CString类型int Getinput(byteint result,CString input);/将字符串转换为对应的大数形式int Getinput1(byteint result,unsigned long input); /将长整形数转换为对应的大数形式void RsaDo(byteint source,byteint R,byteint key,byteint desti);/实现加解密unsigned long

7、 Os2ip(unsigned char* pstr);CString Ip2os(CString str);public:void GenKeys(CString& pk,CString& sk,CString& R); /提供给服务器使用的秘钥产生函数int RsaEncrypt(CString& source,const char* key,const char* R,CStringArray& result);/加密CString RsaDecrypt(CStringArray& source,const char* sk,const char* R);/解密void GenKeysT

8、able(); /生成秘钥对文件void LoadKeysFromFile(CString& r,CString& sk,CString& pk);private:byteint ONEVALUE;byteint ZEROVALUE;byteint TWOVALUE;byteint EIGHTVALUE; /O,1,2,8 constantmtype ModelTESTNUM; /TESTNUM big number to be comparedmtype mZEROVALUE,tempModel; /0 constantsigned char flag400;public:virtual C

9、RsaA();functions here.DECLARE_MESSAGE_MAP();2.算法实现的主要代码：/*-功能：进行相关大数的初始化入口参数：无返回值：无-*/void CRsaA:InitInt(void)SetZero(ZEROVALUE);/对大数变量zerovalue清零memset(mZEROVALUE,0,MLENGTH);SetZero(ONEVALUE); /对大数变量ONEVALUE进行清零ONEVALUEDATALENGTH-1=1;/ONEVALUE的最后一位为1SetZero(TWOVALUE);/将TOWVALUE进行清零 TWOVALUEDATALENG

10、TH-1=2;/TOWVALUE的最后一位为2SetZero(EIGHTVALUE);/对EIGHTVALUE进行清零 EIGHTVALUEDATALENGTH-1=8;/最后一位为8return ;/*-功能：将一个大数A转换为相应的字符串形式入口参数：大数A返回值：相对应的字符串-*/CString CRsaA:PrtInt(byteint A)register i=0;int m,n;while(iDATALENGTH & Ai=0) /跳过大数开始的空白0i+;if(iDATALENGTH)m=DATALENGTH-i; /求出有用的大数长度n=0;/注意到这里的i已经是数组中第一个非

11、零元素的对应位置，CString str=;/因此下面的循环就是从数组中while(iC入口参数：被乘数A和乘数B，结果C返回值：无-*/void CRsaA:Multiply(byteint A,byteint B,byteint C)register i,j,w;int X,Y,Z;int Avalid=0;/Avalid=validating bits of Aint Bvalid=0;/Avalid=validating bits of Bwhile (AAvalid=0 & AvalidDATALENGTH)Avalid+;/计算Avalidwhile (BBvalid=0 & Bv

12、alid=Avalid;i-)for(j=DATALENGTH-1;j=Bvalid;j-) /逐位进行相乘运算X=Ai*Bj; Y=X/10;Z=X-10*Y;w=i+j-(DATALENGTH-1);Cw=Cw+Z;Cw-1=Cw-1+(Cw/10)+Y;Cw=Cw-(Cw/10)*10;return;/*-功能：AB的结果送C入口参数：大数A,B,C返回值：无-*/void CRsaA:Plus(byteint A,byteint B,byteint C)register i;/,w;int X,Y,Z,m,n,valid;m=IntValid(A); /计算A的长度 n=IntVali

13、d(B); /计算B的长度valid=(mn)?m+1:n+1; /计算时要以最长的数为准SetZero(C); /将C清零for(i=DATALENGTH-1;i=DATALENGTH-valid;i-)X=Ai+Bi; /按位相加Y=X/10;Z=X-10*Y;Ci=Ci+Z; /计算进位Ci-1=Ci-1+Y;/*-功能：大数SA减去大数SB，结果放入SC入口参数：被减数SA，减数SB，差SC-*/void CRsaA:Substract(byteint SA,byteint SB,byteint SC)byteint buf;register i,j;int X;IntCpy(buf,

14、SA); /将SA的容拷贝到buf中SetZero(SC); /SC清零初始化for(i=DATALENGTH-1;i=0;i-)if(bufi0) /如果高位够减，直接减1(bufi-1)-; else /否则一直找到够减的位j=i-1;while(bufj=0) /j不会出现越界，是因为保证了最高位不为0bufj-=9;bufj=bufj-1;X=bufi-SBi; /将各位减的结果存入SC中SCi=X;/*-功能：随机地产生一个大数奇数，长度为num，最高位不是0，存放在RandomA中入口参数：大数A，长度num返回值：无-*/void CRsaA:IntRandom(byteint

15、RandomA,int num)int i;SetZero(RandomA); /将RandomA清零while(!(RandomADATALENGTH-1%2)RandomADATALENGTH-1=rand()%10;最后一位是偶数从新产生最后一位while(!(RandomADATALENGTH-num)/判断条件保证RandomA最高位不是0RandomADATALENGTH-num=rand()%10;/如果最高位是0,从新产生最高位i=DATALENGTH-2;while(i=DATALENGTH-num+1)/产生从次低位到次高位的所有位上的数RandomAi-=rand()%1

16、0;/*-功能：将质数类型B拷贝到大数A中，实现类型转换入口参数：大数A，质数类型B返回值：无-*/功能：将数B拷贝到大数A，实现类型转换void CRsaA:LoadInt(byteint A,mtype B)register i,j;SetZero(A); /A进行清零初始化i=DATALENGTH-1;j=MLENGTH-1;while(j0) /循环拷贝各位数字Ai-=Bj-;/*-功能：该函数用来从集合1,b-1中产生若干个用于检测的数，存放在Model中入口参数：无返回值：无-*/void CRsaA:Mdata()register i,j; /Randomly choose a

17、set of 100 numbers in 1,b-1int k=MLENGTH-2;memset(Model,0,TESTNUM*MLENGTH); /这个函数在这里用来将整个数组清零，进行初始化srand( (unsigned)time( NULL ) ); /进行随机函数的初始化for(i=0;i=k;j-)Modelij=rand()%10; /注意这里与测试素数的程序中的区别，if(memcmp(Modeli,mZEROVALUE,MLENGTH)=0) i-;k-; /保证所产生的数不为0if (kbuf SetMode(buf,C,temp,P); /buf%c余数-temp,商

18、-pif(flagi!=0) /如果该位不是0则将其和前一步低一位的结果进行乘法运算 /否则，将其作为该位的模，在高一位的运算中，只要进行一次Multiply(temp,result,buf); /平方运算，就可以得到高一位的模SetMode(buf,C,result,P);i-; /result中存放的是最终结果IntCpy(buf,C);IntCpy(D,result);Substract(buf,ONEVALUE,temp);if(IntCmp(result,ONEVALUE)=0)return 1;if(IntCmp(result,temp)=0) return 0;/*-功能：产生一

19、个质数入口参数：大数Prm返回值：产生成功，返回0-*/int CRsaA:Prime(byteint Prm)int i,k,ok;signed char flag400;byteint A,B,D,buf1,buf2;SetZero(A); SetZero(B); SetZero(D); SetZero(buf1); SetZero(buf2);while(1) /一直循环直到找到一个素数为止int pass=0;srand( (unsigned)time( NULL ) ); /初始化srandIntRandom(B,MLENGTH); IntCpy(Prm,B); /将B拷贝到prm中

20、 C=N result primeSubstract(B,ONEVALUE,buf1); /将B-ONEVALUE的结果放到buf1中SetMode(buf1,TWOVALUE,buf2,B); /B=(B-1)/2的商,buf2=(B-1)/2的余数TransBi(B,flag); /将B转换为二进制大数ok=1;for(i=0;ikif(k!=1 & k!=2) /不符合判定规则ok=0;break;if(k=1) /判定条件1，G=A(n-1)/2=1if(k=2) /判定条件2，G=A(n-1)/2=p-1if (ok)/if(ok & pass_2)return 0;/for循环用来

21、检测IntRandom(B,MLENGTH)产生的数B是否是一个素数/*-功能：计算公钥PK入口参数：$(r)的值在Rvalue中，私钥SK，公钥PK返回值：成功找到，返回1-*/int CRsaA:ComputingPK(byteint Rvalue,byteint SK,byteint PK)register i;byteint PA,PB,PC,buf1,temp,buf2;SetZero(PK); SetZero(PA); SetZero(PB); SetZero(PC); SetZero(buf1); /清零初始化SetZero(temp); SetZero(buf2);while(

22、1)IntRandom(SK,SKLENGTH); IntCpy(PB,SK);IntCpy(PA,Rvalue);while(1)SetMode(PA,PB,PC,PK); /PA=PB*PK+PCi=IntCmp(PC,ONEVALUE);if(i=0) /PC=1, i=0break; /满足条件，是互质的i=IntCmp(PC,ZEROVALUE);if(i=0)i=-1; /PC=0,i=-1break; /不满足互质条件，跳出循环，从新生成一个随机数IntCpy(PA,PB); /按照欧几里的定理继续判断IntCpy(PB,PC);if(i=0) /满足，跳出查找循环break;I

23、ntCpy(temp,ONEVALUE);IntCpy(PA,Rvalue);IntCpy(PB,SK);while(1)Multiply(PA,temp,buf1); /buf1=PA*tempPlus(buf1,ONEVALUE,buf2);/buf2=(PA*temp)+1SetMode(buf2,PB,buf1,PK);/buf2=(PA*temp)+1)%PBif(IntCmp(buf1,ZEROVALUE)=0)break;Plus(temp,ONEVALUE,buf1);IntCpy(temp,buf1);return 1; /SK and PK found/*-功能：计算模R入

24、口参数：产生的质数p，q，模R返回值：无-*/void CRsaA:ComputingR(byteint p,byteint q,byteint R)Multiply(p,q,R); / R=p*q, public mode number/*-功能：计算$(r)入口参数：质数p，质数q，模$(r)放在Rvalue返回值：无-*/void CRsaA:ComputingRvalue(byteint p,byteint q,byteint Rvalue)byteint buf1,buf2;SetZero(buf1); SetZero(buf2);Substract(p,ONEVALUE,buf1)

25、; / buf1=p-1Substract(q,ONEVALUE,buf2); / buf2=q-1Multiply(buf1,buf2,Rvalue); / Rvalue=(p-1)*(q-1)/*-功能：将接受的字符串转换为大数类型入口参数：大数result,字符串input返回值：数的长度-*/int CRsaA:Getinput(byteint result,CString input)int i=DATALENGTH,m=0;long strlen;strlen=input.GetLength();if(strlen=0) return 0;elsefor(int j=0;jstrl

26、en;j+)resulti-strlen+j = (input.GetAt(j)-0);return j;/*-功能：实现加密，解密运算功能入口参数：明文(大数类型source)，模R，秘钥key，结果desti返回值：无-*/void CRsaA:RsaDo(byteint source,byteint R,byteint key,byteint desti)TransBi(key,flag);PowerMode(source,R,desti,flag);/*-功能：将长整型的数转换为大数类型入口参数：大数类型result,长整形input返回值：成功，返回数的长度，否则返回0；-*/int

27、 CRsaA:Getinput1(byteint result,unsigned long input)int i=DATALENGTH-1,m=0;long j=0;int k=0;if(input)doj=input/10;k=input-j*10;resulti=k;i-;m+;input=j;while(j);return m;elsereturn 0;/*-功能：将十六进制的串转换为数值入口参数：字符串指针返回值：成功，返回数-*/unsigned long CRsaA:Os2ip(unsigned char* pstr)unsigned long ch=0;unsigned int

28、 j=0;unsigned long k=1;for(int i=0;i=0&(*(pstr+3-i)=a&(*(pstr+3-i)=A&(*(pstr+3-i)0;i-) /得到相应的数字串,存放在num中temp = (str.GetAt(i-1) - 0);num += temp*k;k *= 10;/采用模除的方式,求得相应的十六进制数for(int j=0;j=0&remainder=10&remainder=15)strResult.Insert(0,(remainder-10+a);*/strResult.Insert(0,(unsigned char)remainder);nu

29、m = quotient;return strResult; /*-功能：产生RSA秘钥对入口参数：存放结果的字符串地址 返回值：无-*/void CRsaA:GenKeys(CString& pk,CString& sk,CString& R)byteint m_p,m_q,m_R,m_Rvalue,m_PK,m_SK;SetZero(m_p); /对大数变量进行清零初始化SetZero(m_q); SetZero(m_R); SetZero(m_Rvalue); SetZero(m_PK); SetZero(m_SK);Mdata(); /生成比较数表AfxMessageBox(开始计算质

30、数P.);Prime(m_p); /生成素数p qAfxMessageBox(开始计算质数Q.);Prime(m_q);AfxMessageBox(开始计算模R.);ComputingR(m_p,m_q,m_R); /计算模RAfxMessageBox(开始计算模r);ComputingRvalue(m_p,m_q,m_Rvalue); /计算rAfxMessageBox(开始计算秘钥SK,PK);ComputingPK(m_Rvalue,m_PK,m_SK); / Generate PK and SK/CGenKeyBusyDlg dlg1;/g1.DoModal();R=PrtInt(m_

31、R);pk=PrtInt(m_PK);sk=PrtInt(m_SK);return ;/*-功能：实现加密功能接口入口参数：明文字符串source，模字符串R，秘钥字符串key，结果字符串数组result返回值：无-*/int CRsaA:RsaEncrypt(CString& source,const char *key,const char *R,CStringArray& result)unsigned char* pstr;int j;/sourcelen,j;byteint m_key,m_R,desti,aa;SetZero(desti); /将大数变量清零初始化SetZero(a

32、a);/SetZero(bb);SetZero(m_key);SetZero(m_R);pstr = (unsigned char*)(LPCTSTR)source; /得到字符串数据的指针j = source.GetLength(); result.SetSize(j,1);Getinput(m_key,key); /将字符串转换为大数类型Getinput(m_R,R);for(int i=0;ij;i+)Getinput1(desti,Os2ip(pstr); /将四个字节的输入转换为大数类型数值RsaDo(desti,m_R,m_key,aa); /进行加密运算result.SetAt(

33、i,PrtInt(aa); /将结果存放到数组中SetZero(desti); SetZero(aa);pstr += 4;return j;/*-功能：实现解密功能接口入口参数：密文字符串数组source，秘钥字符串sk，模字符串R，返回值：结果字符串数组result-*/CString CRsaA:RsaDecrypt(CStringArray& source,const char* sk,const char* R)int index=0;CString result;byteint m_sk,m_r,desti,aa;SetZero(m_sk); SetZero(m_r); SetZe

34、ro(desti); SetZero(aa); /SetZero(bb);index=source.GetSize(); /得到数组的元素个数Getinput(m_sk,sk); /将字符串转换为大数类型Getinput(m_r,R);for(int i=0;iindex;i+)Getinput(desti,source.GetAt(i); /将加密结果转换为大数类型RsaDo(desti,m_r,m_sk,aa); /解密运算result += Ip2os(PrtInt(aa); /组合初始明文SetZero(aa); SetZero(desti);return result; /返回明文串

35、/*-功能：生成一个秘钥存贮文件入口参数：无返回值：无-*/void CRsaA:GenKeysTable()CStringArray RArray,SKArray,PKArray;CString r,pk,sk;int j=1,i; /参数j表示产生的秘钥对的个数unsigned char strlength;/设置数组的元素个数RArray.SetSize(j,1);SKArray.SetSize(j,1);PKArray.SetSize(j,1);CFile file;for(i=0;ij;i+)GenKeys(pk,sk,r); /循环产生秘钥RArray.SetAt(i,r); SK

36、Array.SetAt(i,sk); PKArray.SetAt(i,pk);/if(file.Open(c:key.txt,CFile:modeCreate|CFile:modeReadWrite)=0)if(file.Open(key.txt,CFile:modeCreate|CFile:modeReadWrite)=0)AfxMessageBox(open file error!); /打开文件失败return;for(i=0;ij;i+) /循环写入结果strlength = (unsigned char)(RArray.GetAt(i).GetLength();file.Write(

37、&strlength,1);file.Write(RArray.GetAt(i),(RArray.GetAt(i).GetLength();strlength=(unsignedchar)(SKArray.GetAt(i).GetLength();file.Write(&strlength,1);file.Write(SKArray.GetAt(i),(SKArray.GetAt(i).GetLength();strlength=(unsignedchar)(PKArray.GetAt(i).GetLength();file.Write(&strlength,1);file.Write(PKArray.GetAt(i),(PKArray.GetAt(i).GetLength();file.Close();/*-