rsa加密解密算法c语言

RSA加密解密算法是一种非对称加密算法，它的加密和解密过程使用了不同的密钥，其中公钥用于加密，私钥用于解密。以下是RSA加密解密算法的C语言实现。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>

#define MAX_SIZE 1000

// 计算幂模
long long pow_mod(long long a, long long b, long long c)
{
    long long ans = 1;
    a = a % c;

    while (b > 0)
    {
        if (b % 2 == 1)
            ans = (ans * a) % c;

        b = b / 2;
        a = (a * a) % c;
    }

    return ans;
}

// 判断一个数是否为质数
int is_prime(long long n)
{
    if (n <= 1)
        return 0;

    for (long long i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

// 获取一个随机质数
long long get_prime()
{
    long long prime;
    srand((unsigned)time(NULL));

    do
    {
        prime = rand() % MAX_SIZE + 1;
    } while (!is_prime(prime));

    return prime;
}

// 计算最大公因数
long long gcd(long long a, long long b)
{
    if (a == 0)
        return b;

    return gcd(b % a, a);
}

// 计算模反元素
long long mod_inverse(long long a, long long m)
{
    long long m0 = m, t, q;
    long long x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        q = a / m;
        t = m;

        m = a % m, a = t;
        t = x0;

        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

// 生成公钥和私钥
void generate_key(long long *e, long long *d, long long *n)
{
    long long p, q, phi, e_key;

    // 获取两个随机质数
    p = get_prime();
    q = get_prime();

    // 计算n和phi
    *n = p * q;
    phi = (p - 1) * (q - 1);

    // 获取与phi互质的随机数e
    do
    {
        e_key = rand() % (phi - 2) + 2;
    } while (gcd(e_key, phi) != 1);

    *e = e_key;
    *d = mod_inverse(e_key, phi);
}

// RSA加密
void encrypt(char *plaintext, long long e, long long n, char *ciphertext)
{
    long long i, len = strlen(plaintext), m, c;
    char temp[MAX_SIZE];
    strncpy(temp, plaintext, MAX_SIZE);

    for (i = 0; i < len; i++)
    {
        m = temp[i];
        c = pow_mod(m, e, n);
        sprintf(&ciphertext[i * 4], "%04lld", c);
    }
}

// RSA解密
void decrypt(char *ciphertext, long long d, long long n, char *plaintext)
{
    long long i, len = strlen(ciphertext) / 4, m, c;
    char temp[MAX_SIZE];

    for (i = 0; i < len; i++)
    {
        strncpy(temp, &ciphertext[i * 4], 4);
        c = atol(temp);
        m = pow_mod(c, d, n);
        plaintext[i] = m;
    }

    plaintext[len] = '\0';
}

int main()
{
    long long e, d, n;
    char plaintext[MAX_SIZE], ciphertext[MAX_SIZE];

    printf("请输入明文:");
    scanf("%s", plaintext);

    // 生成公钥和私钥
    generate_key(&e, &d, &n);

    // RSA加密
    encrypt(plaintext, e, n, ciphertext);
    printf("加密后的密文:%s\n", ciphertext);

    // RSA解密
    decrypt(ciphertext, d, n, plaintext);
    printf("解密后的明文:%s\n", plaintext);

    return 0;
}

注意，上述代码中的MAX_SIZE定义了最大字符串长度，需要根据实际情况进行修改。在encrypt函数中，将每个字符的加密结果转化为4位数字，这样可以确保每个字符的加密结果都是固定的长度。在decrypt函数中，每次从密文中读取4位数字并解密为对应的字符。