?? rsa.cpp
字號:
// bmrsa.cpp : Defines the entry point for the console application.
//
#include <string.h>
#include <stdio.h>
#include <time.h>
#include "bignum.h"
#define MAXPRIMECOUNT 1000 // 尋找素?cái)?shù)的最大次數(shù)
unsigned int nSmallPrimes[MAXPRIMECOUNT][2]; // 小素?cái)?shù)數(shù)組
unsigned int nPrimeCount = 0; // 尋找素?cái)?shù)的次數(shù)
// 尋找小素?cái)?shù)
void MakeSmallPrimes()
{
unsigned int n;
unsigned int j;
nPrimeCount = 3;
// 首先定義幾個(gè)小素?cái)?shù)
nSmallPrimes[0][0] = 2;
nSmallPrimes[1][0] = 3;
nSmallPrimes[2][0] = 5;
nSmallPrimes[0][1] = 4;
nSmallPrimes[1][1] = 9;
nSmallPrimes[2][1] = 25;
// 開始尋找素?cái)?shù)
for (n=7; nPrimeCount < MAXPRIMECOUNT; n+=2)
{
for (j=0; nSmallPrimes[j][1] < n; j++)
{
if (j>= nPrimeCount) // 如果大于當(dāng)前素?cái)?shù)組標(biāo)號，則返回
{
return;
}
if (n % nSmallPrimes[j][0]==0) // 如果不是素?cái)?shù)，則退出循環(huán)
{
break;
}
}
// 找到素?cái)?shù)，設(shè)置素?cái)?shù)
if (nSmallPrimes[j][1] > n)
{
nSmallPrimes[nPrimeCount][0] = n;
nSmallPrimes[nPrimeCount++][1] = n*n;
}
}
}
// 生成隨機(jī)大數(shù)
CBigNum GenerateBigRandomNumber(unsigned short nBytes)
{
CBigNum Result=0U; // 初始化大數(shù)
int i;
clock_t ctStart;
unsigned long ctr=0;
// 設(shè)置時(shí)間間隔
clock_t ctInterval = CLOCKS_PER_SEC / 50 + 1;
for (i=0; i<nBytes*2; i++)
{
ctStart = clock();
// 等到大于時(shí)間間隔再開始
while (clock() - ctStart < ctInterval)
ctr++;
ctr = (ctr % 33) & 0xF;
Result <<= 4U; // 大數(shù)左移4位
Result |= ctr; // 做或運(yùn)算
}
putchar('\n');
return Result; // 返回大數(shù)
}
CBigNum FindABigPrime(unsigned short nBytes)
{
CBigNum nBig, nBig2;
DWORD j;
DWORD nTestCount = 0;
DWORD nLehmanCount = 0;
clock_t ctStartTime = clock(); // 記錄開始時(shí)間
DWORD nOffset=0;
bool bPrime=false; // 素?cái)?shù)標(biāo)志位
// 開始尋找對應(yīng)位數(shù)的大素?cái)?shù)
for (nBig = GenerateBigRandomNumber(nBytes) | 1U; !bPrime; nBig+=2U, nOffset+=2)
{
nTestCount++;
for (j=0; j<nPrimeCount; j++)
{
// 如果不是大素?cái)?shù)，則退出循環(huán)
if (nBig % nSmallPrimes[j][0] == 0)
{
break;
}
}
if (j<nPrimeCount)
continue;
nLehmanCount++;
nBig2 = (nBig - 1U) / 2U;
// 設(shè)置一些隨機(jī)的素?cái)?shù)
DWORD arnLehmanPrimes[] = { 89, 5179, 25981, 25439, 25013, 25667, 27397 };
// 初始化大數(shù)組
CBigNum LehmanResults[sizeof(arnLehmanPrimes) / sizeof(arnLehmanPrimes[0])];
nBig2 = nBig - 1U;
bPrime = true;
for (j=0; j<sizeof(arnLehmanPrimes) / sizeof(arnLehmanPrimes[0]); j++)
{
// 開始生成大素?cái)?shù)
LehmanResults[j] =
CBigNum(arnLehmanPrimes[j]).PowMod(nBig2, nBig, CLOCKS_PER_SEC);
if (LehmanResults[j] == nBig2)
{
}
else if (LehmanResults[j] == 1U)
{
}
else // 不是大素?cái)?shù)
{
bPrime = false;
break;
}
}
// 找到大素?cái)?shù)
if (bPrime)
{
break;
}
}
return nBig; // 返回大素?cái)?shù)
}
// 生成公鑰和私鑰
void GenKeyPair(CBigNum &PublicMod, CBigNum &PublicKey, CBigNum &PrivateKey, CBigNum &P, CBigNum &Q, unsigned int nByteCount = 32)
{
if (0U==(P | Q))
{
P=FindABigPrime(nByteCount); // 生成nByteCount位的大素?cái)?shù)
Q=FindABigPrime(nByteCount); // 生成nByteCount位的大素?cái)?shù)
PublicKey=GenerateBigRandomNumber(nByteCount) | 1U;
} else {
PublicKey |= 1U;
}
PrivateKey = (P-1U) * (Q-1U); // 初始化私鑰
while (PublicKey > PrivateKey)
PublicKey=GenerateBigRandomNumber(nByteCount-1) | 1U;
while(CBigNum::gcd(PublicKey,PrivateKey) != 1U) // 生成公鑰
PublicKey+=2; // 累加直至互素
PrivateKey = PublicKey.Inverse(PrivateKey); // 生成私鑰
PublicMod = P*Q; // 公鑰n的生成
}
// 生成特定格式的公鑰和私鑰
void GenerateKeys(CBigNumString &PublicMod, CBigNumString &PublicKey, CBigNumString &PrivateKey, unsigned short nBytes)
{
CBigNum PubMod, PubKey, PriKey, PriP, PriQ;
MakeSmallPrimes();
GenKeyPair(PubMod, PubKey, PriKey, PriP, PriQ, nBytes); // 生成公鑰和私鑰
// 將公鑰和私鑰轉(zhuǎn)換成16進(jìn)制形式
PublicMod = PubMod.ToHexString();
PublicKey = PubKey.ToHexString();
PrivateKey = PriKey.ToHexString();
}
CBigNumString strMod, strPubKey, strPriKey; // 初始化大數(shù)字符變量
// RSA加密函數(shù)
void RSAEncrypt(char *publickey,char *publicmod, char *output, unsigned int *outputlen, char *input, unsigned int inputlen)
{
CBigNum Transform;
CBigNum PubMod, PubKey;
CBigNumString strTransform;
// 將公鑰轉(zhuǎn)換成大數(shù)
PubMod = CBigNum::FromHexString(publicmod);
PubKey = CBigNum::FromHexString(publickey);
// 轉(zhuǎn)換輸入的明文
Transform = Transform.FromByteString(input);
// 使用RSA加密明文
Transform = Transform.PowMod(PubKey,PubMod);
// 將密文轉(zhuǎn)換成16進(jìn)制的字符
strTransform = Transform.ToHexString();
// 輸出密文長度
*outputlen = strlen((const char*)strTransform)+1;
// 輸出密文
memcpy(output,(const char*)strTransform,(*outputlen)+1);
}
// RSA解密
void RSADecrypt(char *output, unsigned int *outputlen, char *input, unsigned int inputlen)
{
CBigNum Transform;
CBigNum PubMod,PriKey;
CBigNumString strTransform;
// 將私鑰轉(zhuǎn)換成大數(shù)
PubMod = CBigNum::FromHexString((const char*)strMod);
PriKey = CBigNum::FromHexString((const char*)strPriKey);
// 轉(zhuǎn)換輸入的密文
Transform = Transform.FromHexString(input);
// 使用RSA對密文進(jìn)行解密
Transform = Transform.PowMod(PriKey,PubMod);
// 將解密文轉(zhuǎn)換成字節(jié)字符串
strTransform = Transform.ToByteString();
// 輸出解密文長度
*outputlen = strlen((const char*)strTransform)+1;
// 輸出解密文
memcpy(output,(const char*)strTransform,(*outputlen)+1);
}
int main(int argc, char* argv[])
{
char pubkey[300]; // 公鑰
char pubmod[300]; // 公鑰
char encrypt_text[300]; // 輸出的密文
char decrypt_text[300]; // 輸出的解密文
unsigned int pubkeylen;
unsigned int encrypt_len;
unsigned int decrypt_len;
char plain_text[50];
strcpy(plain_text,"Welcome to RSA world!");
// 產(chǎn)生公鑰和私鑰
GenerateKeys(strMod,strPubKey,strPriKey,16);
// 設(shè)置公鑰字符串
// 這里轉(zhuǎn)換成char型的是為了在網(wǎng)絡(luò)上傳輸方便
memcpy(pubkey,(const char*)strPubKey,strlen((const char*)strPubKey)+1);
memcpy(pubmod,(const char*)strMod,strlen((const char*)strMod)+1);
// 使用RSA進(jìn)行加密
RSAEncrypt(pubkey,pubmod,encrypt_text,&encrypt_len,plain_text,sizeof(plain_text));
// 使用RSA進(jìn)行解密
RSADecrypt(decrypt_text,&decrypt_len,encrypt_text,encrypt_len);
printf("公鑰n : %s\n",pubmod);
printf("公鑰e : %s\n",pubkey);
printf("\n現(xiàn)在可以把公鑰傳輸給明文所有者進(jìn)行加密\n\n");
printf("加密前的明文:\n");
printf("%s\n\n\n",plain_text);
printf("加密后的密文:\n");
printf("%s\n\n\n",encrypt_text);
printf("解密后的輸出:\n");
printf("%s\n\n\n",decrypt_text);
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -