全部博文（2005）
分类：
2010-02-21 16:41:19
[摘要] 随着信息技术的发展，特别是电子商务的发展，网络信息的安全传输逐渐成为人们最为关心和头痛的事情。密码安全研究与设计是当前密码学领域的热点问题。通过对RSA的安全性进行了分析，提出构造安全素数。
在实际应用中
，在混合密码体制中占有重要地位RSA算法存在着计算复杂，运行速度慢的问题。这些基本算法包括模加，模乘，模逆和模幂运算。大数运算是很费时间的，尤其
是大整数的模逆和模 幂运算。同时我将结合自己在用基本类型进RSA算法中，应注意的一些问题.进行论述。
[关键词] RSA算法 密码 安全
1. 绪论
RSA密码体制是美国麻省理工学院（MIT）Rivest、Shami和Adleman于1978年提出来的，它是第一个理论上最为成功的公开密
钥密码体制，它的安全性基于数论中的Euler定理和计算复杂性理论中的下述论断：求两个大素数的乘积是很容易计算的，但要分解两个大素数的乘积，求出它
们的素数因子却是非常困难的，它属于NP—完全类，是一种幂模运算的加密体制。除了用于加密外，它还能用于数字签字和身份认证。下面将从各个方面来详细对
RSA公钥体制进行研究。
1.1 RSA的构成
RSA系统由以下几部分组成：
(1) 随机选取的在素数P和Q，还有N ，其中N=P*Q ，P和Q保密，N公开。
(2) 任取 (n)=（P-1）*(Q-1)，其中 (n)表示比n小的素数的个数，任取2<=e<= (n),且(e, (n))=1,e为加密密钥，公开。
(3) (计算d,使e*d=1(mod (n)),称d为e对模 (n)的逆，其中d为解密秘钥，保密。在RSA系统中，设m为明文，且明文块的数值大小小于n,c为密文，则其加密和解密算法如下：
加密算法 C=E(m)=me(mod n)
加密算法 m=D(c)=cd(mod n)
在RSA系统中(e,n)构成加密秘钥，即公钥，(d,n) 构成解密秘钥，即私钥。
1.2 RSA思想的证明
RSA是基于数论中的Euler定理和其它同余性质的，在证明RSA系统思想正确性之前，先给出Euler定理和同余式相乘的性质：
Euler定理：设（a,n）=1,即a 和 n互素，则有
图1 加密或解密流程图 |
图2 总的流程图 |
图3 产生密钥流程图 |
|
//////////////////////////////////////////////////////////////////////////////// // 产生第一个大素数 long int iPrimeOne=ProductPrime(); //产生第二个大素数 long int iPrimeTwo=ProductPrime(); //防止产生相同的素数 while(iPrimeTwo==iPrimeOne) { iPrimeTwo=ProductPrime(); } ///////////////////////////////////////////////////////////////////////////////// /*************************** * 产生素数 ****************************/ long int CRSADlg::ProductPrime() { long int iBigPrime=0; //用来保存产生的素数 //产生素数 while(true) { //将素数产生的范围控制在100-----200以内， BigPrime=rand()%100+100; //判断是否为素数,是，跳出循环 if(IsPrime(BigPrime)) break; } return BigPrime; //返回产生的素数 } |
|
#include #include using namespace std; void main() { cout<<"largest long int"<<numeric_limits<long int>::max()<<endl; } //************************************************* // 素数判断. 除到它的开方仍不能被整数，它就是素数 //************************************************* bool CRSADlg::IsPrime(long int iValue) { long int iPrime=iValue; //求这个数开方，加1是为了防止强制类型转换时，使这个数被 //四舍五入后可能少除了最后一个数，故加上1来避免这种误差 long int iSQRT=(long int) sqrt( iPrime)+1; //从2开始到要判断的这个数是否素数的开方+1 for(int i=2;i<iSQRT;i++) { //能够整除，说明不是素数 if((iPrime % i)==0) { return false; } } //都不能整除，说明这个数是素数 return true; } |
|
//************************************************* // 产生加密密钥KEYE,加密密钥的要求 // 2<=iKeyE<=iOrLa-1 // 且iKeyE与iOrLa互素 //************************************************** long int CRSADlg::ProductKEYE(long int iOrLa) { long int keyE=0; while(true) { keyE=rand()%iOrLa; //如果加密密钥大于2，且与欧拉函数公约数为1，即互素满足 if( (keyE>=2) && GCD(keyE,iOrLa)==1) { break; } } return keyE; } //************************** //求两个数的最大公约数 //************************** long int CRSADlg::GCD(long int keyE,long int iOrLa) { long int iDividend=iOrLa; //被除数 long int iDivisor=keyE; //除数 long int iResidual=iDividend%iDivisor; //余数 //碾转相除法 while(iResidual!=0) { //将除数作为被除数 iDividend=iDivisor; //把余数作为除数 iDivisor=iResidual; //求新的余数 iResidual=iDividend%iDivisor; } //最大公约数 return iDivisor; } |
|
1) 求欧拉函数的欧拉函数,欧拉函数的定义是: 1,2,3…………n-1中与n互素的个数称为n的欧拉函数 //************************** //求解欧拉函数的欧拉函数 //************************** long int CRSADlg::IOrLaOfIOrLa(long int iOrLa) { //1与任意的一个数互素故初始化1 long int iOrLaOfiOrLa=1; for(int i=2;i { //根据公式，2……n-1中互素（公约数为1）则欧拉值加1 if(GCD(i,iOrLa)==1) iOrLaOfiOrLa++; } return iOrLaOfiOrLa; } 2) 做高次模运算 //**************************** // 这个函数用来做高次模 //**************************** long int CRSADlg::HightMod(long int iBottomNumber,long int iExponent,long int iMod) { long int iValueMessageAfterCompute=1; long int iValueMessage=iBottomNumber; long int iKey=iExponent; //把key以2进制的形式进行移位乘用 while(iKey) { if(iKey&1) iValueMessageAfterCompute=(iValueMessageAfterCompute*iValueMessage)%iMod; //高位右移 iKey>>=1; iValueMessage=(iValueMessage*iValueMessage)%iMod; } return iValueMessageAfterCompute; } |
|
//*************************** //解密密钥 //************************** long int CRSADlg::ProductKEYD(long int *iOrLaPtr,long int *iKeyEPtr) { //求欧拉函数的欧拉函数 iOrLaOfiOrLa= Φ(Φ(n)) long int iOrLaOfiOrLa=IOrLaOfIOrLa(*iOrLaPtr); //求高次模iKeyE( iOrLaOfiOrLa-1) mod Φ(n) //第一参数为iKeyE,第二个参数为 Φ(Φ(n))-1,第三个参数为 Φ(n) long int iKEYD=HightMod(*iKeyEPtr, iOrLaOfiOrLa-1, *iOrLaPtr); return iKEYD; } 所以,可得解密密钥 //产生解密密钥 long int iKeyD=ProductKEYD(&iOrLa,&iKeyE ); 这里还一种方法可以解解密密钥 因为iKeyD * iKeyE mod iOrLa =1 long int ProductKEYD(long int ikeyE,lont int iOrLa) { long int iKeyD=iOrLa /iKeyE while(true) { if(((iKeyD* iKeyE)%iOrLa)==1) break; else iKeyD++; } return iKeyD; } |
|
//*********************** //做高次模运算 //*********************** long int CEncryptAndDecrypt::GetValues(long int iMessage,long int key) { //保存乘积的模 long int iValueMessageAfterCompute=1; //指数 long int iValueMessage=iMessage; //底数 long int iKey=key; //把key以2进制的形式进行移位相乘做迭代 while(iKey) { //当前的最低位是否为1，是将计算一次乘积 if(iKey&1) iValueMessageAfterCompute=(iValueMessageAfterCompute*ValueMessage)%PUBLICKEY; //高位右移，即指数除以了2 iKey>>=1; //做一次二次方，一直到指数最高位为0为止 iValueMessage=(iValueMessage*iValueMessage)%PUBLICKEY; } return iValueMessageAfterCompute; } |
