最近一个读者私信我说学校信息安全课程设计要求用C语言实现凯撒密码和RSA课本翻了好几遍公式也背得滚瓜烂熟可一打开编译器还是不知道从哪里下手。这个问题我太有共鸣了——我当年也对着几行RSA代码发过呆明明思路都懂真让自己写却漏洞百出。凯撒密码简单到让人怀疑它也算加密RSA又理论到让人怀疑它到底能不能落地。但说句实话这两个算法恰好横跨了密码学的两个时代一个代表古典密码的玩具级实现一个代表公钥密码体系的工业级基石。把这两个吃透了你后续再去看AES、ECC甚至国密算法都会顺很多。这篇文章我就用最直接的方式把凯撒密码的移位思想、RSA的数论原理、C语言实现细节以及那些教科书写不出来的坑全部捋一遍。不管你是在做课程设计还是纯粹想搞懂老外为什么管RSA叫“公钥加密的祖师爷”这篇文章都值得你花二十分钟认真读一遍。1. 为什么先动凯撒再碰RSA两种算法的定位差异很多初学者容易把凯撒密码和RSA混在一起记因为它们名字里都带“加密”。但这两东西从设计思路上就完全不是一个物种。凯撒密码是典型的对称加密——加密用密钥k解密也用同一个密钥k。你先定一个偏移量比如3那A加密后变成D解密的时候所有字母再往回移3位就还原了。这种加密方式简单粗暴但问题也致命一旦密钥泄露整个通信体系就全部瘫痪。RSA则是非对称加密——加密用公钥解密用私钥两者成对出现但不可互相推导。公钥可以随便发给全世界私钥自己死死捂住。别人用你的公钥加密一段消息天底下只有你手里的私钥能解开。这套思想在1977年刚提出的时候几乎是颠覆性的原来两个人从来没有见过面也可以建立一条安全信道而且不需要事先偷偷交换密钥。从实现层面讲凯撒密码考的是字符串处理和取模运算属于“会写循环就能写出来”的范畴。RSA考的是数论算法——素数检测、欧拉函数、模逆元、快速幂取模——这些知识单独拎出来每一个都是数学课上的经典内容拼到一起却需要一个很清晰的工程思维才能组织成可运行的代码。我建议的学习顺序是先花半小时把凯撒彻底写会建立“加密算法无非就是处理数据”的直觉再花一个晚上啃RSA的数学推导和代码实现建立“加密算法原来可以这么精巧”的认识。这篇文章的顺序就按这个来。2. 凯撒密码从字符串处理到循环移位2.1 移位替换的本质凯撒加密本质上是一种“单表替换密码”。所谓单表替换就是明文里每个字母都被固定替换成另一个字母整张替换表从头到尾不变。凯撒的做法特别简单把26个字母看成一个环每个字母向后移动固定数目移动的步长就是密钥。数学表达如下加密C (P k) mod 26解密P (C - k) mod 26其中P代表明文字母在字母表中的序号A到Z对应0到25C代表密文字母的序号k是密钥0到25的整数。注意这里k0等于没加密k3是最经典的凯撒偏移所以有些资料里也叫“移位3密码”。这个式子看着简单但有一个细节特别容易翻车当你处理大写字母和小写字母时不能直接拿ASCII码去做加法。比如大写A的ASCII码是65小写a的ASCII码是97如果直接(c k) % 26算出来的结果不知道落在哪个数字上根本不能正确对应回字母。正确做法是先做归一化——把字符转换为0到25的序号参与取模运算之后再转换回字符。2.2 核心加密函数怎么写我们平时写凯撒加密绝大多数场景只需要处理英文字母。最稳妥的实现方式是区分大小写其余字符原样保留。来看这段代码#include stdio.h #include string.h #include ctype.h void caesar_encrypt(char *text, int shift) { for (int i 0; text[i] ! \0; i) { char c text[i]; if (islower(c)) { text[i] a (c - a shift) % 26; } else if (isupper(c)) { text[i] A (c - A shift) % 26; } // 其他字符数字、标点、空格保持不变 } }这段代码的核心逻辑是c - a先把字母转成0~25的序号加上偏移量取模26保证结果落在同一个字母表范围内最后再加回a恢复ASCII码。如果明文是Hello World密钥为3加密结果就是Khoor Zruog。解密函数可以写一个独立的、或者复用加密函数把偏移量传成负值void caesar_decrypt(char *text, int shift) { for (int i 0; text[i] ! \0; i) { char c text[i]; if (islower(c)) { text[i] a ((c - a - shift) % 26 26) % 26; } else if (isupper(c)) { text[i] A ((c - A - shift) % 26 26) % 26; } } }细心的人应该发现了解密函数里取模的部分我写了两层((c - a - shift) % 26 26) % 26。这是C语言取模运算的经典陷阱后面我会专门拎出来说。2.3 负数取模C语言埋给你的坑C语言里的%运算符在操作符左侧为负数时结果也可能是负数。比如(b - a - 5) % 26实际计算的是(1 - 5) % 26在C语言里结果是-4而不是22。如果你直接把-4当成数组下标或者加回字符结果肯定不对。网上很多代码在解密时直接写(c - a - shift) % 26这在小端场景下碰巧没问题一旦偏移超过当前字母序号就立刻出错。我见过不止一个同学调了半天最后发现就是少加了一个 26再取模。处理方式有两种一种像我上面那样先取模再加26再取模数学上保证结果永远落在0~25另一种是先判断如果结果小于0就加上26。两种都可以但我推荐第一种写起来更紧凑也更好统一逻辑。2.4 暴力破解密钥穷举不过瘾怎么解凯撒密码一共只有26种可能的密钥不算k0的话是25种。这个数量级意味着任何人拿到密文后最多试25次就能遍历所有可能的明文。用程序暴力破解简直不要太轻松void caesar_brute_force(const char *cipher) { char buffer[1024]; for (int key 1; key 26; key) { strcpy(buffer, cipher); caesar_decrypt(buffer, key); printf(Key %2d: %s\n, key, buffer); } }跑出来以后你会看到25行乱糟糟的英文其中只有一行是通顺的——那就是原始明文。上面这个函数打印出结果后你自己肉眼扫一眼就能找到正确答案。这也是凯撒密码在安全领域的定位它现在完全不是用来保护信息的而是用来作为密码学入门的“第一课作业”。从它身上你能理解什么叫密钥空间、什么叫暴力破解、什么叫频率分析——这些都是后面理解更复杂算法的基础。3. RSA从数论定理到可运行代码3.1 RSA的安全根基大数分解难题RSA的安全性根基是这么一句话“把两个大素数乘起来很容易但把它们的乘积分解回两个大素数很难。”你可以亲自感受一下23 * 37 851心算几秒钟就出来了。但给你851让不查表找它的两个素数因子就要试半天。当这两个素数的位数从2位变成500位难度就不是简单的乘法逆过程而是指数级上升。现代计算机要分解一个2048位的整数用最先进的算法和足够多的算力也需要极其漫长的时间这就是RSA可以安全使用的底气。完整的RSA算法涉及这样几个步骤随机选择两个大素数p和q计算n p × qn称为模数计算欧拉函数φ(n) (p - 1) × (q - 1)选择一个公钥指数e要求1 e φ(n)且e与φ(n)互质计算私钥指数d使得e × d ≡ 1 (mod φ(n))公钥为(n, e)私钥为(n, d)加密C M^e mod n解密M C^d mod n。这里加密和解密恰好是一对可逆运算背后的数学证明依赖欧拉定理属于数论里比较优美的结论。写代码的时候你不需要被证明过程卡住只需要明确一个认知只要保证d存在、e和d互为模φ(n)的逆元这一套加减密流程在数学上就一定是自洽的。3.2 密钥生成以p61、q53为例我们不用动辄几百位的大素数那样光是大数运算就得把所有代码淹没。教学演示用两个三位以内的素数就够了。取p61、q53计算过程如下n 61 × 53 3233φ(n) (61 - 1) × (53 - 1) 60 × 52 3120选e 17检查gcd(17, 3120) 1合法任何与3120互质的数都可以为了效率和安全工业界常用65537但演示用17好算求d 17^{-1} mod 3120 2753这里公钥就是(3233, 17)私钥就是(3233, 2753)。有了这两组数你已经可以手动加密一条消息了。比如明文M 65加密C 65^17 mod 3233 2790解密M 2790^2753 mod 3233 65计算过程当然要靠程序来完成但上面的小数据可以帮你验证自己写的代码到底对不对。3.3 模逆元扩展欧几里得算法的C实现求d的过程是RSA的第一个技术难点。你可能想用暴力枚举从1开始逐个试直到找到一个数x满足(17 × x) % 3120 1。这种方法在φ(n)很大的时候低效得可怕。正确做法是使用扩展欧几里得算法它能在算出最大公约数的同时把满足ax by gcd(a, b)的一组x、y也一并算出来。如果a和b互质那么gcd(a, b) 1此时x就是a模b的逆元。代码实现如下int mod_inverse(int a, int m) { int t 0, new_t 1; int r m, new_r a; while (new_r ! 0) { int quotient r / new_r; int tmp t; t new_t; new_t tmp - quotient * new_t; tmp r; r new_r; new_r tmp - quotient * new_r; } if (r 1) return -1; // 不存在逆元 if (t 0) t m; return t; }这个算法的原理如果你不想深究可以直接当作“求解模逆元的模板”来用。但我建议你还是动手推导一次因为扩展欧几里得的每一步迭代其实都是在做带余除法理解以后你会发现它和普通欧几里得算法只是一体两面。3.4 快速幂取模不写这个你的程序会直接卡死RSA的加密要计算M^e mod n。如果你天真地用循环连乘unsigned long long result 1; for (int i 0; i e; i) { result result * M % n; }当e等于17时还能勉强撑住但实际RSA的e是65537私钥d甚至可能是几百位的大数。这种循环乘上百万次不止会很慢更重要的问题是你手上那点数值范围根本撑不住中间结果的膨胀。正确的姿势是“快速幂取模”也叫“平方取模法”。核心思想是把指数按二进制拆开每次都是平方取模只有对应二进制位为1时才额外乘上当前底数。这样原本需要运算e次乘法现在最多只需要log2(e)次。查找下面这段代码的写法unsigned long long mod_pow(unsigned long long base, unsigned long long exp, unsigned long long mod) { unsigned long long result 1; base % mod; while (exp 0) { if (exp 1) { result (result * base) % mod; } base (base * base) % mod; exp 1; } return result; }走一遍流程你就明白它在干什么了。以65^17 mod 3233为例17的二进制是10001所以程序先处理指数的最低位1乘上65然后底数变成65^2再平方变成65^4、65^8最后到65^16。整个过程中每一次乘法都立刻取模中间数值永远压在一个可控范围内。这个技巧是RSA能落到实处的关键。4. 完整RSA演示程序与运行结果验证4.1 程序整体结构写RSA演示程序不建议把密钥生成、加密、解密一股脑堆在main函数里。清晰的分层对调试非常有帮助。我习惯这样组织工具函数层gcd、mod_inverse、mod_pow密钥生成层generate_keys负责选定p和q、计算n和φ(n)、选e、求d加解密层rsa_encrypt、rsa_decrypt测试入口main函数完成密钥生成、加密、解密和结果打印。这样一个标准的小项目骨架后续你往里加性能测试、加界面、甚至改成文件加解密都非常方便。4.2 可直接复制的完整代码我这里给出一套完整的、能跑通的代码并做了详细的注释#include stdio.h #include stdlib.h // 计算最大公约数 int gcd(int a, int b) { while (b ! 0) { int t a % b; a b; b t; } return a; } // 扩展欧几里得求模逆元 int mod_inverse(int a, int m) { int t 0, new_t 1; int r m, new_r a; while (new_r ! 0) { int q r / new_r; int tmp t; t new_t; new_t tmp - q * new_t; tmp r; r new_r; new_r tmp - q * new_r; } if (r 1) return -1; if (t 0) t m; return t; } // 快速幂取模 unsigned long long mod_pow(unsigned long long base, unsigned long long exp, unsigned long long mod) { unsigned long long result 1; base base % mod; while (exp 0) { if (exp 1) { result (result * base) % mod; } base (base * base) % mod; exp 1; } return result; } int main(void) { // 选两个小素数仅演示用 int p 61; int q 53; int n p * q; int phi (p - 1) * (q - 1); // 选择公钥指数 e保证与 phi 互质 int e 17; while (gcd(e, phi) ! 1) { e; } // 计算私钥指数 d int d mod_inverse(e, phi); if (d -1) { printf(无法计算私钥指数请重新选择参数。\n); return 1; } printf(p %d, q %d\n, p, q); printf(n %d, phi(n) %d\n, n, phi); printf(公钥: (%d, %d)\n, n, e); printf(私钥: (%d, %d)\n, n, d); // 演示加密和解密 int plaintext 65; unsigned long long cipher mod_pow(plaintext, e, n); unsigned long long decrypted mod_pow(cipher, d, n); printf(明文: %d\n, plaintext); printf(加密后密文: %llu\n, cipher); printf(解密后明文: %llu\n, decrypted); if (decrypted plaintext) { printf(验证通过加解密正确\n); } else { printf(验证失败加解密结果不一致\n); } return 0; }4.3 运行结果对照我直接用代码里的参数跑了一遍输出如下p 61, q 53 n 3233, phi(n) 3120 公钥: (3233, 17) 私钥: (3233, 2753) 明文: 65 加密后密文: 2790 解密后明文: 65 验证通过加解密正确这里有一个很关键的验证思路加解密本身可能因为代码逻辑错误而“看起来是对的”所以每次写完代码都要用一组精挑细选的小参数确认解密结果和原始明文完全一致。上面这组参数是我常用的你也可以换成别的素数对只要能通过验证说明算法流程没毛病。4.4 从演示代码到工业级应用还差哪些东西如果你以为上面这段代码就是RSA的全部那误会就大了。这个演示程序在生产环境里连“测试版”都算不上主要有几个致命短板第一n只到3233随便分解一下就裸奔。工业级RSA的密钥长度要求至少2048位也就是n是一个约617位十进制的大数。C语言内置的unsigned long long最多64位完全装不下必须借助大数库比如GMP或OpenSSL实现高精度整数运算。第二没有填充机制。直接对数字做模幂运算会产生一些数学上的结构性特征攻击者可能利用这些特征去推测明文所以真实环境必须在加密前给明文加入随机填充比如OAEP。第三密钥生成里对素数的随机性和不可预测性要求极高。如果p和q选得不够随机或者选到了距离很近的素数攻击者可以通过特殊算法快速分解n。我给读者说这些不是为了打击大家用C语言实现RSA的信心而是想说明写一个能跑通的演示程序是学习算法的好方法但千万不要拿它去保护真实数据。5. 实操中绕不开的坑与算法选型心得5.1 大数溢出的边界控制用unsigned long long做模幂运算时你根本没法保证中间结果不溢出。比如(result * base) % mod当result和base都接近mod时乘积很容易超过unsigned long long上限。最简单粗暴的控制方式是选择尽量小的演示参数但如果你想加密的数值稍微大一点就需要把乘法换成“分段乘法”或者引入大数运算库。5.2 明文字符串如何变成整数RSA本质上只能处理小于n的整数因此要加密一串文本必须先把字符串转换成一个大整数。常见方法是把字符串按字节切块对每一块做分组转换或者直接把每个字节当作一个整数分别加密。但要注意如果明文块对应的整数大于或等于n解密时就会出现信息丢失因为模运算把数值截断了。实际系统里的做法是采用“混合加密”用RSA保护对称密钥用对称算法加密正文数据。这也是HTTPS的实际工作方式。5.3 教学代码和实际工程的边界做课程设计的时候老师大概率只关心你能否完整写出凯撒密码的移位逻辑和RSA的模幂运算过程。这时候你交一个能跑通、能验证的小程序即可。但如果你在真实项目里被人要求“用C语言写一套RSA加密”你可以直接告诉对方生产级RSA必须用权威密码学库自己手写的实现不是能不能用的问题而是可能存在大量未知的侧信道漏洞和数学攻击面。5.4 两种算法各有什么现代应用凯撒密码虽然不能保护数据但它的思想在很多地方以变体形式存在比如ROT13是一种凯撒变体用于在一些论坛里对spoiler文本做简单伪装。RSA则到处都在用数字签名、证书体系、密钥交换、比特币地址的生成过程中都能看到RSA或同类公钥算法的影子。更重要的是通过实现这两个算法你能掌握两个核心工程能力一是对经典问题的数学建模能力二是把数学公式工程化的能力。前者让你看得懂论文里的算法描述后者让你能把任何想法变成能运行的代码。我没见过哪个好程序员不经过程序化简单数学问题的训练就突然能驾驭复杂算法的。6. 写在最后我的几个实操体会代码写到这里我多说几句自己的体会。第一凯撒密码的三行核心代码比长篇大论的解释更能让人理解“移位”这个概念。你亲手加上那些取模和字符归一化处理之后再去看维基百科的单表替换密码词条会觉得所有描述都清清楚楚。第二RSA的关键不在代码本身而在于你能否从头推导一遍密钥生成的完整流程。我强烈建议你拿笔算一次用纸笔求一次模逆元再用程序验证一次这个流程走一遍RSA就算真正进门了。第三也是我踩过几次坑之后的教训——任何密码学代码写完第一件事就是拿已知结果做回归验证不要对自己的实现盲目自信。凯撒还好RSA这种一个符号错了结果就全错而且你肉眼根本看不出哪一步出错的算法只能靠精确的验证数据兜底。如果你想进一步扩展这个项目可以试试给凯撒密码加一个频率分析模块或者给RSA加上大数运算和文件加解密功能。把这些做出来你的课程设计在同学里基本就是第一梯队了。