C语言源代码RSA对任意长度的数值型消息采用平方乘法进行加解密

下面是C语言源代码RSA对任意长度的数值型消息采用平方乘法进行加解密的示例代码：

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

#define MAX_DIGITS 1000

// Function to calculate power of x raised to the power of y
long long int power(long long int x, long long int y, long long int p) {
    long long int res = 1;

    x = x % p;

    while (y > 0) {
        if (y & 1) {
            res = (res * x) % p;
        }
        y = y >> 1;
        x = (x * x) % p;
    }

    return res;
}

// Function to calculate GCD of two numbers
long long int gcd(long long int a, long long int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// Function to generate random prime number
long long int generate_prime(int num_bits) {
    long long int p;
    int i, j, is_prime;
    char *sieve = calloc(pow(2, num_bits / 2) + 1, sizeof(char));

    do {
        is_prime = 1;
        p = rand() % (long long int)pow(2, num_bits / 2 - 1) + (long long int)pow(2, num_bits / 2 - 1);

        for (i = 2; i <= sqrt(p); i++) {
            if (p % i == 0) {
                is_prime = 0;
                break;
            }
        }

        if (is_prime) {
            return p;
        }

        memset(sieve, 0, sizeof(char) * (long long int)pow(2, num_bits / 2) + 1);

        for (i = 2; i <= sqrt((long long int)pow(2, num_bits / 2)); i++) {
            if (sieve[i] == 0) {
                for (j = i * i; j <= (long long int)pow(2, num_bits / 2); j += i) {
                    sieve[j] = 1;
                }
            }
        }

        for (i = 2; i <= (long long int)pow(2, num_bits / 2); i++) {
            if (sieve[i] == 0 && gcd(p, i) == 1) {
                return p * i;
            }
        }
    } while (1);
}

// Function to calculate modular inverse
long long int mod_inverse(long long int a, long long int m) {
    long long int m0 = m, t, q;
    long long int x0 = 0, x1 = 1;

    if (m == 1) {
        return 0;
    }

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0) {
        x1 += m0;
    }

    return x1;
}

// Function to encrypt message
long long int* encrypt(char *msg, long long int e, long long int n) {
    long long int *cipher = calloc(strlen(msg), sizeof(long long int));
    int i;

    for (i = 0; i < strlen(msg); i++) {
        cipher[i] = power((long long int)msg[i], e, n);
    }

    return cipher;
}

// Function to decrypt cipher
char* decrypt(long long int *cipher, int length, long long int d, long long int n) {
    char *msg = calloc(length + 1, sizeof(char));
    int i;

    for (i = 0; i < length; i++) {
        msg[i] = (char)power(cipher[i], d, n);
    }

    return msg;
}

int main() {
    int num_bits = 16;
    long long int p, q, n, phi_n, e, d;
    char *msg = "Hello, world!";
    long long int *cipher;
    char *decrypted_msg;

    // Generate random prime numbers
    srand(time(NULL));
    p = generate_prime(num_bits);
    q = generate_prime(num_bits);

    // Calculate n and phi(n)
    n = p * q;
    phi_n = (p - 1) * (q - 1);

    // Choose a small odd integer e that is relatively prime to phi(n)
    e = 3;
    while (gcd(e, phi_n) != 1) {
        e += 2;
    }

    // Calculate modular inverse of e
    d = mod_inverse(e, phi_n);

    // Encrypt message
    cipher = encrypt(msg, e, n);

    // Decrypt cipher
    decrypted_msg = decrypt(cipher, strlen(msg), d, n);

    printf("Original message: %s\n", msg);
    printf("Encrypted message: ");
    int i;
    for (i = 0; i < strlen(msg); i++) {
        printf("%lld ", cipher[i]);
    }
    printf("\n");
    printf("Decrypted message: %s\n", decrypted_msg);

    free(cipher);
    free(decrypted_msg);

    return 0;
}

这个示例代码使用了平方乘法来计算幂，同时还包括了生成随机素数、计算模逆等功能。如果您想要更深入了解RSA算法，可以参考一些相关的书籍或者在线教程。