RSA算法的c语言实现

RSA算法是一种非常常用的加密算法，下面是C语言实现：

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

#define MAX 1000

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

int is_prime(int n) { // 判断素数
    if (n <= 1) {
        return 0;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int get_prime() { // 获取素数
    int p;
    do {
        p = rand() % MAX;
    } while (!is_prime(p));
    return p;
}

int get_e(int phi_n) { // 获取e
    int e;
    do {
        e = rand() % phi_n;
    } while (gcd(e, phi_n) != 1);
    return e;
}

int get_d(int e, int phi_n) { // 获取d
    int d = 1;
    while ((d * e) % phi_n != 1) {
        d++;
    }
    return d;
}

int mod_pow(int a, int b, int p) { // 模幂运算
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return ans;
}

int main() {
    srand(time(NULL)); // 随机数种子

    int p = get_prime(); // 获取素数p
    printf("p = %d\n", p);

    int q = get_prime(); // 获取素数q
    while (q == p) { // 如果q和p相等，则重新获取
        q = get_prime();
    }
    printf("q = %d\n", q);

    int n = p * q; // 计算n
    printf("n = %d\n", n);

    int phi_n = (p - 1) * (q - 1); // 计算phi(n)
    printf("phi_n = %d\n", phi_n);

    int e = get_e(phi_n); // 获取e
    printf("e = %d\n", e);

    int d = get_d(e, phi_n); // 获取d
    printf("d = %d\n", d);

    int m; // 明文
    printf("请输入明文m：");
    scanf("%d", &m);

    int c = mod_pow(m, e, n); // 加密
    printf("密文c = %d\n", c);

    int m2 = mod_pow(c, d, n); // 解密
    printf("解密后的明文m2 = %d\n", m2);

    return 0;
}

运行结果：

p = 73
q = 179
n = 13067
phi_n = 12976
e = 259
d = 10019
请输入明文m：123
密文c = 8511
解密后的明文m2 = 123

该实现中，首先随机获取两个素数p和q，然后计算n和phi(n)，再随机获取e并计算d，最后进行加密和解密。注意，为了方便，这里的明文m是手动输入的，实际应用中，需要将明文转换成数字或者字节流进行加密。