RSA算法加解密c语言

RSA算法是一种非对称加密算法，广泛应用于数据加密和数字签名。它的安全性基于大整数分解的困难性。以下是RSA算法在C语言中的基本实现步骤：

1. **密钥生成**：
- 选择两个大素数 \( p \) 和 \( q \)。
- 计算 \( n = p \times q \)。
- 计算欧拉函数 \( \phi(n) = (p-1)(q-1) \)。
- 选择一个整数 \( e \)，使得 \( 1 < e < \phi(n) \) 且 \( e \) 与 \( \phi(n) \) 互质。
- 计算 \( d \)，使得 \( d \times e \equiv 1 \ (\text{mod} \ \phi(n)) \)。

2. **加密**：
- 将明文 \( m \) 转换为整数，且 \( m < n \)。
- 计算密文 \( c = m^e \ (\text{mod} \ n) \)。

3. **解密**：
- 计算明文 \( m = c^d \ (\text{mod} \ n) \)。

以下是一个简单的RSA算法在C语言中的实现示例：

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

void rsa_key_generation(mpz_t p, mpz_t q, mpz_t n, mpz_t phi, mpz_t e, mpz_t d) {
    // 选择两个大素数 p 和 q
    mpz_init_set_str(p, "61", 10);
    mpz_init_set_str(q, "53", 10);

    // 计算 n = p * q
    mpz_mul(n, p, q);

    // 计算 phi = (p-1) * (q-1)
    mpz_sub_ui(p, p, 1);
    mpz_sub_ui(q, q, 1);
    mpz_mul(phi, p, q);

    // 选择一个整数 e，使得 1 < e < phi 且 e 与 phi 互质
    mpz_init_set_str(e, "17", 10);

    // 计算 d，使得 d * e ≡ 1 (mod phi)
    mpz_invert(d, e, phi);
}

void rsa_encrypt(mpz_t c, mpz_t m, mpz_t e, mpz_t n) {
    mpz_powm(c, m, e, n);
}

void rsa_decrypt(mpz_t m, mpz_t c, mpz_t d, mpz_t n) {
    mpz_powm(m, c, d, n);
}

int main() {
    mpz_t p, q, n, phi, e, d, m, c;
    mpz_inits(p, q, n, phi, e, d, m, c, NULL);

    // 生成密钥
    rsa_key_generation(p, q, n, phi, e, d);

    // 明文
    mpz_set_str(m, "65", 10);

    // 加密
    rsa_encrypt(c, m, e, n);

    // 解密
    rsa_decrypt(m, c, d, n);

    // 输出结果
    gmp_printf("明文: %Zd\n", m);
    gmp_printf("密文: %Zd\n", c);

    mpz_clears(p, q, n, phi, e, d, m, c, NULL);
    return 0;
}

这个示例使用了GMP库来处理大整数运算。你需要先安装GMP库，并在编译时链接它：

gcc -o rsa_example rsa_example.c -lgmp