C语言非对称加密实战指南（手把手教你用C语言实现RSA加密算法）

为什么选择RSA？

RSA是最早且最广泛使用的非对称加密算法之一，其安全性基于大整数分解的数学难题。在本教程中，我们将使用C语言实现一个简化版的RSA，帮助你理解其工作流程。

RSA算法基本步骤

1. 选择两个大素数 p 和 q
2. 计算 n = p × q
3. 计算欧拉函数 φ(n) = (p-1)(q-1)
4. 选择一个整数 e，满足 1 < e < φ(n)，且 gcd(e, φ(n)) = 1
5. 计算 d，使得 (d × e) mod φ(n) = 1（即 d 是 e 关于 φ(n) 的模逆元）
6. 公钥为 (e, n)，私钥为 (d, n)

C语言实现简化版RSA

为了便于理解，我们使用较小的素数（实际应用中应使用非常大的素数）。以下是完整的C语言代码：

#include <stdio.h>#include <stdlib.h>// 计算最大公约数gcd(int a, int b) {    if (b == 0)        return a;    return gcd(b, a % b);}// 扩展欧几里得算法求模逆元int modInverse(int a, int m) {    for (int x = 1; x < m; x++) {        if ((a * x) % m == 1)            return x;    }    return -1; // 不存在逆元}// 快速幂取模long long modPow(long long base, long long exp, long long mod) {    long long result = 1;    base = base % mod;    while (exp > 0) {        if (exp % 2 == 1)            result = (result * base) % mod;        exp = exp >> 1;        base = (base * base) % mod;    }    return result;}int main() {    // 步骤1：选择两个小素数（仅用于演示）    int p = 61, q = 53;        // 步骤2：计算n    long long n = (long long)p * q;        // 步骤3：计算φ(n)    long long phi = (long long)(p - 1) * (q - 1);        // 步骤4：选择e    int e = 17; // 常用值，需满足gcd(e, phi) == 1    if (gcd(e, phi) != 1) {        printf("Error: e and phi are not coprime!\n");        return 1;    }        // 步骤5：计算d    int d = modInverse(e, phi);    if (d == -1) {        printf("Error: Modular inverse does not exist!\n");        return 1;    }        printf("公钥 (e, n): (%d, %lld)\n", e, n);    printf("私钥 (d, n): (%d, %lld)\n", d, n);        // 加密示例    long long message = 123; // 明文    long long ciphertext = modPow(message, e, n);    printf("明文: %lld\n", message);    printf("密文: %lld\n", ciphertext);        // 解密    long long decrypted = modPow(ciphertext, d, n);    printf("解密后: %lld\n", decrypted);        return 0;}

编译与运行

将上述代码保存为 rsa_demo.c，然后在终端执行：

gcc rsa_demo.c -o rsa_demo./rsa_demo

你应该会看到类似以下的输出：

公钥 (e, n): (17, 3233)私钥 (d, n): (2753, 3233)明文: 123密文: 855解密后: 123

重要注意事项

• 本示例使用小素数仅用于教学目的。真实场景中必须使用至少1024位甚至2048位的大素数。
• C语言标准库不提供大数运算支持，实际项目应使用OpenSSL等专业加密库。
• C语言实现RSA时务必注意整数溢出问题，建议使用GMP等大数库。

总结

通过本教程，你已经掌握了C语言非对称加密的基本原理，并亲手实现了RSA算法的核心逻辑。虽然这是一个简化版本，但它为你深入学习密码学打下了坚实基础。记住，在生产环境中，请始终使用经过严格测试的专业加密库，如OpenSSL，以确保系统安全。

希望这篇非对称加密教程对你有所帮助！如果你有任何疑问，欢迎在评论区留言交流。