RSA加密算法C语言实现

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

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

#define MAX_PRIME 10000 // 素数最大值
#define MAX_STRING 100 // 输入字符串最大长度
#define BLOCK_SIZE 2 // 每个块的长度

// 生成随机素数
int generate_prime() {
    int primes[MAX_PRIME], i, j, k = 0;
    primes[0] = 2; // 第一个素数是2
    for (i = 3; i < MAX_PRIME; i += 2) { // 从3开始遍历奇数
        for (j = 0; j < k && primes[j] * primes[j] <= i; j++) {
            if (i % primes[j] == 0) { // 如果i能被已知素数整除，则不是素数
                break;
            }
        }
        if (j == k || primes[j] * primes[j] > i) { // 如果i不能被已知素数整除，则是素数
            primes[k++] = i;
        }
    }
    return primes[rand() % k]; // 从已知素数中随机选择一个素数
}

// 求最大公因数
int gcd(int a, int b) {
    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

// 求模数的逆元
int mod_inverse(int a, int m) {
    int x, y, r, q, x1 = 1, x2 = 0, y1 = 0, y2 = 1;
    if (m == 1) {
        return 0;
    }
    r = a % m;
    while (r != 0) {
        q = a / m;
        x = x2 - q * x1;
        y = y2 - q * y1;
        a = m;
        m = r;
        x2 = x1;
        x1 = x;
        y2 = y1;
        y1 = y;
        r = a % m;
    }
    if (y2 < 0) {
        y2 += abs(m);
    }
    return y2;
}

// 加密函数
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() {
    srand(time(NULL));

    int p = generate_prime(); // 生成素数p
    int q = generate_prime(); // 生成素数q
    int n = p * q; // 计算n
    int phi_n = (p - 1) * (q - 1); // 计算phi_n

    // 选择与phi_n互质的e
    int e = 65537; // 公钥指数e
    while (gcd(e, phi_n) != 1) {
        e = rand() % phi_n;
    }

    // 计算私钥指数d
    int d = mod_inverse(e, phi_n);

    char input[MAX_STRING];
    printf("请输入要加密的字符串：");
    fgets(input, MAX_STRING, stdin);
    int len = strlen(input) - 1; // 去掉输入字符串末尾的换行符
    int blocks[len / BLOCK_SIZE + 1]; // 将输入字符串分块
    memset(blocks, 0, sizeof(blocks));
    for (int i = 0; i < len; i++) {
        blocks[i / BLOCK_SIZE] += input[i] * pow(256, i % BLOCK_SIZE);
    }

    // 加密每个块
    printf("加密后的密文：");
    for (int i = 0; i < len / BLOCK_SIZE + 1; i++) {
        int c = encrypt(blocks[i], e, n);
        printf("%d ", c);
    }
    printf("\n");

    // 解密每个块
    printf("解密后的明文：");
    for (int i = 0; i < len / BLOCK_SIZE + 1; i++) {
        int m = decrypt(blocks[i], d, n);
        for (int j = 0; j < BLOCK_SIZE; j++) {
            printf("%c", (m / (int) pow(256, j)) % 256);
        }
    }
    printf("\n");

    return 0;
}

在本程序中，首先生成两个随机素数p和q，并计算n和phi_n。然后选择与phi_n互质的公钥指数e，并计算私钥指数d。接着将输入的字符串分块，并对每个块进行加密，输出加密后的密文。最后对每个块进行解密，输出解密后的明文。注意，为了方便起见，本程序中每个块的长度固定为2，可以根据需要进行修改。