用c语言写一个RSA算法

RSA算法是一种非对称加密算法，它的安全性基于大数分解的困难性。以下是一个用C语言实现RSA算法的示例代码：

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

#define MAX_PRIME 10000

int is_prime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int mod_pow(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent /= 2;
    }
    return result;
}

int mod_inverse(int a, int m) {
    int m0 = m, t, q;
    int 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;
}

int generate_prime() {
    int prime;
    do {
        prime = rand() % MAX_PRIME + 1;
    } while (!is_prime(prime));
    return prime;
}

int main() {
    srand(time(NULL));
    int p = generate_prime();
    int q = generate_prime();
    int n = p * q;
    int phi = (p - 1) * (q - 1);
    int e;
    do {
        e = rand() % phi + 1;
    } while (gcd(e, phi) != 1);
    int d = mod_inverse(e, phi);
    printf("p = %d\n", p);
    printf("q = %d\n", q);
    printf("n = %d\n", n);
    printf("phi = %d\n", phi);
    printf("e = %d\n", e);
    printf("d = %d\n", d);
    int message = 123456;
    int encrypted = mod_pow(message, e, n);
    int decrypted = mod_pow(encrypted, d, n);
    printf("message = %d\n", message);
    printf("encrypted = %d\n", encrypted);
    printf("decrypted = %d\n", decrypted);
    return 0;
}

这段代码实现了RSA算法的关键步骤，包括生成两个随机质数p和q，计算n和phi，选择一个与phi互质的整数e作为公钥，计算d作为私钥，以及使用公钥加密和私钥解密消息。