用C语言实现RSA算法，编程实现模逆算法

RSA算法是一种非对称加密算法，用于实现数据加密和数字签名等功能。它基于两个大素数的乘积作为公钥，私钥则由这两个素数的乘积及一些其他参数计算得出。在RSA算法中，模逆算法是非常重要的一部分，它用于计算一个数的模逆。

以下是用C语言实现RSA算法的代码，包括模逆算法：

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

// 求a和b的最大公约数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// 求a和b的最小公倍数
int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}

// 判断一个数是否为素数
int is_prime(int n)
{
    int i, flag = 1;
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            flag = 0;
            break;
        }
    }
    return flag;
}

// 生成随机素数
int get_random_prime(int min, int max)
{
    int i, p;
    for (i = 0; i < 100; i++) {
        p = rand() % (max - min + 1) + min;
        if (is_prime(p))
            return p;
    }
    return -1;
}

// 求模逆
int mod_inverse(int a, int n)
{
    int t, r, t1 = 0, t2 = 1, r1 = n, r2 = a;
    while (r2 != 0) {
        t = r1 / r2;
        r = r1 - t * r2;
        r1 = r2;
        r2 = r;
        t = t1 - t * t2;
        t1 = t2;
        t2 = t;
    }
    if (r1 > 1)
        return -1;
    if (t1 < 0)
        t1 += n;
    return t1;
}

// RSA加密
int rsa_encrypt(int m, int e, int n)
{
    int c = 1, i;
    for (i = 0; i < e; i++) {
        c *= m;
        c %= n;
    }
    return c;
}

// RSA解密
int rsa_decrypt(int c, int d, int n)
{
    int m = 1, i;
    for (i = 0; i < d; i++) {
        m *= c;
        m %= n;
    }
    return m;
}

int main()
{
    srand(time(NULL));
    int p, q, n, fn, e, d, m, c;
    printf("输入明文m：");
    scanf("%d", &m);
    do {
        p = get_random_prime(100, 1000);
        q = get_random_prime(100, 1000);
        n = p * q;
        fn = lcm(p - 1, q - 1);
        e = rand() % (fn - 2) + 2;
    } while (gcd(e, fn) != 1);
    d = mod_inverse(e, fn);
    c = rsa_encrypt(m, e, n);
    printf("p=%d, q=%d, n=%d, fn=%d, e=%d, d=%d, c=%d\n", p, q, n, fn, e, d, c);
    m = rsa_decrypt(c, d, n);
    printf("解密后的明文m：%d\n", m);
    return 0;
}

在上述代码中，我们使用了求最大公约数、求最小公倍数、判断素数、求模逆、RSA加密和RSA解密等函数。其中，求模逆算法使用了扩展欧几里得算法，用于求解a在模n下的逆元x，即满足ax ≡ 1 (mod n)的x。

需要注意的是，在实际应用中，通常会选择更大的素数p和q来保证加密的安全性。同时，为了避免破解，还需要在选择素数时进行一定的随机化处理。