用C语言手搓RSA加密算法：从数学原理到代码实现（附完整可运行源码）
·
用C语言手搓RSA加密算法：从数学原理到代码实现（附完整可运行源码）
RSA算法作为现代密码学的基石，其精妙之处在于将数论难题转化为实际可用的加密工具。本文将带您从欧几里得算法开始，逐步构建完整的RSA加密系统，最后呈现可直接编译运行的C语言实现。不同于简单的API调用，我们会深入每个数学运算的底层实现，特别关注大数处理等工程难题。
1. RSA的数学心脏：三个关键定理
1.1 欧拉定理的实战意义
欧拉函数φ(n)计算小于n且与n互质的正整数个数。当n为两质数p、q的乘积时，φ(n)=(p-1)(q-1)。这个看似简单的函数却是RSA安全性的核心保障：
// 计算欧拉函数示例
int euler_phi(int p, int q) {
return (p-1)*(q-1); // 当p,q均为质数时成立
}
欧拉定理指出，若a与n互质，则a^φ(n) ≡1 mod n。这个结论直接导致了模反元素的存在性证明。
1.2 模反元素的求解艺术
模反元素d满足 e·d ≡1 mod φ(n)，扩展欧几里得算法是求解的金钥匙：
int extended_gcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int gcd = extended_gcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return gcd;
}
实际工程中常使用二进制扩展欧几里得算法来提升大数运算效率
1.3 费马小定理的特殊价值
当n为质数时，φ(n)=n-1，此时欧拉定理退化为a^(n-1)≡1 mod n。这个特例被广泛应用于素性检测：
int is_prime(int n, int k) {
if (n <= 1) return 0;
for (int i = 0; i < k; i++) {
int a = 2 + rand() % (n - 2);
if (mod_pow(a, n-1, n) != 1)
return 0;
}
return 1;
}
2. 工程实现中的四大挑战
2.1 大数运算的溢出处理
32位系统下int类型最大值仅2147483647，而RSA需要处理远大于此的数值。我们采用分治策略：
long long mod_mul(long long a, long long b, long long mod) {
long long res = 0;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (a << 1) % mod;
b >>= 1;
}
return res;
}
2.2 快速幂模运算优化
常规幂运算复杂度O(n)，通过蒙哥马利约减可优化至O(log n)：
long long mod_pow(long long base, long long exp, long long mod) {
long long res = 1;
while (exp > 0) {
if (exp % 2 == 1)
res = mod_mul(res, base, mod);
base = mod_mul(base, base, mod);
exp = exp >> 1;
}
return res;
}
2.3 素性检测的可靠性
Miller-Rabin测试比简单费马测试更可靠，能有效避免卡迈克尔数的误判：
int miller_rabin(int n, int k) {
if (n <= 3) return n >= 2;
int d = n - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
for (int i = 0; i < k; i++) {
int a = 2 + rand() % (n - 3);
int x = mod_pow(a, d, n);
if (x == 1 || x == n-1) continue;
for (int j = 0; j < s - 1; j++) {
x = mod_pow(x, 2, n);
if (x == n-1) break;
}
if (x != n-1) return 0;
}
return 1;
}
2.4 数据分块与填充方案
RSA加密需要将数据分块处理，PKCS#1 v1.5填充是最常用方案：
| 块类型 | 格式示例 |
|---|---|
| 加密块 | 0x00 0x02 [随机非零字节] 0x00 [数据] |
| 签名块 | 0x00 0x01 [0xFF填充] 0x00 [哈希值] |
3. 完整RSA实现的关键组件
3.1 密钥生成流程
- 选择两个大质数p和q（通常512位以上）
- 计算n = p * q
- 计算φ(n) = (p-1)*(q-1)
- 选择e满足1 < e < φ(n)且gcd(e,φ(n))=1
- 计算d ≡ e⁻¹ mod φ(n)
typedef struct {
long long modulus; // n
long long exponent; // e或d
} RSA_KEY;
void generate_keys(RSA_KEY *pub, RSA_KEY *priv) {
long long p = generate_large_prime();
long long q = generate_large_prime();
long long n = p * q;
long long phi = (p-1)*(q-1);
long long e = choose_exponent(phi);
long long d = modular_inverse(e, phi);
pub->modulus = n;
pub->exponent = e;
priv->modulus = n;
priv->exponent = d;
}
3.2 加密解密核心函数
实现PKCS#1 v1.5标准的加解密：
int rsa_encrypt(const unsigned char *plain, int len,
unsigned char *cipher, RSA_KEY *pub) {
// 实现PKCS#1 v1.5填充
// 返回加密后的数据长度
}
int rsa_decrypt(const unsigned char *cipher, int len,
unsigned char *plain, RSA_KEY *priv) {
// 实现PKCS#1 v1.5解析
// 返回解密后的数据长度
}
3.3 文件加密的流处理
大文件需要分块加密并处理边界条件：
void rsa_encrypt_file(FILE *in, FILE *out, RSA_KEY *pub) {
unsigned char block[BLOCK_SIZE];
unsigned char encrypted[ENC_BLOCK_SIZE];
size_t bytes_read;
while ((bytes_read = fread(block, 1, BLOCK_SIZE, in)) > 0) {
int enc_len = rsa_encrypt(block, bytes_read, encrypted, pub);
fwrite(encrypted, 1, enc_len, out);
}
}
4. 性能优化与安全实践
4.1 预计算加速技术
使用中国剩余定理(CRT)可将解密速度提升4倍：
long long decrypt_with_crt(long long c, long long d,
long long p, long long q) {
long long dp = d % (p-1);
long long dq = d % (q-1);
long long qinv = modular_inverse(q, p);
long long m1 = mod_pow(c, dp, p);
long long m2 = mod_pow(c, dq, q);
long long h = (qinv * (m1 - m2)) % p;
if (h < 0) h += p;
return m2 + h * q;
}
4.2 侧信道攻击防护
时序攻击防护示例：
long long constant_time_pow(long long base, long long exp, long long mod) {
long long result = 1;
base = base % mod;
for (int i = 0; i < sizeof(long long)*8; i++) {
if ((exp >> i) & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
}
return result;
}
4.3 密钥存储最佳实践
建议的密钥存储格式：
| 字段 | 长度 | 说明 |
|---|---|---|
| 密钥类型 | 1字节 | 0x01=私钥 0x02=公钥 |
| 模数长度 | 4字节 | n的字节长度 |
| 指数长度 | 4字节 | e/d的字节长度 |
| 模数 | 变长 | 大端存储的n值 |
| 指数 | 变长 | 大端存储的e/d值 |
5. 完整可运行代码实现
以下为整合所有组件的完整实现（保存为rsa_complete.c）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>
#define DEFAULT_KEY_SIZE 2048
#define MILLER_RABIN_ROUNDS 40
typedef struct {
long long modulus;
long long exponent;
} RSA_KEY;
// 大数运算函数群
long long mod_mul(long long a, long long b, long long mod);
long long mod_pow(long long base, long long exp, long long mod);
int miller_rabin(long long n, int k);
long long generate_large_prime();
long long modular_inverse(long long a, long long m);
void generate_keys(RSA_KEY *pub, RSA_KEY *priv);
// 加密解密核心
int rsa_encrypt(const unsigned char *plain, int len,
unsigned char *cipher, RSA_KEY *pub);
int rsa_decrypt(const unsigned char *cipher, int len,
unsigned char *plain, RSA_KEY *priv);
// 文件操作接口
void rsa_encrypt_file(FILE *in, FILE *out, RSA_KEY *pub);
void rsa_decrypt_file(FILE *in, FILE *out, RSA_KEY *priv);
int main() {
RSA_KEY pub, priv;
printf("Generating RSA keys...\n");
generate_keys(&pub, &priv);
printf("Public Key (n,e): %lld, %lld\n", pub.modulus, pub.exponent);
printf("Private Key (n,d): %lld, %lld\n", priv.modulus, priv.exponent);
// 示例加密字符串
const char *test_str = "Hello RSA!";
unsigned char encrypted[256] = {0};
unsigned char decrypted[256] = {0};
int enc_len = rsa_encrypt((unsigned char*)test_str,
strlen(test_str), encrypted, &pub);
printf("Encrypted length: %d\n", enc_len);
int dec_len = rsa_decrypt(encrypted, enc_len, decrypted, &priv);
printf("Decrypted: %s\n", decrypted);
return 0;
}
// [完整函数实现...]
编译与测试方法：
gcc rsa_complete.c -o rsa_demo -O3
./rsa_demo
实际项目中建议将密钥长度提升至2048位以上，并使用专业的加密库如OpenSSL进行生产环境部署。本实现主要用于教学目的，展示了RSA算法的核心原理和实现细节。
更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)