📄 main.cpp
字号:
/*
* 本程序生成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;
}
//向右移位，相当于a/2^shift
//移位不能超过a的比特长度
void bignum_rightshift2(BIGNUM a, unsigned int shift,BIGNUM c)
{
int alen=a[0];
int i,len;
int iShift32,iShift1_31;
unsigned int iBitCount=0;
memset(c,0,sizeof(BIGNUM));
iBitCount=GetBigNumBitCount(a);
if(alen==0||iBitCount<=shift)//二进制位数<移位数
{
return;
}
len=(iBitCount-shift+32-1)/32;//移位后的数组长度
BIGNUM result;
memset(result,0,sizeof(BIGNUM));
iShift32=shift/32;//
iShift1_31=shift%32;//
unsigned __int32 high,low;//high为高位，low为低位
high=a[iShift32 + 1];
for (i = 1; i <= len; i++)
{
low = high;
high=(alen>=i + iShift32 + 1 ? a[i + iShift32 + 1]:0);
//c[i]=( (low>>iShift1_31)|(high<<(32-iShift1_31)) )& BIGNUM_INT_MASK;
c[i]=(low>>iShift1_31);
if(iShift1_31)
c[i]|=(high<<(32-iShift1_31));
c[i]&=BIGNUM_INT_MASK;
//result[i]=c[i];
}
for(i=len;i>=1;--i)
{
if(c[i]>0)
{
c[0]=i;
result[0]=i;
return;
}
}
c[0]=0;
//result[0]=0;
}
void bignum_add(BIGNUM summand, BIGNUM addend, BIGNUM c)
{
int alen, blen;
//int mlen = (alen > blen ? alen : blen);
BIGNUM a;//被加数
BIGNUM b;//加数
int i;
unsigned __int32 carry = 0;//进位标志
unsigned __int64 temp;
unsigned __int32 laddend;
if(CompareBigNum(summand,addend) >= 0)
{
CopyBigNum(a,summand);
CopyBigNum(b,addend);
}
else
{
CopyBigNum(b,summand);
CopyBigNum(a,addend);
}
alen = a[0];
blen = b[0];
//保证 a>=b
memset(c,0,sizeof(BIGNUM));
for(i=1;i<=alen;i++)
{
if(i>blen)
{
laddend=0;
}
else
laddend=b[i];
temp=a[i];
temp=temp+laddend+carry;
//temp=(unsigned __int64)a[i]+laddend+carry;
c[i]=(unsigned __int32)temp;//自动溢出
carry=(unsigned __int32)(temp>>32);
/*if(temp>>32)
{
carry=1;
}
else
carry=0;*/
}
if(carry==1)
{
c[i]=1;
c[0]=i;
}
else
c[0]=i-1;
}
void bignum_add_long(BIGNUM a, unsigned __int32 b, BIGNUM c)
{
int alen = a[0] ;
memset(c,0,sizeof(BIGNUM));
int i;
unsigned __int32 carry = 0;//进位标志
unsigned __int64 temp;
unsigned __int32 laddend;//加数
laddend=b;
for(i=1;i<=alen;i++)
{
temp=a[i];
temp=temp+laddend+carry;
c[i]=unsigned __int32 (temp);//自动溢出
carry=(unsigned __int32)(temp>>32);
/*if(temp>>32)
{
carry=1;
}
else
carry=0;*/
laddend=0;
}
if(carry==1)
{
c[i]=1;
c[0]=i;
}
else
c[0]=i-1;
}
/******************************************************************************/
/* */
/* 函数: 实现2^32进制大数加1 */
/* 语法: bignum_Increment(BIGNUM a); */
/* 输入: */
/* a：2^32进制大数 */
/* */
/* 输出: */
/* a：a+1 */
/* 返回: void */
/* 算法： a=a+1 */
/******************************************************************************/
void bignum_Increment(BIGNUM a)
{
int i = 1;
int alen=a[0];
if(alen==0)
{
a[0]=1;
a[1]=1;
return;
}
while (i <= alen && a[i] == 0xFFFFFFFF)
a[i++] = 0;
a[i]++;
if(a[alen]==0)
a[0]=alen+1;
}
/******************************************************************************/
/* */
/* 函数: 实现2^32进制大数减1 */
/* 语法: bignum_Decrement(BIGNUM a); */
/* 输入: */
/* a：2^32进制大数 */
/* */
/* 输出: */
/* a：a-1 */
/* 返回: void */
/* 算法： a=a-1 */
/******************************************************************************/
void bignum_Decrement(BIGNUM a)
{
BIGNUM b;
CopyBigNum(b,a);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -