用C语言编程实现RSA算法

RSA算法是一种非对称加密算法，其基本原理是利用两个大质数的乘积作为公钥，将明文进行加密，只有私钥能够解密。以下是用C语言编写RSA算法的示例代码：

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

#define MAX 1000

//判断一个数是否为质数
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 generate_prime() {
    int p = rand() % MAX;
    while (!is_prime(p)) {
        p = rand() % MAX;
    }
    return p;
}

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

//求逆元
int inverse(int a, int b) {
    int r, q, t1, t2, t;
    t1 = 0;
    t2 = 1;
    r = a;
    q = a / b;
    while (r != 1) {
        t = t1 - t2 * q;
        t1 = t2;
        t2 = t;
        r = a % b;
        a = b;
        b = r;
        q = a / b;
    }
    if (t2 < 0) {
        t2 += t1;
    }
    return t2;
}

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

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

int main() {
    int p, q, n, phi, e, d, m, c, m1;
    srand((unsigned)time(NULL));
    //生成两个大质数p和q
    p = generate_prime();
    q = generate_prime();
    while (p == q) {
        q = generate_prime();
    }
    //计算n和phi
    n = p * q;
    phi = (p - 1) * (q - 1);
    //选择e，保证e与phi互质
    e = rand() % (phi - 2) + 2;
    while (gcd(e, phi) != 1) {
        e = rand() % (phi - 2) + 2;
    }
    //求d，使得d为e的逆元
    d = inverse(phi, e);
    //输入明文
    printf("请输入要加密的数字:");
    scanf("%d", &m);
    //加密
    c = encrypt(m, e, n);
    printf("加密后的数字为：%d\n", c);
    //解密
    m1 = decrypt(c, d, n);
    printf("解密后的数字为：%d\n", m1);
    return 0;
}

在这个示例代码中，首先生成两个大质数p和q，然后计算出n和phi，选择e使得e和phi互质，然后求出d，使得d为e的逆元。接着输入要加密的明文m，进行加密得到密文c，然后再对密文进行解密，得到明文m1。