RSA C语言实现

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

#ifndef _tool_h_
#define _tool_h_

#include 
#include 
#include 
#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

#include "tool.h"

// C program of finding modulo multiplication
#include 

// 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 mod
    a %= mod;

    while (b)
    {
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;

        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;

        b >>= 1; // b = b / 2
    }

    return res;
}

bignum powMod(bignum base, bignum index, bignum mod)
{
    bignum res = 1; // Initialize result

    while (index > 0)
    {
        // If index is odd, multiply base with result
        if (index & 1u)
            res = moduloMultiplication(res, base, mod);

        // index must be even now
        index = index >> 1;           // index = index/2
        base = 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 * m
    int 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.
#include 

// C function for extended Euclidean Algorithm
bignum gcdExtended(bignum a, bignum b, bignum *x, bignum *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }

    bignum x1, y1; // To store results of recursive call
    bignum 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 x
    bignum 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;
}

#include 
#include 
#include 
#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;
}

#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

#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);
}

#include 
#include "rsa.h"
#include 

bool cipher(char *n_path, char *e_path, char *message_path, char *out_path)
{
    // rsa_cipher
    FILE *n_fp = fopen(n_path, "r");
    if (n_fp == NULL)
    {
        printf("Unable to open %sn", n_path);
        return false;
    }

    FILE *e_fp = fopen(e_path, "r");
    if (e_fp == NULL)
    {
        printf("Unable to open %sn", e_path);
        return false;
    }

    FILE *m_fp = fopen(message_path, "r");
    if (m_fp == NULL)
    {
        printf("Unable to open %sn", message_path);
        return false;
    }

    FILE *out_fp = fopen(out_path, "w");
    if (out_fp == NULL)
    {
        printf("Unable to open %sn", 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 %sn", hash_path);
        return false;
    }

    FILE *n_fp = fopen(n_path, "r");
    if (n_fp == NULL)
    {
        printf("Unable to open %sn", n_path);
        return false;
    }

    FILE *d_fp = fopen(d_path, "r");
    if (d_fp == NULL)
    {
        printf("Unable to open %sn", d_path);
        return false;
    }

    FILE *out_fp = fopen(out_path, "w");
    if (out_fp == NULL)
    {
        printf("Unable to open %sn", 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 plainfilet指定明文文件的位置和名称n");
            printf("-n nfilet指定存放整数 n 的文件的位置和名称n");
            printf("-e efilet在数据加密时, 指定存放整数 e 的文件的位置和名称n");
            printf("-d dfilet在数字签名时, 指定存放整数 d 的文件的位置和名称n");
            printf("-c cipherfilet指定密文文件的位置和名称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 指定密文文件的位置和名称