用c语言实现RSA算法

RSA算法是一种非常重要的公钥加密算法，它基于大整数的质因数分解难题。下面是用C语言实现RSA算法的代码示例：

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

#define MAX_LEN 1000
#define BLOCK_SIZE 2

typedef struct {
    int n; // modulus
    int e; // public exponent
} PublicKey;

typedef struct {
    int n; // modulus
    int d; // private exponent
} PrivateKey;

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

int mod_pow(int base, int exp, int mod) {
    int result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

// 生成公钥和私钥
void generate_keys(PublicKey *pub, PrivateKey *priv) {
    int p, q, phi, e, d;

    // 生成两个大素数p和q
    do {
        p = rand() % (int) sqrt(MAX_LEN) + 1;
    } while (!is_prime(p));
    do {
        q = rand() % (int) sqrt(MAX_LEN) + 1;
    } while (!is_prime(q));

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

    // 选择公钥e
    do {
        e = rand() % phi + 1;
    } while (gcd(e, phi) != 1);

    // 计算私钥d
    d = mod_inverse(e, phi);

    pub->e = e;
    priv->n = pub->n;
    priv->d = d;
}

// 加密
char *encrypt(char *msg, PublicKey pub) {
    int len, i, j, num, encrypted;
    char *encrypted_msg;

    len = strlen(msg);
    encrypted_msg = (char *) malloc(len * BLOCK_SIZE + 1);
    memset(encrypted_msg, 0, len * BLOCK_SIZE + 1);

    for (i = 0, j = 0; i < len; i += BLOCK_SIZE, j += BLOCK_SIZE) {
        num = msg[i] * 256 + msg[i + 1];
        encrypted = mod_pow(num, pub.e, pub.n);
        sprintf(&encrypted_msg[j], "%04d", encrypted);
    }

    return encrypted_msg;
}

// 解密
char *decrypt(char *encrypted_msg, PrivateKey priv) {
    int len, i, j, num, decrypted;
    char *msg;

    len = strlen(encrypted_msg);
    msg = (char *) malloc(len / BLOCK_SIZE + 1);
    memset(msg, 0, len / BLOCK_SIZE + 1);

    for (i = 0, j = 0; i < len; i += BLOCK_SIZE, j++) {
        num = (encrypted_msg[i] - '0') * 1000 + (encrypted_msg[i + 1] - '0') * 100
            + (encrypted_msg[i + 2] - '0') * 10 + (encrypted_msg[i + 3] - '0');
        decrypted = mod_pow(num, priv.d, priv.n);
        msg[j] = decrypted / 256;
        msg[j + 1] = decrypted % 256;
    }

    return msg;
}

int main() {
    PublicKey pub;
    PrivateKey priv;
    char *msg = "Hello World!";
    char *encrypted_msg;
    char *decrypted_msg;

    srand(time(NULL));

    generate_keys(&pub, &priv);

    printf("Public key: n=%d, e=%d\n", pub.n, pub.e);
    printf("Private key: n=%d, d=%d\n", priv.n, priv.d);

    encrypted_msg = encrypt(msg, pub);
    printf("Encrypted message: %s\n", encrypted_msg);

    decrypted_msg = decrypt(encrypted_msg, priv);
    printf("Decrypted message: %s\n", decrypted_msg);

    free(encrypted_msg);
    free(decrypted_msg);

    return 0;
}

需要注意的是，这里使用的是简化版的RSA算法，仅用于示例。在实际使用中，需要使用更加复杂的算法来确保安全性。此外，还需要注意对大整数的处理，可使用第三方库如GMP来进行处理。