当前位置：首页 > news >正文

C语言实现凯撒密码与RSA算法：从古典加密到现代公钥体系实践

news 2026/6/30 19:12:37

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

最近在整理一些旧项目，翻到了当年学习C语言时写的加密算法实现。从最基础的凯撒密码，到后来接触的非对称加密RSA，这些代码现在看来虽然稚嫩，但却是理解密码学核心思想非常好的敲门砖。很多刚接触C语言和算法的朋友，往往觉得加密算法高深莫测，其实它们的底层逻辑，尤其是用C语言这种贴近硬件的语言来实现时，更能让你看清数据是如何被“打乱”和“还原”的。这篇文章，我就来拆解一下如何用C语言实现凯撒密码和RSA算法，我会把当年踩过的坑、需要注意的细节，以及如何从简单的替换加密过渡到复杂的公钥体系，都详细地捋一遍。无论你是正在学习C语言，想找点有挑战性的练手项目，还是对加密原理感兴趣，想知其然更知其所以然，这篇内容应该都能给你提供一条清晰的实践路径。

2. 凯撒密码：古典加密的C语言实现

凯撒密码可以说是密码学的“Hello World”。它的原理极其简单：将明文中的每个字母按照字母表顺序偏移一个固定的位数，比如偏移3位，那么‘A’就变成‘D’，‘B’变成‘E’，以此类推。解密时则反向偏移同样的位数。虽然它毫无安全性可言，但作为入门项目，它能让你快速理解加密、解密的基本流程，以及如何在C语言中操作字符。

2.1 核心思路与边界处理

用C语言实现凯撒加密，核心就是字符的算术运算。在ASCII码表中，大写字母‘A’到‘Z’是连续的（65-90），小写字母‘a’到‘z’也是连续的（97-122）。加密过程就是给字符的ASCII码加上一个偏移量key。

但这里有个关键陷阱：直接加完之后，字符可能会超出字母的范围。比如‘z’（122）偏移3位，直接加3得到125，对应的ASCII字符是‘}’，这显然不是我们想要的字母。因此，我们必须处理“回环”问题，让超出‘z’或‘Z’的字符能够绕回到字母表的开头。这就是模运算（Modulo Operation）大显身手的地方。

具体思路是：

判断字符是否为大写或小写字母。
找到该字母在字母表中的相对位置（‘A’或‘a’记为0）。
进行偏移和模26运算，确保结果始终在0-25之间。
将相对位置转换回对应的ASCII码。

这个处理过程，是初学者最容易出错的地方。很多早期的实现只是简单判断是否越界然后加减26，但使用模运算可以让逻辑更清晰、代码更简洁。

2.2 代码实现与逐行解析

下面是一个包含加密和解密功能的完整凯撒密码C语言实现。我会在关键代码后加上注释，解释每一部分的意图和注意事项。

#include <stdio.h> #include <ctype.h> // 用于 isalpha, isupper, islower 等字符判断函数 void caesar_cipher(char* text, int key, int encrypt) { // encrypt: 1 表示加密，0 表示解密 int i = 0; char c; // 如果解密，偏移量取反。因为解密是加密的逆过程。 if (!encrypt) { key = -key; } while (text[i] != '\0') { c = text[i]; // 只处理字母字符，空格、标点等保持不变，这是古典密码的常见特征 if (isalpha(c)) { // 确定基准点：大写字母以‘A’为基准，小写以‘a’为基准 char base = isupper(c) ? 'A' : 'a'; // 核心计算：先减去基准得到0-25的相对位置，加上密钥，再模26，最后加回基准。 // 注意：key可能为负数，而C语言的`%`运算符对负数取模的结果可能是负数。 // 因此采用 `(x % n + n) % n` 的技巧确保结果非负。 text[i] = ((c - base + key) % 26 + 26) % 26 + base; } i++; } } int main() { char text[1000]; int key; int choice; printf("输入文本 (明/密文): "); fgets(text, sizeof(text), stdin); // 使用fgets安全读取，避免缓冲区溢出 printf("输入密钥 (整数): "); scanf("%d", &key); printf("选择操作: 1. 加密 2. 解密\n"); scanf("%d", &choice); // 调用函数，encrypt参数为1表示加密，为0表示解密 caesar_cipher(text, key, choice == 1); printf("结果: %s\n", text); return 0; }

关键点解析与避坑指南：

字符处理函数<ctype.h>：使用isalpha(),isupper(),islower()等函数比手动比较ASCII码范围更安全、可读性更好。它能正确处理不同字符集的环境。
负数的模运算：这是最大的一个坑。C语言中，-1 % 26的结果可能是-1，而不是我们期望的25。因此，公式((c - base + key) % 26 + 26) % 26是确保结果始终在[0, 25]范围内的标准写法。先取模，加上模数，再取模，万无一失。
输入缓冲区清理：在连续使用scanf和fgets时，scanf会在输入流中留下一个换行符\n，导致接下来的fgets直接读取到一个空行。一个简单的解决方法是，在scanf后使用while(getchar() != '\n');来清空输入缓冲区。
密钥的有效范围：偏移量key对26取模后才有意义，因为偏移26位等于没有偏移。所以key=27和key=1的效果是一样的。在实际应用中，可以加入key = key % 26;来规范化密钥。

注意：这个凯撒密码的实现仅用于教学和兴趣实践。在任何需要真实安全性的场景中，绝对不要使用凯撒密码。它只需尝试25次（偏移1到25位）即可被轻易暴力破解。

3. RSA算法原理与C语言实现的挑战

如果说凯撒密码是密码学的“独轮车”，那RSA算法就是“航天飞机”。它由Ron Rivest, Adi Shamir, Leonard Adleman三位学者在1977年提出，是一种非对称加密算法。非对称意味着加密和解密使用不同的密钥：一个公开的公钥（Public Key）用于加密，一个私密的私钥（Private Key）用于解密。这种特性使得它完美解决了密钥分发难题，成为现代安全通信（如HTTPS、SSH）的基石。

3.1 RSA的核心数学原理

RSA的安全性建立在大数分解的困难性上。简单来说，给你两个很大的质数p和q，把它们相乘得到n很容易；但反过来，给你一个很大的n，让你找出它是哪两个质数相乘得到的，以目前计算机的计算能力，需要极其漫长的时间。

密钥生成步骤：

选择两个大质数：随机选择两个足够大的、不同的质数p和q。在教学中，我们使用小质数便于理解，如p=61, q=53。
计算模数n：n = p * q。n的长度就是密钥长度（如61*53=3233，相当于一个12位的密钥）。n是公开的。
计算欧拉函数φ(n)：φ(n) = (p-1) * (q-1)。这个值必须保密。例如，φ(3233) = 60 * 52 = 3120。
选择公钥指数e：选择一个整数e，满足1 < e < φ(n)，且e与φ(n)互质（即最大公约数gcd(e, φ(n)) = 1）。通常选择65537（0x10001），因为它二进制表示中1很少，计算效率高，且足够大。这里我们选e=17。
计算私钥指数d：d是e关于φ(n)的模逆元。即满足(d * e) % φ(n) = 1。计算d需要使用扩展欧几里得算法。对于e=17, φ(n)=3120，可以算出d=2753。

至此，我们得到：

公钥：(n=3233, e=17)
私钥：(n=3233, d=2753)

加密与解密过程：

加密：对于明文数字m（需小于n），计算密文c = m^e mod n。
解密：对于密文c，计算明文m = c^d mod n。

这里的mod n就是模运算，保证了结果始终在0到n-1之间。整个算法的魔力在于，用公钥(e, n)加密后，只有拥有私钥(d, n)的人才能解密。

3.2 C语言实现的关键难点与简化策略

用C语言完整实现一个工业级的RSA是极其复杂的工程，涉及到大数运算、随机质数生成、填充方案等。作为教学项目，我们必须做出合理简化，聚焦于理解核心流程。

我们面临的挑战：

大数问题：C语言的基本数据类型（如long long）能表示的范围有限（通常小于2^64）。而RSA密钥长度至少为1024位（约308位十进制数），远超此范围。我们需要实现大数（多精度整数）的加、减、乘、除、模幂运算。
质数生成：生成大质数需要高效的素性检测算法（如Miller-Rabin算法），而非简单的试除法。
模逆元计算：计算私钥d需要扩展欧几里得算法。
数据分块与填充：RSA只能加密比模数n小的数据。对于长文本，需要分块，并引入PKCS#1等填充方案来增强安全性。

教学实现策略：为了聚焦核心，我们的教学实现将做出以下限定：

使用很小的质数（如p=61, q=53），使得所有中间结果能用C语言的long long类型（或int64_t）容纳。
手动输入质数p和q，绕过复杂的质数生成。
加密单个小的整数（比如字符的ASCII码），暂不处理字符串分块和填充。
实现核心的模幂运算和模逆元计算函数。

这样，我们就能在可控的复杂度内，勾勒出RSA算法的完整骨架。

4. 教学级RSA算法的C语言实现

基于上述简化策略，我们来编写一个能够演示RSA密钥生成、加密和解密全流程的程序。这个程序不具实用性，但能让你透彻理解RSA的每一步计算。

4.1 辅助函数：模幂运算与模逆元

RSA的核心运算是模幂运算base^exp mod mod。直接先计算幂再取模，结果会巨大无比导致溢出。必须使用快速模幂算法（Fast Modular Exponentiation），其思想是将指数exp用二进制表示，通过平方和乘法来逐步计算。

#include <stdio.h> #include <stdint.h> // 使用 int64_t 确保位宽 // 快速模幂计算函数：计算 (base^exp) % mod long long mod_pow(long long base, long long exp, long long mod) { long long result = 1; base = base % mod; // 确保 base 小于 mod while (exp > 0) { // 如果 exp 是奇数，将当前的 base 乘入结果 if (exp % 2 == 1) { result = (result * base) % mod; } // 将 base 平方，并将 exp 减半（向下取整） base = (base * base) % mod; exp = exp / 2; } return result; }

接下来，我们需要计算私钥指数d，即e关于φ(n)的模逆元。这需要扩展欧几里得算法。该算法不仅能求出最大公约数gcd(a, b)，还能找到整数x和y，使得a*x + b*y = gcd(a, b)。当a与b互质时，gcd(a,b)=1，那么x就是a关于模b的逆元。

// 扩展欧几里得算法，返回 gcd(a, b)，并通过指针返回系数 x, y long long extended_gcd(long long a, long long b, long long *x, long long *y) { if (b == 0) { *x = 1; *y = 0; return a; } long long x1, y1; long long gcd = extended_gcd(b, a % b, &x1, &y1); // 根据递归结果更新 x 和 y *x = y1; *y = x1 - (a / b) * y1; return gcd; } // 计算 a 关于模 m 的模逆元，返回 -1 如果逆元不存在 long long mod_inverse(long long a, long long m) { long long x, y; long long gcd = extended_gcd(a, m, &x, &y); if (gcd != 1) { // a 和 m 不互质，逆元不存在 return -1; } else { // 确保结果为正数 return (x % m + m) % m; } }

4.2 完整的RSA流程演示代码

现在，我们将密钥生成、加密、解密串联起来。为了清晰，我们分步打印中间结果。

int main() { long long p, q, n, phi_n, e, d; long long plaintext, ciphertext, decrypted; // 步骤1：输入两个小质数（教学演示用） printf("=== RSA密钥生成演示（使用小整数）===\n"); printf("输入第一个质数 p (例如 61): "); scanf("%lld", &p); printf("输入第二个质数 q (例如 53): "); scanf("%lld", &q); // 步骤2：计算 n 和 φ(n) n = p * q; phi_n = (p - 1) * (q - 1); printf("\n计算得到:\n"); printf(" 模数 n = p * q = %lld\n", n); printf(" 欧拉函数 φ(n) = (p-1)*(q-1) = %lld\n", phi_n); // 步骤3：选择公钥指数 e (通常取65537，这里用小值演示) e = 17; // 确保 1 < e < φ(n) 且与 φ(n) 互质 printf("\n选择公钥指数 e = %lld (需与%lld互质)\n", e, phi_n); // 步骤4：计算私钥指数 d d = mod_inverse(e, phi_n); if (d == -1) { printf("错误：e 与 φ(n) 不互质，无法计算私钥。请重新选择 e。\n"); return 1; } printf("计算得到私钥指数 d = %lld\n", d); printf("\n=== 生成的密钥对 ===\n"); printf("公钥 (n, e): (%lld, %lld)\n", n, e); printf("私钥 (n, d): (%lld, %lld)\n", n, d); // 步骤5：加密演示 printf("\n=== 加密演示 ===\n"); printf("输入要加密的明文数字 (需小于 %lld): ", n); scanf("%lld", &plaintext); if (plaintext >= n) { printf("错误：明文必须小于模数 n。\n"); return 1; } ciphertext = mod_pow(plaintext, e, n); printf("密文 c = %lld^%lld mod %lld = %lld\n", plaintext, e, n, ciphertext); // 步骤6：解密演示 printf("\n=== 解密演示 ===\n"); decrypted = mod_pow(ciphertext, d, n); printf("解密结果 = %lld^%lld mod %lld = %lld\n", ciphertext, d, n, decrypted); if (decrypted == plaintext) { printf("成功！解密结果与原始明文一致。\n"); } else { printf("错误！解密失败。\n"); } return 0; }

运行示例与验证：

=== RSA密钥生成演示（使用小整数）=== 输入第一个质数 p (例如 61): 61 输入第二个质数 q (例如 53): 53 计算得到: 模数 n = p * q = 3233 欧拉函数 φ(n) = (p-1)*(q-1) = 3120 选择公钥指数 e = 17 (需与3120互质) 计算得到私钥指数 d = 2753 === 生成的密钥对 === 公钥 (n, e): (3233, 17) 私钥 (n, d): (3233, 2753) === 加密演示 === 输入要加密的明文数字 (需小于 3233): 123 密文 c = 123^17 mod 3233 = 855 === 解密演示 === 解密结果 = 855^2753 mod 3233 = 123 成功！解密结果与原始明文一致。

这个演示清晰地展示了RSA从密钥生成到加解密的完整数学过程。你可以尝试用公钥(3233, 17)加密一个数字，然后用私钥(3233, 2753)解密，验证其正确性。

5. 从教学到实践：RSA实现的深入问题与扩展

上面的教学代码帮你理解了RSA的“心脏”，但要构建一个哪怕只是能用的RSA工具，还有漫漫长路。这里梳理几个关键进阶问题，如果你想继续深入，这些是必须攻克的方向。

5.1 大数运算库的引入

这是最核心的一步。C语言标准库没有大数类型。你有几个选择：

自己实现：用数组或字符串表示大数，实现加减乘除、取模等运算。这是一个极好的学习项目，但工作量巨大且容易出错，性能也难优化。
使用第三方库：这是务实的选择。最著名的是GMP (GNU Multiple Precision Arithmetic Library)。它是一个高性能的多精度运算库，广泛用于密码学和数学计算。

使用GMP实现RSA模幂运算的简单示例：

#include <gmp.h> void rsa_encrypt_gmp(mpz_t cipher, const mpz_t plain, const mpz_t e, const mpz_t n) { mpz_powm(cipher, plain, e, n); // 计算 cipher = plain^e mod n }

GMP的一行mpz_powm函数，就安全高效地完成了我们之前需要自己写快速模幂算法的核心计算。在实际项目中，绝对推荐使用成熟的库。

5.2 数据分块、填充与编码

RSA不能直接加密字符串。一个完整的RSA加密文本流程是：

编码：将字符串（如“Hello”）转换为字节数据。
分块：根据密钥长度（如1024位，即128字节），确定每块数据的最大长度。还需要为填充留出空间（例如PKCS#1 v1.5填充需要至少11字节）。所以，对于1024位RSA，明文块可能被限制在117字节。
填充：对每个明文块应用填充方案（如PKCS#1 v1.5或OAEP）。填充不仅增加了随机性，防止相同的明文产生相同的密文，更重要的是提供了抵抗某些攻击的安全性保障。没有填充的“裸”RSA是不安全的。
整数转换：将填充后的字节块，当作一个大整数（mpz_t）。
模幂运算：使用公钥对这个整数进行加密。
字节转换：将得到的大整数密文转换回字节序列。
传输/存储：通常会将密文字节进行Base64编码，以便于在文本协议（如JSON、邮件）中传输。

解密则是逆过程。这个过程非常繁琐，但又是必须的。许多编程语言（如Python的cryptography库）的高级API帮你隐藏了这些细节，但在C语言层实现，你必须亲手处理。

5.3 密钥的存储与格式

生成的密钥对不能直接以数字形式打印。它们需要按照标准格式序列化。最常见的格式是PEM（Privacy-Enhanced Mail），它本质上是将DER编码的密钥进行Base64编码，并加上“-----BEGIN RSA PRIVATE KEY-----”这样的头尾标识。

例如，一个PEM格式的私钥开头是这样的：

-----BEGIN RSA PRIVATE KEY----- MIICXQIBAAKBgQC1...（Base64编码的数据）... -----END RSA PRIVATE KEY-----

处理PEM格式需要理解ASN.1（抽象语法标记一）和DER（可辨别编码规则），这又是一个复杂的领域。同样，使用现成的库（如OpenSSL）来读写这些格式是标准做法。

5.4 性能与安全考量

密钥长度：教学示例用了60位的n，瞬间可破。目前认为安全的RSA密钥长度至少为2048位，推荐使用3072位或4096位。
质数生成：p和q必须是随机生成的大质数。需要使用密码学安全的随机数生成器（CSPRNG）和像Miller-Rabin这样的概率性素性检测算法进行多次测试。
侧信道攻击：即使算法数学上安全，实现不当也会被攻破。例如，通过测量解密操作的时间（时序攻击），或者分析功耗变化（功耗分析），都可能泄露私钥信息。专业的密码库会包含对抗这些攻击的措施。

6. 常见问题与调试心得

在编写和调试这些加密代码时，我遇到过不少典型问题。这里列出来，希望能帮你节省时间。

凯撒密码相关：

问题：加密后的文本出现乱码或不可打印字符。
- 排查：99%是因为没有正确处理字母边界（‘z’或‘Z’的绕回）。检查你的模运算公式是否正确处理了负数情况。务必使用((c - base + key) % 26 + 26) % 26这个“双模”技巧。
问题：空格和标点被修改了。
- 排查：确认在if (isalpha(c))条件内才进行偏移操作，否则应直接保留原字符。
问题：解密结果不对。
- 排查：确保加密和解密使用的是同一个密钥。解密时，偏移量应是加密偏移量的负数（或等价地，用26减去加密偏移量）。检查你的encrypt标志逻辑是否正确。

RSA算法相关：

问题：计算私钥d时失败，返回-1。
- 排查：你选择的公钥指数e与欧拉函数φ(n)不互质。e必须是大于1且小于φ(n)的整数，并且gcd(e, φ(n)) = 1。常见的e=65537（0x10001）是一个质数，且很大，通常能满足条件。在小数字演示时，手动检查e和φ(n)是否有公因数。
问题：加密或解密结果错误，与预期不符。
- 排查步骤：
  1. 验证基础计算：手动或用计算器验证n = p * q和φ(n) = (p-1)*(q-1)是否正确。
  2. 验证模逆元：验证(e * d) % φ(n)是否等于1。这是私钥是否正确的最直接检验。
  3. 验证模幂运算：用小的数字单独测试你的mod_pow函数。例如，计算2^10 mod 1000是否等于24。
  4. 检查输入限制：确保你要加密的明文数字m严格小于模数n。如果m >= n，算法将无法正确解密。
问题：使用较大数字时程序崩溃或输出溢出。
- 排查：你遇到了整数溢出。long long类型在64位系统上通常只有64位，能表示的最大值约是9.22e18。一旦中间计算（比如base * base）超过这个范围，就会溢出。这是教学代码的固有局限。唯一的解决方案是引入大数运算库（如GMP）。
问题：如何加密一个字符串或文件？
- 回答：如上文第5.2节所述，你需要将整个过程流程化：字符串->字节->分块->填充->转换为大整数->RSA加密->转换为字节->Base64编码。反之亦然。强烈建议使用像OpenSSL这样的成熟库（RSA_public_encrypt,RSA_private_decrypt等函数）来完成这些工作，而不是自己从头再造轮子。自己实现用于学习原理很棒，但用于生产环境则风险极高。

最后，也是最重要的心得：密码学是一个极其专业的领域，细微的错误就会导致整个系统毫无安全性可言。学习实现这些经典算法，目的是为了深入理解其原理。当你需要在真实项目中应用加密功能时，最安全、最正确的做法永远是：使用经过广泛审计、长期维护的成熟密码学库，如OpenSSL, libsodium, 或你所使用语言的标准密码库（如Python的cryptography），并严格遵循其官方文档和最佳实践。

查看全文

http://www.jsqmd.com/news/1097762/