最近一个读者私信我说，学校信息安全课程设计要求用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到25），C代表密文字母的序号，k是密钥（0到25的整数）。注意这里k=0等于没加密，k=3是最经典的凯撒偏移，所以有些资料里也叫“移位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种可能的密钥（不算k=0的话是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 × q，n称为模数；
- 计算欧拉函数φ(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 密钥生成：以p=61、q=53为例
我们不用动辄几百位的大素数，那样光是大数运算就得把所有代码淹没。教学演示用两个三位以内的素数就够了。取p=61、q=53，计算过程如下：
- 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加上大数运算和文件加解密功能。把这些做出来，你的课程设计在同学里基本就是第一梯队了。
