4.RSA加密算法的C语言实现

以下是RSA加密算法的C语言实现：

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

#define MAX 10000

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

int prime(int n) {
    int i, j;
    int isPrime = 1;
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            isPrime = 0;
            break;
        }
    }
    return isPrime;
}

int generate_primes(int *p, int *q) {
    srand(time(NULL));
    int n1 = rand() % MAX + 1;
    int n2 = rand() % MAX + 1;
    while (!prime(n1)) {
        n1 = rand() % MAX + 1;
    }
    while (!prime(n2) || n1 == n2) {
        n2 = rand() % MAX + 1;
    }
    *p = n1;
    *q = n2;
    return (*p) * (*q);
}

int generate_key(int *e, int *d, int phi) {
    srand(time(NULL));
    int k = 2;
    int temp = phi;
    while (gcd(k, temp) != 1) {
        k = rand() % (phi - 2) + 2;
    }
    *e = k;
    int i = 1;
    while (1) {
        if ((i * phi + 1) % k == 0) {
            *d = (i * phi + 1) / k;
            break;
        }
        i++;
    }
    return *e;
}

int power_mod(int a, int b, int m) {
    int result = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b = b / 2;
    }
    return result;
}

void encrypt(int *cipher, char *message, int len, int e, int n) {
    int i;
    for (i = 0; i < len; i++) {
        cipher[i] = power_mod(message[i], e, n);
    }
}

void decrypt(char *message, int *cipher, int len, int d, int n) {
    int i;
    for (i = 0; i < len; i++) {
        message[i] = power_mod(cipher[i], d, n);
    }
}

int main() {
    int p, q;
    int n = generate_primes(&p, &q);
    int phi = (p - 1) * (q - 1);
    int e, d;
    generate_key(&e, &d, phi);
    printf("p = %d\nq = %d\nn = %d\ne = %d\nd = %d\n", p, q, n, e, d);
    char message[MAX];
    printf("Enter message to encrypt: ");
    scanf("%s", message);
    int len = strlen(message);
    int cipher[len];
    encrypt(cipher, message, len, e, n);
    printf("Encrypted message: ");
    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", cipher[i]);
    }
    printf("\n");
    char decrypted[len];
    decrypt(decrypted, cipher, len, d, n);
    printf("Decrypted message: %s\n", decrypted);
    return 0;
}

该程序实现了RSA加密算法的基本功能，包括生成素数、生成公钥和私钥、加密和解密消息。程序中使用了随机数生成器来生成素数和公钥，同时利用欧拉函数计算私钥。加密和解密过程使用了模幂运算，避免了对大数进行直接计算的问题。