应用密码学实验实战：从AES到RSA的完整实现与排错指南

简介本资源是吉林大学应用密码学课程配套的四次综合性实验实现代码与文档面向密码学初学者、信息安全专业学生及密码算法实践者聚焦分组密码设计、公钥密码实现、混合加密系统构建与盲签名协议落地等核心能力训练。压缩包共27个文件含5个C源码.cpp、5个可执行程序.exe、7个编译中间文件.o及4个Code::Blocks项目配置文件.cfp/.cfpg辅以1份Word实验说明文档和1份文本说明总大小1.02MB结构清晰便于分模块编译与调试。已有1731人学习下载。资源完整覆盖Feistel结构128位分组密码含LFSR轮函数、基于NTL库的RSA密钥生成/加解密、数字信封OFB模式会话密钥封装及Chaum盲签名四大实验要求所有算法均提供可运行工程含输入输出验证逻辑适合直接编译运行、理解密码协议交互流程与工程实现细节。 聊到“应用密码学”实验很多人第一反应就是几个加密算法的代码实现。但真坐在电脑前开始写代码时才会发现书上的公式和能跑的程序之间隔着好大一段距离。吉林大学这套应用密码学实验覆盖面比较完整从古典密码一直延伸到RSA签名认真做完一轮对对称加密、非对称加密、哈希函数这些核心概念的理解会和只看书完全不一样。这篇文章不是标准答案只是把我自己跑通整套实验的思路、实现细节和踩过的坑整理出来。如果你正在做类似的应用密码学实验或者想自己动手把教材里的算法真正实现一遍这份记录应该能帮你少走不少弯路。1. 实验总体设计与模块拆解1.1 实验到底在考察什么能力先聊聊这门实验的定位。应用密码学实验不是密码学理论的重复考卷它考察的点其实很具体而且和以后做安全相关的工程开发直接相关。第一层是算法理解能力。你能不能把一个算法从文字描述转换成流程框图再翻译成可执行代码。比如AES里的字节代换教材上写的是“在有限域GF(2^8)上求乘法逆元再做仿射变换”这句话看着很短但真要把S盒自己生成出来你得先搞清楚GF(2^8)上的乘法规则到底是怎么回事。很多同学直接抄一张标准S盒表然后从表里查这当然也能跑通但实验报告里如果连S盒怎么生成都写不出来分数肯定不会高。第二层是工程实现能力。大数运算、字节序、填充方式、分组模式这些细节教材上一笔带过但真正动手实现的时候全是坑。比如RSA里的模幂运算如果用C语言自带的 int 类型算到一半就溢出了必须自己实现大数乘法或者用现成的大数库。再比如AES的CBC模式需要对明文做PKCS#7填充填充规则写错一个字节解密出来的结果就是乱码。第三层是验证与排错能力。密码算法本身是个黑盒你没法通过“看”来确认S盒写对了没有只能通过测试向量来验证。我见过不少同学卡在一个小错误上比如行移位方向反了、列混合矩阵某个系数写错排查一整天都对不上结果。这时候如果会用OpenSSL命令行做交叉验证问题就能很快定位。所以这门实验表面上是“把算法实现一遍”实际上是逼着你把“读论文—写代码—验证结果—排查问题”这套工程循环完整走一遍。这也是为什么很多公司在招聘安全方向的应届生时会特别看重这类课程的实验项目因为它能直接体现一个人的动手能力和排查能力。1.2 环境与工具选型选对工具实验能省一半时间。我自己的配置是这样的主语言用CIDE用Visual Studio验证阶段用Python交叉验证用OpenSSL命令行。这个组合对我来说是最顺手的下面详细说理由。C的好处是贴近底层字节操作、数组、指针都很好用而且不用装一堆运行时环境。做AES实验时一个uint8_t数组就能表示状态矩阵做行移位时直接用循环移位非常直观。缺点是做RSA时如果不用大数库得自己实现大数运算这部分工作量不小。所以做RSA实验时我建议分成两步走先用C写小素数版本的RSA验证整个流程跑得通再用Python或者直接调用OpenSSL来演示大素数版本的效果。这样既展示了原理又节约了时间。Python的好处是自带大整数a ** b % n一行代码就能完成模幂运算做Miller-Rabin素性检测也很方便。缺点是性能比C差很多而且Python的字节处理有时候会有坑比如bytes和str混用会导致编码问题。所以Python我只用来做快速验证不用于最终交付。OpenSSL命令行是调试利器这个后面专门说。强烈建议在实验开始前先装好OpenSSL并熟悉几个常用命令比如openssl enc做AES加解密、openssl genrsa生成RSA密钥、openssl rsa查看密钥信息等。很多同学写代码写到最后结果对不上又不知道怎么排查其实就是缺一个“标准答案”。OpenSSL命令输出的结果就是你的标准答案。2. 对称密码实验AES的完整实现思路2.1 为什么拿AES练手最合适对称密码这部分不同学校的实验要求不一样有的让做DES有的让做AES也有两个都做的。如果你可以自己选我推荐选AES-128原因有三个。第一AES是目前实际应用中使用最广泛的分组加密算法对于“应用密码学”这门课来说做AES比做DES更有现实意义。第二AES的结构非常规整字节代换、行移位、列混合、轮密钥加四个操作循环十轮每一轮都有明确的计算流程很适合用来展示算法的工程实现。第三AES的S盒和列混合都是基于GF(2^8)的运算做完这个实验你对有限域的理解会有一个质的提升这个知识后面学RSA、椭圆曲线都能用上。如果实验要求做DES我也有个提醒DES的初始置换IP和逆置换IP各有一张64位查表这两张表非常容易抄错而且S盒从6位映射到4位的过程也很容易搞混。DES的坑主要不在算法理解上而在细节准确性上做的时候一定要仔细核对教材的表格。2.2 一步步拆解AES核心步骤AES-128的流程不长密钥扩展生成11个轮密钥初始轮密钥加然后进行10轮迭代。前9轮是字节代换、行移位、列混合、轮密钥加最后一轮跳过列混合。结构清晰但是每一个小步骤都有容易写错的地方。先看字节代换。S盒可以用查表的方式实现教材上都附有S盒表直接抄下来查就行。但如果你想让实验报告更有分量我建议用代码生成S盒。生成步骤是先求出每个字节在GF(2^8)上的乘法逆元再做仿射变换。求乘法逆元可以用扩展欧几里得算法也可以用指数表加对数表的方式。仿射变换要注意矩阵乘法和加法都是在GF(2)上进行的加法就是异或。列混合是第二个容易出错的点。列混合的本质是状态矩阵的每一列和一个固定矩阵在GF(2^8)上做矩阵乘法。这里需要实现两个乘法乘2和乘3。乘2的规则是左移一位如果最高位是1再异或0x1B乘3等于乘2再加原数。我写了一个简单的实现uint8_t xtime(uint8_t x) { uint8_t res x 1; if (x 0x80) res ^ 0x1B; return res; } uint8_t gmul(uint8_t a, uint8_t b) { uint8_t res 0; while (b) { if (b 1) res ^ a; a xtime(a); b 1; } return res; }这一段代码基本就是列混合的核心。先用xtime处理乘2然后gmul通过循环处理任意的乘数。很多同学容易在xtime的异或条件上写错只有左移前最高位是1时才需要异或0x1B这个条件一定要检查清楚否则加密到一半就开始对不上了。密钥扩展也有一个常见的坑。AES-128需要10轮扩展每轮扩展4个字每个字4字节。扩展的时候每轮的第一个字需要先循环左移一个字节再对每个字节做S盒代换然后异或轮常数Rcon。这个Rcon每一轮的值是不同的第一轮是0x01第二轮是0x02之后依次翻倍超过0x80后同样要走GF(2^8)上的x乘法。密钥扩展的公式不复杂但因为要循环很多轮代码写起来容易在索引上出错建议写完以后用标准密钥和标准扩展结果对比一遍。整个AES写完之后一定要用FIPS-197附录里的测试向量做验证。我自己第一次写完以后恰好是S盒生成时仿射变换的矩阵顺序搞反了加密结果从第一轮就不对当时排查了很久。后来学乖了每完成一个步骤就打印中间状态和标准向量对比这样能快速定位是哪一步出了问题。2.3 分组模式与填充方式的坑AES本身是分组算法一次处理16字节。如果明文长度不是16的倍数就需要填充。实验里最常见的填充方式是PKCS#7规则很简单缺几个字节就填几个几。比如明文最后一块只剩5个字节需要补11个字节那就补11个0x0B如果明文恰好是16的倍数那还要额外补一整块16个0x10。这个“恰好是16的倍数也要补一整块”的规则是最容易被忽略的。不少同学写完代码后测试短字符串都可以一测恰好16字节的字符串就解密失败就是因为填充逻辑写错了。解密的时候要取密文最后一个字节的值假设是k则从尾部去掉最后k个字节。注意这里要判断合法性比如k不能大于16、不能等于0否则就是解密出了问题。分组模式我建议优先实现CBC模式。ECB模式虽然简单但相同的明文块会得到相同的密文块完全不隐藏数据模式在实验报告里如果只做ECB老师可能会追问一句“为什么不用CBC”。CBC的实现也不复杂每个明文块先和上一个密文块异或再做AES加密解密方向反过来先解密再做异或。第一块的“上一个密文块”就是初始化向量IVIV在加解密两端必须保持一致实验报告里要写明IV是怎么生成和传递的。文件加密的场景下IV一般用一个随机生成的16字节和密文一起传给接收方。实验里为了简化可以用固定IV但报告中要说明这只是一个演示用途真实场景下IV必须随机。这些细节看起来不影响代码跑通但能让你在答辩环节多几句专业表达。3. RSA与现代密码学实验实现3.1 RSA的数学基础与密钥生成RSA实验是另一座大山。它的数学流程其实不长选两个大素数p和q计算npq和欧拉函数φ(n)(p-1)(q-1)选一个与φ(n)互素的公钥指数e再用扩展欧几里得算法计算出满足ed≡1(mod φ(n))的私钥指数d公钥是(e,n)私钥是(d,n)。看起来简单但真正动手做的时候第一个问题就是p和q从哪来当然不能随便选一个整数当素数必须先用素性检测验证。实验里一般用的是Miller-Rabin算法这是一个概率性素性检测算法基本思想是利用费马小定理的逆否命题如果n是素数则对任意a都有a^(n-1)≡1(mod n)。随机取若干个底数a如果某个a不满足这个条件n就是合数如果多个a都满足n就大概率是素数。Miller-Rabin的轮数选多少合适一般建议40轮出错的概率低于2^(-40)这个量级在实际工程中已经可以忽略了。我自己的实现里先用小素数表2、3、5、7、11、13……做一次快速排除再跑Miller-Rabin这样能节约不少时间。如果实验不要求自己实现大数运算在Python里直接生成1024位素数也就在几秒到几十秒的量级。选公钥指数e的时候最常见的取值是65537也就是0x10001。为什么不选3因为3虽然计算效率高但它的安全性有隐患尤其在使用不当的填充方案时更容易受到攻击。65537是素数且和很多φ(n)都互素二进制表示里只有两个1计算时相对高效所以是现代RSA的标准选择。3.2 大数运算的实现技巧RSA实验里最让人头疼的不是算法而是“数的长度”。教材里做例题时p和q都是很小的数n不过几十用计算器都能算。但真实的RSA要求n至少1024位p和q都是512位的大素数这在C语言里用unsigned long long也远远放不下。解决大数问题的路子有三条。第一条是直接用现成的大数库比如GMP或者OpenSSL的BN库。好处是省事一行代码搞定乘法取模坏处是如果你整个RSA实验都依赖库那就没有达到“理解算法”的目的实验报告也不太好写。第二条是自研大数类用vectoruint32_t或者vectoruint64_t来存储一个大数自己实现加减乘除和模幂运算。这个工作量非常大但如果能完成对理解计算机底层运算会有很大帮助。我在做RSA实验时写了一个简化版的大数类只实现了自己需要的乘法和模幂运算配合快速幂算法能处理64位以内的数相乘。这个“半自研”的方案对于实验来说最合适。第三条建议是如果时间实在紧张可以用Python。Python自带大整数底层的运算已经帮你处理好了。你可以用Python写一版完整的RSA演示然后在小素数域上用C实现一遍同样的逻辑两者对比验证。这样既能说明你理解了RSA的流程又能展示大数场景下的完整实现。模幂运算是RSA中最核心的计算。无论是加密还是解密本质上都是要做形如base^exp mod n的计算。如果用最朴素的方法循环乘指数稍微大一点就会非常慢。正确的方法是“平方-乘”算法也叫快速幂取模。核心思路是把指数按二进制展开遇到1就乘上当前的底数每一步都取模防止溢出。C里的简化实现长这样uint64_t mod_pow(uint64_t base, uint64_t exp, uint64_t mod) { uint64_t res 1 % mod; base % mod; while (exp 0) { if (exp 1) res (res * base) % mod; base (base * base) % mod; exp 1; } return res; }这个函数在exp很大时依然很快因为它把指数降到了log2(exp)次乘法。如果做大数版本只需要把uint64_t替换成大数类逻辑完全一样。3.3 带签名功能的RSA应用很多实验要求不只是做RSA加解密还要求实现数字签名。签名和加密看着都用同样一套密钥运算但两者本质不同。加密是公钥加密、私钥解密目的是保密签名是私钥运算、公钥验证目的是认证和防篡改。RSA签名流程是先对消息计算哈希值比如SHA-256得到32字节摘要然后用私钥对这32字节做模幂运算得到的值就是签名。验签时用公钥对签名做模幂运算得到解密后的摘要再对原始消息重新计算哈希两个值一致就说明签名有效。为什么不能直接对整条消息做签名因为RSA是确定性算法直接对消息做幂运算会把消息内容暴露出去而且长消息分块处理很容易引入复杂度。先哈希再签名是工程界普遍采用的标准做法它既提高了效率又让签名结果只和摘要相关不暴露原文。实验报告中可以再补充一个增强点中国剩余定理CRT加速。私钥解密时可以不用直接做c^d mod n而是分别计算m1 c^dp mod p和m2 c^dq mod q其中dp d mod (p-1)、dq d mod (q-1)最后用CRT组合出明文。这个优化能让解密速度提升大约4倍市面上很多RSA实现都用了这个技巧。如果实验做到这个深度答辩时老师一般都会眼前一亮。4. 实验中容易踩的坑与排查方法4.1 字符编码与二进制的坑密码算法处理的是二进制数据和普通字符串完全不同。这一点不亲自动手写一次代码很容易忽略。我第一次写AES时用char数组保存密文然后直接用strlen获取长度结果加密到一半就发现密文长度不对。原因很简单密文是二进制字节可能包含0x00而char数组的空字符就是\0strlen读到0x00就停了。解决方法是长度要自己保存不要依赖字符串函数。还有一种方式是先把密文转成十六进制字符串或者Base64字符串再存文件但要注意转码和解码过程中不要引入额外的字节。还有一个和中文有关的坑。如果明文包含中文比如“你好世界”在Windows环境下如果不注意编码用的是GBK编码而在Linux或者macOS下默认UTF-8两端的字节序列不同加解密会出问题。建议实验代码里统一在加密前把字符串转为UTF-8字节序列解密后再按UTF-8解码这样跨平台才不会出乱码。如果实验内容只是ASCII字符串那基本不会遇到这个问题但提前处理了会比较稳妥。输出密文到终端时直接打印二进制字节会出现一堆乱码这是正常现象。建议用十六进制输出方式比如C里可以这样for (int i 0; i len; i) { printf(%02x, data[i]); } printf(\n);这样能看到完整的密文内容方便对比和保存。4.2 调试与验证方法单测不够还要有一个“标准答案”来做交叉验证。最可靠的方案就是用OpenSSL命令行。比如你用C实现了一个AES-128-CBC加密想验证结果对不对可以用下面的命令生成标准密文echo -n hello | openssl enc -aes-128-cbc -K 00112233445566778899aabbccddeeff -iv 000102030405060708090a0b0c0d0e0f | xxd这里的-K是128位密钥的十六进制表示-iv是16字节初始化向量。如果你的C代码和这条命令的密钥、IV、明文完全一致那么输出的十六进制密文也应该完全一致。这个方法对AES的ECB、CBC模式都适用。RSA的验证可以用openssl genrsa生成密钥用openssl pkeyutl -encrypt做加密再拿你的代码来解密。如果你的代码实现的是标准RSA那应该能正确解密OpenSSL生成的密文。注意OpenSSL的RSA加密默认使用PKCS#1 v1.5填充如果你在代码里做明文直接模幂运算两者结果对不上是正常的因为OpenSSL对明文做了填充处理。搞清楚这个区别本身也是实验的收获之一。除了OpenSSL还可以用Python的cryptography库或者pycryptodome库做双向验证。我的习惯是先用Python手写一遍简化逻辑得到一份可以调用的参考实现再用C正式实现两个版本输出对比。这样排查问题时只需要在两边都打上中间值就能精确到步骤。4.3 高频问题速查表下面是我在做实验时遇到过的还有听同学提到过的典型问题整理成了一张速查表问题现象可能原因排查思路与解决办法AES加解密结果不一致S盒或逆S盒不配对、轮密钥数量不正确、密钥扩展逻辑错误拆开每轮打印中间状态和标准向量对比检查S盒是否是FSK里那张表密文输出到终端显示乱码二进制字节被当成文本输出不要直接输出原始字节转成十六进制或Base64字符串解密后末尾有多余字符PKCS#7填充解析错误检查去掉填充的字节数是否正确如果明文恰好是16倍数确认是否补了完整一块RSA解密后得到的是乱码模幂运算溢出、密钥长度不足、数据没有按块处理确认大数运算是否溢出检查明文长度是否大于n的字节长度密钥生成时反复找不到素数Miller-Rabin轮数太少或随机数范围不对增加轮数到40先用小素数表排除合数注意随机数是偶数时直接跳过CBC模式第一块解密正确后续全错IV在解密端没有正确使用或异或顺序写反检查解密时第一块的异或对象是不是IV后续块是不是异或上一块密文文件加密后无法打开加密的是整个文件解密端不知道原文件长度在文件头部记录原始长度或填充信息解密后根据PKCS#7规则去除填充这些问题大多数不是算法理解问题而是细节问题。排查的时候不要慌逐层打印中间值逐项对比标准结果很快就能定位到具体是哪一环出了问题。最后再分享一个自己摸索出来的小技巧在做AES实验时我给每个核心步骤都写了一个独立的测试函数比如test_sub_bytes()、test_shift_rows()、test_mix_columns()、test_key_expansion()每个函数传入一个标准输入断言输出是否等于标准输出。这样一旦整个算法出错不需要从第一个字节开始查直接运行这一系列单元测试跑到哪一个断言失败就说明哪一步实现有问题。这个小习惯帮我节省了大量调Bug时间后来做其他复杂项目时我也一直保持这个做法。本文还有配套的精品资源点击获取