RSA加解密算法实现
发布时间
阅读量：
阅读量
该代码用于完成大作业中的RSA加密与解密任务，在选择q和p时采用了基于伪随机算法生成大数的方法，并通过素性测试确保其有效性。明文信息被划分为每三个字符一组，在每个块中不足三个字符时，则采用特定方式进行填充。采用的填充方案是PKCS#7格式的标准方法。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
long long int N;
long long int D;
// 生成伪素数
const int MAX_ROW = 50;
size_t Pseudoprime()
{
bool ifprime = false;
size_t a = 0;
int arr[MAX_ROW]; //数组arr为{3，4，5，6...52}
for (int i = 0; i < MAX_ROW; ++i)
{
arr[i] = i + 3;
}
while (!ifprime)
{
srand((unsigned)time(0));
ifprime = true;
a = (rand() % 10000) * 3 + 10000; //生成一个范围在10000到40000里的奇数
for (int j = 0; j < MAX_ROW; ++j)
{
if (a % arr[j] == 0)
{
ifprime = false;
break;
}
}
}
return a;
}
size_t repeatMod(size_t base, size_t n, size_t mod)//模重复平方算法求(b^n)%m
{
size_t a = 1;
while (n)
{
if (n & 1)
{
a = (a * base) % mod;
}
base = (base * base) % mod;
n = n >> 1;
}
return a;
}
//Miller-Rabin素数检测
bool rabinmiller(size_t n, size_t k)
{
int s = 0;
int temp = n - 1;
while ((temp & 0x1) == 0 && temp)
{
temp = temp >> 1;
s++;
} //将n-1表示为(2^s)*t
size_t t = temp;
while (k--) //判断k轮误判概率不大于(1/4)^k
{
srand((unsigned)time(0));
size_t b = rand() % (n - 2) + 2; //生成一个b(2≤a ≤n-2)
size_t y = repeatMod(b, t, n);
if (y == 1 || y == (n - 1))
return true;
for (int j = 1; j <= (s - 1) && y != (n - 1); ++j)
{
y = repeatMod(y, 2, n);
if (y == 1)
return false;
}
if (y != (n - 1))
return false;
}
return true;
}
/*
//简单的素数检测方法
bool isprime(size_t n)
{
if (n == 2)
return true;
for (int i = 2; i <= (int)sqrt((float)n); ++i)
{
if (n % i == 0)
return false;
}
return true;
}*/
// 计算最大公约数
unsigned long long gcd(unsigned long long a, unsigned long long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// 计算模反元素
unsigned long long modInverse(unsigned long long a, unsigned long long m) {
long long m0 = m;
long long y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1) {
long long q = a / m;
long long t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0)
x += m0;
return x;
}
// 快速模幂运算
unsigned long long modExp(unsigned long long base, unsigned long long exponent, unsigned long long modulus) {
unsigned long long result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent & 1) {
result = (result * base) % modulus;
}
exponent = exponent >> 1;
base = (base * base) % modulus;
}
return result;
}
// RSA分段加密函数（包括填充）
unsigned long long* encryptString(const char* plaintext, unsigned long long n, unsigned long long e, int blockSize, int* numBlocks) {
int plaintextLength = strlen(plaintext);
int paddingLength = blockSize - (plaintextLength % blockSize);
*numBlocks = (int)ceil((double)(plaintextLength + paddingLength) / blockSize);
unsigned long long* ciphertext = new unsigned long long[*numBlocks];
for (int i = 0; i < *numBlocks; i++) {
int startIndex = i * blockSize;
int endIndex = (i + 1) * blockSize;
if (endIndex > plaintextLength) {
endIndex = plaintextLength;
}
unsigned long long blockValue = 0;
for (int j = startIndex; j < endIndex; j++) {
blockValue = blockValue * 256 + (unsigned long long)plaintext[j];
}
if (i == (*numBlocks - 1)) {
// 最后一个块进行填充
for (int j = 0; j < paddingLength; j++) {
blockValue = blockValue * 256 + paddingLength;
}
}
ciphertext[i] = modExp(blockValue, e, n);
}
return ciphertext;
}
// RSA分段解密函数（包括去填充）
char* decryptString(unsigned long long* ciphertext, unsigned long long n, unsigned long long d, int blockSize, int numBlocks) {
char* plaintext = new char[numBlocks * blockSize + 1]; // 加1用于存储空终止符
for (int i = 0; i < numBlocks; i++) {
unsigned long long decryptedBlock = modExp(ciphertext[i], d, n);
for (int j = blockSize - 1; j >= 0; j--) {
plaintext[i * blockSize + j] = (char)(decryptedBlock % 256);
decryptedBlock = decryptedBlock / 256;
}
}
// 去除填充的字节
int padding = (int)plaintext[numBlocks * blockSize - 1]; // 最后一个字节表示填充长度
int plaintextLength = numBlocks * blockSize - padding;
plaintext[plaintextLength] = '\0';
return plaintext;
}
void encryptNumber(long M, unsigned long long n, unsigned long long e) {
int r = 1;
e = e + 1;
while (e != 1)
{
r = r * M;
r = r % n;
e--;
}
printf("原始消息：%ld\n", M);
printf("加密后的消息：");
cout << r << endl;
}
// RSA加解密的各个参数
void rsa(int mode) {
cout << "正在生成RSA加密的公钥与私钥，请稍后……" << endl;
unsigned long long int p = 0;
unsigned long long int q = 0;
for (int i = 0; i <= 1; i++) {
size_t ret = Pseudoprime();
if (i == 0 && p == 0) {
if (rabinmiller(ret, 10)) {
cout << "生成的" << ret << "是素数" << endl;
cout << "p为:" << ret << endl;
p = ret;
cout << "------------------------------------------" << endl;
}
else {
i--;
}
}
else if (i == 1 && q == 0 && p != 0) {
if (rabinmiller(ret, 10) && ret != p) {
cout << "生成的" << ret << "是素数" << endl;
cout << "q为:" << ret << endl;
q = ret;
cout << "------------------------------------------" << endl;
}
else {
i--;
}
}
}
unsigned long long int n = p * q; // 计算n
unsigned long long int phi = (p - 1) * (q - 1); // 计算欧拉函数phi(n)
unsigned long long int e = 0;
while (1) {
e = rand() % phi; // 随机选择一个加密指数e
if (gcd(e, phi) == 1) // 确保e和phi互质
break;
}
cout << "n为:" << n << endl;
N = n;
cout << "随机生成e:" << e << endl;
cout << "phi值为:" << phi << endl;
// 计算解密指数d
unsigned long long d = modInverse(e, phi);
printf("私钥 (d): %llu\n", d);
D = d;
cout << "------------------------------------------" << endl;
if (mode == 10) {
char filename[256];
printf("请输入包含明文的本地文件名：");
scanf("%255s", filename);
FILE* file = fopen(filename, "r");
if (file == NULL) {
printf("无法打开文件 %s\n", filename);
return;
}
fseek(file, 0, SEEK_END);
long fileSize = ftell(file);
fseek(file, 0, SEEK_SET);
char* plaintext = (char*)malloc((fileSize + 1) * sizeof(char));
fread(plaintext, sizeof(char), fileSize, file);
plaintext[fileSize] = '\0';
fclose(file);
int blockSize = 3;
int numBlocks;
unsigned long long* encrypted = encryptString(plaintext, n, e, blockSize, &numBlocks);
printf("原始消息：%s\n", plaintext);
printf("加密后的消息：");
for (int i = 0; i < numBlocks; i++) {
printf("%llu ", encrypted[i]);
}
printf("\n");
// 写入txt本地文件中
printf("请输入要保存密文的文件名：");
char filename1[256];
scanf("%255s", filename1);
FILE* file1 = fopen(filename1, "w");
if (file == NULL) {
printf("无法打开文件 %s\n", filename1);
return;
}
for (int i = 0; i < numBlocks; i++) {
fprintf(file1, "%llu ", encrypted[i]);
}
fclose(file1);
printf("密文已保存到文件 %s\n", filename1);
free(plaintext);
free(encrypted);
}
if (mode == 21) {
char plaintext[256];
printf("请输入待加密的明文：");
scanf("%255s", plaintext);
int numBlocks;
unsigned long long* encrypted = encryptString(plaintext, n, e, 3, &numBlocks);
printf("原始消息：%s\n", plaintext);
printf("加密后的消息：");
for (int i = 0; i < numBlocks; i++) {
printf("%llu ", encrypted[i]);
}
cout << endl;
// 写入txt本地文件中
printf("请输入要保存密文的文件名：");
char filename[256];
scanf("%255s", filename);
FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("无法打开文件 %s\n", filename);
return;
}
for (int i = 0; i < numBlocks; i++) {
fprintf(file, "%llu ", encrypted[i]);
}
fclose(file);
printf("密文已保存到文件 %s\n", filename);
free(encrypted);
}
if (mode == 22) {
long M;
cout << "请输入数字：";
scanf("%ld", &M);
encryptNumber(M, n, e);
}
}
//主函数
int main(void)
{
int choice = 0;
while (choice != 3) {
printf(" 欢迎来到RSA加解密系统\n");
cout << "--------------------------------------------------------------------------------------------------------------------" << endl;
printf(" 请选择功能：\n");
printf(" 1. 加密\n");
printf(" 2. 解密\n");
printf(" 3. 退出\n");
printf(" 选择：");
scanf("%d", &choice);
switch (choice) {
case 1: {
int option = 0;
printf("请选择输入方式：\n");
printf("1. 从本地文件读取明文\n");
printf("2. 直接输出明文\n");
printf("选择：");
scanf("%d", &option);
if (option == 1) {
// 从文件读取明文
// char* plainText = readPlainTextFromFile(filename);
// if (plainText == NULL) {
// break;
// }
// free(plainText);
rsa(10); break;
}
else if (option == 2) {
int op = 0;
bool flag = false;
printf(" 请选择输入方式：\n");
printf(" 1. 加密字符串\n");
printf(" 2. 加密数字\n");
printf(" 选择：");
int modeNumber = 22; //加密数字
int modeString = 21; //加密字符串
while (op > -1 && flag == false) {
scanf("%d", &op);
if (op == 1) {
rsa(modeString); flag = 1; break;
}
else if (op == 2)
break;
else {
printf("无效的选择，请重新输入:\n");
}
}
while (op > -1 && flag == false) {
scanf("%d", &op);
if (op == 2) {
rsa(modeNumber); flag = 1; break;
}
else {
printf("无效的选择，请重新输入:\n");
}
}
break;
}
}
//密文进行解密
case 2: {
printf(" 请选择输入方式：\n");
printf(" 1. 从本地文件读取密文\n");
printf(" 2. 直接输出密文\n");
printf(" 选择：");
int option = 0;
scanf("%d", &option);
if (option == 2) {
unsigned long long ciphertext[256];
int numBlocks = 0;
printf("请输入待解密的密文（以空格分隔，换行符停止）：");
while (scanf("%llu", &ciphertext[numBlocks]) == 1) {
numBlocks++;
// 读取并丢弃换行符
if (getchar() == '\n') {
break;
}
}
getchar(); // 清除输入缓冲区中的换行符
// 获取私钥d和n
unsigned long long d, n;
cout << "请输入私钥d和n" << endl;
cout << "d为: ";
cin >> d;
cout << "n为: ";
cin >> n;
// 进行解密操作
char* decrypted = decryptString(ciphertext, n, d, 3, numBlocks);
printf("解密后的消息：%s\n", decrypted);
free(decrypted);
break;
}
else if (option == 1) {
cout <<
"私钥PR={" << D << "," << N << "}" << endl;
printf("请输入要读取的密文文件名：");
char filename[256];
scanf("%255s", filename);
FILE* file = fopen(filename, "r");
if (file == NULL) {
printf("无法打开文件 %s\n", filename);
return 1;
}
unsigned long long* ciphertext = NULL;
int numBlocks = 0;
int c;
// 读取密文数据
unsigned long long block;
while ((c = fgetc(file)) != EOF) {
if (isdigit(c) || c == '-') {
ungetc(c, file);
if (fscanf(file, "%llu", &block) == 1) {
numBlocks++;
ciphertext = (unsigned long long*)realloc(ciphertext, numBlocks * sizeof(unsigned long long));
ciphertext[numBlocks - 1] = block;
}
}
else if (c == ' ') {
continue; // 忽略空格字符
}
}
fclose(file);
char* decrypted = decryptString(ciphertext, N, D, 3, numBlocks);
printf("解密后的明文：%s\n", decrypted);
free(ciphertext);
free(decrypted);
break;
}
}
case 3: {
printf("退出程序。\n");
break;
}
default: {
printf("无效的选择。\n");
break;
}
}
cout << endl;
}
return 0;
}如有雷同，纯数巧合。
全部评论 (0)
还没有任何评论哟~