C语言实现凯撒密码与RSA算法：从古典到现代的加密原理与实践

1. 项目概述：从古典到现代的加密之旅

最近在整理一些旧项目，翻到了当年学习C语言时写的加密算法实现，从最基础的凯撒密码到后来接触的RSA算法，感觉挺有意思的。加密这个话题，听起来高大上，其实离我们很近。你每天用的聊天软件、网上支付，背后都离不开各种加密算法的支撑。对于咱们C语言开发者来说，理解这些算法的原理并用代码实现出来，不仅是巩固编程基础的好方法，更是深入理解计算机安全底层逻辑的绝佳途径。

这个项目，说白了就是用C语言手搓两个经典的加密算法：凯撒密码和RSA。凯撒密码是古典密码学的代表，简单直观，适合入门，理解它就像理解字母表的滑动游戏。而RSA算法则是现代非对称加密的基石，涉及到大数运算、模幂计算等更复杂的数学和编程技巧。通过实现它们，我们能清晰地看到加密技术从“移位”到“数学难题”的演进脉络。无论你是刚学完C语言基础想找点有成就感的项目练手，还是对密码学感兴趣想一探究竟，跟着这篇笔记，你都能获得一套可以直接运行、可以拆解学习的代码，以及背后那些“为什么这么做”的思考。

2. 核心思路与算法选型背后的考量

为什么选择凯撒密码和RSA这一古一今的组合？这背后有教学和实践的双重考虑。

2.1 凯撒密码：理解加密的基本范式

凯撒密码的核心思路是“替换”。它把明文中的每个字母，按照字母表顺序向后（或向前）移动固定的位数，得到密文。比如，移位数为3时，‘A’变成‘D’，‘B’变成‘E’……‘Z’绕回变成‘C’。解密过程就是反向移动相同的位数。

选择实现它，首要原因是教学意义。它的逻辑极其简单，一个for循环加字符运算就能搞定，非常适合用来建立“加密/解密”、“密钥”、“明文/密文”这些基本概念。其次，它能很好地锻炼我们对字符编码（ASCII）和数组（或字符串）的操作能力。在实现时，我们需要仔细处理大小写字母的边界（‘z’之后回到‘a’），以及非字母字符（如空格、标点）保持不变，这些都是很基础的编程训练。

2.2 RSA算法：踏入非对称加密的大门

RSA的核心思路则建立在数论难题之上，具体来说是“大整数的质因数分解在计算上非常困难”。它使用一对密钥：公钥加密，私钥解密。公钥可以公开，私钥必须保密。

选择实现RSA，是因为它是非对称加密的典范，理解了RSA，就掌握了理解HTTPS、SSH、数字签名等现代安全协议的一把钥匙。用C语言实现一个简化版的RSA，挑战在于：

1. 大数处理：RSA的密钥长度通常是1024位、2048位甚至更长，远超C语言基本数据类型（如long long）的范围。我们必须自己设计或利用库来处理大整数。
2. 核心数论算法：需要实现模幂运算（计算m^e mod n要高效）、扩展欧几里得算法（用于求模逆元，生成私钥）、素性检测（生成大素数p和q）。
3. 编码转换：需要将字符串（明文）转换为整数（才能进行数学运算），运算后再转换回字符串。

通过这个组合，我们能完成一个从“玩具级”加密到“实用级”加密原型的认知跨越。在工具选型上，为了聚焦算法本身，我们不会引入像OpenSSL那样庞大的第三方库，而是尽可能用C标准库和自己实现的函数来完成，这对于深刻理解原理至关重要。

注意：我们这里实现的RSA是“教学版本”，密钥长度很小（比如用两个几十位的素数），仅用于演示原理。绝对不可将其用于任何真实的、要求安全性的场景。真正的RSA应用依赖于经过严格安全审计的库（如OpenSSL, Libgcrypt），并使用足够长的密钥（目前推荐至少2048位）。

3. 凯撒密码的C语言实现与细节雕琢

我们先从简单的开始。凯撒密码的实现虽然简单，但细节决定成败。

3.1 函数设计与边界处理

一个健壮的凯撒加密函数需要考虑以下几点：

• 输入：明文字符串、移位密钥（整数）。
• 处理：遍历字符串，对每个字符判断是否为字母，然后根据大小写进行相应的移位。
• 输出：密文字符串。

这里的关键在于边界处理和非字母字符保留。我们来看核心代码逻辑：

#include <stdio.h> #include <string.h> #include <ctype.h> // 用于 isalpha, isupper, islower void caesar_cipher(char* text, int key) { // 确保密钥在0-25之间，避免无效的大幅度移位 key = key % 26; if (key < 0) { key += 26; // 处理负密钥（左移） } for (int i = 0; text[i] != '\0'; ++i) { char ch = text[i]; if (isalpha(ch)) { // 只处理字母字符 char base = isupper(ch) ? 'A' : 'a'; // 确定是大写字母基准还是小写字母基准 text[i] = (ch - base + key) % 26 + base; // 核心移位与取模操作 } // 非字母字符（空格、标点、数字）原样保留 } }

解密函数几乎一模一样，只是传入的密钥是-key，或者用(26 - key) % 26作为新密钥进行“加密”操作即可。

3.2 实操心得与常见陷阱

1. 密钥取模是关键：key = key % 26这行代码必不可少。如果用户输入了100，实际效果等同于100 % 26 = 22。这保证了移位操作始终在字母表范围内。
2. 负密钥的处理：支持负密钥意味着支持向左移位。上述代码通过if (key < 0) key += 26;将负密钥转换到0-25的正数范围内，统一了处理逻辑。
3. 区分大小写：使用isupper()和islower()判断，并分别以‘A’或‘a’作为基准进行计算，这是保证大小写字母独立且正确移位的核心。
4. 原地修改与副本：上面的函数直接修改了原字符串。在实际应用中，如果需要保留原文，务必先使用strcpy将原文复制到一个新数组中再进行加密操作。
5. ASCII码的陷阱：直接对字符进行加减运算，实际上是对其ASCII码进行操作。必须通过ch - base将其映射到0-25的范围，运算完后再加回base，才能得到正确的字母。跳过这一步会导致结果混乱。

一个简单的测试用例：

int main() { char message[] = "Hello, World! 2023"; int key = 3; printf("Original: %s\n", message); caesar_cipher(message, key); printf("Encrypted: %s\n", message); // 解密 caesar_cipher(message, -key); // 或使用 26-key printf("Decrypted: %s\n", message); return 0; }

输出应显示加密后的文本和解密恢复的原文。

4. RSA算法的C语言实现：核心模块拆解

RSA的实现要复杂得多，我们将其分解为几个核心模块，并采用较小的数字以便演示。

4.1 大数表示与基础运算（简化版）

由于是教学演示，我们暂时使用C语言内置的long long类型（或unsigned long long），并假设我们的素数p和q很小，使得n和φ(n)也在其表示范围内。在实际中，这远远不够，你需要一个真正的大数库（如GNU MP）。这里我们先理解流程。

我们定义几个类型和工具函数：

typedef long long int64; // 为了方便，给long long起个别名 // 欧几里得算法求最大公约数 int64 gcd(int64 a, int64 b) { while (b != 0) { int64 temp = b; b = a % b; a = temp; } return a; } // 扩展欧几里得算法，求 ax + by = gcd(a, b) 的解，并返回模逆元 // 函数返回 gcd(a, b)，并通过指针返回 x, y int64 extended_gcd(int64 a, int64 b, int64 *x, int64 *y) { if (b == 0) { *x = 1; *y = 0; return a; } int64 x1, y1; int64 g = extended_gcd(b, a % b, &x1, &y1); *x = y1; *y = x1 - (a / b) * y1; return g; } // 模逆元计算：求 a 在模 m 下的逆元，即找到 x 使得 (a * x) % m == 1 // 返回 -1 表示逆元不存在（a与m不互素） int64 mod_inverse(int64 a, int64 m) { int64 x, y; int64 g = extended_gcd(a, m, &x, &y); if (g != 1) { return -1; // 没有乘法逆元 } else { // 确保结果为正数 return (x % m + m) % m; } }

4.2 快速模幂运算

RSA加解密的核心操作是c = m^e mod n和m = c^d mod n。直接计算幂再取模，对于大指数是不可能的（数字会溢出到天文数字）。必须使用快速模幂算法（Exponentiation by Squaring）。

// 快速模幂运算：计算 (base^exp) % mod int64 mod_pow(int64 base, int64 exp, int64 mod) { int64 result = 1; base = base % mod; // 先取模，防止后续乘法溢出 while (exp > 0) { // 如果exp是奇数，乘一次当前的base if (exp & 1) { result = (result * base) % mod; } // exp右移一位（除以2），base平方 exp >>= 1; base = (base * base) % mod; } return result; }

这个算法的妙处在于，它将指数exp用二进制表示，将计算复杂度从O(exp)降到了O(log exp)。这是实现RSA可行性的关键。

4.3 密钥生成流程

1. 选择两个大素数p和q（演示中我们手动指定小的素数）。
2. 计算n = p * q。n的长度就是密钥长度。
3. 计算欧拉函数φ(n) = (p-1) * (q-1)。
4. 选择一个整数e，满足1 < e < φ(n)，且gcd(e, φ(n)) = 1（即e与φ(n)互质）。通常选择65537，因为它二进制表示中1很少，计算效率高，且是素数。
5. 计算e对于φ(n)的模逆元d，即d * e ≡ 1 (mod φ(n))。d就是私钥。

// RSA密钥生成示例（使用小素数演示） void generate_rsa_keys(int64 p, int64 q, int64 *n, int64 *e, int64 *d) { *n = p * q; int64 phi = (p - 1) * (q - 1); // 选择公钥指数e，通常为65537，这里为演示选一个小值 *e = 65537; // 确保 e < phi 且 gcd(e, phi)==1 // 简单检查一下，如果e不小于phi，就选一个小点的值 if (*e >= phi) { for (*e = 3; gcd(*e, phi) != 1; *e += 2) { // 寻找一个与phi互质的奇数e } } else { // 检查65537是否与phi互质 if (gcd(*e, phi) != 1) { for (*e = 3; gcd(*e, phi) != 1; *e += 2) {} } } // 计算私钥指数d *d = mod_inverse(*e, phi); if (*d == -1) { printf("Error: Failed to find modular inverse for e. Choose different p, q, or e.\n"); // 处理错误... } }

4.4 加密与解密函数

有了n, e, d，加解密就很简单了，本质都是调用mod_pow。

// RSA加密： ciphertext = plaintext^e mod n int64 rsa_encrypt(int64 plaintext, int64 e, int64 n) { if (plaintext >= n) { printf("Warning: Plaintext (%lld) must be less than n (%lld).\n", plaintext, n); // 在实际中，长明文需要分块，每块的值必须小于n return -1; // 或进行分块处理 } return mod_pow(plaintext, e, n); } // RSA解密： plaintext = ciphertext^d mod n int64 rsa_decrypt(int64 ciphertext, int64 d, int64 n) { return mod_pow(ciphertext, d, n); }

4.5 字符串与数字的转换

RSA操作的是大整数，但我们要加密的是字符串。所以需要一个转换过程。一个简单（但不安全）的方法是，将字符串视为一个256进制（或更大进制）的大数。为了简化演示，我们可以一次加密一个字符（前提是n > 255），但这毫无安全性可言，仅用于演示流程。

// 简化版：逐字符加密（仅用于原理演示，绝不安全！） void rsa_encrypt_string(const char* plaintext, int64 e, int64 n, int64* ciphertext_array, int len) { for (int i = 0; i < len; ++i) { ciphertext_array[i] = rsa_encrypt((int64)plaintext[i], e, n); } } void rsa_decrypt_string(const int64* ciphertext_array, int64 d, int64 n, char* plaintext, int len) { for (int i = 0; i < len; ++i) { plaintext[i] = (char)rsa_decrypt(ciphertext_array[i], d, n); } plaintext[len] = '\0'; }

重要警告：这种逐字符加密等同于简单的替换密码，完全丧失了RSA的安全性。真正的RSA需要结合填充方案（如OAEP）和分组加密模式，将长明文分割成符合要求的块进行处理。这里的代码仅用于理解RSA数学原理的流程。

5. 完整演示与问题深度排查

让我们把上面的模块组合起来，完成一个完整的、可运行的演示程序，并深入探讨其中会遇到的问题。

5.1 一个完整的教学演示程序

#include <stdio.h> #include <string.h> #include <ctype.h> // ... 将前面章节的所有函数定义（gcd, extended_gcd, mod_inverse, mod_pow, generate_rsa_keys, rsa_encrypt, rsa_decrypt, rsa_encrypt_string, rsa_decrypt_string）放在这里 ... int main() { printf("=== 凯撒密码演示 ===\n"); char message[] = "Secret Message"; int caesar_key = 5; printf("原始文本: %s\n", message); caesar_cipher(message, caesar_key); printf("凯撒加密后: %s\n", message); caesar_cipher(message, -caesar_key); printf("凯撒解密后: %s\n", message); printf("\n=== RSA算法演示 (教学简化版) ===\n"); // 警告：使用极小的素数，仅用于演示数学原理 int64 p = 61; // 第一个“大”素数（实际上很小） int64 q = 53; // 第二个“大”素数 int64 n, e, d; generate_rsa_keys(p, q, &n, &e, &d); printf("生成的密钥:\n"); printf(" 素数 p = %lld\n", p); printf(" 素数 q = %lld\n", q); printf(" 模数 n = p*q = %lld\n", n); printf(" 公钥指数 e = %lld\n", e); printf(" 私钥指数 d = %lld\n", d); printf(" 公钥: (e=%lld, n=%lld)\n", e, n); printf(" 私钥: (d=%lld, n=%lld)\n", d, n); // 要加密的明文（数字），必须小于n int64 plain_num = 65; // 假设代表字符 'A' if (plain_num >= n) { printf("明文 %lld 必须小于 n (%lld)。\n", plain_num, n); return 1; } printf("\n加密数字 %lld ...\n", plain_num); int64 cipher_num = rsa_encrypt(plain_num, e, n); printf("加密结果 (密文): %lld\n", cipher_num); printf("\n解密密文 %lld ...\n", cipher_num); int64 decrypted_num = rsa_decrypt(cipher_num, d, n); printf("解密结果: %lld\n", decrypted_num); printf(decrypted_num == plain_num ? "加解密成功！\n" : "加解密失败！\n"); // 字符串加密演示（极不安全的方式） printf("\n=== RSA字符串加密演示 (不安全，仅流程演示) ===\n"); char str_plain[] = "HELLO"; int len = strlen(str_plain); int64 cipher_arr[10]; // 假设足够大 char decrypted_str[10]; printf("原始字符串: %s\n", str_plain); rsa_encrypt_string(str_plain, e, n, cipher_arr, len); printf("加密后的数字序列: "); for (int i = 0; i < len; ++i) printf("%lld ", cipher_arr[i]); printf("\n"); rsa_decrypt_string(cipher_arr, d, n, decrypted_str, len); printf("解密后的字符串: %s\n", decrypted_str); return 0; }

5.2 深度问题排查与经验实录

在实际编写和运行上述代码时，你几乎一定会遇到下面这些问题：

1. 整数溢出（最普遍的问题）

   • 现象：当p和q稍大（比如几百），计算n=p*q或mod_pow中的乘法时，结果超出long long的范围（通常约±9e18），导致溢出，得到错误结果。
   • 排查：打印中间变量。计算n后，立即打印p、q和n，看n是否为负数或一个明显不合理的值。
   • 解决：这是教学版代码的根本局限。真正的解决方案是引入大数库。你可以尝试使用__int128（如果编译器支持），或者使用数组/字符串来模拟大整数，实现加减乘除和取模运算。这本身就是一个庞大的编程项目。

2. 模逆元不存在

   • 现象：在generate_rsa_keys中，mod_inverse返回-1。
   • 原因：你选择的公钥指数e与欧拉函数φ(n)不互质，即gcd(e, φ(n)) != 1。这违反了RSA的基本要求。
   • 排查：打印e和phi的值，并计算它们的最大公约数。
   • 解决：确保e是一个素数，并且不是p-1或q-1的因子。使用常见的e=65537通常可以避免此问题，但如果p-1或q-1能被65537整除，仍然会失败。我们的演示代码中有一个简单的回退机制，会尝试寻找一个小的、互质的奇数e。

3. 明文必须小于模数n

   • 现象：加密函数返回-1或解密结果错误。
   • 原因：RSA算法要求待加密的整数明文m必须满足0 <= m < n。如果m >= n，加密解密过程将不成立。
   • 排查：在调用rsa_encrypt前，检查plaintext和n的大小。
   • 解决：这是RSA作为“分组密码”的特性。对于长明文，必须进行分块，每块转换为整数后必须小于n。同时，为了安全，不能直接对明文整数加密，必须进行填充（Padding），如PKCS#1 v1.5或OAEP填充，这增加了随机性并防止一些攻击。

4. “逐字符加密”毫无安全性

   • 现象：虽然演示程序能工作，但从密码学角度看，这种加密方式极其脆弱。
   • 分析：它等同于单表替换密码，攻击者通过分析密文频率很容易破解。例如，加密“HELLO”后，两个‘L’字符对应的密文数字是一样的。
   • 正确做法：工业级实现中，RSA通常不直接加密数据本身，而是用于加密一个对称加密算法（如AES）的密钥（即“密钥交换”或“密钥封装”）。数据本身用更快的AES加密。或者，在使用RSA加密数据时，必须使用安全的填充方案和适当的分块大小。

5. 素性检测的挑战

   • 现象：我们的演示代码手动指定了p和q。真实场景需要随机生成大素数。
   • 解决：生成大素数是一个概率过程。常用方法是Miller-Rabin素性检测算法。它通过多次随机测试，能以极高的概率判断一个数是否为素数。你需要实现这个算法，并从一个随机的大奇数开始，不断递增直到找到一个通过测试的“ probable prime”（概率素数）。

5.3 从教学版到实用化的思考

通过这个教学项目，我们清晰地看到了理论与实践的鸿沟。用C语言实现一个“玩具级”的RSA来理解数论基础是完美的，但距离一个“可用”的加密组件还差十万八千里，中间隔着：

• 真正的大整数运算库。
• 安全的随机数生成器（用于生成素数）。
• 标准的填充方案（PKCS#1, OAEP）。
• 侧信道攻击防护（时间攻击、功耗分析等）。

所以，最后的实操心得也是最重要的建议：学习密码学，自己动手实现算法是理解原理的黄金法则；但在实际项目中，请务必使用久经考验的、经过专业审计的密码学库，如OpenSSL, Libsodium, 或你所用语言/框架的标准安全模块。不要自己造轮子，尤其是在加密这个领域，细微的错误都可能导致整个安全体系的崩塌。这个C语言项目的目的，就是帮你造一个精致的玩具轮子，让你明白真轮子为什么那么复杂，从而在以后使用真轮子时，心里更有底。