语言实现"/>

RSA C语言实现

完整代码上传至GitHub:

由于目前gcc最大只支持128位整数（需使用64位gcc进行编译），故如果在不重写相关数学运算的前提下，无法实现较大密钥的RSA加密。

tool：实现一些基本的数学运算

tool.h

#ifndef _tool_h_
#define _tool_h_#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ASSERT(condition)                                                \if (!condition)                                                      \{                                                                    \printf("Assertion failed: line %d file %s", __LINE__, __FILE__); \exit(1);                                                         \}#define EXCHANGE(x, y, tmp) \tmp = x;                \x = y;                  \y = tmp;typedef unsigned __int128 bignum;bignum powMod(bignum base, bignum index, bignum mod);// generate unsigned int64 random number
unsigned __int64 uint64Rand();// generate unsigned int128 random number
unsigned __int128 uint128Rand();// 判断一个大于3的数是否为素数
bool isprime(bignum n);// 判断两数是否互质
bool coprime(bignum x, bignum y);//将int128类型的整数保存到文件
void int128tofile(bignum num, FILE *fp);//将hex的string转换成 int128
unsigned __int128 stringToInt128(char *str);// Function to find modulo inverse of a
bignum modInverse(bignum a, bignum m);// Returns (a * b) % mod
bignum moduloMultiplication(bignum a, bignum b, bignum mod);#endif

tool.c

#include "tool.h"// C program of finding modulo multiplication
#include <stdio.h>// Returns (a * b) % mod
bignum moduloMultiplication(bignum a, bignum b, bignum mod)
{bignum res = 0; // Initialize result// Update a if it is more than// or equal to moda %= mod;while (b){// If b is odd, add a with resultif (b & 1)res = (res + a) % mod;// Here we assume that doing 2*a// doesn't cause overflowa = (2 * a) % mod;b >>= 1; // b = b / 2}return res;
}bignum powMod(bignum base, bignum index, bignum mod)
{bignum res = 1; // Initialize resultwhile (index > 0){// If index is odd, multiply base with resultif (index & 1u)res = moduloMultiplication(res, base, mod);// index must be even nowindex = index >> 1;           // index = index/2base = moduloMultiplication(base, base, mod); // Change base to base^2%mod}return (res % mod);
}// generate unsigned __int64 random number
unsigned __int64 uint64Rand()
{ASSERT((0x7FFF == RAND_MAX))unsigned __int64 r = 0;for (int i = 0; i < 5; ++i){r = (r << 15) | (rand() & 0x7FFF);}return r & 0xFFFFFFFFFFFFFFFFULL;
}unsigned __int128 uint128Rand()
{ASSERT((0x7FFF == RAND_MAX))bignum r = 0;for (int i = 0; i < 9; ++i){r = (r << 15) | (rand() & 0x7FFF);}__int128 allone = 0;allone--;return r & allone;
}// n为大于3的数
bool isprime(bignum n)
{ASSERT((n > 3))if (n % 2 == 0){return false;}// n-1 = 2^k * mint k = 0;bignum m = n - 1;for (; m % 2 == 0; m /= 2){k++;}// 使用 Miller-Rabin算法for (int i = 0; i < 100; i++){bignum a = uint128Rand() % (n - 2) + 2;bignum b = powMod(a, m, n);if (b == 1){continue;}for (int i = 0; i < k; i++){if (b == n - 1){goto ENDMillerRabin;}else{b = powMod(b, b, n);}}return false;ENDMillerRabin:;}return true;
}//判断x, y是否互质
bool coprime(bignum x, bignum y)
{bignum tmp;if (y > x){EXCHANGE(x, y, tmp);}if (x == y || x % y == 0){return false;}while (true){x %= y;if (y > x){EXCHANGE(x, y, tmp);}if (y == 1){return true;}if (x % y == 0){return false;}}
}// C program to find multiplicative modulo inverse using
// Extended Euclid algorithm.// C function for extended Euclidean Algorithm
bignum gcdExtended(bignum a, bignum b, bignum *x, bignum *y)
{// Base Caseif (a == 0){*x = 0, *y = 1;return b;}bignum x1, y1; // To store results of recursive callbignum gcd = gcdExtended(b % a, a, &x1, &y1);// Update x and y using results of recursive// call*x = y1 - (b / a) * x1;*y = x1;return gcd;
}// Function to find modulo inverse of a
bignum modInverse(bignum a, bignum m)
{bignum x, y;if (gcdExtended(a, m, &x, &y) != 1){printf("Inverse doesn't exist");exit(1);}// m is added to handle negative xbignum res = (x % m + m) % m;return res;
}// 将int128类型的整数保存到文件
void int128tofile(unsigned __int128 num, FILE *fp)
{if (num == 0){fputc('0', fp);}else{char c;char str[33];int i = 0;int remain;while (num != 0){remain = num % 16;num /= 16;if (remain < 10){c = '0' + remain;}else{c = 'A' + (remain - 10);}str[i++] = c;}while (i > 0){fputc(str[--i], fp);}}
}//将hex的string转换成 int128
unsigned __int128 stringToInt128(char *str)
{unsigned __int128 num = 0;for (int i = 0; str[i] != 0; i++){if ('0' <= str[i] && str[i] <= '9'){num = num * 16 + (str[i] - '0');}else if ('A' <= str[i] && str[i] <= 'F'){num = num * 16 + (str[i] - 'A' + 10);}else if ('a' <= str[i] && str[i] <= 'f'){num = num * 16 + (str[i] - 'a' + 10);}else{printf("Invalid hex string");exit(1);}}return num;
}

keyGenerator：密钥生成

keyGenerator.c

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "tool.h"#define MIN_PRIME 10000000000ull
#define MAX_PRIME 100000000000ull// generate a prime bignum > min
bignum generatePrime(bignum min, bignum max)
{bignum result;while (true){result = uint64Rand() % max;if (result > min && isprime(result)){return result;}}
}void generateKey()
{bignum p = generatePrime(MIN_PRIME, MAX_PRIME);bignum q = generatePrime(MIN_PRIME, MAX_PRIME);ASSERT(coprime(p, q))bignum n = (bignum)p * q;bignum fain = (bignum)(p - 1) * (q - 1);// fain 与 e 互素bignum e = uint128Rand() % fain;while(!coprime(fain, e)){e = uint128Rand() % fain;}bignum d = modInverse(e, fain);// 写入文件FILE *p_txt = fopen("p.txt", "w");int128tofile(p, p_txt);fclose(p_txt);FILE *q_txt = fopen("q.txt", "w");int128tofile(q, q_txt);fclose(q_txt);FILE *n_txt = fopen("n.txt", "w");int128tofile(n, n_txt);fclose(n_txt);FILE *e_txt = fopen("e.txt", "w");int128tofile(e, e_txt);fclose(e_txt);FILE *d_txt = fopen("d.txt", "w");int128tofile(d, d_txt);fclose(d_txt);
}int main()
{generateKey();return 0;
}

RSA

rsa.h

#ifndef _rsa_h_
#define _rsa_h_#include "tool.h"
// rsa加密
bignum rsaEncrypt(bignum m, bignum e, bignum n);// rsa解密与签名
bignum rsaSign(bignum m, bignum d, bignum n);#endif

rsa.c

#include "tool.h"bignum rsaEncrypt(bignum m, bignum e, bignum n)
{return powMod(m, e, n);
}bignum rsaSign(bignum m, bignum d, bignum n)
{return powMod(m, d, n);
}

main.c

#include <stdio.h>
#include "rsa.h"
#include <string.h>bool cipher(char *n_path, char *e_path, char *message_path, char *out_path)
{// rsa_cipherFILE *n_fp = fopen(n_path, "r");if (n_fp == NULL){printf("Unable to open %s\n", n_path);return false;}FILE *e_fp = fopen(e_path, "r");if (e_fp == NULL){printf("Unable to open %s\n", e_path);return false;}FILE *m_fp = fopen(message_path, "r");if (m_fp == NULL){printf("Unable to open %s\n", message_path);return false;}FILE *out_fp = fopen(out_path, "w");if (out_fp == NULL){printf("Unable to open %s\n", out_path);return false;}char n_str[50];fscanf(n_fp, "%s", n_str);fclose(n_fp);char e_str[50];fscanf(e_fp, "%s", e_str);fclose(e_fp);char m_str[50];fscanf(m_fp, "%s", m_str);fclose(m_fp);bignum n = stringToInt128(n_str);bignum e = stringToInt128(e_str);bignum m = stringToInt128(m_str);bignum c = rsaEncrypt(m, e, n);int128tofile(c, out_fp);fclose(out_fp);return true;
}bool sign(char *hash_path, char *n_path, char *d_path, char *out_path)
{FILE *hash_fp = fopen(hash_path, "r");if (hash_fp == NULL){printf("Unable to open %s\n", hash_path);return false;}FILE *n_fp = fopen(n_path, "r");if (n_fp == NULL){printf("Unable to open %s\n", n_path);return false;}FILE *d_fp = fopen(d_path, "r");if (d_fp == NULL){printf("Unable to open %s\n", d_path);return false;}FILE *out_fp = fopen(out_path, "w");if (out_fp == NULL){printf("Unable to open %s\n", out_path);return false;}char n_str[50];fscanf(n_fp, "%s", n_str);fclose(n_fp);char d_str[50];fscanf(d_fp, "%s", d_str);fclose(d_fp);char hash_str[50];fscanf(hash_fp, "%s", hash_str);fclose(hash_fp);bignum n = stringToInt128(n_str);bignum d = stringToInt128(d_str);bignum hash = stringToInt128(hash_str);bignum c = rsaSign(hash, d, n);int128tofile(c, out_fp);fclose(out_fp);return true;
}
int main(int argc, char *argv[])
{char *plainfile = NULL;char *nfile = NULL;char *efile = NULL;char *dfile = NULL;char *cipherfile = NULL;for (int i = 1; i < argc; i++){if (strcmp(argv[i], "-p") == 0){plainfile = argv[++i];}else if (strcmp(argv[i], "-n") == 0){nfile = argv[++i];}else if (strcmp(argv[i], "-e") == 0){efile = argv[++i];}else if (strcmp(argv[i], "-d") == 0){dfile = argv[++i];}else if (strcmp(argv[i], "-c") == 0){cipherfile = argv[++i];}else{printf("-p plainfile\t指定明文文件的位置和名称\n");printf("-n nfile\t指定存放整数 n 的文件的位置和名称\n");printf("-e efile\t在数据加密时, 指定存放整数 e 的文件的位置和名称\n");printf("-d dfile\t在数字签名时, 指定存放整数 d 的文件的位置和名称\n");printf("-c cipherfile\t指定密文文件的位置和名称\n");}}if (efile != NULL && dfile == NULL){if (cipher(nfile, efile, plainfile, cipherfile)){printf("RSA Encryption success!\n");}}else if (efile == NULL && dfile != NULL){if (sign(plainfile, nfile, dfile, cipherfile)){printf("RSA Sign success!\n");}}else{printf("arguments error!\n");}return 0;
}

main.exe -p plainfile -n nfile [-e efile] [-d dfile] -c cipherfile 

参数：
-p plainfile 指定明文文件的位置和名称
-n nfile 指定存放整数 n 的文件的位置和名称
-e efile 在数据加密时，指定存放整数 e 的文件的位置和名称
-d dfile 在数字签名时，指定存放整数 d 的文件的位置和名称
-c cipherfile 指定密文文件的位置和名称