1. 项目概述从“凯撒”到“仿射”的密码学跃迁如果你接触过C并且对古典密码学有那么一点兴趣那么“仿射密码”这个名字你应该不陌生。它就像是凯撒密码的“威力加强版”不再满足于简单的字母平移而是引入了数学中的乘法和加法运算让加密过程多了一层“线性变换”的屏障。这个项目就是带你用C亲手实现一套完整的仿射密码加解密算法从原理到代码从加密到解密把整个过程掰开揉碎了讲清楚。我会附上可以直接编译运行的源码但更重要的是我会分享在实现过程中关于字符处理、模运算、密钥选择等环节那些教科书上不会写的“坑”和技巧。为什么是仿射密码因为它足够经典结构清晰是理解现代对称加密算法中“代换”和“模运算”思想的绝佳入门案例。同时它的实现又涉及C中字符串处理、函数封装、异常处理等多个基础但核心的知识点是一个综合性很强的练手项目。无论你是想巩固C基础还是对密码学原理感到好奇亦或是需要一个结构清晰的小项目来充实你的作品集这个内容都能满足你。2. 仿射密码的核心原理与数学基础拆解2.1 算法定义一个公式背后的世界仿射密码的加密和解密过程可以用两个简洁的数学公式来概括。但这简单的公式背后却藏着几个必须理解透彻的关键概念。加密公式为C (a * P b) mod m解密公式为P a_inv * (C - b) mod m这里的每一个符号都至关重要P 明文Plaintext中单个字母对应的数字例如A0, B1, ..., Z25。C 密文Ciphertext中单个字母对应的数字。a和b 加密密钥。a是乘法因子b是加法偏移量。m 字母表的大小。对于我们常用的26个英文字母m 26。mod m 模m运算确保结果始终落在0到m-1的范围内对应回字母表。a_inv 密钥a在模m下的乘法逆元。这是解密能否成功的关键。注意a的选择不是随意的。a必须与m互质即最大公约数gcd(a, m) 1。否则a在模m下没有乘法逆元解密过程将无法进行。对于m26这意味着a只能是1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25这些与26互质的数。2.2 为什么需要乘法逆元一个生活化的类比理解乘法逆元是掌握仿射密码的钥匙。你可以把它想象成一种“撤销”操作。在普通算术里如果你用数字3乘以一个数要“撤销”这个操作你会乘以1/3即3的倒数。但在模运算的世界里分数没有意义我们寻找的是一个整数使得(a * a_inv) mod m 1。例如当a3,m26时我们需要找到一个a_inv使得(3 * a_inv) mod 26 1。通过计算或后续我们将实现的扩展欧几里得算法可以找到a_inv 9因为(3 * 9) mod 26 27 mod 26 1。这样在解密时乘以a_inv(9)就抵消了加密时乘以a(3)的效果。2.3 处理大小写与特殊字符的务实思路教科书上的仿射密码通常只处理大写字母A-Z。但在实际应用中我们很可能遇到大小写混合的文本、空格、标点甚至中文。一个健壮的实现必须考虑这些情况。常见的策略有以下几种各有优劣统一转换策略将所有输入文本统一转换为大写或小写后再进行加密解密后再尝试恢复大小写如果原信息保留。这种方法简单但会丢失原始的大小写信息。分区处理策略分别建立大写字母表A-Z和小写字母表a-z的映射。加密时判断字符所属区间分别用对应的m26进行运算。这能保留大小写但加解密逻辑稍复杂。忽略非字母字符策略只加密字母字符数字、空格、标点等原样保留。这保证了密文的“可读性”虽然已是乱码和格式是最常见也最实用的做法。扩展字符集策略将字符集扩大到包含空格、标点、数字例如使用ASCII码的某个子集并相应增大m的值如128。但这会使得密钥a的选择更复杂需要与更大的m互质且密文可能包含不可打印字符实用性不高。在我们的实现中我将采用策略3因为它最贴近实际应用场景且能让我们聚焦于核心算法逻辑。策略1和2的代码我也会在注意事项中给出关键提示。3. C实现的关键模块设计与编码要点3.1 项目结构与头文件设计一个清晰的项目结构能让代码更易读、易维护。我们设计两个主要文件affine_cipher.h 声明所有函数和必要的常量。affine_cipher.cpp 实现所有函数。main.cpp 用于测试的主程序。首先来看头文件affine_cipher.h的设计// affine_cipher.h #ifndef AFFINE_CIPHER_H #define AFFINE_CIPHER_H #include string #include utility // for std::pair namespace AffineCipher { // 常量定义 const int MOD 26; // 字母表模数 // 函数声明 // 计算最大公约数 (Greatest Common Divisor) // 用于检查密钥a是否合法gcd(a, 26) 1 int gcd(int a, int b); // 使用扩展欧几里得算法求乘法逆元 // 返回一个pair first是gcd second是a在模m下的逆元如果存在 std::pairint, int extendedEuclid(int a, int m); // 计算a在模m下的乘法逆元如果不存在则抛出异常 int modInverse(int a, int m); // 核心加密函数 // 参数明文文本 乘法密钥a 加法密钥b // 返回密文字符串 std::string encrypt(const std::string plaintext, int a, int b); // 核心解密函数 // 参数密文字符串 乘法密钥a 加法密钥b // 返回明文字符串 std::string decrypt(const std::string ciphertext, int a, int b); // 辅助函数检查密钥a是否有效与MOD互质 bool isValidKeyA(int a); } // namespace AffineCipher #endif // AFFINE_CIPHER_H使用命名空间AffineCipher将我们的功能封装起来避免全局命名污染。std::pair用于从扩展欧几里得算法中同时返回最大公约数和逆元。3.2 核心算法函数的逐步实现接下来是重头戏在affine_cipher.cpp中实现这些函数。3.2.1 基础数学工具函数任何加密系统的可靠性都建立在正确的数学基础上。我们首先实现两个关键数学函数。// affine_cipher.cpp #include affine_cipher.h #include stdexcept // for std::invalid_argument #include cctype // for std::isalpha, std::toupper namespace AffineCipher { // 计算最大公约数 - 辗转相除法欧几里得算法 int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; } // 扩展欧几里得算法 // 求解 ax my gcd(a, m) 中的 x, y, gcd // 当 gcd(a,m)1 时x 就是 a 模 m 的乘法逆元 std::pairint, int extendedEuclid(int a, int m) { if (m 0) { return {1, 0}; // gcd a, x1, y0 } auto [x1, y1] extendedEuclid(m, a % m); int x y1; int y x1 - (a / m) * y1; return {x, y}; } // 计算模逆元 int modInverse(int a, int m) { auto [x, gcd] extendedEuclid(a, m); // 确保得到的是正数解且gcd必须为1逆元才存在 if (gcd ! 1) { throw std::invalid_argument(乘法密钥a在模 std::to_string(m) 下没有逆元。请确保a与模数互质。); } // 调整结果为正数 int inverse (x % m m) % m; return inverse; } // 密钥有效性检查 bool isValidKeyA(int a) { return gcd(a, MOD) 1; }这里有几个实操心得递归与迭代extendedEuclid我用递归实现代码清晰体现了数学公式。对于性能极度敏感的场景可以改为迭代但对此项目递归完全足够。逆元的正数化extendedEuclid返回的x可能是负数。(x % m m) % m这个技巧能确保我们得到的是一个在[0, m-1]范围内的正逆元。异常处理在modInverse中如果gcd ! 1我们抛出std::invalid_argument异常。这是一种清晰的错误传递方式比返回一个特殊值如-1更好能强制调用者处理错误情况。3.2.2 加密函数实现加密函数需要遍历明文字符串对每个字母字符应用加密公式。std::string encrypt(const std::string plaintext, int a, int b) { // 1. 密钥有效性验证 if (!isValidKeyA(a)) { throw std::invalid_argument(无效的乘法密钥a std::to_string(a) 。a必须与 std::to_string(MOD) 互质。); } std::string ciphertext; ciphertext.reserve(plaintext.length()); // 预分配空间提升性能 for (char ch : plaintext) { if (std::isalpha(static_castunsigned char(ch))) { // 只处理字母字符 // 统一转换为大写字母的索引0-25 char upperCh std::toupper(static_castunsigned char(ch)); int P upperCh - A; // 明文字母对应的数字 // 应用仿射加密公式: C (a*P b) mod 26 int C (a * P b) % MOD; // 处理C语言中负数取模的问题C11后a%b当a为负时结果为负 // 但我们这里的a, P, b都是非负所以C也是非负。为健壮性可以加 if (C 0) C MOD; // 将数字转换回大写字母 char encryptedCh static_castchar(A C); // 如果原字符是小写密文也输出小写可选这里统一输出大写 // 为了简单和一致性我们密文统一用大写字母表示 ciphertext.push_back(encryptedCh); } else { // 非字母字符原样保留 ciphertext.push_back(ch); } } return ciphertext; }关键点解析std::isalpha和std::toupper的参数需要转换为unsigned char这是为了正确处理可能为负的char值在一些编译器上char默认为signed char避免未定义行为。ciphertext.reserve(plaintext.length())这是一个重要的性能优化。它预先为ciphertext字符串分配足够的内存避免在push_back过程中多次重新分配和拷贝对于长文本加密效率提升明显。大小写策略这里我选择了“加密过程统一转大写密文输出大写”的方式。这简化了逻辑。如果你希望密文大小写与原明文对应就需要在加密前记录原字符的大小写状态并在加密后恢复。这会增加一个状态变量稍微复杂一点。3.2.3 解密函数实现解密是加密的逆过程但需要用到之前计算的乘法逆元。std::string decrypt(const std::string ciphertext, int a, int b) { // 1. 密钥有效性验证同样需要 if (!isValidKeyA(a)) { throw std::invalid_argument(无效的乘法密钥a std::to_string(a) 。解密也需要有效的密钥a。); } // 2. 计算乘法逆元 a_inv int a_inv modInverse(a, MOD); // 这里可能抛出异常 std::string plaintext; plaintext.reserve(ciphertext.length()); for (char ch : ciphertext) { if (std::isalpha(static_castunsigned char(ch))) { // 同样我们假设密文字母是大写的根据我们的加密函数 char upperCh std::toupper(static_castunsigned char(ch)); int C upperCh - A; // 密文字母对应的数字 // 应用仿射解密公式: P a_inv * (C - b) mod 26 // 注意C - b 可能为负数所以先加MOD再取模确保非负 int P (a_inv * (C - b)) % MOD; if (P 0) P MOD; // 确保结果为非负 char decryptedCh static_castchar(A P); // 这里同样解密后统一输出为大写字母。 // 如果加密时保留了大小写信息这里需要复杂逻辑来恢复。 plaintext.push_back(decryptedCh); } else { // 非字母字符原样保留 plaintext.push_back(ch); } } return plaintext; } }解密中的坑(C - b) % MOD在C中如果(C-b)是负数取模结果也是负数。这会导致后续计算错误。因此必须先进行if (P 0) P MOD;调整。更安全的写法是int P (a_inv * ((C - b MOD) % MOD)) % MOD;先处理(C-b)可能为负的情况。解密必须使用与加密完全相同的密钥a和b并且a必须有效有逆元。modInverse函数已经包含了有效性检查。4. 完整源码整合与测试用例4.1 主程序测试与交互将以上模块组合并编写一个main.cpp来测试我们的仿射密码库。// main.cpp #include iostream #include string #include affine_cipher.h void runTest(const std::string testName, const std::string plaintext, int a, int b) { std::cout \n 测试: testName std::endl; std::cout 明文: \ plaintext \ std::endl; std::cout 密钥: a a , b b std::endl; try { std::string ciphertext AffineCipher::encrypt(plaintext, a, b); std::cout 密文: \ ciphertext \ std::endl; std::string decryptedText AffineCipher::decrypt(ciphertext, a, b); std::cout 解密: \ decryptedText \ std::endl; if (decryptedText plaintext) { std::cout 结果: 加解密成功 std::endl; } else { std::cout 结果: 错误解密文本与原文不符。 std::endl; } } catch (const std::invalid_argument e) { std::cout 错误: e.what() std::endl; } } int main() { // 测试1经典示例 runTest(经典示例全大写, HELLO WORLD, 5, 8); // 常用有效密钥a5, b8 // 测试2包含空格和标点 runTest(混合文本, Hello, C Programmer! 2024, 7, 10); // 测试3无效密钥测试 runTest(无效密钥a偶数, TEST, 2, 3); // a2与26不互质应抛出异常 // 测试4长文本测试 runTest(长文本, The Affine Cipher is a type of monoalphabetic substitution cipher., 9, 13); // 测试5边界测试单个字符 runTest(边界A/Z, AZ, 11, 4); // 交互式测试 std::cout \n\n 交互式加解密 std::endl; std::string inputText; int a, b; char mode; std::cout 输入模式 (E)ncrypt / (D)ecrypt: ; std::cin mode; std::cin.ignore(); // 清除输入缓冲区中的换行符 std::cout 输入文本: ; std::getline(std::cin, inputText); std::cout 输入密钥a (必须与26互质): ; std::cin a; std::cout 输入密钥b (0-25): ; std::cin b; try { if (mode E || mode e) { std::string result AffineCipher::encrypt(inputText, a, b); std::cout 加密结果: result std::endl; } else if (mode D || mode d) { std::string result AffineCipher::decrypt(inputText, a, b); std::cout 解密结果: result std::endl; } else { std::cout 未知模式。 std::endl; } } catch (const std::invalid_argument e) { std::cout 操作失败: e.what() std::endl; } return 0; }4.2 编译与运行你可以使用任何标准的C编译器来编译这个项目。例如使用gg -stdc11 -o affine_cipher main.cpp affine_cipher.cpp ./affine_cipher-stdc11标志确保支持我们使用的std::to_string等功能。运行程序你会看到预定义的测试用例输出并可以进入交互模式进行自定义加解密。5. 深入探讨安全性、局限性与扩展方向5.1 仿射密码的安全性究竟如何坦率地说仿射密码在现代计算机面前非常脆弱绝对不应用于任何真实的敏感信息加密。它的安全性弱点非常明显密钥空间极小有效密钥a只有12种选择与26互质的数密钥b有26种选择。总的密钥空间仅为12 * 26 312。对于计算机来说暴力破解穷举所有密钥是瞬间完成的事情。单表替换它是一种单表替换密码即一个明文字母始终被替换成同一个密文字母。这保留了原始语言的统计特征如字母频率。通过频率分析英文中E、T、A出现频率最高即使不知道密钥也能很容易地被破译。已知明文攻击脆弱如果攻击者知道哪怕一小段明文和对应的密文就可以直接解出密钥a和b。因为对于两个不同的字母可以建立一个二元一次方程组求解。所以这个项目的价值在于教育和练手而非实用加密。5.2 常见问题与调试技巧实录在实际编码和测试中你可能会遇到以下问题问题1解密出来的文本是乱码或者与原文不符。排查步骤检查密钥一致性确保加密和解密使用的是完全相同的a和b。验证密钥a的有效性在加密和解密前确认gcd(a, 26) 1。可以在main函数里加一条检查语句。检查模逆元计算在decrypt函数内部打印或调试查看a_inv的值是否正确。例如a5时a_inv应该是21因为5*21105, 105 mod 26 1。检查负数取模这是最常见的坑。确保在解密公式a_inv * (C - b) mod 26中(C - b)为负数时通过(C - b MOD) % MOD或if (value 0) value MOD的方式将其转为正数。检查字符处理逻辑确认你的加密和解密函数对大小写和非字母字符的处理逻辑是完全互逆的。比如加密时转成了大写解密时是否也按大写处理问题2程序抛出“没有乘法逆元”的异常。原因你使用的密钥a与26不互质如2, 4, 6, 13等。解决从有效密钥列表{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}中选择一个。问题3我想加密包含空格和小写字母的文本并希望密文也保留格式。方案修改encrypt和decrypt函数。在遍历字符时用std::islower和std::isupper判断原字符大小写并记录一个bool isLower标志。加密/解密计算时统一使用大写字母的索引0-25。在输出结果字符时根据记录的标志使用‘a’ C或‘A’ C。非字母字符原样输出。5.3 项目扩展与优化思路如果你已经掌握了基础实现可以尝试以下扩展让项目更具挑战性和实用性支持扩展字符集将字符集扩大到包含数字和常见标点如A-Z, a-z, 0-9, 空格逗号句号。此时m不再是26可能是64或更大。你需要重新定义字符到数字的映射表。编写函数生成与新的m互质的密钥a的列表。注意随着m增大计算模逆元的复杂度也会增加需要确保extendedEuclid函数能正确处理。实现文件加密从控制台输入输出扩展到文件操作。使用fstream库读取文本文件内容加密后写入新文件反之亦然。这涉及到内存管理对于大文件和编码问题。增加加密模式实现块加密Block Cipher模式的思想例如ECB电子密码本或CBC密码块链接。虽然仿射密码本身很弱但结合模式可以学习分组密码的工作方式。例如将文本分成固定大小的块如8个字符对每个块进行独立的仿射加密需要将块视为一个数字或向量进行处理这更复杂。制作图形界面GUI使用Qt、wxWidgets或甚至简单的Web前端通过Emscripten将C编译成WebAssembly为你的加解密程序制作一个可视化界面提升用户体验。性能分析与优化对于超长文本如整本书分析当前实现的性能瓶颈。是modInverse的递归调用还是字符串的频繁拼接尝试使用更高效的算法如迭代版扩展欧几里得和性能分析工具如gprof进行优化。实现这个仿射密码项目就像完成了一次微型的密码学工程演练。从数学原理推导到C代码的严谨实现再到边界情况的处理和错误排查每一个环节都考验着编程的基本功和逻辑思维。最重要的是通过亲手实现你会深刻理解“为什么这样的密码不安全”这种理解远比死记硬背书本知识要牢固得多。代码就在那里你可以随意修改、扩展、破坏再修复这才是学习编程和密码学最有效的方式。
