/*
* 本程序生成RSA密钥对,最大支持4096位比特:
*
* 该程序参考了网上不少加密资料,对那些公开算法和资料的网友和专家表示
* 深深的谢意
* 本程序没有任何版权,每个人都可以参考使用,希望参考者能把改进后的程序能共享出来,
* 让更多的人学习参考,谢谢!
* 有Bug的话,或者对RSA加解密比较兴趣的网友可以跟俺联系
* e-mail:vagrantseagull@sina.com.cn
xiejunlin@yeah.net
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#include "Prime.h"
#define BIGNUM_INT_MASK 0xFFFFFFFFUL
#define BIGNUM_TOP_BIT 0x80000000UL
#define BIGNUM_INT_BITS 32
#define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
#define BIGNUM_INT_BYTE 8
#define BIGNUM_MAX_BOUND 128U
#define BIGNUM_MAX_DIGIT (BIGNUM_MAX_BOUND + 1)
#define BIGNUM_MAX_BITCOUNT (BIGNUM_MAX_BOUND<<5)//不超过4096位比特的大数
#define BIGNUM_MIN_BITCOUNT (BIGNUM_MAX_BOUND<<1)//不小于256位比特的大数
#define PUBLICKEYLENGTH 10//公钥的比特位数
#define MUL_WORD(w1, w2) ((unsigned __int64)w1 * w2)
#define DIVMOD_WORD(hi,lo,w,q, r) do { \
__asm mov edx, hi \
__asm mov eax, lo \
__asm div w \
__asm mov r, edx \
__asm mov q, eax \
} while(0)
typedef unsigned short int16;
typedef unsigned __int32 int32;
typedef unsigned __int32 BIGNUM[BIGNUM_MAX_BOUND];//不超过4096位比特的大数
static int32 A64[] ={0x00000002,0x4c957f2d,0x5851f42d};//高位在后
BIGNUM SEED64;//随机种子
BIGNUM ZEROVALUE;//大数零值
BIGNUM ONEVALUE;//大数1
BIGNUM TWOVALUE;//大数2
void GetEuclidEquation2(unsigned __int32 a, unsigned __int64 b,unsigned __int32 &x,unsigned __int32 &y);
void GetEuclidGcd(BIGNUM p, BIGNUM q,BIGNUM r);
void GetEuclidEquation(BIGNUM a, BIGNUM b,BIGNUM x,BIGNUM y);
///////////////////////////////////////////////////////////////////////////////
//功能:比较正2^32进制大数大小
//入口参数:
// first----------一个大数
// second----------一个大数
//返回值:1--大于,0--等于,-1--小于
///////////////////////////////////////////////////////////////////////////////
int CompareBigNum( BIGNUM first,BIGNUM second)
{
int iFirst=first[0];
int iSecond=second[0];
if(iFirst>iSecond)
return 1;
if(iFirst<iSecond)
return -1;
for(int i=iFirst;i>=1;--i)
{
if(first[i]>second[i])
return 1;
else if(first[i]<second[i])
return -1;
}
return 0;
}
int CompareBigNum2( BIGNUM first,unsigned __int32 second)
{
int iFirst=first[0];
int iSecond=1;
if(iFirst>iSecond)
return 1;
if(iFirst<iSecond)
return -1;
if(first[1]>second)
return 1;
else if(first[1]==second)
return 0;
else
return -1;
}
void CopyBigNum(BIGNUM dest,BIGNUM src)
{
memcpy(dest,src,sizeof(BIGNUM));
//memcpy(dest,src,(src[0]+1)*32);
}
void CopyBigNum2(BIGNUM dest,unsigned __int64 src)
{
memset(dest,0,sizeof(BIGNUM));
if(src==0)
return;
dest[0]=1;
dest[1]=(unsigned __int32)src;//截断
if((src>>32))
{
dest[0]=2;
//dest[1]=(unsigned __int32)div&0xFFFFFFFF;
dest[2]=(unsigned __int32)(src>>32);
}
return;
}
void CopyBigNum3(BIGNUM dest,unsigned __int32 src)
{
memset(dest,0,sizeof(BIGNUM));
if(src==0)
return;
dest[0]=1;
dest[1]=src;
return;
}
unsigned int GetBigNumBitCount(BIGNUM src)
{
int iLen=0;
iLen=src[0]*BIGNUM_INT_BITS-1;
while (iLen >= 0 && (src[iLen / BIGNUM_INT_BITS + 1] >> (iLen % BIGNUM_INT_BITS)) == 0)
iLen--;
return iLen+1;
}
/*---------------------------------------------------------------------------
功能:该函数用来获取2^32进制的大整数二进制比特位的某一位比特值,
入口参数:大数src,比特位i,i从0开始
返回值:二进制数某一位比特值
----------------------------------------------------------------------------*/
int bignum_get_bit(BIGNUM src, int i)
{
if (i >= (int)(BIGNUM_INT_BITS* src[0]))
return 0; /* 超出界限 */
else
return (src[i / BIGNUM_INT_BITS+ 1] >> (i % BIGNUM_INT_BITS)) & 1;
}
/*
* Set a bit in a bignum; 0 is least significant, etc.
*/
/*---------------------------------------------------------------------------
功能:该函数用来设置2^32进制的大整数二进制比特位的某一位比特值,
入口参数:大数src,比特位i,i从0开始
返回值:二进制数某一位比特值
----------------------------------------------------------------------------*/
void bignum_set_bit(BIGNUM bn, int bitnum, int value)
{
if (bitnum >= (int)(BIGNUM_INT_BITS * bn[0]))
abort(); /* beyond the end */
else {
int v = bitnum / BIGNUM_INT_BITS + 1;
unsigned int mask = 1 << (bitnum % BIGNUM_INT_BITS);
if (value)
bn[v] |= mask;
else
bn[v] &= ~mask;
}
}
/*---------------------------------------------------------------------------
功能:该函数用来将2^32进制的大整数转换成二进制的数,高位在前
入口参数:需转换的大数src,二进制结果pszResult
返回值:二进制位数
----------------------------------------------------------------------------*/
char* BigNumToBinary(BIGNUM src,char *pszResult,int size)
{
unsigned __int32 i(0);
char szdest[33]={0};
unsigned char byte;
memset(pszResult,0,size);
for(i=src[0];i>=1;i--)
{
for(int j=1;j<=32;j++)
{
byte=(unsigned char)(src[i]>>(32-j))&0x1;
szdest[j-1]=byte+'0';
}
//ltoa(src[i],szdest,2);
//printf(" %lu=%s \n",src[i],szdest);
strcat(pszResult,szdest);
}
//printf(" %s \n",pszResult);
return pszResult;
}
/*---------------------------------------------------------------------------
功能:该函数用来将2^32进制的大整数转换成16进制的数,高位在前,低位在后
入口参数:需转换的大数src,16进制结果pszResult
返回值:16进制字符串
----------------------------------------------------------------------------*/
char* BigNumToHex(BIGNUM src,char *pszResult,int size)
{
unsigned __int32 i(0);
unsigned char byte;
char szdest[9]={0};
memset(pszResult,0,size);
for(i=src[0];i>=1;--i)
{
//ultoa(src[i],szdest,16);
for(int j=1;j<=8;j++)
{
byte=(unsigned char)(src[i]>>(32-4*j))&0xF;
if(byte>9 && byte<=15)
{
szdest[j-1]=byte+'A'-10;
}
else
szdest[j-1]=byte+'0';
}
//strcat(pszResult,strupr(szdest));
strcat(pszResult,szdest);
}
return pszResult;
}
/*---------------------------------------------------------------------------
功能:该函数用来将16进制的字符串转换成2^32进制的数,低位在前,高位在后
入口参数:需转换的16进制的字符串pszSrc,2^32进制的数结果dest
返回值:无
----------------------------------------------------------------------------*/
void BigNumFromHex(char *pszSrc,int nsize,BIGNUM dest)
{
unsigned __int32 i(0);
char szdest[9]={0};
unsigned int iLen=strlen(pszSrc);
char cTempChar;
unsigned __int32 byte;
memset(dest,0,sizeof(BIGNUM));
dest[0] = (iLen + BIGNUM_INT_BYTE - 1) / BIGNUM_INT_BYTE; /* char->words */
for (i = iLen;i--;)
{
cTempChar=*pszSrc++;
if(cTempChar>='0'&&cTempChar<='9')
byte =cTempChar-'0' ;
else if(cTempChar>='A'&&cTempChar<='F')
byte =cTempChar-'A'+10 ;
else if(cTempChar>='a'&&cTempChar<='f')
byte =cTempChar-'a' +10;
else
byte=0;//字符不合法
dest[1 + i / BIGNUM_INT_BYTE] |= byte << (4*i % BIGNUM_INT_BITS);
}
while (dest[0] > 1 && dest[dest[0]] == 0)
dest[0]--;
}
//向右移位,相当于a/2^shift
//移位不能超过a的比特长度
void bignum_rightshift1(BIGNUM a, unsigned int shift,BIGNUM c)
{
int alen=a[0];
__int64 temp;
int i,len;
unsigned int iBitCount=0;
memset(c,0,sizeof(BIGNUM));
iBitCount=GetBigNumBitCount(a);
if(alen==0||iBitCount<=shift)//二进制位数<移位数
{
return;
}
BIGNUM result;
len=shift/32;//
if(len>0)
{
for(i=0;i<len;i++)
{
result[i+1]=a[len+i+1];
}
result[0]=alen-len;
}
else
CopyBigNum(result,a);
for(i=1;i<=alen-len;i++)
{
temp=(__int64)a[i];
temp=(temp<<32)+(i+1<=alen-len? a[i+i]:0);
c[i]=(unsigned __int32)temp;
}
if(c[i-i]==0)
{
c[0]=i-2;
}
else
c[0]=i-1;
}
//向右�