www.pudn.com > RSA.rar > Rsa.cpp
// RsaA.cpp : implementation file
//
#include "stdafx.h"
#include "Rsa.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CRsaA
IMPLEMENT_DYNCREATE(CRsaA, CCmdTarget)
CRsaA::CRsaA()
{
InitInt();
}
CRsaA::~CRsaA()
{
}
BEGIN_MESSAGE_MAP(CRsaA, CCmdTarget)
//{{AFX_MSG_MAP(CRsaA)
// NOTE - the ClassWizard will add and remove mapping macros here.
//}}AFX_MSG_MAP
//ON_MESSAGE(WM_COMPUTING,OnComputing)
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CRsaA message handlers
/*----------------------------------------------------------------------------
功能：进行相关大数的初始化
入口参数：无
返回值：无
----------------------------------------------------------------------------*/
void CRsaA::InitInt(void)
{
SetZero(ZEROVALUE); //对大数变量zerovalue清零
memset(mZEROVALUE,0,MLENGTH);
SetZero(ONEVALUE); //对大数变量ONEVALUE进行清零
ONEVALUE[DATALENGTH-1]=1; //ONEVALUE的最后一位为1
SetZero(TWOVALUE); //将TOWVALUE进行清零
TWOVALUE[DATALENGTH-1]=2; //TOWVALUE的最后一位为2
SetZero(EIGHTVALUE); //对EIGHTVALUE进行清零
EIGHTVALUE[DATALENGTH-1]=8; //最后一位为8
return ;
}
/*---------------------------------------------------------------------------
功能：将一个大数A转换为相应的字符串形式
入口参数：大数A
返回值：相对应的字符串
----------------------------------------------------------------------------*/
CString CRsaA::PrtInt(byteint A)
{
register i=0;
int m,n;
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 A
int Bvalid=0; //Avalid=validating bits of B
while (A[Avalid]==0 && Avalid=Avalid;i--)
for(j=DATALENGTH-1;j>=Bvalid;j--) //逐位进行相乘运算
{
X=A[i]*B[j];
Y=X/10;
Z=X-10*Y;
w=i+j-(DATALENGTH-1);
C[w]=C[w]+Z;
C[w-1]=C[w-1]+(C[w]/10)+Y;
C[w]=C[w]-(C[w]/10)*10;
}
return;
}
/*---------------------------------------------------------------------------
功能：将指定的自定义的大数进行0初始化
入口参数：大数A名
返回值：无
----------------------------------------------------------------------------*/
void CRsaA::SetZero(byteint A)
{
memset(A,0,DATALENGTH); //调用系统函数进行初始化
}
/*---------------------------------------------------------------------------
功能：将大数B拷贝到大数A中
入口参数：大数A，大数B
返回值：无
----------------------------------------------------------------------------*/
void CRsaA::IntCpy(byteint A,byteint B)
{
memcpy(A,B,DATALENGTH); //调用系统函数完成拷贝
}
/*---------------------------------------------------------------------------
功能：A＋B的结果送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=IntValid(B); //计算B的长度
valid=(m>n)?m+1:n+1; //计算时要以最长的数为准
SetZero(C); //将C清零
for(i=DATALENGTH-1;i>=DATALENGTH-valid;i--)
{
X=A[i]+B[i]; //按位相加
Y=X/10;
Z=X-10*Y;
C[i]=C[i]+Z; //计算进位
C[i-1]=C[i-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,SA); //将SA的内容拷贝到buf中
SetZero(SC); //SC清零初始化
for(i=DATALENGTH-1;i>=0;i--)
{
if(buf[i]0) //如果高位够减，直接减1
(buf[i-1])--;
else //否则一直找到够减的位
{
j=i-1;
while(buf[j]==0) //j不会出现越界，是因为保证了最高位不为0
buf[j--]=9;
buf[j]=buf[j]-1;
}
}
X=buf[i]-SB[i]; //将各位减的结果存入SC中
SC[i]=X;
}
}
/*---------------------------------------------------------------------------
功能：比较两个大数A和B的大小
入口参数：大数A和大数B
返回值：A>B:return 1 ; A=B:return 0 ; A0)
return 1;
return -1;
}
/*---------------------------------------------------------------------------
功能：得到一个大数的非零位数
入口参数：大数validtemp
返回值：大数中非零的位数
----------------------------------------------------------------------------*/
int CRsaA::IntValid(byteint validtemp)
{
register i=0;
while(validtemp[i]==0 && i0) //变除法为减法,每减一次就判断是否有C>B,如果满足就继续减。
{
valid_1=IntValid(C); //计算C(被除数)的位数,因为它的位数在循环过程中是变化的
//做减法后(C-B)仍然存放在C中
valid=valid_1-valid_2; //C的长度与B的长度的差（该值最小为0）
if(valid>0) //如果被除数比除数的位数多
{
i=DATALENGTH-valid_1; //被除数前导零的个数
j=DATALENGTH-valid_2; //除数前导零的个数，作下标指示器
sbits=0;
for(k=j;kB[j]) //从C和B的最高位开始依次比较对应位的大小，判断是否够减
break;
if(C[i]=DATALENGTH-num+1) //循环产生从次低位开始到次高位的所有位上的数
RandomA[i--]=rand()%10;
}
/*---------------------------------------------------------------------------
功能：将质数类型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(j>0) //循环拷贝各位数字
{
A[i--]=B[j--];
}
}
/*---------------------------------------------------------------------------
功能：该函数用来从集合[1,b-1]中产生若干个用于检测的数，存放在Model[]中
入口参数：无
返回值：无
----------------------------------------------------------------------------*/
void CRsaA::Mdata()
{
register i,j; //Randomly choose a set of 100 numbers in [1,b-1]
int k=MLENGTH-2;
memset(Model,0,TESTNUM*MLENGTH); //这个函数在这里用来将整个数组清零，进行初始化
srand( (unsigned)time( NULL ) ); //进行随机函数的初始化
for(i=0;i=k;j--)
{
Model[i][j]=rand()%10; //注意这里与测试素数的程序中的区别，
}
if((memcmp(Model[i],mZEROVALUE,MLENGTH))==0)
i--;
k--; //保证所产生的数不为0
if (k<0) k=MLENGTH-2;
}
}
/*---------------------------------------------------------------------------
功能：该函数用来将十进制的大整数转换成二进制的数
入口参数：需转换的大数B，二进制结果flag[400]
返回值：无
----------------------------------------------------------------------------*/
void CRsaA::TransBi(byteint B,signed char flag[400])
{
byteint buf;
byteint result;
byteint temp;
register i;
SetZero(buf); SetZero(result); SetZero(temp);
memset(flag,0,400); //将flag数组清零
i=399;
IntCpy(buf,B); //将B拷贝到buf中
while(IntCmp(buf,ZEROVALUE)==1) //如果buf内容为0
{
SetMode(buf,TWOVALUE,temp,result); //将buf进行大数的模2运算，商在result中，余数temp
flag[i]=temp[DATALENGTH-1];
IntCpy(buf,result); //对商继续进行模2运算
i--;
}
flag[i]=-1; //设置一个标志位，表明二进制数的开始
}
/*---------------------------------------------------------------------------
功能：该函数用来进行模幂算法，A为底数，模为c，二进制的指数B存放在数组flag中
入口参数：底数A，模C，结果D，二进制质数flag[400]
返回值：A^B=1(mod C),返回1；A^B=p-1(mod C),返回2；否则返回0
----------------------------------------------------------------------------*/
int CRsaA::PowerMode(byteint A,byteint C,byteint D,signed char flag[400])
{
byteint buf;
byteint result;
byteint temp,P;
register i;
SetZero(D); SetZero(buf); SetZero(result); SetZero(temp); SetZero(P); //将D清零
IntCpy(temp,A); //将A的值拷贝到temp中
if(flag[399]==1) //最低位为1，拷贝本身，flag[i]只有1或者0两种情况
IntCpy(result,A);
else //最低位为0，则幂为1
IntCpy(result,ONEVALUE);
i=398;
while(flag[i]!=-1) //判断是否已经到达指数尽头
{
Multiply(temp,temp,buf); //temp*temp->buf
SetMode(buf,C,temp,P); //buf%c余数->temp,商->p
if(flag[i]!=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) //p mod n=1，判断是否有A^B=1(mod C)
return 1;
if(IntCmp(result,temp)==0) //p mod n=-1[p-1=-1(mod p)]，判断是否有A^B=p-1(mod C)
return 2;
return 0;
}
/*---------------------------------------------------------------------------
功能：产生一个质数
入口参数：大数Prm
返回值：产生成功，返回0
----------------------------------------------------------------------------*/
int CRsaA::Prime(byteint Prm)
{
int i,k,ok;
signed char flag[400];
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 ) ); //初始化srand
IntRandom(B,MLENGTH); //随机产生一个大数B try b if prime,B是一个奇数
IntCpy(Prm,B); //将B拷贝到prm中 C=N result prime
Substract(B,ONEVALUE,buf1); //将B-ONEVALUE的结果放到buf1中
SetMode(buf1,TWOVALUE,buf2,B); //B=(B-1)/2的商,buf2=(B-1)/2的余数=0
TransBi(B,flag); //将B转换为二进制大数
ok=1;
for(i=0;iD
if(k!=1 && k!=2) //不符合判定规则
{
ok=0;
break;
}
if(k==1) //判定条件1，G=A^(n-1)/2=1
{
}
if(k==2) //判定条件2，G=A^(n-1)/2=p-1
{
}
}
if (ok)//if(ok && pass_2)
{
return 0;
}//for循环用来检测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(1)
{
IntRandom(SK,SKLENGTH); //随机产生一个大数奇数作为Generated secret key
IntCpy(PB,SK);
IntCpy(PA,Rvalue);
while(1)
{
SetMode(PA,PB,PC,PK); //PA=PB*PK+PC
i=IntCmp(PC,ONEVALUE);
if(i==0) //PC=1, i=0
break; //满足条件，是互质的
i=IntCmp(PC,ZEROVALUE);
if(i==0)
{
i=-1; //PC=0,i=-1
break; //不满足互质条件，跳出循环，从新生成一个随机数
}
IntCpy(PA,PB); //按照欧几里的定理继续判断
IntCpy(PB,PC);
}
if(i==0) //满足，跳出查找循环
break;
}
IntCpy(temp,ONEVALUE);
IntCpy(PA,Rvalue);
IntCpy(PB,SK);
while(1)
{
Multiply(PA,temp,buf1); //buf1=PA*temp
Plus(buf1,ONEVALUE,buf2);//buf2=(PA*temp)+1
SetMode(buf2,PB,buf1,PK);//buf=((PA*temp)+1)%PB
if(IntCmp(buf1,ZEROVALUE)==0)
break;
Plus(temp,ONEVALUE,buf1);
IntCpy(temp,buf1);
}
return 1; //SK and PK found
}
/*---------------------------------------------------------------------------
功能：计算模R
入口参数：产生的质数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); // buf1=p-1
Substract(q,ONEVALUE,buf2); // buf2=q-1
Multiply(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;
else
{
for(int j=0;j='0'&&(*(pstr+3-i))<='9')
j = (*(pstr+3-i)) - '0';
if( (*(pstr+3-i))>='a'&&(*(pstr+3-i))<='f')
j = (*(pstr+3-i)) - 'a'+10;
if( (*(pstr+3-i))>='A'&&(*(pstr+3-i))<='F')
j = (*(pstr+3-i)) - 'A'+10;*/
ch += j*k;
k*=256;
}
return ch;
}
/*---------------------------------------------------------------------------
功能：将数串转换为相应的字符串
入口参数：字符串str
返回值：返回转换的结果；
----------------------------------------------------------------------------*/
CString CRsaA::Ip2os(CString str)
{
int strlen=str.GetLength(),quotient=0,remainder=0;
unsigned long num=0,temp=0;
unsigned int k=1;
CString strResult="";
for(int i=strlen;i>0;i--) //得到相应的数字串,存放在num中
{
temp = (str.GetAt(i-1) - '0');
num += temp*k;
k *= 10;
}
//采用模除的方式,求得相应的十六进制数
for(int j=0;j<4;j++)
{
quotient = num/256;
remainder = num - quotient*256;
/*if(remainder>=0&&remainder<=9)
strResult.Insert(0,(remainder+'0'));
if(remainder>=10&&remainder<=15)
strResult.Insert(0,(remainder-10+'a'));*/
strResult.Insert(0,(unsigned char)remainder);
num = 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("开始计算质数P...");
Prime(m_p); //生成素数p q
AfxMessageBox("开始计算质数Q...");
Prime(m_q);*/
int i;
int k_p[]={3,4,0,2,8,2,3,6,6,9,2,0,9,3,8,4,6,3,4,6,3,3,7,4,6,0,7,4,3,1,7,6,8,2,1,1,2,9,7};
int k_q[]={2,5,5,2,1,1,7,7,5,1,9,0,7,0,3,8,4,7,5,9,7,5,3,0,9,5,5,5,7,3,8,2,6,1,5,8,5,7,9};
for(i = 0; i< 39; i++)
{
m_p[256-i] = k_p[38-i];
m_q[256-i] = k_q[38-i];
}
AfxMessageBox("开始计算模R...");
ComputingR(m_p,m_q,m_R); //计算模R
AfxMessageBox("开始计算模r");
ComputingRvalue(m_p,m_q,m_Rvalue); //计算r
AfxMessageBox("开始计算秘钥SK,PK");
ComputingPK(m_Rvalue,m_PK,m_SK); // Generate PK and SK
//CGenKeyBusyDlg dlg1;
//g1.DoModal();
R=PrtInt(m_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(aa);
//SetZero(bb);
SetZero(m_key);
SetZero(m_R);
pstr = (unsigned char*)(LPCTSTR)source; //得到字符串数据的指针
j = source.GetLength()/4; //得到数组的元素个数
result.SetSize(j,1);
Getinput(m_key,key); //将字符串转换为大数类型
Getinput(m_R,R);
for(int i=0;i