用C语言实现完整的RSA加密算法

以下是一个完整的C语言实现RSA加密算法的示例代码，包括密钥生成、加密、解密三个过程。代码仅供参考。

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

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

/* 求扩展欧几里得算法 */
int extend_euclid(int a, int b, int *x, int *y) {
    if(b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int r = extend_euclid(b, a % b, x, y);
    int temp = *x;
    *x = *y;
    *y = temp - a / b * (*y);
    return r;
}

/* 判断素数 */
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 bit_len) {
    int random_num = 0;
    while(1) {
        random_num = rand() % (int)pow(10, bit_len);
        if(is_prime(random_num)) {
            break;
        }
    }
    return random_num;
}

/* 生成密钥 */
void generate_key(int bit_len, int *n, int *e, int *d) {
    srand((unsigned)time(NULL));
    int p = generate_prime(bit_len);
    int q = generate_prime(bit_len);
    *n = p * q;
    int phi_n = (p - 1) * (q - 1);

    *e = 17; // 固定选择公钥e=17，也可以使用其他值
    while(gcd(phi_n, *e) != 1) {
        *e += 2;
    }

    extend_euclid(phi_n, *e, d, NULL);
    *d = (*d % phi_n + phi_n) % phi_n;
}

/* 加密 */
int encrypt(int plaintext, int n, int e) {
    return (int)(pow(plaintext, e)) % n;
}

/* 解密 */
int decrypt(int ciphertext, int n, int d) {
    return (int)(pow(ciphertext, d)) % n;
}

int main() {
    int bit_len = 8; // 选择素数的位数
    int n, e, d;
    generate_key(bit_len, &n, &e, &d);

    char plaintext_str[100];
    printf("请输入要加密的明文：");
    scanf("%s", plaintext_str);
    int plaintext_len = strlen(plaintext_str);

    int *ciphertext = (int *)malloc(plaintext_len * sizeof(int));
    for(int i = 0; i < plaintext_len; i++) {
        ciphertext[i] = encrypt(plaintext_str[i], n, e);
    }

    printf("加密后的密文为：");
    for(int i = 0; i < plaintext_len; i++) {
        printf("%d ", ciphertext[i]);
    }
    printf("\n");

    printf("解密后的明文为：");
    for(int i = 0; i < plaintext_len; i++) {
        printf("%c", decrypt(ciphertext[i], n, d));
    }
    printf("\n");

    free(ciphertext);
    return 0;
}

在实现过程中，密钥生成过程中选择两个大素数p、q，计算n=pq和phi(n)=(p-1)(q-1)，通过扩展欧几里得算法计算得到私钥d。加密和解密过程中使用快速幂算法。为方便操作，本示例代码将明文转换为字符串的形式进行加密和解密。