当前位置：首页 > news >正文

别再死记硬背了！用C语言手撸RSA算法，彻底搞懂公钥私钥那点事

news 2026/6/11 9:24:12

从零实现RSA算法：用C语言拆解公钥加密的核心数学原理

当你在浏览器地址栏看到那个绿色小锁图标时，背后正是RSA算法在守护数据传输的安全。作为首个实用公钥加密系统，RSA的精妙之处在于它用简单的数论知识构建了牢不可破的加密体系。本文将带你用C语言实现一个简化版RSA，在编码过程中理解那些看似神秘的数学概念如何转化为可执行的逻辑。

1. RSA背后的数学工具箱

在开始写代码前，我们需要理解支撑RSA的三个关键数学概念：大素数选择、欧拉函数和模逆运算。这些抽象概念将在代码中具象化为函数和变量。

1.1 素数检测：加密系统的基石

RSA的安全性建立在"大整数分解是困难问题"这一假设上。我们首先实现一个素数检测函数：

int is_prime(int num) { if (num <= 1) return 0; if (num % 2 == 0 && num > 2) return 0; for(int i = 3; i <= sqrt(num); i += 2) { if (num % i == 0) return 0; } return 1; }

这个优化版的检测函数：

排除了小于2的数
单独处理偶数
只需检查到平方根为止
以步长2跳过偶数除数

1.2 欧拉函数：计算密钥空间

欧拉函数φ(n)表示小于n且与n互质的正整数个数。对于两个素数p和q，有：

int euler_phi(int p, int q) { return (p - 1) * (q - 1); }

这个简单公式正是RSA效率的关键——不需要遍历计算互质数的个数。

1.3 模逆运算：生成私钥的核心

私钥d是公钥e关于φ(n)的模逆元，满足：

e * d ≡ 1 mod φ(n)

我们可以用扩展欧几里得算法高效计算：

int mod_inverse(int e, int phi) { int x, y; int g = extended_gcd(e, phi, &x, &y); if (g != 1) return -1; // 无逆元 return (x % phi + phi) % phi; // 保证结果为正 }

2. 密钥生成：从数学到代码

有了这些数学工具，我们可以着手实现RSA的核心——密钥生成。

2.1 密钥生成步骤

选择两个大素数p和q
计算n = p * q
计算φ(n) = (p-1)*(q-1)
选择e使得1 < e < φ(n)且gcd(e, φ(n)) = 1
计算d ≡ e⁻¹ mod φ(n)

对应的C语言实现：

void generate_keys(int p, int q, int *e, int *d, int *n) { *n = p * q; int phi = euler_phi(p, q); // 选择适当的e *e = choose_co_prime(phi); // 计算模逆元d *d = mod_inverse(*e, phi); }

2.2 选择合数e的实用技巧

实际应用中，e常取65537，因为：

它是素数
二进制表示只有两个1，便于快速幂运算
足够大以保证安全性

但在我们的教学实现中，可以随机选择：

int choose_co_prime(int phi) { int e; do { e = rand() % (phi - 2) + 2; // 2 <= e < phi } while(gcd(e, phi) != 1); return e; }

3. 加密与解密实现

RSA的加密解密都是模幂运算，只是使用的密钥不同。

3.1 模幂运算优化

直接计算大数的幂再取模效率极低。我们使用快速幂算法：

int mod_pow(int base, int exp, int mod) { int 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; }

这个算法的时间复杂度从O(n)降到了O(log n)。

3.2 加密过程

加密时，对每个明文字符m计算：

c ≡ m^e mod n

C语言实现：

void encrypt(const char *plaintext, int *ciphertext, int e, int n) { for(int i = 0; plaintext[i] != '\0'; i++) { ciphertext[i] = mod_pow(plaintext[i], e, n); } }

3.3 解密过程

解密时，对每个密文字符c计算：

m ≡ c^d mod n

对应的解密函数：

void decrypt(const int *ciphertext, char *plaintext, int len, int d, int n) { for(int i = 0; i < len; i++) { plaintext[i] = mod_pow(ciphertext[i], d, n); } plaintext[len] = '\0'; }

4. 完整示例与常见陷阱

让我们把这些片段组合成一个完整的示例程序，并讨论几个关键注意事项。

4.1 完整示例代码

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> // 前面定义的所有函数... int main() { int p, q, n, phi, e, d; char plaintext[256]; int ciphertext[256]; char decrypted[256]; srand(time(0)); printf("输入两个素数p和q: "); scanf("%d %d", &p, &q); if(!is_prime(p) || !is_prime(q)) { printf("输入必须是素数!\n"); return 1; } generate_keys(p, q, &e, &d, &n); printf("公钥 (e=%d, n=%d)\n", e, n); printf("私钥 d=%d\n", d); printf("输入要加密的文本: "); scanf("%s", plaintext); encrypt(plaintext, ciphertext, e, n); printf("加密结果: "); for(int i = 0; plaintext[i] != '\0'; i++) { printf("%d ", ciphertext[i]); } printf("\n"); decrypt(ciphertext, decrypted, strlen(plaintext), d, n); printf("解密结果: %s\n", decrypted); return 0; }

4.2 实际应用中的注意事项

密钥长度：教学示例使用小整数，实际应用需要2048位以上的大整数
填充方案：直接加密小数值不安全，需要使用OAEP等填充方案
性能优化：
- 使用蒙哥马利模乘
- 中国剩余定理加速解密
侧信道攻击防护：
- 防止时序攻击
- 防止功耗分析

提示：这个简化实现仅用于教学目的，实际应用请使用成熟的加密库如OpenSSL。

5. 深入理解RSA的安全性

为什么RSA被认为是安全的？让我们从代码实现的角度分析其安全基础。

5.1 大整数分解难题

破解RSA等价于从n反推p和q。对于下面这段密钥生成代码：

*n = p * q;

看似简单的乘法，反过来却是极其困难的问题。当n是1024位以上的大数时，即使使用超级计算机也需要数年时间分解。

5.2 密钥空间与暴力破解

即使攻击者知道e和n，要找到d需要：

分解n得到p和q
计算φ(n) = (p-1)(q-1)
找到e关于φ(n)的模逆元d

第二步和第三步在知道p和q的情况下很容易，但第一步的难度保证了安全性。

5.3 选择合适参数的重要性

不恰当的参数选择会削弱RSA的安全性：

不良实践	潜在风险	改进方案
使用小素数	容易被暴力分解	使用1024位以上大素数
e取值过小	容易受到低指数攻击	使用65537
p和q接近	容易被费马分解	确保