rsa加密算法c语言实现

RSA加密算法是一种非对称加密算法，它需要一对公钥和私钥来加密和解密数据。以下是RSA加密算法的C语言实现代码：

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

#define MAX_PRIME 1000000 // 最大素数范围
#define BUFFER_SIZE 1024 // 缓冲区大小

// 生成素数
int generate_prime(int *prime_array, int max_prime) {
    int i, j, is_prime, count = 0;
    for (i = 2; i <= max_prime; i++) {
        is_prime = 1;
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                is_prime = 0;
                break;
            }
        }
        if (is_prime) {
            prime_array[count++] = i;
        }
    }
    return count;
}

// 随机选择素数
int random_prime(int *prime_array, int prime_count) {
    int index = rand() % prime_count;
    return prime_array[index];
}

// 计算模反元素
int mod_inverse(int a, int b) {
    int m0 = b, t, q;
    int x0 = 0, x1 = 1;
    if (b == 1) {
        return 0;
    }
    while (a > 1) {
        q = a / b;
        t = b;
        b = a % b;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0) {
        x1 += m0;
    }
    return x1;
}

// 计算幂模
int mod_pow(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent / 2;
        base = (base * base) % modulus;
    }
    return result;
}

// 生成公钥和私钥
void generate_key(int *public_key, int *private_key, int prime1, int prime2) {
    int n, phi, e, d, i, prime_count, prime_array[MAX_PRIME];
    srand(time(NULL));
    n = prime1 * prime2;
    phi = (prime1 - 1) * (prime2 - 1);
    prime_count = generate_prime(prime_array, MAX_PRIME);
    e = random_prime(prime_array, prime_count);
    while (e < phi && mod_inverse(e, phi) != 1) {
        e = random_prime(prime_array, prime_count);
    }
    d = mod_inverse(e, phi);
    public_key[0] = e;
    public_key[1] = n;
    private_key[0] = d;
    private_key[1] = n;
}

// 加密数据
void encrypt(char *plain_text, char *cipher_text, int *public_key) {
    int i, j, len, block, cipher, public_key_e, public_key_n;
    len = strlen(plain_text);
    public_key_e = public_key[0];
    public_key_n = public_key[1];
    for (i = 0; i < len; i += BUFFER_SIZE) {
        block = 0;
        for (j = 0; j < BUFFER_SIZE && i + j < len; j++) {
            block = block * 256 + plain_text[i + j];
        }
        cipher = mod_pow(block, public_key_e, public_key_n);
        sprintf(cipher_text + strlen(cipher_text), "%d ", cipher);
    }
}

// 解密数据
void decrypt(char *cipher_text, char *plain_text, int *private_key) {
    int i, j, len, block, plain, private_key_d, private_key_n;
    char *cipher_token;
    len = strlen(cipher_text);
    private_key_d = private_key[0];
    private_key_n = private_key[1];
    cipher_token = strtok(cipher_text, " ");
    while (cipher_token != NULL) {
        sscanf(cipher_token, "%d", &cipher);
        plain = mod_pow(cipher, private_key_d, private_key_n);
        for (i = BUFFER_SIZE - 1; i >= 0; i--) {
            block = plain / pow(256, i);
            plain_text[strlen(plain_text)] = block;
            plain = plain - block * pow(256, i);
        }
        cipher_token = strtok(NULL, " ");
    }
}

int main() {
    int prime1 = 61, prime2 = 53;
    int public_key[2], private_key[2];
    char plain_text[] = "Hello, World!";
    char cipher_text[1024] = "";
    char decrypted_text[1024] = "";
    generate_key(public_key, private_key, prime1, prime2);
    encrypt(plain_text, cipher_text, public_key);
    decrypt(cipher_text, decrypted_text, private_key);
    printf("Plain text: %s\n", plain_text);
    printf("Cipher text: %s\n", cipher_text);
    printf("Decrypted text: %s\n", decrypted_text);
    return 0;
}

在此示例中，我们使用了固定的两个素数61和53来生成公钥和私钥。在实际应用中，需要使用更大的素数来保证安全性。