C语言实现RSA算法加解密

使用c语言实现了RSA加解密算法，可以加解密文件和字符串。

rsa算法原理

• 选择两个大素数p和q；
• 计算n = p * q;
• 计算φ(n)=(p-1)(q-1)；
• 选择与φ(n)互素的整数d；
• 由de=1 mod φ(n)计算得到e；
• 公钥是(e, n), 私钥是(d, n);
• 假设明文是M（一个整数），则密文C =  mod n，此为加密过程；
• 解密过程为M =  mod n;

rsa.h

#pragma once
#include <iostream>
#include <fstream>
#include <tommath.h>
#include <time.h>
#include <Windows.h>
#include <string>#define SUBKEY_LENGTH 78  //  >512 bit#define FILE_NAME_LENGTH 99#define PLAINTEXT_LENGTH 64#define BINARY_LENGTH 512using namespace std;void initial();int Get_char_bit(char c, int pos);void Create_prime_number(mp_int *number);void Generate_key(char *key_name);void Write_key_2_File(char *file_name, mp_int *key, mp_int *n);void ADD_0(char *binary, int mode);void rsa_decrypt(char *src, char *dst, char *key_name, int mode);void rsa_encrypt(char *src, char *dst, char *key_name, int mode);void mp_print(mp_int *number);void Get_key_from_file(mp_int *key, mp_int *n, char *key_name, int mode);void Create_number(mp_int *number, int mode);int Miller_rabin(mp_int *number);void Char_2_binary(char *text, char *binary, int len);void Binary_2_char(char *binary, char *text, int binary_len);void quick_pow(mp_int *a, mp_int *b, mp_int *c, mp_int *d);int Get_file_length(char *filename);

rsa.cpp

#include "rsa.h"mp_int two;
mp_int five;
mp_int zero;
mp_int one;int Get_char_bit(char c, int pos)
{return ((c >> (7 - pos)) & 1);
}// mode 0: number of n digits
// mode 1: 2 <= number <= n - 2  for miller rabin test
void Create_number(mp_int *number, int mode)
{int i;srand((unsigned)time(NULL));char temp_number[SUBKEY_LENGTH + 1];temp_number[0] = rand() % 9 + 1 + 48;if (0 == mode){int temp;for (i = 1; i <= SUBKEY_LENGTH - 2; i++)temp_number[i] = rand() % 10 + 48;temp = rand() % 10;if (0 == temp % 2)temp++;if (5 == temp)temp = 7;temp_number[SUBKEY_LENGTH - 1] = temp + 48;temp_number[SUBKEY_LENGTH] = '\0';}else if (1 == mode){int digit = rand() % (SUBKEY_LENGTH - 2) + 2;for (i = 1; i <= digit - 1; i++)temp_number[i] = rand() % 10 + 48;temp_number[digit] = '\0';}mp_read_radix(number, temp_number, 10);
}int Miller_rabin(mp_int *number)
{int result;mp_int base;mp_init_size(&base, SUBKEY_LENGTH);Create_number(&base, 1);mp_prime_miller_rabin(number, &base, &result);mp_clear(&base);return result;
}void Create_prime_number(mp_int *number)
{mp_int r;mp_init(&r);int time = 100;int result;int i;Create_number(number, 0);while (1){mp_prime_is_divisible(number, &result);if (0 != result){do{mp_add(number, &two, number);mp_mod(number, &five, &r);} while (MP_EQ == mp_cmp_mag(&zero, &r));continue;}for (i = 0; i < time; i++){if (!Miller_rabin(number))break;}if (i == time)return;else{do{mp_add(number, &two, number);mp_mod(number, &five, &r);} while (MP_EQ == mp_cmp_mag(&zero, &r));}}
}void Generate_key(char *key_name)
{mp_int p, q, n, f, e, d;mp_init_size(&p, SUBKEY_LENGTH);mp_init_size(&q, SUBKEY_LENGTH);mp_init_size(&n, SUBKEY_LENGTH * 2);mp_init_size(&f, SUBKEY_LENGTH * 2);mp_init_size(&d, SUBKEY_LENGTH * 2);mp_init_size(&e, SUBKEY_LENGTH * 2);Create_prime_number(&p);Sleep(1000);Create_prime_number(&q);mp_mul(&p, &q, &n);mp_sub(&p, &one, &p);mp_sub(&q, &one, &q);mp_mul(&p, &q, &f);mp_set_int(&d, 127);mp_int gcd;mp_init_size(&gcd, SUBKEY_LENGTH * 2);do{mp_add(&d, &two, &d);mp_gcd(&d, &f, &gcd);} while (MP_EQ != mp_cmp_mag(&gcd, &one));mp_invmod(&d, &f, &e);char PUBLIC_KEY[FILE_NAME_LENGTH] = "d:\\public_key_";char PRIVATE_KEY[FILE_NAME_LENGTH] = "d:\\private_key_";strcat(PUBLIC_KEY, key_name);strcat(PRIVATE_KEY, key_name);Write_key_2_File(PUBLIC_KEY, &d, &n);Write_key_2_File(PRIVATE_KEY, &e, &n);mp_clear_multi(&p, &q, &e, &d, &f, &n, &gcd, NULL);
}void initial()
{mp_init_set_int(&two, 2);mp_init_set_int(&five, 5);mp_init_set_int(&zero, 0);mp_init_set_int(&one, 1);
}void Write_key_2_File(char *file_name, mp_int *key, mp_int *n)
{remove(file_name);FILE *fp = fopen(file_name, "w+");if (NULL == fp){cout << "open file error!" << endl;return;}char key_str[SUBKEY_LENGTH * 2 + 1];char n_str[SUBKEY_LENGTH * 2 + 1];mp_toradix(key, key_str, 10);mp_toradix(n, n_str, 10);fprintf(fp, "%s\n", n_str);fprintf(fp, "%s", key_str);fclose(fp);
}void mp_print(mp_int *number)
{char str[SUBKEY_LENGTH * 2 + 1];mp_toradix(number, str, 10);cout << str << endl;
}// mode 0: get public key
// mode 1: get private keyvoid Get_key_from_file(mp_int *key, mp_int *n, char *key_name, int mode)
{FILE *fp = NULL;char PUBLIC_KEY[FILE_NAME_LENGTH] = "";char PRIVATE_KEY[FILE_NAME_LENGTH] = "";if (0 == mode){strcat(PUBLIC_KEY, key_name);fp = fopen(PUBLIC_KEY, "r+");}else if (1 == mode){strcat(PRIVATE_KEY, key_name);fp = fopen(PRIVATE_KEY, "r+");}if (NULL == fp){cout << "open file error!" << endl;return;}char key_str[SUBKEY_LENGTH * 2 + 1];char n_str[SUBKEY_LENGTH * 2 + 1];fscanf(fp, "%s\n", n_str);fscanf(fp, "%s", key_str);mp_read_radix(n, n_str, 10);mp_read_radix(key, key_str, 10);fclose(fp);
}void Char_2_binary(char *text, char *binary, int len)
{int i;int j;int k = 0;for (i = 0; i <= len - 1; i++){for (j = 0; j <= 7; j++)binary[k++] = Get_char_bit(text[i], j) + '0';}binary[k] = '\0';
}void Binary_2_char(char *binary, char *text, int binary_len)
{int i;int j = 0;int k = 0;int sum = 0;for (i = 0; i <= binary_len - 1; i++){sum = sum + pow(2, 7 - j)*(int)((binary[i]) - '0');j++;if (8 == j){text[k++] = sum;sum = 0;j = 0;}}
}// mode 0: encrypt char*
// mode 1: encrypt file
void rsa_encrypt(char *src, char *dst, char *key_name, int mode)
{mp_int n;mp_int public_key;mp_int plain_number;mp_int cipher_number;mp_init_size(&n, SUBKEY_LENGTH * 2);mp_init_size(&public_key, SUBKEY_LENGTH * 2);mp_init_size(&plain_number, SUBKEY_LENGTH * 2);mp_init_size(&cipher_number, SUBKEY_LENGTH * 2);Get_key_from_file(&public_key, &n, key_name, 0);char plain_text[PLAINTEXT_LENGTH + 1];char cipher_text[PLAINTEXT_LENGTH + 2];char plain_binary[BINARY_LENGTH + 1];char cipher_binary[BINARY_LENGTH + 9];int i;int j;int k;int l;if (0 == mode){int round = ceil(strlen(src) / 64.0);for (i = 0; i < round; i++){for (l = 0; l <= BINARY_LENGTH; l++)plain_binary[l] = '\0';for (l = 0; l <= BINARY_LENGTH + 8; l++)cipher_binary[l] = '\0';for (l = 0; l <= PLAINTEXT_LENGTH; l++)plain_text[l] = '\0';for (l = 0; l <= PLAINTEXT_LENGTH + 1; l++)cipher_text[l] = '\0';for (j = 0; j <= PLAINTEXT_LENGTH - 1; j++){plain_text[j] = src[i * PLAINTEXT_LENGTH + j];if ('\0' == plain_text[j]){for (k = j + 1; k <= PLAINTEXT_LENGTH - 1; k++)plain_text[k] = '\0';break;}}plain_text[PLAINTEXT_LENGTH] = '\0';Char_2_binary(plain_text, plain_binary, PLAINTEXT_LENGTH);mp_zero(&plain_number);mp_read_radix(&plain_number, plain_binary, 2);mp_zero(&cipher_number);// ----------------------------------------------------------------mp_exptmod(&plain_number, &public_key, &n, &cipher_number);//quick_pow(&plain_number, &public_key, &n, &cipher_number);// ----------------------------------------------------------------mp_toradix(&cipher_number, cipher_binary, 2);ADD_0(cipher_binary, 0);Binary_2_char(cipher_binary, cipher_text, BINARY_LENGTH + 8);for (l = 0; l <= PLAINTEXT_LENGTH; l++)dst[i*(PLAINTEXT_LENGTH + 1) + l] = cipher_text[l];}dst[round * (PLAINTEXT_LENGTH + 1)] = '\0';mp_clear_multi(&n, &public_key, &plain_number, &cipher_number, NULL);}else if (1 == mode){ifstream fin;ofstream fout;fin.open(src, ios::binary);fout.open(dst, ios::binary);char ch;int i = 0;int len = Get_file_length(src) % 64;fout << len << endl;while (1){fin.get(ch);plain_text[i++] = ch;if (i == PLAINTEXT_LENGTH || fin.eof()){if (i == PLAINTEXT_LENGTH)plain_text[i] = '\0';else{for (k = i - 1; k <= PLAINTEXT_LENGTH; k++)plain_text[k] = '\0';}for (l = 0; l <= BINARY_LENGTH; l++)plain_binary[l] = '\0';for (l = 0; l <= BINARY_LENGTH + 8; l++)cipher_binary[l] = '\0';for (l = 0; l <= PLAINTEXT_LENGTH + 1; l++)cipher_text[l] = '\0';Char_2_binary(plain_text, plain_binary, PLAINTEXT_LENGTH);mp_zero(&plain_number);mp_read_radix(&plain_number, plain_binary, 2);mp_zero(&cipher_number);// ----------------------------------------------------------------mp_exptmod(&plain_number, &public_key, &n, &cipher_number);//quick_pow(&plain_number, &public_key, &n, &cipher_number);// ----------------------------------------------------------------mp_toradix(&cipher_number, cipher_binary, 2);ADD_0(cipher_binary, 0);Binary_2_char(cipher_binary, cipher_text, BINARY_LENGTH + 8);for (l = 0; l <= PLAINTEXT_LENGTH; l++)fout << cipher_text[l];for (l = 0; l <= PLAINTEXT_LENGTH; l++)plain_text[l] = '\0';i = 0;}if (fin.eof())break;}fin.close();fout.close();mp_clear_multi(&n, &public_key, &plain_number, &cipher_number, NULL);}
}// mode 0: for encrypt
// mode 1: for decrypt
void ADD_0(char *binary, int mode)
{int i;int difference;if (0 == mode)difference = BINARY_LENGTH + 8 - strlen(binary);else if(1 == mode)difference = BINARY_LENGTH - strlen(binary);;for (i = strlen(binary); i >= 0; i--)binary[i + difference] = binary[i];for (i = 0; i < difference; i++)binary[i] = '0';
}// mode 0: decrypt char*
// mode 1: decrypt file
void rsa_decrypt(char *src, char *dst, char *key_name, int mode)
{mp_int n;mp_int private_key;mp_int plain_number;mp_int cipher_number;mp_init_size(&n, SUBKEY_LENGTH * 2);mp_init_size(&private_key, SUBKEY_LENGTH * 2);mp_init_size(&plain_number, SUBKEY_LENGTH * 2);mp_init_size(&cipher_number, SUBKEY_LENGTH * 2);Get_key_from_file(&private_key, &n, key_name, 1);char plain_text[PLAINTEXT_LENGTH + 1];char cipher_text[PLAINTEXT_LENGTH + 2];char plain_binary[BINARY_LENGTH + 1];char cipher_binary[BINARY_LENGTH + 9];int j;int k;int l;if (0 == mode){k = -1;do{k++;for (l = 0; l <= PLAINTEXT_LENGTH; l++)plain_text[l] = '\0';for (l = 0; l <= BINARY_LENGTH; l++)plain_binary[l] = '\0';for (l = 0; l <= BINARY_LENGTH + 8; l++)cipher_binary[l] = '\0';for (j = 0; j <= PLAINTEXT_LENGTH; j++)cipher_text[j] = src[k * (PLAINTEXT_LENGTH + 1) + j];cipher_text[PLAINTEXT_LENGTH + 1] = '\0';Char_2_binary(cipher_text, cipher_binary, PLAINTEXT_LENGTH + 1);mp_zero(&cipher_number);mp_read_radix(&cipher_number, cipher_binary, 2);mp_zero(&plain_number);// ----------------------------------------------------------------mp_exptmod(&cipher_number, &private_key, &n, &plain_number);//quick_pow(&cipher_number, &private_key, &n, &plain_number);// ----------------------------------------------------------------mp_toradix(&plain_number, plain_binary, 2);ADD_0(plain_binary, 1);Binary_2_char(plain_binary, plain_text, BINARY_LENGTH);for (l = 0; l <= PLAINTEXT_LENGTH - 1; l++) dst[k*PLAINTEXT_LENGTH + l] = plain_text[l];} while ('\0' != src[(k + 1)*(PLAINTEXT_LENGTH + 1)]);dst[(k + 1) * PLAINTEXT_LENGTH] = '\0';}else if (1 == mode){ifstream fin;ofstream fout;fin.open(src, ios::binary);fout.open(dst, ios::binary);int i = 0;int limit = PLAINTEXT_LENGTH;char ch;string temp = "";while (1){fin.get(ch);if ('\n' == ch)break;temp += ch;}int len = atoi(temp.c_str());while (1){fin.get(ch);cipher_text[i++] = ch;if (i == PLAINTEXT_LENGTH + 1){if (i == PLAINTEXT_LENGTH + 1) cipher_text[i] = '\0';elsecipher_text[i - 1] = '\0';for (l = 0; l <= BINARY_LENGTH + 8; l++)cipher_binary[l] = '\0';for (l = 0; l <= PLAINTEXT_LENGTH; l++)plain_text[l] = '\0';for (l = 0; l <= BINARY_LENGTH; l++)plain_binary[l] = '\0';Char_2_binary(cipher_text, cipher_binary, PLAINTEXT_LENGTH + 1);mp_zero(&cipher_number);mp_read_radix(&cipher_number, cipher_binary, 2);mp_zero(&plain_number);// ----------------------------------------------------------------mp_exptmod(&cipher_number, &private_key, &n, &plain_number);//quick_pow(&cipher_number, &private_key, &n, &plain_number);// ----------------------------------------------------------------mp_toradix(&plain_number, plain_binary, 2);ADD_0(plain_binary, 1);Binary_2_char(plain_binary, plain_text, BINARY_LENGTH);if (fin.peek() == EOF)limit = len;for (l = 0; l < limit; l++)fout << plain_text[l];for (l = 0; l <= PLAINTEXT_LENGTH + 1; l++)cipher_text[l] = '\0';i = 0;}if (fin.eof())break;}fin.close();fout.close();}mp_clear_multi(&n, &private_key, &plain_number, &cipher_number, NULL);
}// compute d = a ^ b (mod c)
void quick_pow(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
{mp_int temp;mp_int temp_a;mp_int temp_b;mp_init_size(&temp, SUBKEY_LENGTH * 2);mp_init_size(&temp_a, SUBKEY_LENGTH * 2);mp_init_size(&temp_b, SUBKEY_LENGTH * 2);mp_copy(a, &temp_a);mp_copy(b, &temp_b);mp_set_int(d, 1);mp_mod(&temp_a, c, &temp_a);while (MP_GT == mp_cmp(&temp_b, &zero)){mp_mod(&temp_b, &two, &temp);if (MP_EQ == mp_cmp(&one, &temp)){mp_mul(d, &temp_a, d);mp_mod(d, c, d);}mp_div_2(&temp_b, &temp_b);mp_mul(&temp_a, &temp_a, &temp_a);mp_mod(&temp_a, c, &temp_a);}mp_clear_multi(&temp, &temp_a, &temp_b, NULL);
}int Get_file_length(char *filename) 
{FILE *fp = fopen(filename, "rb");if (NULL == fp)return -1;fseek(fp, 0, SEEK_END);int temp = ftell(fp);fclose(fp);return temp;
}

main.h

#pragma once
#include "rsa.h"

 main.cpp

#include "main.h"// example
void main()
{initial();// generate key belong to arg " "Generate_key("hello_world");// ----------------------example: encrypt char* ---------------------------char a[200] = "to_be_or_not_to_be_it_is_a_question";char b[400];char c[200];//rsa_encrypt(a, b, "hello_world", 0);//rsa_decrypt(b, c, "hello_world", 0);cout << "c: " << c << endl;// ------------------------------------------------------------------------// ----------------------example: encrypt file ----------------------------rsa_encrypt("d:\\a.gif", "d:\\m", "d:\\public_key_hello_world", 1);rsa_decrypt("d:\\m", "D:\\b.gif", "d:\\private_key_hello_world", 1);// ------------------------------------------------------------------------}