C语言实现RSA加密算法：从数学原理到代码实践

1. 项目概述：为什么要在C语言里啃RSA这块硬骨头？

如果你正在学习密码学，或者你的C语言项目里需要处理点“见不得人”的数据，比如用户密码、通信密钥或者一些敏感的配置信息，那你大概率绕不开RSA。这个由三位大佬名字首字母组成的算法，几乎是现代安全体系的基石之一，从HTTPS的握手到SSH的登录，再到数字签名，到处都有它的身影。网上关于RSA原理的文章一抓一大把，但当你真正打开代码编辑器，想在C语言里把它从数学公式变成可运行的代码时，那种“眼睛会了，手不会”的无力感就来了。参数怎么选？大整数运算怎么搞？填充方案用哪个？一堆问题扑面而来。

这个指南的目的，就是帮你跨过这道坎。我们不只讲“RSA是什么”，我们重点解决“怎么用C语言把它写出来”。我会带你从最核心的数学原理开始，手把手搭建一个最小化的、可运行的RSA加密解密程序，过程中遇到的每一个坑、每一个关键选择，我都会解释清楚为什么。最终，你会得到一个清晰的、模块化的代码框架，它可能不适用于生产环境（生产级库要考虑的性能优化和边界情况太多了），但绝对能让你透彻理解RSA在C语言中的实现脉络，无论是为了通过考试、完成课程设计，还是为你后续集成OpenSSL这样的成熟库打下坚实基础，都足够了。

2. RSA算法核心原理快速回顾

在动手写代码之前，我们必须把RSA的“数学引擎”搞清楚。别怕，我们只抓最关键的几个公式和概念，保证够用。

2.1 非对称加密的基石：公钥与私钥

RSA属于非对称加密。简单类比：你想收信，就造一个带投递口（公钥）的锁箱公布出去，谁都可以用这个投递口（公钥）把信塞进去（加密）。但这个箱子只有你有一把独特的钥匙（私钥）才能打开（解密）。公钥和私钥是一对，由算法生成，但无法从公钥推导出私钥，这是安全性的根本。

2.2 关键数学操作：模幂运算

RSA的所有加解密和签名操作，本质上都是模幂运算。它的形式是：m^e mod n。意思是，计算底数m的e次方，然后除以n取余数。这里的m是我们要加密的明文（或数字），e和n是密钥的一部分。直接计算大数的幂再取模效率极低，我们后面会用到快速模幂算法来优化。

2.3 密钥生成：三步走策略

生成一对RSA密钥，其实就是找到三个特殊的数字：n,e,d。

1. 选择两个大质数p和q：这是起点。p和q必须足够大、随机，并且彼此不同。它们的乘积n = p * q就是模数，决定了密钥的强度（例如，n为2048位，即约617位十进制数）。
2. 计算欧拉函数 φ(n)：φ(n) = (p-1) * (q-1)。这个数在后续计算中至关重要，但必须绝对保密，因为知道它就能破解私钥。
3. 选择公钥指数e：e是一个整数，需要满足两个条件：1 < e < φ(n)，并且e与φ(n)互质（即最大公约数gcd(e, φ(n)) = 1）。为了计算高效和标准化，最常用的e是65537 (0x10001)。这个数二进制下只有两个1，利于快速模幂运算，且安全性经过充分验证。
4. 计算私钥指数d：d是e关于φ(n)的模逆元。即满足(d * e) mod φ(n) = 1。计算d需要用到扩展欧几里得算法。d和n一起构成私钥。

注意：在真正的实现中，私钥通常不止保存(d, n)，还会保存p,q,dmp1,dmq1,iqmp等值，用于基于中国剩余定理(CRT)的加速解密。我们初版实现为了简化，只使用(d, n)。

2.4 加密与解密公式

• 加密（用公钥(e, n)）： 对于明文数字m（需满足0 <= m < n），计算密文c = m^e mod n。
• 解密（用私钥(d, n)）： 对于密文c，计算明文m = c^d mod n。

验证一下：因为c^d mod n = (m^e)^d mod n = m^(e*d) mod n，而根据d的定义，e*d ≡ 1 (mod φ(n))，即e*d = k*φ(n) + 1。根据欧拉定理，当m与n互质时，m^(φ(n)) ≡ 1 (mod n)，所以m^(e*d) = m^(k*φ(n)+1) = (m^(φ(n)))^k * m ≡ 1^k * m ≡ m (mod n)。即使m与n不互质，该结论依然成立（证明略），保证了加解密的正确性。

3. C语言实现的核心挑战与自研大数库选型

理解了原理，我们来看C语言的实现困境。C语言标准库并没有直接支持数百位大整数运算的数据类型。int或long long在64位系统下最多也就20位十进制数，远远不够。因此，实现RSA的第一个，也是最核心的决策，就是：如何表示和计算大整数？

3.1 方案对比：自研 vs 使用现有库

1. 完全自研大数运算库：

   • 优点：学习价值极高，能彻底掌握大数加法、减法、乘法、除法、取模、模幂、模逆等底层操作。对理解算法本质帮助最大。
   • 缺点：工程量巨大，极易引入安全漏洞（如侧信道攻击、时序攻击），性能优化困难。不适合急于实现功能或用于真实项目。

2. 使用第三方大数库（如GMP, OpenSSL BN）：

   • 优点：成熟、高效、安全。是生产环境的标准选择。OpenSSL的BN（Bignum）库尤其适合，因为它和其RSA高阶API是一体的。
   • 缺点：像是一个“黑盒”，可能会掩盖底层细节，不利于初学者理解RSA的每一个计算步骤。

3. 使用简化的大数表示进行教学实现：

   • 优点：聚焦于RSA算法流程本身，而非大数库的复杂实现。我们可以用数组来表示大数，并只实现最必要的运算（如模乘、模幂）。这是本指南选择的折中路线。
   • 缺点：性能很差，只能处理很小的密钥（比如几十位），无法达到实际安全强度。但作为教学和原理验证，完全足够。

我们的选择：为了最佳的学习效果，我们将采用第3种方案。我们会定义一个简单的BIGNUM结构体，用uint32_t数组来存储大数，并实现一个最关键的快速模幂算法。其他辅助运算（如大数乘法、取模）我们会做最大程度的简化，甚至借用一些已知函数或简单实现，以确保主线清晰。

3.2 定义我们的大数结构体

#include <stdint.h> #include <stdlib.h> #include <string.h> #define MAX_BIGNUM_SIZE 64 // 假设我们的最大位数是 64 * 32 = 2048位，对于教学示例足够 typedef struct { uint32_t digits[MAX_BIGNUM_SIZE]; // 每个元素存储32位，低位在前（little-endian） int size; // 实际使用的digits数组长度，避免遍历整个数组 } BIGNUM;

这个结构体非常简单。digits数组按从低位到高位（小端序）存储数字的每一个“块”。size表示当前数字实际占用了数组的前多少位。这种表示法在进行加减乘除时比较直观。

4. 核心算法实现：快速模幂运算

这是RSA性能的瓶颈，也是实现的关键。直接计算a^b mod m会先得到一个巨大的中间值a^b，极易溢出且效率低下。快速模幂算法通过平方-乘方法将计算分解为一系列小规模的模乘运算。

算法思想：将指数b用二进制表示。例如b = 13(二进制1101)。那么a^13 = a^(8+4+0+1) = a^8 * a^4 * a^1。我们可以从最低位开始扫描b的二进制位，在扫描过程中，a自身不断平方（计算a^1, a^2, a^4, a^8...），当遇到b的二进制位为1时，就将当前的a乘到结果中。

以下是基于我们简化BIGNUM的快速模幂算法实现框架。我们假设已有大数赋值(bn_assign)、模乘(bn_mod_mul)、取模(bn_mod)等函数（下一节会补充关键部分）。

// 快速模幂计算： result = base^exp mod mod void bn_mod_exp(BIGNUM *result, const BIGNUM *base, const BIGNUM *exp, const BIGNUM *mod) { BIGNUM temp_base, temp_exp; BIGNUM one; // 初始化：result = 1, temp_base = base % mod bn_assign_int(&one, 1); bn_assign(result, &one); bn_mod(&temp_base, base, mod); // temp_base = base % mod bn_assign(&temp_exp, exp); // 当指数大于0时循环 while (bn_cmp(&temp_exp, &one) >= 0) { // while exp >= 1 // 如果当前指数是奇数 (exp & 1)， result = (result * temp_base) % mod if (temp_exp.digits[0] & 1) { bn_mod_mul(result, result, &temp_base, mod); } // 指数右移一位 (exp = exp / 2) bn_rshift(&temp_exp, 1); // 底数平方并取模： temp_base = (temp_base * temp_base) % mod bn_mod_mul(&temp_base, &temp_base, &temp_base, mod); } }

实操心得：快速模幂算法的核心在于“边平方，边乘”，将指数运算转化为对数级别的乘法运算。在实现bn_mod_mul（模乘）时，一定要先做普通乘法，再做取模。如果先取模再乘，结果会是错误的，因为(a mod m) * (b mod m)不一定等于(a*b) mod m。

5. 完整RSA流程的C语言分步实现

现在，我们有了核心的模幂引擎，可以串联起整个RSA流程了。我们将分步骤实现密钥生成、加密和解密。

5.1 密钥生成：寻找质数与计算模逆

这是最复杂的一步。在教学中，我们通常直接指定两个小的质数p和q，避免实现复杂的质数检测算法（如米勒-拉宾素性测试）。

步骤1：选择p, q, e

// 教学示例，使用很小的质数 BIGNUM p, q, e, n, phi, d; bn_assign_int(&p, 61); // 质数p bn_assign_int(&q, 53); // 质数q bn_assign_int(&e, 17); // 公钥指数e， 需要与phi互质，17满足条件

步骤2：计算 n 和 φ(n)

// n = p * q bn_mul(&n, &p, &q); // 需要实现大数乘法 bn_mul printf("Modulus n = "); bn_print(&n); // 应输出 3233 // φ(n) = (p-1) * (q-1) BIGNUM p1, q1; bn_assign_int(&p1, 60); // p-1 bn_assign_int(&q1, 52); // q-1 bn_mul(&phi, &p1, &q1); // phi = 3120

步骤3：计算私钥指数 d (e关于φ(n)的模逆元)计算d使得(d * e) % φ(n) = 1。这需要使用扩展欧几里得算法。这里给出一个简化的迭代实现（对于教学小数字有效）：

// 简化版求模逆元，仅适用于教学小数字，非通用高效实现 int bn_mod_inverse(BIGNUM *result, const BIGNUM *a, const BIGNUM *m) { // 这里我们假设a和m是常规整数，用long long计算。实际大数需用扩展欧几里得。 long long a_val = ...; // 从BIGNUM提取值（简化） long long m_val = ...; long long t = 0, newt = 1; long long r = m_val, newr = a_val; while (newr != 0) { long long quotient = r / newr; long long tmp_t = t; t = newt; newt = tmp_t - quotient * newt; long long tmp_r = r; r = newr; newr = tmp_r - quotient * newr; } if (r > 1) return 0; // 不可逆 if (t < 0) t += m_val; bn_assign_int(result, t); return 1; } // 调用 bn_mod_inverse(&d, &e, &phi); // 计算 d = e^(-1) mod phi printf("Private exponent d = "); bn_print(&d); // 应输出 2753 (因为 17 * 2753 = 46801, 46801 % 3120 = 1)

现在，我们得到了公钥(e=17, n=3233)和私钥(d=2753, n=3233)。

5.2 数据加密：将明文转化为数字并计算

RSA加密的对象是整数。所以我们需要把字符串（如“HELLO”）先转换成整数。一个简单的方法是使用ASCII码拼接。但请注意，转换后的整数m必须满足0 <= m < n，否则加密无效。

// 示例：加密明文 "A" (ASCII 65) BIGNUM m, c; bn_assign_int(&m, 65); // 明文整数 m = 65 // 加密： c = m^e mod n bn_mod_exp(&c, &m, &e, &n); printf("Ciphertext c = "); bn_print(&c); // 输出密文整数

5.3 数据解密：还原明文数字

解密过程是加密的逆过程，使用私钥指数d。

// 解密： m_decrypted = c^d mod n BIGNUM m_decrypted; bn_mod_exp(&m_decrypted, &c, &d, &n); printf("Decrypted number = "); bn_print(&m_decrypted); // 应输出 65 // 将数字65转换回字符 printf("Decrypted char: %c\n", (char)bn_to_int(&m_decrypted)); // 输出 'A'

6. 从玩具到实用：填充方案与数据分块

上面的例子只能加密一个很小的数字（小于n）。现实中，我们需要加密任意长度的数据（如一个文件）。这就需要解决两个问题：

1. 数据转换与分块：将原始数据（字节流）分割成多个小于n的整数块。
2. 安全性增强：原始的RSA加密（教科书式RSA）是不安全的，因为它具有确定性（同样的明文永远加密成同样的密文），并且对某些特殊值（如0，1）加密后不变。因此，必须使用填充方案。

6.1 PKCS#1 v1.5 填充方案简介

最常用的填充方案之一是PKCS#1 v1.5。在加密前，它会按以下格式组装一个数据块：

00 || 02 || PS || 00 || D

• 00：保证加密后的数据块（作为整数）小于模数n。
• 02：表示这是加密块。
• PS：伪随机填充字符串，至少8字节，每个字节非零。用于使每次加密结果都不同。
• 00：分隔符。
• D：原始数据。

加密时，将这个组装好的数据块当作一个大整数m，然后计算c = m^e mod n。解密后，接收方需要解析这个格式，验证00和02，找到分隔符00，然后提取出原始数据D。

实现提示：在我们的教学代码中，可以简化填充过程。例如，在加密前，手动构造一个包含随机数的字节数组，然后将其转换为BIGNUM。这能让你理解填充的目的：引入随机性，破坏确定性。

6.2 数据分块处理流程

假设模数n是2048位（256字节）。PKCS#1 v1.5填充会占用至少11字节（00+02+至少8字节PS+00），所以实际能加密的原始数据长度最大为256 - 11 = 245字节。

因此，加密一个长文件的流程是：

1. 读取文件数据。
2. 将数据按245字节分块。
3. 对每一块数据应用PKCS#1 v1.5填充，生成一个256字节的块。
4. 将这个256字节的块转换为BIGNUMm。
5. 计算密文c = m^e mod n。
6. 将c转换回字节串（固定256字节），写入输出文件。
7. 重复直到文件结束。

解密则是逆过程：读取256字节密文块 -> 转换为BIGNUMc-> 计算m = c^d mod n-> 将m转换为字节串 -> 解析PKCS#1 v1.5格式提取数据块 -> 拼接所有数据块。

注意事项：自己实现PKCS#1 v1.5解析需要非常小心，必须严格检查格式，否则可能受到著名的“Bleichenbacher攻击”。生产环境中绝对应该使用库函数（如OpenSSL的RSA_public_encrypt/RSA_private_decrypt）来处理这些细节。

7. 集成OpenSSL库：从“造轮子”到“用轮子”

经过上面的折腾，你应该对RSA的每一步都了然于胸了。但对于真实的项目，重新发明一个RSA轮子不仅是低效的，更是危险的。现在，让我们看看如何用行业标准——OpenSSL库，来安全、高效地实现RSA。

7.1 使用OpenSSL的高阶API

OpenSSL提供了非常易用的RSA加解密API。以下是一个使用公钥加密、私钥解密的示例框架：

#include <openssl/rsa.h> #include <openssl/pem.h> #include <openssl/err.h> #include <string.h> int rsa_encrypt_with_openssl() { // 1. 生成RSA密钥对（示例，实际应从文件读取） RSA *rsa_keypair = RSA_generate_key(2048, RSA_F4, NULL, NULL); if (!rsa_keypair) { ERR_print_errors_fp(stderr); return -1; } // 待加密的明文 const unsigned char plaintext[] = "This is a secret message."; int plaintext_len = strlen((char*)plaintext) + 1; // 包含结尾的\0 // RSA_PKCS1_OAEP_PADDING 是比 PKCS#1 v1.5 更安全的填充方案 int padding = RSA_PKCS1_OAEP_PADDING; int rsa_size = RSA_size(rsa_keypair); // 获取RSA密钥长度（字节），如2048位是256字节 // 2. 加密 unsigned char ciphertext[4096]; // 缓冲区应足够大 int ciphertext_len = RSA_public_encrypt(plaintext_len, plaintext, ciphertext, rsa_keypair, padding); if (ciphertext_len == -1) { ERR_print_errors_fp(stderr); RSA_free(rsa_keypair); return -1; } printf("Encryption successful. Ciphertext length: %d\n", ciphertext_len); // 3. 解密 unsigned char decrypted[4096]; int decrypted_len = RSA_private_decrypt(ciphertext_len, ciphertext, decrypted, rsa_keypair, padding); if (decrypted_len == -1) { ERR_print_errors_fp(stderr); RSA_free(rsa_keypair); return -1; } printf("Decryption successful. Decrypted text: %s\n", decrypted); // 4. 清理 RSA_free(rsa_keypair); return 0; }

使用OpenSSL，密钥生成、填充、分块、大数运算所有这些复杂细节都被封装了。你只需要关心：用什么密钥、加密什么数据、选择什么填充方案。

7.2 从文件加载和保存密钥

实际应用中，密钥对通常是预先生成并保存在文件中的（如PEM格式）。

// 从PEM文件加载公钥 FILE *pub_key_file = fopen("public_key.pem", "r"); RSA *rsa_pubkey = PEM_read_RSA_PUBKEY(pub_key_file, NULL, NULL, NULL); fclose(pub_key_file); // 从PEM文件加载私钥（可能需要密码） FILE *priv_key_file = fopen("private_key.pem", "r"); RSA *rsa_privkey = PEM_read_RSAPrivateKey(priv_key_file, NULL, NULL, (void*)"your_password"); fclose(priv_key_file); // 使用完毕后释放 RSA_free(rsa_pubkey); RSA_free(rsa_privkey);

8. 常见问题、调试技巧与安全警示

在实现和调试RSA代码时，你会遇到各种奇怪的问题。这里记录一些典型的坑和排查思路。

8.1 自研实现中的典型问题

8.2 使用OpenSSL时的常见编译与运行错误

• 编译错误：openssl/rsa.h: No such file or directory

  • 原因：没有安装OpenSSL开发库。
  • 解决：
    • Ubuntu/Debian:sudo apt-get install libssl-dev
    • CentOS/RHEL:sudo yum install openssl-devel
    • 编译时链接库：gcc your_program.c -o your_program -lssl -lcrypto

• 运行时错误：EVP_PKEY_encrypt_init:rsa routines:OPENSSL_internal:NO_KEY_SET

  • 原因：通常是因为使用了错误类型的密钥结构。PEM_read_RSA_PUBKEY和PEM_read_RSAPublicKey读取的格式不同。前者是SubjectPublicKeyInfo格式（通用），后者是PKCS#1格式。
  • 解决：统一使用PEM_read_RSA_PUBKEY读公钥，PEM_read_RSAPrivateKey读私钥。检查你的PEM文件开头是否是-----BEGIN PUBLIC KEY-----（对应PUBKEY）或-----BEGIN RSA PRIVATE KEY-----（对应RSAPrivateKey）。

• 解密失败，返回-1：

  • 原因1：密文损坏，或者长度不对（必须等于RSA密钥长度）。
  • 原因2：使用的填充方案与加密时不一致。
  • 原因3：用错了密钥（比如用公钥去解密）。
  • 解决：确保加解密双方使用相同的密钥对和填充方案。打印并对比密文长度与RSA_size()的返回值。

8.3 至关重要的安全警示

1. 绝对不要使用自己编写的RSA代码处理真实敏感数据。教学实现缺少侧信道攻击防护、随机数质量无法保证、填充解析可能存在漏洞。生产环境必须使用经过严格审计的库，如OpenSSL, LibreSSL, BoringSSL。
2. 密钥管理是关键。私钥必须妥善保管，最好使用硬件安全模块(HSM)。公钥可以分发。
3. 使用现代填充方案。优先选择OAEP (Optimal Asymmetric Encryption Padding)而不是 PKCS#1 v1.5。在OpenSSL中，对应RSA_PKCS1_OAEP_PADDING。OAEP安全性更好。
4. RSA不直接用于加密长数据。RSA速度慢，通常用于加密一个随机的对称密钥（如AES密钥），然后用对称密钥加密实际数据。这种模式称为混合加密系统。
5. 密钥长度：1024位RSA已不再安全，至少使用2048位，对于长期安全考虑，建议使用3072或4096位。

走完这一趟从原理推导到手工实现，再到库函数调用的完整旅程，你应该不再觉得RSA是一个黑盒了。下次当你用ssh-keygen -t rsa生成密钥，或者配置一个使用RSA证书的Web服务器时，你脑海中对背后发生的这一切，会有一个清晰而坚实的图景。这就是动手实现一次的意义所在——不是要取代标准库，而是要理解它，从而能更自信、更正确地使用它。