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

1. 项目概述为什么选择C语言实现RSA在信息安全领域RSA算法是一个绕不开的里程碑。它不仅是第一个既能用于数据加密也能用于数字签名的非对称算法更是现代互联网安全如HTTPS、SSH、PGP的基石之一。你可能每天都在用它只是感觉不到。网上关于RSA原理的文章很多但大多停留在数学公式层面或者直接调用OpenSSL等成熟库。对于一个想真正理解其内部运作机制甚至想自己动手“造轮子”的开发者来说这远远不够。这就是我动手写这个C语言RSA加密库的初衷。为什么是C语言首先C语言足够“底层”能让你清晰地看到大数运算、模幂计算这些核心操作是如何一步步实现的没有高级语言那些封装好的“黑箱”。其次性能和控制力。在嵌入式系统、对性能有极致要求的场景或者某些无法引入庞大第三方库的环境中一个精简、可控的C语言实现具有不可替代的价值。最后它是一次绝佳的修炼。通过实现RSA你会被迫深入理解数论如欧拉函数、模逆元亲手处理大整数运算的溢出问题这些经验对任何方向的程序员都是宝贵的财富。这个项目不是一个玩具。它实现了RSA的核心流程密钥生成包括寻找大素数、计算模数、公钥指数e和私钥指数d、数据加密和解密。我会带你从最底层的数学原理开始一步步用C语言将其构建出来并分享我在实现过程中踩过的所有坑和总结的优化技巧。无论你是想巩固密码学基础的学生还是需要在资源受限环境中集成加密功能的工程师这篇指南都能提供直接的参考。2. 核心原理与数学基础拆解在动手写代码之前我们必须吃透RSA背后的数学原理。很多人觉得密码学数学很难其实RSA的核心只围绕几个数论概念我们把它掰开揉碎了讲。2.1 RSA算法的三大支柱RSA的安全性建立在“大数分解难题”之上。简单说给你两个很大的质数p和q把它们相乘得到N很容易但反过来给你一个很大的N让你找出它是由哪两个质数p和q相乘得到的在现有计算能力下极其困难。整个算法就围绕这个难题展开。第一步密钥生成选择两个大质数随机选择两个足够大的、不同的质数p和q。这里“足够大”是关键通常需要1024位约308位十进制数或更长才能保证安全。我们稍后会讨论如何在C语言中“找”到这些大质数。计算模数NN p * q。这个N就是公钥和私钥共用的模数长度比特数决定了密钥强度。计算欧拉函数φ(N)φ(N) (p-1) * (q-1)。欧拉函数φ(n)表示小于n的正整数中与n互质的数的个数。对于两个质数相乘的情况计算非常简单。选择公钥指数e选择一个整数e满足1 e φ(N)且e与φ(N)互质即最大公约数gcd(e, φ(N)) 1。通常选择65537 (0x10001)因为它二进制表示中1很少能加速加密运算且是质数很大概率与φ(N)互质。计算私钥指数d计算e对于φ(N)的模逆元d。即满足(d * e) % φ(N) 1的d。这个d就是私钥的核心部分。计算d需要用到扩展欧几里得算法。公钥就是(e, N)可以公开。私钥就是(d, N)必须严格保密。p, q, φ(N)在生成密钥后应立即从内存中安全擦除。第二步加密与解密加密对于明文消息M需要先转换为一个小于N的整数计算密文C M^e mod N。解密对于密文C计算明文M C^d mod N。注意这里的M^e和C^d都是天文数字直接计算是不可能的。必须依赖快速模幂算法这也是实现中的性能关键点。2.2 必须掌握的数学工具要实现上述流程我们需要在C语言中实现三个核心数学工具大整数表示与运算C语言的基本数据类型如long long远远不足以表示安全所需的大整数几百位。我们必须自己定义数据结构比如用数组表示每一位并实现加法、减法、乘法、除法、取模等运算。扩展欧几里得算法用于求解e * d φ(N) * k 1这个方程从而得到私钥指数d。这个算法还能同时求出最大公约数用于判断e和φ(N)是否互质。快速模幂算法核心中的核心。直接计算M^e mod N会溢出且极慢。快速模幂算法如平方-乘算法能将计算复杂度从O(e)降低到O(log e)使得加密解密变得可行。理解了这些我们就有了清晰的施工蓝图。接下来我们进入具体的C语言实现环节。3. C语言实现数据结构与基础工具函数我们不能直接用int或long long需要自己造一个“大整数”轮子。这里我选择了一种简单直观的表示方法用动态数组存储十进制数的每一位当然实际为了效率可能会用uint32_t数组以2^32为基进行存储但为清晰起见我们先从十进制讲起。3.1 定义大整数结构体// big_int.h #ifndef BIG_INT_H #define BIG_INT_H #include stdint.h #include stdbool.h // 定义大整数结构体 typedef struct { uint32_t *digits; // 动态数组每个元素存储一个“位”例如以10为基或更高效的以2^32为基 int length; // 当前使用的位数 int capacity; // 数组分配的总容量 bool sign; // 符号位true表示负数RSA中通常只处理正数但为完整性保留 } BigInt; // 函数声明 BigInt* big_int_create(const char *str); void big_int_destroy(BigInt *num); void big_int_print(const BigInt *num); int big_int_compare(const BigInt *a, const BigInt *b); // 比较大小 BigInt* big_int_add(const BigInt *a, const BigInt *b); BigInt* big_int_sub(const BigInt *a, const BigInt *b); BigInt* big_int_mul(const BigInt *a, const BigInt *b); BigInt* big_int_div_mod(const BigInt *a, const BigInt *b, BigInt **remainder); // 除法同时返回余数 BigInt* big_int_mod(const BigInt *a, const BigInt *b); // 取模运算 BigInt* big_int_mod_exp(const BigInt *base, const BigInt *exp, const BigInt *mod); // 快速模幂 base^exp mod mod #endif // BIG_INT_H这个BigInt结构体是我们的基石。digits数组存储数字length是有效长度。实现这些基础运算加、减、乘、除、取模需要仔细处理进位、借位和数组扩容这是第一个挑战也是调试最耗时的部分。实操心得在实现大数乘法时我最初使用了最朴素的O(n²)算法模拟竖式计算对于1024位的数尚可接受。但当测试2048位时性能瓶颈立刻出现。后来我换成了Karatsuba算法它是一种分治算法能将乘法复杂度从O(n²)降到约O(n^1.585)性能提升显著。如果你的库对性能有要求强烈建议实现Karatsuba或更高级的Toom-Cook、FFT乘法。3.2 实现扩展欧几里得算法这个算法用于求模逆元是生成私钥d的关键。// rsa_math.c #include big_int.h // 扩展欧几里得算法计算 ax by gcd(a, b) // 返回gcd(a, b)并通过指针返回x, y BigInt* extended_gcd(const BigInt *a, const BigInt *b, BigInt **x, BigInt **y) { if (big_int_compare(b, ZERO) 0) { // ZERO是一个表示0的BigInt常量 *x big_int_create(1); *y big_int_create(0); return big_int_copy(a); // 返回a的副本作为gcd } BigInt *x1 NULL, *y1 NULL; BigInt *mod_result big_int_mod(a, b); // a % b BigInt *gcd extended_gcd(b, mod_result, x1, y1); // 递归调用 big_int_destroy(mod_result); // 更新 x y1, y x1 - (a/b) * y1 BigInt *quotient big_int_div(a, b); // 需要实现整数除法只返回商 BigInt *temp big_int_mul(quotient, y1); *x big_int_copy(y1); *y big_int_sub(x1, temp); big_int_destroy(quotient); big_int_destroy(temp); big_int_destroy(x1); big_int_destroy(y1); return gcd; } // 计算a在模m下的模逆元即找到 x 使得 (a * x) % m 1 // 如果逆元不存在a和m不互质返回NULL BigInt* mod_inverse(const BigInt *a, const BigInt *m) { BigInt *x NULL, *y NULL; BigInt *gcd extended_gcd(a, m, x, y); // 检查gcd是否为1 BigInt *one big_int_create(1); int cmp big_int_compare(gcd, one); big_int_destroy(one); big_int_destroy(gcd); if (cmp ! 0) { // 不互质逆元不存在 if (x) big_int_destroy(x); if (y) big_int_destroy(y); return NULL; } // 确保x是正数 BigInt *result big_int_mod(x, m); if (result-sign) { // 如果结果是负数加上m使其为正 BigInt *temp big_int_add(result, m); big_int_destroy(result); result temp; } big_int_destroy(x); big_int_destroy(y); return result; // 这个result就是私钥指数d的候选值 }这段代码是密钥生成的核心。递归逻辑需要仔细跟踪确保内存管理正确避免泄漏。3.3 实现快速模幂算法这是加密解密运算的引擎必须高效。// big_int.c 的一部分 BigInt* big_int_mod_exp(const BigInt *base, const BigInt *exp, const BigInt *mod) { if (big_int_compare(mod, ONE) 0) { // 如果模数为1结果恒为0 return big_int_create(0); } BigInt *result big_int_create(1); // 初始化结果为1 BigInt *b big_int_copy(base); BigInt *e big_int_copy(exp); // 将底数对模数取模减少后续计算量 BigInt *b_mod big_int_mod(b, mod); big_int_destroy(b); b b_mod; // 平方-乘算法 while (big_int_compare(e, ZERO) 0) { // 当指数大于0时循环 // 如果当前指数是奇数 result (result * b) % mod if (big_int_is_odd(e)) { // 需要实现判断奇偶的函数 BigInt *temp big_int_mul(result, b); BigInt *temp2 big_int_mod(temp, mod); big_int_destroy(temp); big_int_destroy(result); result temp2; } // 指数右移一位除以2 BigInt *e_div_2 big_int_shift_right(e, 1); // 需要实现右移函数比除法快 big_int_destroy(e); e e_div_2; // 底数平方并取模 b (b * b) % mod if (big_int_compare(e, ZERO) 0) { // 如果指数还没完才需要更新底数 BigInt *temp big_int_mul(b, b); BigInt *temp2 big_int_mod(temp, mod); big_int_destroy(temp); big_int_destroy(b); b temp2; } } big_int_destroy(b); big_int_destroy(e); return result; }这个算法是RSA性能的关键。它通过将指数e或d用二进制表示然后根据每一位是0还是1来决定是“平方”还是“平方后乘”将计算量从线性级降到对数级。4. RSA密钥生成从寻找素数到组装密钥有了强大的数学工具我们就可以着手实现RSA最关键的步骤——密钥生成。这个过程充满了随机性和技巧。4.1 生成大素数Miller-Rabin素性测试在C语言中生成一个几百位的大素数不能靠枚举。我们使用概率性测试最经典的就是Miller-Rabin素性测试。它速度很快并且可以将错误概率即把一个合数误判为质数降到极低例如测试k次后错误概率小于4^{-k}。// prime.c #include big_int.h #include stdlib.h #include time.h // 随机生成一个指定位数的奇数大整数 BigInt* generate_random_odd(int num_bits) { // 实现细节分配一个足够大的BigInt确保最高位和最低位都是1以保证是奇数且达到指定位数 // 这里省略具体的位操作代码核心是使用随机数生成器填充digits数组 // ... } // Miller-Rabin素性测试 bool is_probable_prime(const BigInt *n, int iterations) { if (big_int_compare(n, TWO) 0) return false; if (big_int_compare(n, TWO) 0 || big_int_compare(n, THREE) 0) return true; // 检查小偶数 if (big_int_is_even(n)) return false; // 将 n-1 写成 d * 2^s 的形式其中 d 是奇数 BigInt *d big_int_sub(n, ONE); int s 0; while (big_int_is_even(d)) { big_int_shift_right_inplace(d, 1); // d / 2 s; } // 进行k次测试 for (int i 0; i iterations; i) { // 随机选择一个底数 a, 2 a n-2 BigInt *a generate_random_big_int_range(TWO, big_int_sub(n, TWO)); // 计算 x a^d mod n BigInt *x big_int_mod_exp(a, d, n); bool composite true; if (big_int_compare(x, ONE) 0 || big_int_compare(x, big_int_sub(n, ONE)) 0) { composite false; } else { for (int j 0; j s - 1; j) { // x x^2 mod n BigInt *temp big_int_mul(x, x); BigInt *new_x big_int_mod(temp, n); big_int_destroy(temp); big_int_destroy(x); x new_x; if (big_int_compare(x, ONE) 0) { // 发现非平凡平方根n一定是合数 composite true; break; } if (big_int_compare(x, big_int_sub(n, ONE)) 0) { composite false; break; } } } big_int_destroy(a); big_int_destroy(x); if (composite) { big_int_destroy(d); return false; // n是合数 } } big_int_destroy(d); return true; // n很可能是质数 } // 生成一个指定位数的素数 BigInt* generate_large_prime(int num_bits) { BigInt *candidate NULL; srand((unsigned int)time(NULL)); // 初始化随机种子生产环境应用更安全的随机源 do { if (candidate) big_int_destroy(candidate); candidate generate_random_odd(num_bits); } while (!is_probable_prime(candidate, 50)); // 测试50次错误概率极低 return candidate; }注意事项srand(time(NULL))在学习和测试中可以用但在真正的安全应用中随机数生成是生命线。必须使用密码学安全的随机数生成器CSPRNG如/dev/urandomLinux或CryptGenRandomWindows。劣质的随机数会导致生成的素数可预测从而使整个RSA密钥被轻易破解。4.2 完整的密钥生成流程现在我们可以把所有的零件组装起来。// rsa_keygen.c #include big_int.h #include prime.h typedef struct { BigInt *n; // 模数 BigInt *e; // 公钥指数 BigInt *d; // 私钥指数 } RSAKeyPair; RSAKeyPair* rsa_generate_keys(int key_size_bits) { RSAKeyPair *keys (RSAKeyPair*)malloc(sizeof(RSAKeyPair)); // 1. 生成两个大素数p和q各约为key_size_bits/2位 printf(正在生成素数p...\n); BigInt *p generate_large_prime(key_size_bits / 2); printf(正在生成素数q...\n); BigInt *q generate_large_prime(key_size_bits / 2); // 确保p和q不相等极小概率事件但需检查 while (big_int_compare(p, q) 0) { big_int_destroy(q); q generate_large_prime(key_size_bits / 2); } // 2. 计算 n p * q keys-n big_int_mul(p, q); // 3. 计算 φ(n) (p-1) * (q-1) BigInt *p_minus_1 big_int_sub(p, ONE); BigInt *q_minus_1 big_int_sub(q, ONE); BigInt *phi_n big_int_mul(p_minus_1, q_minus_1); // 4. 选择公钥指数e通常为65537 keys-e big_int_create(65537); // 检查e是否与φ(n)互质如果不互质需要重新选择e65537不互质的概率极低 BigInt *gcd big_int_gcd(keys-e, phi_n); if (big_int_compare(gcd, ONE) ! 0) { // 处理不互质的情况可以尝试另一个常见的质数如17 big_int_destroy(keys-e); keys-e big_int_create(17); big_int_destroy(gcd); gcd big_int_gcd(keys-e, phi_n); // 理论上应循环直到找到互质的e但65537和17几乎总能工作 } big_int_destroy(gcd); // 5. 计算私钥指数d即e模φ(n)的逆元 keys-d mod_inverse(keys-e, phi_n); if (keys-d NULL) { // 理论上不应该发生因为我们已经检查了gcd(e, φ(n)) 1 fprintf(stderr, 错误无法计算模逆元。密钥生成失败。\n); // 清理内存并退出或重试 } // 6. 清理中间变量安全擦除敏感数据 // 注意在实际安全应用中应从内存中彻底清除p, q, phi_n等 big_int_destroy(p); big_int_destroy(q); big_int_destroy(p_minus_1); big_int_destroy(q_minus_1); big_int_destroy(phi_n); // 简单的方法用随机数据覆盖内存此处为示意需要操作digits数组 // memset(p-digits, 0, p-capacity * sizeof(uint32_t)); // ... return keys; }至此我们成功生成了RSA密钥对(e, n)和(d, n)。接下来就是使用它们进行加密和解密。5. 数据加密与解密实现RSA算法本身是定义在整数上的。要加密文本、文件等任意数据我们需要一套“填充方案”将数据转换为整数并且要处理数据可能比模数N大的情况需要分块。5.1 数据编码与分块一个简单的方案仅用于演示生产环境应用PKCS#1等标准填充如下字符串/数据转整数可以将数据视为一个大字节数组然后将其解释为一个大的整数。例如将字符串Hello的每个ASCII码拼接起来。分块如果数据转换后的整数大于模数N就必须分块加密。每块的大小字节数必须小于floor(log_{256} N)以确保转换后的整数小于N。// rsa_io.c #include big_int.h #include string.h // 将字节数组转换为BigInt大端序 BigInt* bytes_to_big_int(const unsigned char *bytes, size_t len) { // 实现将字节数组视为一个以256为基的大整数 // 从最后一个字节开始逐字节累加 BigInt *result big_int_create(0); BigInt *base big_int_create(256); BigInt *temp NULL; for (size_t i 0; i len; i) { // result result * 256 bytes[i] temp big_int_mul(result, base); big_int_destroy(result); result temp; char byte_str[4]; sprintf(byte_str, %d, bytes[i]); BigInt *byte_val big_int_create(byte_str); temp big_int_add(result, byte_val); big_int_destroy(result); result temp; big_int_destroy(byte_val); } big_int_destroy(base); return result; } // 将BigInt转换回字节数组大端序 unsigned char* big_int_to_bytes(const BigInt *num, size_t *out_len) { // 实现反复对256取模得到各个字节 // 需要计算大致长度并分配数组 // ... } // RSA加密一个数据块BigInt表示 BigInt* rsa_encrypt_block(const BigInt *plaintext_block, const BigInt *e, const BigInt *n) { // 确保明文块小于n if (big_int_compare(plaintext_block, n) 0) { fprintf(stderr, 错误明文块必须小于模数n。\n); return NULL; } // C M^e mod n return big_int_mod_exp(plaintext_block, e, n); } // RSA解密一个数据块 BigInt* rsa_decrypt_block(const BigInt *ciphertext_block, const BigInt *d, const BigInt *n) { // M C^d mod n return big_int_mod_exp(ciphertext_block, d, n); }5.2 完整的加密解密流程示例假设我们有一个短字符串需要加密。// example.c #include rsa_keygen.h #include rsa_io.h void example_encrypt_decrypt_string() { // 1. 生成密钥例如1024位 printf(生成1024位RSA密钥对...\n); RSAKeyPair *keys rsa_generate_keys(1024); // 2. 待加密的明文 const char *plaintext Secret Message!; size_t plaintext_len strlen(plaintext); // 3. 计算每块的最大字节数 (确保整数表示 n) // 简单估算n的最大值约为2^key_size。块大小 floor(log_{256} n) ≈ key_size_bits / 8 int block_size_bytes 1024 / 8 - 11; // 减11是为可能的填充预留空间如果使用PKCS#1 v1.5填充 // 为简单演示我们假设明文很短不超过块大小 if (plaintext_len block_size_bytes) { fprintf(stderr, 明文过长需要实现分块加密。\n); return; } // 4. 将明文转换为BigInt BigInt *plaintext_int bytes_to_big_int((const unsigned char*)plaintext, plaintext_len); // 5. 加密 printf(正在加密...\n); BigInt *ciphertext_int rsa_encrypt_block(plaintext_int, keys-e, keys-n); // 6. 解密 printf(正在解密...\n); BigInt *decrypted_int rsa_decrypt_block(ciphertext_int, keys-d, keys-n); // 7. 将解密后的BigInt转换回字节 size_t decrypted_len; unsigned char *decrypted_bytes big_int_to_bytes(decrypted_int, decrypted_len); // 8. 输出结果 printf(原始明文: %s\n, plaintext); printf(解密结果: %.*s\n, (int)decrypted_len, decrypted_bytes); // 9. 验证 if (decrypted_len plaintext_len memcmp(plaintext, decrypted_bytes, plaintext_len) 0) { printf(加解密成功\n); } else { printf(加解密失败\n); } // 10. 清理内存 free(decrypted_bytes); big_int_destroy(plaintext_int); big_int_destroy(ciphertext_int); big_int_destroy(decrypted_int); rsa_keypair_destroy(keys); // 需要实现清理函数 }这个例子演示了核心流程。对于长数据你需要循环处理每个数据块。6. 性能优化与安全加固实战一个能用的RSA库和一个好用的、安全的RSA库之间隔着巨大的鸿沟。以下是几个关键的优化和安全考量点。6.1 性能优化技巧大数运算算法升级乘法如前所述用Karatsuba算法替换朴素乘法。模运算实现Barrett约减或Montgomery乘法能极大加速模幂运算中的取模操作。Montgomery乘法是工业级实现如OpenSSL的标准选择它通过将数字转换到一种特殊的表示形式使得模乘运算不需要昂贵的除法。模幂除了平方-乘可以研究滑动窗口法等更高效的指数运算方法。内存与计算复用在频繁调用的函数如big_int_mod_exp内部避免反复创建和销毁临时大整数对象。可以预先分配一个“工作区”池重复使用。对于固定的模数N在RSA中很常见可以预先计算一些用于加速模运算的参数如Montgomery变换中的R和N。密钥生成优化寻找素数时可以先用小素数表进行试除快速过滤掉大部分合数再进行耗时的Miller-Rabin测试。确保p和q的差值足够大并且(p-1)和(q-1)都有大质因子以抵抗某些特殊的因子分解攻击。6.2 安全注意事项与“坑”随机数生成再强调一遍这是最大的坑。绝对不要用rand()。在Linux/macOS上使用/dev/urandom在Windows上使用BCryptGenRandom或CryptGenRandom。一个脆弱的随机源会直接导致密钥被预测。侧信道攻击防护时间攻击如果根据私钥位是0还是1代码执行路径或时间有差异攻击者通过测量解密时间就可能推测出私钥。实现快速模幂时必须采用常数时间的实现即无论指数位是0还是1执行的操作序列和耗时都应相同。缓存攻击确保敏感数据如p, q, d, φ(n)在使用后立即从内存中安全擦除用0或随机数覆盖而不仅仅是释放指针。填充方案永远不要使用“教科书式RSA”即直接加密整数而不填充。这不仅是非标准的而且极其不安全容易受到多种攻击如共模攻击、低指数攻击。必须使用标准的填充方案如PKCS#1 v1.5 Padding曾经最常用但现在已知在某些情况下可能受到自适应选择密文攻击如Bleichenbacher攻击。OAEP (Optimal Asymmetric Encryption Padding)目前推荐的非对称加密填充方案安全性可证明。实现OAEP需要哈希函数和掩码生成函数MGF比PKCS#1 v1.5复杂但安全得多。密钥长度1024位RSA目前已不被认为对长期安全足够。对于新项目至少应使用2048位。3072位或4096位则用于更高安全需求。错误处理加密解密失败时不要返回详细的错误信息如“解密失败因为填充不正确”这会给攻击者提供侧信道信息。应统一返回一个泛化的错误。7. 常见问题与调试实录在开发这个库的过程中我遇到了无数个编译错误、运行时崩溃和逻辑错误。这里记录几个最具代表性的。7.1 内存管理噩梦C语言没有垃圾回收所有BigInt对象都需要手动create和destroy。内存泄漏和野指针是最常见的问题。问题程序运行一段时间后内存占用暴涨最终崩溃。排查使用Valgrind (valgrind --leak-checkfull ./your_program) 工具检查。发现是在快速模幂循环中某些分支路径下临时变量没有正确释放。解决为每个BigInt*的创建和销毁绘制清晰的流程图。对于复杂函数在开头就规划好所有可能的退出路径并在每个路径上确保释放所有已分配的资源。也可以考虑实现一个简单的引用计数或内存池但这会引入复杂度。7.2 大数运算结果错误问题加密后再解密得到的明文和原始明文对不上。排查单元测试首先隔离测试每一个基础运算函数加、减、乘、除、取模。编写大量测试用例包括边界情况如0、1、非常大的数。打印调试在密钥生成过程中打印出p, q, n, e, d, φ(n)的值。用一个小型、已知的示例例如p61, q53, e17进行手工计算对比验证你的mod_inverse函数计算出的d是否正确。检查比较函数big_int_compare的实现是否正确符号处理对了吗这是很多其他函数的基础。检查模幂单独测试big_int_mod_exp用小的数字验证(a^b) % m的结果是否正确。7.3 性能瓶颈定位问题生成一个2048位的密钥需要几分钟太慢了。排查使用性能分析工具如gprof。发现90%的时间花在了大数除法big_int_div_mod上而除法在Miller-Rabin测试和模运算中被频繁调用。解决优化除法算法例如实现Knuth的“算法D”。更重要的是在Miller-Rabin测试中我们计算a^d mod n时指数d是一个很大的奇数n-1不断除以2得到。实际上我们可以先计算a mod n然后在循环平方时逐步取模避免中间结果变得巨大从而减少大数除法的次数和规模。这就是为什么在big_int_mod_exp函数中我们在循环开始前就先做了b b % mod。7.4 填充与数据编码问题问题实现了PKCS#1 v1.5填充后解密时偶尔会失败提示“填充错误”。排查检查编码和解码过程是否完全可逆。单独测试填充和去除填充的函数。确保在将填充后的字节串转换为BigInt时使用的是大端序最高有效字节在前并且转换后的整数严格小于模数N。检查分块逻辑。当明文长度恰好等于块大小时是否需要特殊处理填充会增加额外的字节所以加密前的数据块必须比模数对应的字节长度短。最后的小技巧在开发初期使用小密钥比如32位或64位进行测试。这样你可以轻松地打印出所有中间变量p, q, n, e, d并用计算器或Python脚本验证它们的正确性。等所有逻辑在“小模型”上跑通后再扩展到安全的大密钥位数。这能为你节省大量的调试时间。从头实现一个RSA库是一次深入密码学腹地的旅程。它强迫你理解每一个数学细节谨慎处理每一处内存分配并时刻绷紧安全这根弦。最终得到的不仅仅是一个可用的库更是对非对称加密深刻而直观的理解。当你再次使用openssl rsa命令时你会清楚地知道背后那波澜壮阔的数学和工程故事。希望这篇指南能成为你这段旅程的一张可靠地图。