?? rsaa.cpp
字號:
// RsaA.cpp : implementation file
#include "RsaA.h"
#include <iostream.h>
/////////////////////////////////////////////////////////////////////////////
// CRsaA
CRsaA::CRsaA()
{
InitInt();
}
CRsaA::~CRsaA()
{
}
/////////////////////////////////////////////////////////////////////////////
// CRsaA message handlers
/*----------------------------------------------------------------------------
功能：進行相關大數(shù)的初始化
入口參數(shù)：無
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::InitInt(void)
{
SetZero(ZEROVALUE); //對大數(shù)變量zerovalue清零
memset(mZEROVALUE,0,MLENGTH);
SetZero(ONEVALUE); //對大數(shù)變量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 ;
}
/*---------------------------------------------------------------------------
功能：將一個大數(shù)A轉(zhuǎn)換為相應的字符串形式
入口參數(shù)：大數(shù)A
返回值：相對應的字符串
----------------------------------------------------------------------------*/
//該函數(shù)
signed char* CRsaA::PrtInt(byteint A)
{
register i=0;
int m,n;
while(i<DATALENGTH && A[i]==0) //跳過大數(shù)開始的空白0
i++;
if(i<DATALENGTH)
m=DATALENGTH-i; //求出有用的大數(shù)長度
n=0;
//注意到這里的i已經(jīng)是數(shù)組中第一個非零元素的對應位置，
// CString str=""; //因此下面的循環(huán)就是從數(shù)組中
//存放的數(shù)的最高位開始輸出。
// unsigned char b[DATALENGTH];
signed char b[DATALENGTH];
for(int j=0;i<DATALENGTH;i++)
{
b[j++]=A[i];
}
return b;
// while(i<DATALENGTH)
// {
// str += (A[i++]+'0');
// }
// return str;
}
/*---------------------------------------------------------------------------
功能：大數(shù)A與大數(shù)B相乘，結(jié)果放入C中 A×B->C
入口參數(shù)：被乘數(shù)A和乘數(shù)B，結(jié)果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<DATALENGTH)
Avalid++; //計算Avalid
while (B[Bvalid]==0 && Bvalid<DATALENGTH)
Bvalid++; //計算Bvalid
SetZero(C); //將C清零初始化
for(i=DATALENGTH-1;i>=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;
}
/*---------------------------------------------------------------------------
功能：將指定的自定義的大數(shù)進行0初始化
入口參數(shù)：大數(shù)A名
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::SetZero(byteint A)
{
memset(A,0,DATALENGTH); //調(diào)用系統(tǒng)函數(shù)進行初始化
}
/*---------------------------------------------------------------------------
功能：將大數(shù)B拷貝到大數(shù)A中
入口參數(shù)：大數(shù)A，大數(shù)B
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::IntCpy(byteint A,byteint B)
{
memcpy(A,B,DATALENGTH); //調(diào)用系統(tǒng)函數(shù)完成拷貝
}
/*---------------------------------------------------------------------------
功能：A＋B的結(jié)果送C
入口參數(shù)：大數(shù)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; //計算時要以最長的數(shù)為準
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;
}
}
/*---------------------------------------------------------------------------
功能：大數(shù)SA減去大數(shù)SB，結(jié)果放入SC
入口參數(shù)：被減數(shù)SA，減數(shù)SB，差SC
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::Substract(byteint SA,byteint SB,byteint SC)
{
byteint buf;
register i,j;
int X;
IntCpy(buf,SA); //將SA的內(nèi)容拷貝到buf中
SetZero(SC); //SC清零初始化
for(i=DATALENGTH-1;i>=0;i--)
{
if(buf[i]<SB[i]) //如果最低位不夠減
{
buf[i]=buf[i]+10; //向高位借1
if(buf[i-1]>0) //如果高位夠減，直接減1
(buf[i-1])--;
else //否則一直找到夠減的位
{
j=i-1;
while(buf[j]==0) //j不會出現(xiàn)越界，是因為保證了最高位不為0
buf[j--]=9;
buf[j]=buf[j]-1;
}
}
X=buf[i]-SB[i]; //將各位減的結(jié)果存入SC中
SC[i]=X;
}
}
/*---------------------------------------------------------------------------
功能：比較兩個大數(shù)A和B的大小
入口參數(shù)：大數(shù)A和大數(shù)B
返回值：A>B:return 1 ; A=B:return 0 ; A<B:return -1
----------------------------------------------------------------------------*/
int CRsaA::IntCmp(byteint A,byteint B)
{
int stat;
stat=memcmp(A,B,DATALENGTH); //系統(tǒng)函數(shù)
if(stat==0)
return 0;
if(stat>0)
return 1;
return -1;
}
/*---------------------------------------------------------------------------
功能：得到一個大數(shù)的非零位數(shù)
入口參數(shù)：大數(shù)validtemp
返回值：大數(shù)中非零的位數(shù)
----------------------------------------------------------------------------*/
int CRsaA::IntValid(byteint validtemp)
{
register i=0;
while(validtemp[i]==0 && i<DATALENGTH)
i++;
return DATALENGTH-i;
}
/*---------------------------------------------------------------------------
功能：計算大數(shù)A÷B的結(jié)果，余數(shù)放在C中，商在D中
入口參數(shù)：被除數(shù)A，除數(shù)B，余數(shù)C，商D
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::SetMode(byteint A,byteint B,byteint C,byteint D)
{
register i,j,k;
int valid_1,valid_2,valid,sbits,cmpval;
byteint buf1,buf2;
SetZero(buf1); SetZero(buf2);
SetZero(D); //將大數(shù)D進行清零初始化
IntCpy(C,A); //將被除數(shù)A拷貝到C中
valid_2=IntValid(B); //計算B(除數(shù))的位數(shù),
while((cmpval=IntCmp(C,B))>0) //變除法為減法,每減一次就判斷是否有C>B,如果滿足就繼續(xù)減。
{
valid_1=IntValid(C); //計算C(被除數(shù))的位數(shù),因為它的位數(shù)在循環(huán)過程中是變化的
//做減法后(C-B)仍然存放在C中
valid=valid_1-valid_2; //C的長度與B的長度的差（該值最小為0）
if(valid>0) //如果被除數(shù)比除數(shù)的位數(shù)多
{
i=DATALENGTH-valid_1; //被除數(shù)前導零的個數(shù)
j=DATALENGTH-valid_2; //除數(shù)前導零的個數(shù)，作下標指示器
sbits=0;
for(k=j;k<DATALENGTH;k++)
{
if(C[i]>B[j]) //從C和B的最高位開始依次比較對應位的大小，判斷是否夠減
break;
if(C[i]<B[j])
{
sbits=1; //如果不夠減，那么C就退一位，再做減法
break;
}
i++;j++; //當C和B的最高位相等時,就比較二者的次高位
}
valid=valid-sbits;
SetZero(buf1); //buf1清零
for(i=valid;i<DATALENGTH;i++)
{
j=i-valid;
buf1[j]=B[i]; //buf1中存放的是B左移若干位之后得到的值
//如果夠減,則B左移后最高位與C的最高位對齊,
//否則與C的次高位對齊
}
}
else
IntCpy(buf1,B); //當C和B的位數(shù)相同時,就直接把B放入緩沖區(qū)buf1中
D[DATALENGTH-1-valid]++; //這里保存的是在某一位上所做的減法的次數(shù)，每做一次就加1
Substract(C,buf1,buf2); //不論C的長度與B的長度的差是否大于0，都要做減法，直到C<=B
IntCpy(C,buf2);
}
if(cmpval==0) //兩個數(shù)相等
{
SetZero(C); //余數(shù)為0
D[DATALENGTH-1]++; //商為1
}
}
/*---------------------------------------------------------------------------
功能：隨機地產(chǎn)生一個大數(shù)奇數(shù)，長度為num，最高位不是0，存放在RandomA中
入口參數(shù)：大數(shù)A，長度num
返回值：無
----------------------------------------------------------------------------*/
void CRsaA::IntRandom(byteint RandomA,int num)
{
int i;
SetZero(RandomA); //將RandomA清零
while(!(RandomA[DATALENGTH-1]%2)) //判斷條件保證RandomA的最后一位數(shù)是奇數(shù)
RandomA[DATALENGTH-1]=rand()%10; //如果最后一位是偶數(shù)，則從新產(chǎn)生最后一位
while(!(RandomA[DATALENGTH-num])) //判斷條件保證RandomA最高位不是0
RandomA[DATALENGTH-num]=rand()%10;//如果最高位是0,則從新產(chǎn)生最高位
i=DATALENGTH-2;
while(i>=DATALENGTH-num+1) //循環(huán)產(chǎn)生從次低位開始到次高位的所有位上的數(shù)
RandomA[i--]=rand()%10;
}
/*---------------------------------------------------------------------------
功能：將質(zhì)數(shù)類型B拷貝到A中，實現(xiàn)類型轉(zhuǎn)換
入口參數(shù)：大數(shù)A，質(zhì)數(shù)類型B
返回值：無
----------------------------------------------------------------------------*/
//功能：將數(shù)B拷貝到大數(shù)A，實現(xiàn)類型轉(zhuǎn)換
void CRsaA::LoadInt(byteint A,mtype B)
{
register i,j;
SetZero(A); //A進行清零初始化
i=DATALENGTH-1;
j=MLENGTH-1;
while(j>0) //循環(huán)拷貝各位數(shù)字
{
A[i--]=B[j--];
}
}
/*---------------------------------------------------------------------------
功能：該函數(shù)用來從集合[1,b-1]中產(chǎn)生若干個用于檢測的數(shù)，存放在Model[]中
入口參數(shù)：無
返回值：無
----------------------------------------------------------------------------*/
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); //這個函數(shù)在這里用來將整個數(shù)組清零，進行初始化
srand( (unsigned)time( NULL ) ); //進行隨機函數(shù)的初始化
for(i=0;i<TESTNUM;i++) //TESTNUM為需要產(chǎn)生的個數(shù)
{
for(j=MLENGTH-1;j>=k;j--)
{
Model[i][j]=rand()%10; //注意這里與測試素數(shù)的程序中的區(qū)別，
}
if((memcmp(Model[i],mZEROVALUE,MLENGTH))==0)
i--;
k--; //保證所產(chǎn)生的數(shù)不為0
if (k<0) k=MLENGTH-2;
}
}
/*---------------------------------------------------------------------------
功能：該函數(shù)用來將十進制的大整數(shù)轉(zhuǎn)換成二進制的數(shù)
入口參數(shù)：需轉(zhuǎn)換的大數(shù)B，二進制結(jié)果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數(shù)組清零
i=399;
IntCpy(buf,B); //將B拷貝到buf中
while(IntCmp(buf,ZEROVALUE)==1) //如果buf內(nèi)容為0
{
SetMode(buf,TWOVALUE,temp,result); //將buf進行大數(shù)的模2運算，商在result中，余數(shù)temp
flag[i]=temp[DATALENGTH-1];
IntCpy(buf,result); //對商繼續(xù)進行模2運算
i--;
}
flag[i]=-1; //設置一個標志位，表明二進制數(shù)的開始
}
/*---------------------------------------------------------------------------
功能：該函數(shù)用來進行模冪算法，A為底數(shù)，模為c，二進制的指數(shù)B存放在數(shù)組flag中
入口參數(shù)：底數(shù)A，模C，結(jié)果D，二進制質(zhì)數(shù)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) //判斷是否已經(jīng)到達指數(shù)盡頭
{
Multiply(temp,temp,buf); //temp*temp->buf
SetMode(buf,C,temp,P); //buf%c余數(shù)->temp,商->p
if(flag[i]!=0) //如果該位不是0，則將其和前一步低一位的結(jié)果進行乘法運算
{ //否則，將其作為該位的模，在高一位的運算中，只要進行一次
Multiply(temp,result,buf); //平方運算，就可以得到高一位的模
SetMode(buf,C,result,P);
}
i--;
} //result中存放的是最終結(jié)果
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;
}
/*---------------------------------------------------------------------------
功能：產(chǎn)生一個質(zhì)數(shù)
入口參數(shù)：大數(shù)Prm
返回值：產(chǎn)生成功，返回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) //一直循環(huán)直到找到一個素數(shù)為止
{
int pass=0;
srand( (unsigned)time( NULL ) ); //初始化srand
IntRandom(B,MLENGTH); //隨機產(chǎn)生一個大數(shù)B try b if prime,B是一個奇數(shù)
IntCpy(Prm,B); //將B拷貝到prm中 C=N result prime
Substract(B,ONEVALUE,buf1); //將B-ONEVALUE的結(jié)果放到buf1中
SetMode(buf1,TWOVALUE,buf2,B); //B=(B-1)/2的商,buf2=(B-1)/2的余數(shù)=0
TransBi(B,flag); //將B轉(zhuǎn)換為二進制大數(shù)
ok=1;
for(i=0;i<TESTNUM;i++)
{
LoadInt(A,Model[i]); //將數(shù)組Model中的第i+1個數(shù)讀取到A中
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -