C语言程序设计综合实验课程布置了关于RSA算法实现的作业，查了查算法实现思想，特此记录。
RSA算法的描述
1、选取长度相等的两个大素数p和q，计算其乘积：
$$
n = p*q
$$
然后随机选取加密密钥e，使e和(p–1)(q–1)互素。
最后用欧几里德扩展算法计算解密密钥d，以满足
$$
ed = 1(mod(p – 1)(q – 1))
$$
$$
=>d = e–1 mod((p – 1)(q – 1))
$$
e和n是公钥，d是私钥
2、加密公式如下：
$$
ci = mi^e（mod n）
$$
3、解密时，取每一密文分组 ci 并计算：
$$
mi = ci^d（mod n）
$$
$$
Ci^d =（mi^e）^d = mi^{ed} = mi^{k（p–1）（q–1）+1}
$$
4、消息也可以用d加密用e解密
代码如下：
/**********************************
A simple implementation of RSA algorithm
Create by topK on 2020/4/18
blog: topkli.com
**********************************/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
char buffer[1024];
const int MAX_DIGITS = 50;
ll *encrypted;
char *decrypted;
struct public_key
{
ll modulus;
ll exponent;
}pub;
struct private_key{
ll modulus;
ll exponent;
}priv;
//-----------------------rsa_gen_keys---------------------------
ll gcd(ll a, ll b)
{
ll c;
while ( a != 0 )
{
c = a; a = b%a; b = c;
}
return b;
}
ll ExtEuclid(ll a, ll b)
{
ll x = 0, y = 1, u = 1, v = 0, gcd = b, m, n, q, r;
while (a!=0)
{
q = gcd/a; r = gcd % a;
m = x-u*q; n = y-v*q;
gcd = a; a = r; x = u; y = v; u = m; v = n;
}
return y;
}
void rsa_gen_keys()
{
FILE *primes_list;
if(!(primes_list = fopen("prime_source_file.txt", "r")))
{
fprintf(stderr,"Error reading prime_source_file");
exit(1);
}
//count number of primes in the list
ll prime_count = 0;
do{
int bytes_read = fread(buffer,1,sizeof(buffer)-1,primes_list);
buffer[bytes_read] = '\0';
for(int i = 0; buffer[i]; i++)
{
if(buffer[i] == '\n')
{
prime_count++;
}
}
}while(feof(primes_list) == 0);
// choose random primes from the list, store them as p,q
ll p = 0, q = 0;
ll e = 257;
ll d = 0;
char prime_buffer[MAX_DIGITS];
ll max = 0;
ll phi_max = 0;
srand(time(NULL));
do{
// a and b are the positions of p and q in the list
int a = (double)rand() * (prime_count+1) / (RAND_MAX+1.0);
int b = (double)rand() * (prime_count+1) / (RAND_MAX+1.0);
//store a as p
rewind(primes_list);
for(int i = 0; i < a+1; i++)
{
fgets(prime_buffer,sizeof(prime_buffer)-1, primes_list);
}
p = atol(prime_buffer);
//store b as q
rewind(primes_list);
for(int i = 0; i < b+1; i++)
{
for(int j = 0; j < MAX_DIGITS; j++)
{
prime_buffer[j] = 0;
}
fgets(prime_buffer,sizeof(prime_buffer)-1, primes_list);
}
q = atol(prime_buffer);
max = p*q;
phi_max = (p-1)*(q-1);
}while(!(p && q) || (p == q) || (gcd(phi_max, e) != 1));
//solve the d
d = ExtEuclid(phi_max,e);
while(d < 0)
{
d = d+phi_max;
}
FILE *gen_primes;
if(!(gen_primes = fopen("gen_primes.txt", "w")))
{
fprintf(stderr,"Error write gen_primes");
exit(1);
}
fprintf(gen_primes,"primes are %lld and %lld\n",(ll)p, (ll)q);
fclose(gen_primes);
pub.modulus = max;
pub.exponent = e;
priv.modulus = max;
priv.exponent = d;
}
//--------------------------------------------------------------
ll rsa_modExp(ll b, ll e, ll m)
{
if (b < 0 || e < 0 || m <= 0)
{
printf("Too large integer, PLease change other prime\n");
exit(1);
}
b = b % m;
if(e == 0) return 1;
if(e == 1) return b;
if( e % 2 == 0)
{
return ( rsa_modExp(b * b % m, e/2, m) % m );
}
if( e % 2 == 1)
{
return ( b * rsa_modExp(b, (e-1), m) % m );
}
}
//--------------------------rsa_encrypt-------------------------
ll *rsa_encrypt(char *message, const unsigned long message_size)
{
ll *encrypted = (ll*)malloc(sizeof(ll)*message_size);
if(encrypted == NULL)
{
fprintf(stderr, "Error: Heap allocation failed.\n");
return NULL;
}
long long i = 0;
for(int i = 0; i < message_size; i++)
{
encrypted[i] = rsa_modExp(message[i], pub.exponent, pub.modulus);
}
return encrypted;
}
//--------------------------------------------------------------
//--------------------------rsa_decrypt-------------------------
char *rsa_decrypt(ll *message, unsigned long message_size)
{
if(message_size % sizeof(long long) != 0)
{
fprintf(stderr, "Error: message_size is not divisible by %d, so cannot be output of rsa_encrypt\n", (int)sizeof(long long));
return NULL;
}
// We allocate space to do the decryption (temp) and space for the output as a char array
char *decrypted = (char*)malloc(message_size/sizeof(long long));
char *temp = (char*)malloc(message_size);
if((decrypted == NULL) || (temp == NULL))
{
fprintf(stderr, "Error: Heap allocation failed.\n");
return NULL;
}
// Now we go through each 8-byte chunk and decrypt it.
long long i = 0;
for(int i = 0; i < message_size/8; i++)
{
temp[i] = rsa_modExp(message[i], priv.exponent, priv.modulus);
}
// The result should be a number in the char range, which gives back the original byte.
// We put that into decrypted, then return.
for(int i = 0; i < message_size/8; i++)
{
decrypted[i] = temp[i];
}
free(temp);
return decrypted;
}
//--------------------------------------------------------------
int main()
{
char message[50];
long message_size = 0;
FILE *message_file;
FILE *public_key_file;
FILE *private_key_file;
while(1)
{
int flag1 = -1;
printf("Welcome to the RSA encryption & decryption system!\n");
printf("The system instruction manual is as follows:\n\n");
printf("1: Generatethe RSA secret key\n");
printf("2: Encrypte the message file\n");
printf("3: Decrypted encrypted text file\n");
printf("4: Check encrypted file\n");
printf("5: Check decrypted file\n");
printf("0: Exit RSA encryption & decryption system\n\n");
printf("Waiting for input...\n");
scanf("%d",&flag1);
printf("\n");
switch(flag1)
{
case 0:
{
printf("Thank you for using RSA encryption & decryption system\n");
break;
}
case 1:
{
printf("Generating the rsa secret key, please wait...\n");
rsa_gen_keys();
if(!(public_key_file = fopen("public_key_file.txt", "w")))
{
fprintf(stderr,"Error write public_key_file");
exit(1);
}
fprintf(public_key_file, "Public Key: Modulus: %lld Exponent: %lld", pub.modulus, pub.exponent);
if(!(private_key_file = fopen("private_key_file.txt", "w")))
{
fprintf(stderr,"Error write private_key_file");
exit(1);
}
fprintf(private_key_file, "Private Key: Modulus: %lld Exponent: %lld", priv.modulus, priv.exponent);
fclose(public_key_file);
fclose(private_key_file);
printf("The rsa secret key was successfully generated!\n");
printf("The generated primes are in the gen_primes.txt in the current directory.\n");
printf("The generated public keys are in the public_key_file.txt in the current directory.\n");
printf("The generated private keys are in the private_key_file.txt in the current directory.\n");
while(1)
{
int flag2 = -1;
printf("\n");
printf("What would you like to do next?\n");
printf("1: Check the prime file\n");
printf("2: Check the public keys file\n");
printf("3: Check the private keys file\n");
printf("0: Back to main menu\n");
scanf("%d",&flag2);
printf("\n");
switch(flag2)
{
case 1:
{
printf("Reading gen_primes file, please wait...\n");
FILE *gen_primes;
ll a,b;
if(!(gen_primes = fopen("gen_primes.txt", "r")))
{
fprintf(stderr,"Error read gen_primes");
exit(1);
}
fscanf(gen_primes,"primes are %lld and %lld\n",&a, &b);
printf("primes are %lld and %lld\n", a, b);
fclose(gen_primes);
break;
}
case 2:
{
printf("Reading pubilc_key_file, please wait...\n");
if(!(public_key_file = fopen("public_key_file.txt", "r")))
{
fprintf(stderr,"Error read public_key_file.txt");
exit(1);
}
char s;
while(fscanf(public_key_file,"%c",&s) != EOF)
printf("%c",s);
fclose(public_key_file);
break;
}
case 3:
{
ll a,b;
printf("Reading private_key_file, please wait...\n");
if(!(private_key_file = fopen("private_key_file.txt", "r")))
{
fprintf(stderr,"Error read private_key_file.txt");
exit(1);
}
char s;
while(fscanf(private_key_file,"%c",&s) != EOF)
printf("%c",s);
fclose(private_key_file);
break;
}
case 0:
{
printf("Returning to main menu.\n");
break;
}
default:
{
printf("Invalid input, please try again.");
break;
}
}
if(flag2 == 0)
break;
}
break;
}
case 2:
{
printf("Loading message file, Please wait.\n");
if(!(message_file = fopen("message_file.txt", "r")))
{
fprintf(stderr,"Error reading message_file");
exit(1);
}
fscanf(message_file, "%s", &message);
for(int i = 0; i < sizeof(message); i++)
{
if(message[i] != '\0')
{
message_size++;
}
else break;
}
printf("Loading success!\n");
encrypted = rsa_encrypt(message, message_size);
if (!encrypted)
{
fprintf(stderr, "Error in encryption!\n");
return 1;
}
FILE *encrypted_file;
if(!(encrypted_file = fopen("encrypted_file.txt", "w")))
{
fprintf(stderr,"Error write encrypted_file");
exit(1);
}
for(int i = 0; i < strlen(message); i++)
fprintf(encrypted_file,"%lld\n", encrypted[i]);
fclose(encrypted_file);
printf("Encryption to complete!\n");
printf("The encrypted_file is in the encryption_file.txt in the current directory.\n");
printf("\n");
int flag2 = -1;
while(1)
{
printf("Please input 0 to back to main menu.\n");
scanf("%d",&flag2);
printf("\n");
if(flag2 == 0)
break;
else
{
printf("Invalid input, please try again.\n");
}
}
break;
}
case 3:
{
//open encrypted file
FILE *encrypted_file;
if(!(encrypted_file = fopen("encrypted_file.txt", "r")))
{
fprintf(stderr,"Error read encrypted_file");
exit(1);
}
ll s;
ll *encrypted_text;
int n = 0;
while(fscanf(encrypted_file,"%lld",&s) != EOF)
{
encrypted_text[n] = s;
n++;
}
fclose(encrypted_file);
//open private file
FILE *private_key_file;
if(!(private_key_file = fopen("private_key_file.txt", "r")))
{
fprintf(stderr,"Error read private_key_file.txt");
exit(1);
}
fscanf(private_key_file,"Private Key: Modulus: %lld Exponent: %lld",&priv.modulus, &priv.exponent);
fclose(private_key_file);
//open public file
FILE *public_key_file;
if(!(public_key_file = fopen("public_key_file.txt", "r")))
{
fprintf(stderr,"Error read public_key_file.txt");
exit(1);
}
fscanf(public_key_file,"Public Key: Modulus: %lld Exponent: %lld",&pub.modulus, &pub.exponent);
fclose(public_key_file);
//decrypte encrypted text
decrypted = rsa_decrypt(encrypted_text, 8*n);
if (!decrypted)
{
fprintf(stderr, "Error in decryption!\n");
return 1;
}
FILE *decrypted_file;
if(!(decrypted_file = fopen("decrypted_file.txt", "w")))
{
fprintf(stderr,"Error write decrypted_file");
exit(1);
}
for(int i = 0; i < strlen(message); i++)
fprintf(decrypted_file,"%c",decrypted[i]);
fclose(decrypted_file);
printf("Decryption to complete!\n");
printf("The decrypted_file is in the decryption_file.txt in the current directory.\n");
printf("\n");
int flag2 = -1;
while(1)
{
printf("Please input 0 to back to main menu.\n");
scanf("%d",&flag2);
printf("\n");
if(flag2 == 0)
break;
else
{
printf("Invalid input, please try again.\n");
}
}
break;
}
case 4:
{
printf("The encrypted_file is as follows:\n\n");
FILE *encrypted_file;
if(!(encrypted_file = fopen("encrypted_file.txt", "r")))
{
fprintf(stderr,"Error read encrypted_file");
exit(1);
}
ll s;
while(fscanf(encrypted_file,"%lld",&s) != EOF)
printf("%lld ",s);
fclose(encrypted_file);
printf("\n\n");
int flag2 = -1;
while(1)
{
printf("Please input 0 to back to main menu.\n");
scanf("%d",&flag2);
printf("\n");
if(flag2 == 0)
break;
else
{
printf("Invalid input, please try again.\n");
}
}
break;
}
case 5:
{
printf("The decrypted_file is as follows:\n\n");
FILE *decrypted_file;
if(!(decrypted_file = fopen("decrypted_file.txt","r")))
{
fprintf(stderr,"Error read decrypted_file");
exit(1);
}
char s;
while(fscanf(decrypted_file,"%c",&s) != EOF)
printf("%c",s);
fclose(decrypted_file);
printf("\n\n");
int flag2 = -1;
while(1)
{
printf("Please input 0 to back to main menu.\n");
scanf("%d",&flag2);
printf("\n");
if(flag2 == 0)
break;
else
{
printf("Invalid input, please try again.\n");
}
}
break;
break;
}
default:
printf("Invalid input, please try again.");
break;
}
if(flag1 == 0)
break;
printf("\n\n");
}
free(encrypted);
free(decrypted);
return 0;
}
