RSA算法实现C语言

RSA算法是一种非对称加密算法，其实现过程主要分为三个步骤：密钥生成、加密和解密。下面是RSA算法的C语言实现：

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

// 定义常量
#define SIZE 1024

// 定义大素数p和q，以及公钥e和私钥d
unsigned long p,q,n,e,d;

// 定义欧拉函数值
unsigned long phi;

// 定义明文和密文数组
char plaintext[SIZE], ciphertext[SIZE];

// 生成大素数函数
unsigned long generate_prime(unsigned long min, unsigned long max)
{
    unsigned long i;
    while (1)
    {
        // 生成随机数
        i = rand() % (max - min + 1) + min;
        // 判断是否为素数
        if (is_prime(i))
        {
            return i;
        }
    }
}

// 判断素数函数
int is_prime(unsigned long num)
{
    unsigned long i;
    if (num < 2)
    {
        return 0;
    }
    for (i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

// 计算最大公约数函数
unsigned long gcd(unsigned long a, unsigned long b)
{
    unsigned long r;
    while (b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 计算扩展欧几里得算法函数
unsigned long extended_euclidean_algorithm(unsigned long a, unsigned long b, int *x, int *y)
{
    unsigned long r, temp;
    if (b == 0)
    {
        *x = 1;
        *y = 0;
        return a;
    }
    r = extended_euclidean_algorithm(b, a % b, x, y);
    temp = *x;
    *x = *y;
    *y = temp - a / b * (*y);
    return r;
}

// 加密函数
void encrypt(char *plaintext, char *ciphertext)
{
    int i;
    unsigned long m, c;
    for (i = 0; plaintext[i] != '\0'; i++)
    {
        // 将明文转换为数字
        m = plaintext[i];
        // 计算密文
        c = (unsigned long)pow(m, e) % n;
        // 将密文转换为字符
        ciphertext[i] = (char)c;
    }
    ciphertext[i] = '\0';
}

// 解密函数
void decrypt(char *ciphertext, char *plaintext)
{
    int i;
    unsigned long m, c;
    for (i = 0; ciphertext[i] != '\0'; i++)
    {
        // 将密文转换为数字
        c = ciphertext[i];
        // 计算明文
        m = (unsigned long)pow(c, d) % n;
        // 将明文转换为字符
        plaintext[i] = (char)m;
    }
    plaintext[i] = '\0';
}

// 主函数
int main()
{
    int i, x, y;
    srand((unsigned)time(NULL));
    // 生成两个大素数p和q
    p = generate_prime(1000, 10000);
    q = generate_prime(1000, 10000);
    // 计算n和phi
    n = p * q;
    phi = (p - 1) * (q - 1);
    // 生成公钥e
    do
    {
        e = rand() % phi;
    } while (gcd(e, phi) != 1);
    // 生成私钥d
    d = extended_euclidean_algorithm(e, phi, &x, &y);
    if (x < 0)
    {
        d = x + phi;
    }
    else
    {
        d = x;
    }
    // 输出公钥和私钥
    printf("p=%lu, q=%lu\n", p, q);
    printf("n=%lu, phi=%lu\n", n, phi);
    printf("e=%lu, d=%lu\n", e, d);
    // 输入明文
    printf("Enter the plaintext: ");
    gets(plaintext);
    // 加密明文
    encrypt(plaintext, ciphertext);
    // 输出密文
    printf("The ciphertext is: ");
    for (i = 0; ciphertext[i] != '\0'; i++)
    {
        printf("%02X", (unsigned char)ciphertext[i]);
    }
    printf("\n");
    // 解密密文
    decrypt(ciphertext, plaintext);
    // 输出明文
    printf("The plaintext is: %s\n", plaintext);
    return 0;
}

在上述代码中，我们定义了常量SIZE为1024，表示明文和密文的最大长度为1024。我们还定义了大素数p和q、公钥e和私钥d、欧拉函数值phi、明文和密文数组plaintext和ciphertext等变量。

在主函数中，我们首先生成两个大素数p和q，并计算n和phi。然后，我们随机生成公钥e，并用扩展欧几里得算法生成私钥d。接着，我们输入明文，调用encrypt函数进行加密，再输出密文。最后，我们调用decrypt函数进行解密，再输出明文。

在encrypt函数中，我们将明文转换为数字m，然后计算密文c，最后将密文转换为字符ciphertext。在decrypt函数中，我们将密文转换为数字c，然后计算明文m，最后将明文转换为字符plaintext。

需要注意的是，在加密和解密过程中，我们使用了pow函数来计算幂，因此需要引入math.h头文件。