C语言手把手实现RSA加密：从大数运算到模幂算法详解

1. 项目概述为什么要在C语言里啃RSA这块硬骨头最近在整理一些旧项目发现很多朋友对加密这块尤其是非对称加密总感觉隔着一层纱。网上教程要么是纯数学理论看得人头大要么直接甩给你一个OpenSSL的调用示例知其然不知其所以然。特别是用C语言来实现好像门槛特别高。今天我就想抛开那些庞大的库带着大家用最纯粹的C语言从零开始一步一步把RSA加密算法的核心给实现出来。这不仅仅是为了完成一个“加密解密”的功能更是为了彻底搞懂非对称加密到底是怎么一回事——公钥和私钥为何能成对出现大数运算是如何保障安全的为什么说“分解质因数”是RSA的命门如果你是一名C语言开发者或者是对密码学底层原理有浓厚兴趣的学习者那么这次手把手的实现过程会让你对“加密”这两个字有全新的认识。我们不止于调用API而是要深入到模幂运算、欧几里得算法、大素数生成这些核心环节。你会发现用C语言实现RSA是对你编程能力、数学思维和耐心的一次绝佳锻炼。整个过程就像在组装一台精密的机械钟表每一个齿轮算法步骤都必须严丝合缝。2. RSA算法核心原理拆解不只是两个质数相乘那么简单在动手写代码之前我们必须把RSA的数学骨架摸清楚。很多资料会告诉你选两个大质数p和q相乘得到n再算个欧拉函数φ(n)选个公钥指数e算出私钥指数d然后就完事了。但魔鬼藏在细节里每一步的选择都直接影响算法的安全性和正确性。2.1 密钥生成每一步的“为什么”比“怎么做”更重要RSA密钥的生成可以分解为五个关键步骤。我们不仅要会算更要明白为什么这么算。第一步选择两个不相等的大质数p和q这是所有安全的基础。n p * q会成为公钥的一部分也是模数。这里的“大”是相对的在教学中我们用几百以内的数便于验证但在实际应用中p和q通常是1024位约308位十进制数或2048位的随机大质数。选择它们必须满足真正随机不能是固定的或者有规律的数否则会被轻易猜测或通过预计算破解。强度足够p和q本身应该足够大并且差值不能太小否则n可能容易被通过费马分解法等特殊方法因式分解。高级强质数在某些高安全场景要求(p-1)和(q-1)都有大质因子以抵抗某些特定的密码分析攻击如Pollard‘s p-1算法。我们教学实现暂不涉及但需要知道这个概念。注意在我们的C语言实现中由于标准库没有大整数和质数生成函数我们会先实现基础的大数运算并用一个“伪随机”且足够大的质数来演示流程。真正的随机大质数生成是一个复杂的课题涉及米勒-拉宾素性测试等算法。第二步计算模数n和欧拉函数φ(n)n p * q。n的二进制长度就是RSA的密钥长度如2048位。n是公开的。φ(n) (p-1) * (q-1)。这是欧拉函数在n为两个质数乘积时的特例。φ(n)必须被严格保密因为它直接关系到私钥d的计算。一旦φ(n)泄露攻击者可以轻松算出d。第三步选择公钥指数ee是一个整数且必须满足两个条件1 e φ(n)e与φ(n)互质即最大公约数gcd(e, φ(n)) 1。e通常是固定的几个值如3,17,65537 (0x10001)。为什么65537是最常用的。它是一个费马数2^161其二进制表示只有两个110000000000000001这使得基于它的模幂运算加密操作可以通过快速算法高效完成。3和17计算更快但历史上曾有小指数攻击的风险现在已不推荐用于新系统。 在我们的实现中为了通用性我们会编写一个函数来寻找一个与φ(n)互质的e。第四步计算私钥指数dd是e关于模φ(n)的模逆元。即满足(d * e) % φ(n) 1。 换句话说d是方程d * e ≡ 1 (mod φ(n))的解。 计算d需要用到扩展欧几里得算法。这个算法不仅能求出e和φ(n)的最大公约数确保为1还能同时求出满足e*d φ(n)*k 1的系数d和k而我们需要的d正是这个d可能需要调整到正数范围。第五步得到密钥对公钥由(n, e)组成。可以公开发布。私钥由(n, d)组成。必须绝对保密。有时也会保存(p, q, d)以便使用中国剩余定理加速解密。2.2 加密与解密模幂运算的舞台原理非常简单但计算量巨大加密用公钥对于明文消息M需要转换为一个小于n的整数计算密文C M^e mod n。解密用私钥对于密文C计算明文M C^d mod n。这里的^表示幂运算mod是取模运算。核心难点在于当e、d、n都是几百位的大数时直接计算M^e会得到一个天文数字没有任何基本数据类型可以存储。因此我们必须实现高效的模幂运算算法典型的就是“快速幂取模”算法它通过对指数进行二进制分解将计算复杂度从O(e)降低到O(log e)。2.3 安全性基石大整数分解难题RSA的安全性完全依赖于“大整数分解难题”。即已知公钥(n, e)和密文C想求出明文M理论上需要先通过n求出d而求d需要φ(n)求φ(n)需要分解n得到p和q。 当n足够大时例如2048位即使在最强大的超级计算机上用已知最好的算法进行因式分解所需时间也远超宇宙年龄。这就是RSA安全的根本。因此密钥长度n的位数直接决定了安全等级。1024位RSA目前已不被认为绝对安全推荐使用2048位或更长。3. C语言实现前的核心准备打造我们自己的“大数”工具箱C语言的标准库并没有直接支持数百位整数运算的类型。int或long long在64位系统下也只能处理最多约20位的十进制数远远不够。因此我们的首要任务是建立一个简易的大数运算库。这里我们采用最直观的数组表示法。3.1 大数的表示与基础操作我们用一个字符数组或整型数组来表示大数每个元素存储数字的一位十进制或一个字节。为了简化我们先实现十进制表示便于调试。// 定义大数的最大位数例如对于1024位的n其十进制位数大约为 1024*log10(2) ≈ 309 #define MAX_DIGITS 500 typedef struct { char digits[MAX_DIGITS]; // 从低位到高位存储digits[0]是个位 int length; // 数字的实际长度 } BigInt; // 初始化函数 void initBigInt(BigInt *num) { memset(num-digits, 0, sizeof(num-digits)); num-length 1; // 初始化为0 }我们需要实现一系列基础函数void strToBigInt(const char* str, BigInt *num);// 从字符串初始化void printBigInt(const BigInt *num);// 打印大数int compareBigInt(const BigInt *a, const BigInt *b);// 比较大小void addBigInt(const BigInt *a, const BigInt *b, BigInt *result);// 加法void subBigInt(const BigInt *a, const BigInt *b, BigInt *result);// 减法假设abvoid multiplyBigInt(const BigInt *a, const BigInt *b, BigInt *result);// 乘法基础竖式乘法void divideBigInt(const BigInt *a, const BigInt *b, BigInt *quotient, BigInt *remainder);// 除法返回商和余数这是最复杂的部分实操心得大数除法的实现是第一个难点。可以参考“长除法”的笔算过程从被除数的高位开始逐位试商。调试时务必先用小数字如几十位验证所有基础运算的正确性再逐步增大。一个常见的坑是处理前导零和结果为0的情况。3.2 核心算法一扩展欧几里得算法求模逆元这是计算私钥d的关键。给定互质的两个数e和φ(n)求d使得e*d ≡ 1 (mod φ(n))。// 扩展欧几里得算法计算 ax by gcd(a, b) 的系数 x, y // 当 gcd(a, b) 1 时x 就是 a 关于模 b 的模逆元可能需要调整 void extendedEuclid(const BigInt *a, const BigInt *b, BigInt *x, BigInt *y, BigInt *gcd) { if (compareBigInt(b, ZERO) 0) { // ZERO是预先定义好的大数0 // gcd a, x 1, y 0 assignBigInt(gcd, a); assignBigInt(x, ONE); // ONE是预先定义好的大数1 assignBigInt(y, ZERO); return; } BigInt b_mod_a, quotient; initBigInt(b_mod_a); initBigInt(quotient); // 计算 quotient a / b, b_mod_a a % b divideBigInt(a, b, quotient, b_mod_a); BigInt x1, y1; initBigInt(x1); initBigInt(y1); // 递归调用 extendedEuclid(b, b_mod_a, x1, y1, gcd); // 回溯更新 x, y // x y1 assignBigInt(x, y1); // y x1 - (a / b) * y1 BigInt temp; initBigInt(temp); multiplyBigInt(quotient, y1, temp); subBigInt(x1, temp, y); }计算出x后如果x是负数需要加上模数b即φ(n)使其变为正数这个正数就是私钥d。3.3 核心算法二快速幂取模算法这是加密和解密运算的核心必须高效。直接计算M^e再取模不可行。快速幂取模算法的思想是(a * b) mod n [(a mod n) * (b mod n)] mod n我们可以将指数e用二进制表示例如e 13 (二进制1101)那么M^13 M^8 * M^4 * M^1。 我们从低位到高位遍历e的二进制位底数平方增长遇到二进制位为1时将当前的底数乘到结果上。// 快速幂取模计算 base^exp mod mod void modExp(const BigInt *base, const BigInt *exp, const BigInt *mod, BigInt *result) { BigInt b, e, m; assignBigInt(b, base); assignBigInt(e, exp); assignBigInt(m, mod); assignBigInt(result, ONE); // result 1 BigInt temp; initBigInt(temp); while (compareBigInt(e, ZERO) 0) { // while e 0 // 如果e是奇数 result (result * b) % mod if (isOdd(e)) { multiplyBigInt(result, b, temp); divideBigInt(temp, m, NULL, result); // result temp % m } // b (b * b) % mod multiplyBigInt(b, b, temp); divideBigInt(temp, m, NULL, b); // b temp % m // e e / 2 rightShift(e, 1); // 实现大数右移一位除以2 } }注意事项isOdd和rightShift需要我们自己实现为大数操作。rightShift除以2对于二进制存储的大数很简单但对于我们十进制存储的大数需要实现完整的除法除以2。在性能要求高的场景大数应采用二进制如以2^32为基存储运算效率会高得多。这里为清晰起见我们使用十进制。4. 从零开始C语言实现RSA的完整步骤有了上面的工具箱我们现在可以串联起整个RSA流程。为了演示我们选择两个较小的质数但流程与使用大质数完全一致。4.1 第一步密钥生成假设我们选择p 61,q 53实际应用绝不会这么小。计算n和φ(n):n p * q 61 * 53 3233φ(n) (p-1)*(q-1) 60 * 52 3120选择公钥指数e选择一个与3120互质的数比如e 17(因为gcd(17, 3120)1)。计算私钥指数d寻找d使得(d * 17) % 3120 1。 使用扩展欧几里得算法求解17*d 3120*k 1可以得到一组解d 2753, k -15。因为d为正所以我们取d 2753。 验证2753 * 17 46801, 46801 % 3120 1至此我们得到公钥: (n3233, e17)私钥: (n3233, d2753)在C代码中我们需要将上述计算过程用我们实现的大数运算函数重写。p,q,e的选择可以写死也可以设计成输入。4.2 第二步数据分组与填充RSA算法本身是用于加密一个整数。但我们要加密的通常是字符串或文件。这就需要将明文转换为整数常见方法是将其视为一个大端序的字节数组然后转换成一个大的整数。例如字符串“HELLO”可以先转换成ASCII码序列。确保整数M小于nRSA要求待加密的整数M必须满足0 M n。如果明文转换后的整数大于等于n就必须进行分组。将长明文分割成多个小于n的块分别加密。使用填充方案直接转换和分组存在安全问题如确定性加密无法抵抗猜谜攻击。因此实际标准如PKCS#1 v1.5或OAEP会在加密前对明文块进行随机填充增加随机性和安全性。在我们的教学实现中为了聚焦核心算法我们暂不实现复杂的填充仅演示对单个小整数代表一个字符或小块数据的加密过程。但你必须知道没有填充的RSA教科书式RSA是不安全的。4.3 第三步加密与解密实现现在我们加密一个数字。假设我们想加密字符‘A’其ASCII码是65。加密C M^e mod n 65^17 mod 3233使用我们的modExp函数计算得到密文C一个整数。解密M C^d mod n C^2753 mod 3233计算出的M‘应该等于65。在C语言中我们需要将数字65、17、3233、2753都转换成我们的BigInt类型然后调用modExp函数。// 伪代码流程 BigInt M, n, e, d, C, M_dec; initBigInt(M); strToBigInt(65, M); initBigInt(n); strToBigInt(3233, n); initBigInt(e); strToBigInt(17, e); initBigInt(d); strToBigInt(2753, d); // 加密 modExp(M, e, n, C); printf(密文C: ); printBigInt(C); // 解密 modExp(C, d, n, M_dec); printf(解密结果: ); printBigInt(M_dec);如果一切正确打印的M_dec应该是65。4.4 一个完整的、可编译的简化示例框架由于完整的大数库代码过长这里给出一个高度简化的、使用unsigned long long演示核心逻辑的框架并指出在何处应替换为我们的大数库。#include stdio.h #include stdlib.h #include string.h // 假设这是我们的大数类型和函数声明实际需要完整实现 typedef struct BigInt BigInt; void modExp(const BigInt *base, const BigInt *exp, const BigInt *mod, BigInt *result); void strToBigInt(const char* str, BigInt *num); void printBigInt(const BigInt *num); // 使用小数字演示逻辑实际必须使用大数 void rsa_demo_with_small_numbers() { unsigned long long p 61, q 53; unsigned long long n p * q; // 3233 unsigned long long phi (p-1)*(q-1); // 3120 unsigned long long e 17; unsigned long long d 2753; // 通过扩展欧几里得算法算出 unsigned long long M 65; // 明文 A printf(明文 M %llu\n, M); // 加密C M^e mod n unsigned long long C 1; for(unsigned long long i 0; i e; i) { // 这是低效的演示实际应用快速幂 C (C * M) % n; } // 快速幂写法 // unsigned long long C 1, base M, exp e; // while (exp 0) { // if (exp 1) C (C * base) % n; // base (base * base) % n; // exp 1; // } printf(密文 C %llu\n, C); // 解密M_dec C^d mod n unsigned long long M_dec 1; for(unsigned long long i 0; i d; i) { // 同样低效演示 M_dec (M_dec * C) % n; } // 快速幂写法同上 printf(解密结果 %llu\n, M_dec); if (M M_dec) { printf(RSA 加解密成功\n); } else { printf(错误\n); } } int main() { printf( RSA算法C语言核心演示 \n); rsa_demo_with_small_numbers(); printf(\n 注以上使用小整数演示流程 \n); printf( 实际应用需替换为上文实现的完整大数(BigInt)运算库 \n); return 0; }这个程序用很小的数字验证了RSA流程。要使其真正工作于安全尺寸的密钥你需要将unsigned long long替换为BigInt并将注释中的快速幂算法用我们实现的modExp函数替代同时补全大数运算的所有函数。5. 实现过程中的关键问题与深度优化当你按照上述步骤实现时一定会遇到性能和正确性上的挑战。这里分享一些踩坑经验和优化思路。5.1 大数运算的性能瓶颈与优化我们实现的十进制数组大数库在用于RSA时性能会非常差尤其是在进行2048位密钥的模幂运算时。主要瓶颈在于乘法与除法我们实现的竖式乘法/除法复杂度是O(n^2)对于几百位的数字尚可忍受对于2048位约600多位十进制数则非常慢。取模运算我们通过除法求余数来实现取模而除法本身就很慢。优化方向更换进制不要用十进制数组改用uint32_t或uint64_t数组以2^32或2^64为基进行存储。这样加法和乘法可以利用处理器的原生指令和进位标志进行优化。实现更高效的乘法算法对于大数应采用Karatsuba算法或FFT快速傅里叶变换乘法可以将乘法复杂度从O(n^2)降低到约O(n^1.585)或O(n log n)。实现蒙哥马利模乘这是专门为模幂运算设计的算法。它通过一系列变换将耗时的模运算转化为乘法与移位操作极大提升了(a * b) % n这类运算的速度。几乎所有高性能的RSA实现如OpenSSL都使用蒙哥马利约简。使用中国剩余定理加速解密私钥持有者知道p和q。解密时可以分别计算M_p C^d mod p和M_q C^d mod q因为p和q比n小得多所以这两个指数运算更快。然后再通过CRT合成最终结果M mod n。这可以将解密速度提升约4倍。实操心得对于学习和理解实现一个基础的十进制大数库就足够了。但如果你希望得到一个“可用”的RSA实现强烈建议基于一个成熟的大数库如GNU MP来构建而不是从头造轮子。我们的目标是理解原理生产环境请使用OpenSSL或libcrypto。5.2 质数生成与素性测试我们演示中使用了固定的质数。真实场景需要随机生成大质数。随机数生成使用安全的随机数发生器如/dev/urandom或 CryptGenRandom生成一个大的随机奇数。素性测试判断一个大数是否为质数。确定性测试如试除法对于大数太慢。实际使用概率性测试最常用的是米勒-拉宾素性测试。给定一个奇数n和测试轮数k如果n通过所有k轮测试那么它是合数的概率小于4^{-k}。通常取k10~20出错概率就低到可以忽略。这是一个相对容易实现的算法。生成流程随机生成大奇数 - 米勒-拉宾测试 - 通过则作为质数候选否则加2继续测试。5.3 填充方案的重要性再强调我们之前略过了填充。这里必须强调没有填充的RSA是极不安全的。教科书式RSATextbook RSA存在多种攻击确定性加密同样的明文永远产生同样的密文攻击者可以构建字典。小明文攻击如果明文M很小可能M^e n那么密文C M^e未取模直接开e次方根就能得到M。共模攻击、选择密文攻击等。因此在实际加密数据前必须对明文进行填充。PKCS#1 v1.5 Padding或更安全的OAEP (Optimal Asymmetric Encryption Padding)是标准做法。它们会在明文前加入随机字节确保每次加密同一明文得到的密文都不同并且破坏了明文的数学结构抵抗多种攻击。6. 常见问题与调试技巧实录在实现过程中你肯定会遇到各种bug。以下是一些常见问题和解决思路。6.1 加解密结果不正确这是最普遍的问题。请按以下顺序排查检查大数基础运算首先单独测试你的大数加法、减法、乘法、除法函数用一系列小数字验证其正确性。特别是除法和取模运算很容易出错。验证密钥生成手动计算或用已知正确的工具如Python的pow函数配合大整数计算一遍你的n,φ(n),e,d。确保(e * d) % φ(n) 1成立。单步调试模幂运算用很小的数字如base5, exp3, mod13测试你的modExp函数。手动计算5^3 % 13 125 % 13 8看你的函数是否输出8。在快速幂循环中打印出每一步的中间结果。检查数据转换确保你从字符串或字节流转换到大整数BigInt的函数是正确的没有弄错字节序我们是低位在前。6.2 程序运行极其缓慢如果你的程序处理稍大的数字比如100位就慢得无法忍受算法复杂度检查你的乘法、除法是否是O(n^2)的朴素算法。对于教学可以接受对于实用必须优化。不必要的拷贝在函数传递和返回大数时尽量使用指针避免整个数组的结构体拷贝。调试信息关闭所有调试用的printf。编译优化使用编译器优化选项如gcc的-O2。6.3 内存错误与泄漏由于我们使用固定大小的数组内存错误通常表现为数组越界。边界检查在所有大数运算函数中特别是乘法和加法要检查结果是否会超过MAX_DIGITS。实现一个checkOverflow函数。初始化确保每个BigInt变量在使用前都被initBigInt初始化。临时变量函数内部创建的临时BigInt变量如果频繁调用可以考虑从外部传入或使用静态/全局变量池来减少栈开销。6.4 与标准库/其他工具结果对比这是最有效的验证方法。你可以用Python或OpenSSL命令行工具生成一个结果与你的C程序对比。用OpenSSL生成密钥对openssl genrsa -out private.pem 64生成一个极小的64位RSA密钥仅用于测试用OpenSSL提取公钥和参数openssl rsa -in private.pem -text -noout用你的C程序加载相同的p, q, e计算n和d看是否匹配。用OpenSSL加密一个数据然后用你的C程序解密看是否能成功。这个过程能帮你定位问题是出在密钥生成、加密还是解密环节。从头用C语言实现RSA就像亲手搭建了一座密码学的桥梁。你会对每一个螺栓算法步骤的承重和拧紧程度有切身的感受。虽然最终的产品在性能和安全性上无法与工业级的OpenSSL相提并论但这个过程赋予你的洞察力——对模运算、数论、大数处理和安全边界的理解——是单纯调用库函数无法比拟的。当你下次再看到ssh-keygen -t rsa或者遇到那些CTF中千变万化的RSA题目时你看到的将不再是一个黑盒而是一套你可以清晰剖析的、由数学之美构筑的精密系统。这份从零构建的体验或许就是学习密码学最扎实的路径。