1. 先说清楚DES到底是个什么东西你在任何一本密码学的教材里都会遇到DESData Encryption Standard我也一样。第一次学它的时候我最大的感受是“晕”又是置换表又是S盒又是16轮循环一张接一张的表怎么看都像在看天书。后来我自己一行一行实现了整个算法才真正明白它为什么被人称作现代分组密码的“活化石”——它的每一张表、每一步操作都暗含当年设计者的深思熟虑。DES是一个对称分组密码算法。所谓分组密码就是把明文切成固定长度的小块一块一块独立加密。DES的块长是64位密钥名义上是64位但真正参与运算的只有56位因为每个字节的第8位是奇偶校验位不参与加密逻辑。加密时64位明文块经过初始置换拆成左右两半各32位再经过16轮迭代最后通过逆置换得到64位密文块。解密则是用完全相同的结构、只把子密钥顺序反过来重跑一遍。这种结构有个专门的名字叫Feistel网络后面几乎所有经典分组密码包括Blowfish、Twofish都继承了它的衣钵。这不是一篇罗列知识点的科普而是想带着你把DES的“内脏”掏出来一块一块看明白为什么要有Feistel结构IP置换那张表到底在干什么密钥是怎么从一把主密钥变出16把子密钥的S盒为什么是DES的灵魂我会用一张张展开的表、一段段可以照着算的数据告诉你这个“退休”的算法到底是怎么运转的。适合谁来读呢如果你是第一次接触分组密码建议从头到尾慢慢看保证能建立完整的脑图。如果你是想自己写一个DES实现或者要在竞赛、课程设计、CTF里手搓代码那可以直接跳到轮函数和实操部分非常有帮助。哪怕你只想知道“AES之前人们用的是什么”这篇文章也能给你一份足够清晰的答案。2. 整体结构Feistel网络与16轮大循环先看宏观结构别钻进细节里。DES加密一个64位块分四步走输入64位明文 - 初始置换IP - 16轮Feistel迭代 - 交换左右32位 - 逆置换IP^-1 - 输出64位密文其中“16轮Feistel迭代”是核心。每一轮做的事非常统一把当前状态拆成左半L和右半R然后右半通过轮函数F加工与左半异或再把两个半区互换位置进入下一轮。用公式表达就是L_i R_{i-1}R_i L_{i-1} ⊕ F(R_{i-1}, K_i)这里K_i是第i轮的子密钥每轮都用不同的48位子密钥而子密钥全部由同一个56位主密钥派生而来。2.1 为什么费劲搞Feistel结构Feistel结构最精妙的一点是它天然可逆。加密的时候你用某个顺序放子密钥解密的时候只要把子密钥顺序倒过来、把加密和解密的代码写成一模一样就能正确还原。试想一下如果轮函数F设计得非常复杂那没关系因为解密根本不需要求F的反函数。F只需要是“确定性的、固定输入输出长度的函数”即可哪怕它非线性、不可逆、丢失信息反正解密时用同样的F和逆序子密钥就能还原。那为什么不需要F的逆来看解密公式R_{i-1} L_iL_{i-1} R_i ⊕ F(L_i, K_i)这个表达式的意思是只要知道这一轮的L_i、R_i和本轮子密钥K_i就能无损恢复出上一轮的L_{i-1}和R_{i-1}。整个过程只用到异或和函数F本身完全不需要解方程。这就是Feistel结构“加密解密同构”的底层逻辑。相比之下S盒的逆运算在实现时是很麻烦的如果整个算法在整体层面依赖逆函数工程实现和安全性分析都会多出很多负担。Feistel结构把“可逆性”这个包袱甩给了整体结构让轮函数可以自由追求混淆和扩散这是它能够横跨数十年的根本原因。2.2 16轮数据流全景我习惯把DES的一条完整数据流画成下面这样初始置换IP把64位明文的位置打乱输出L0和R0各32位第1轮R0进入F函数与K1异或得到F(R0, K1)然后L0与其异或得到R1而L1直接取R0第2轮到第16轮完全重复这个过程第16轮结束后交换左右得到R16 || L16而不是L16 || R16最后经过逆置换IP^-1输出64位密文这里有一个初学者最容易忽略的细节第16轮结束后要“交换左右”。在Feistel结构里每一轮都已经天然交换了左右如果第16轮之后直接按L16 || R16的顺序走那逆置换会得到错误结果。标准做法是输出R16 || L16这个连接顺序让整个加密和解密流程在结构上完全对称。我当年第一次实现时忘了这一步解密出来一堆乱码排查半天才发现问题。这个“16轮”不是随便定的。每一轮只通过F函数把右半的信息混入左半一轮下来一个位最多只能影响到32位里的部分位置需要多轮循环才能让雪崩效应扩散到整个64位块。DES选16轮其中一个重要原因就是保证“改变任意一个明文位或者密钥位大约有一半的密文位会变化”这一效果得到充分体现。3. 第一层换位初始置换IP与逆置换接下来看64位明文进入算法后遭遇的第一件事初始置换IP。这个操作不涉及任何密钥纯粹是把64个位的顺序按照一张固定表格重新排列。听起来很简单但你拿着表动手排一次才能真正理解什么叫“按位搬家”。标准IP置换表是这样的按从左到右、从上到下的顺序读取输出的第1位来自输入的58位第2位来自50位以此类推输出位置 1-858 50 42 34 26 18 10 2 输出位置 9-1660 52 44 36 28 20 12 4 输出位置 17-2462 54 46 38 30 22 14 6 输出位置 25-3264 56 48 40 32 24 16 8 输出位置 33-4057 49 41 33 25 17 9 1 输出位置 41-4859 51 43 35 27 19 11 3 输出位置 49-5661 53 45 37 29 21 13 5 输出位置 57-6463 55 47 39 31 23 15 7注意看这张表上32个输出位置来自输入的奇数位近似下32个来自偶数位。更精确地说IP把原始输入的交叉位重排成“先奇数位的主块、再偶数位的主块”这样的形态。这个置换的特殊之处在于它输出的前32位正好成为L0后32位成为R0。3.1 IP置换表怎么读举个例子假设输入64位明文是M 00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111我们给这64个位编号1到64。按IP表输出的第1位来自原第58位M的第58位是1输出的第2位来自原第50位M的第50位是1依此类推。整张表排完后得到的L0和R0分别是L0 11001100 00000000 11001100 11111111 R0 11110000 11001100 10101010 11111111这两个值在后面的实操演示里会接着用你可以自己拿笔对着表算一遍结果能对上说明你懂这套“按位搬家”的玩法了。逆置换IP^-1是IP的精确逆操作它把置换后的64位恢复到与原输入对应的位置。两张表在结构上完全对应一个由过程中“打散”一个在结尾“拼回”。它们之间看起来相似但顺序完全不同千万别在代码里把两张表混用。3.2 为什么这一层被批评为“华而不实”密码学界对IP和IP^-1的评价一直很微妙。从功能上看IP置换本身不增加任何安全性因为它的映射关系是公开的、固定的攻击者完全可以在分析时反向恢复相当于在算法外面加了一层固定的“转码”。从硬件实现来看当年的芯片设计喜欢这种固定连线式的布线方式IP置换在硬件上只需要改变引脚的连接关系就能实现成本几乎为零但对于纯软件实现来说IP置换反而成了性能负担。后来AES在设计时干脆去掉了这种固定层直接在软件层面用字节代换和扩散结构效率更高。但这并不意味着学DES可以跳过IP——恰恰相反理解IP会让你明白现代密码学是如何从“硬件友好”一步步走向“软硬件兼顾”的也能帮你以后读其他经典算法时更快适应置换表风格的操作。4. 密钥扩展64位主密钥如何变成16轮48位子密钥轮函数F是每轮都用的核心组件但每一轮用的子密钥K_i不能是同一个否则16轮的安全性会大打折扣。DES的密钥扩展也叫密钥编排就是干这件事的把一把64位主密钥变成16把48位子密钥。整个流程分三段先做PC-1置换去掉8个奇偶校验位再把剩下的56位分成两半各28位接着两个半区分别按固定规则循环左移最后把左右两个28位合并成56位后做PC-2压缩置换选出48位作为本轮子密钥。4.1 PC-1先裁掉8个奇偶校验位64位主密钥K里的每个字节第8位是奇偶校验位实际参与加密的只有56位。PC-1的输入是64位输出是56位它把52个数据位换位并丢弃第8、16、24、32、40、48、56、64这8个校验位。PC-1置换表输出位置 1-757 49 41 33 25 17 9 输出位置 8-141 58 50 42 34 26 18 输出位置 15-2110 2 59 51 43 35 27 输出位置 22-2819 11 3 60 52 44 36 输出位置 29-3563 55 47 39 31 23 15 输出位置 36-427 62 54 46 38 30 22 输出位置 43-4914 6 61 53 45 37 29 输出位置 50-5621 13 5 28 20 12 4PC-1输出的前28位记为C0后28位记为D0。以教科书里很经典的测试密钥K 0x133457799BBCDFF1为例经过PC-1后得到C0 1111000011001100101010101111 D0 0101010101100110011110001111注意C0和D0各自只有28位。后面每一步循环左移都是对C、D两个半区分别进行的绝不要把它们合在一起再移位。4.2 循环左移表把所有子密钥错开DES规定了一个每轮左移位数表第1轮1 第2轮1 第3轮2 第4轮2 第5轮2 第6轮2 第7轮2 第8轮2 第9轮1 第10轮2 第11轮2 第12轮2 第13轮2 第14轮2 第15轮2 第16轮1循环左移的意思是C和D分别在自己的28位范围内左移溢出到最左侧的位回到最右侧。比如C0 1111000011001100101010101111左移1位就变成1110000110011001010101011111。第i轮的子密钥由C_i和D_i合并后经过PC-2得到而C_i和D_i是在C_{i-1}和D_{i-1}的基础上再左移相应位数得到的所以每轮子密钥都不一样。这个移位表是有意设计的左移1位和2位的交替能保证16轮之间不存在明显的周期性重复。4.3 PC-2压缩置换到48位C_i和D_i合并后是56位但轮函数F需要48位子密钥所以PC-2是一个56位输入、48位输出的置换表它丢掉其中8位并重排顺序。PC-2置换表输出位置 1-614 17 11 24 1 5 输出位置 7-123 28 15 6 21 10 输出位置 13-1823 19 12 4 26 8 输出位置 19-2416 7 27 20 13 2 输出位置 25-3041 52 31 37 47 55 输出位置 31-3630 40 51 45 33 48 输出位置 37-4244 49 39 56 34 53 输出位置 43-4846 42 50 36 29 32以刚才的C1和D1为例合并后经过PC-2得到第1轮子密钥K1 000110 110000 001011 101111 111111 000111 000001 110010这正是著名的教科书测试向量里的K1。建议你手动推一次这个结果把K的64位逐位标号按PC-1取位两个半区各左移一位再按PC-2取位中间每一步都用二进制写出来。走完一遍密钥扩展的整个机制就彻底通了。子密钥生成过程是单向依赖的K_i只依赖上一轮的C_{i-1}和D_{i-1}在代码里用一个循环顺次生成即可。解密时只需要先跑一遍密钥扩展得到全部16个子密钥然后从K16逆序应用到K1。5. 轮函数FDES发动机的内部构造有了子密钥接下来看轮函数F。F的输入是32位的右半区R_{i-1}和48位的子密钥K_i输出是32位结果要与左半区L_{i-1}异或。F内部有四步E扩展、与子密钥异或、S盒代换、P置换。用一个生活化的比喻帮助你理解F函数就是一台加工机器先把32位原料扩展成48位“半成品”然后与子密钥混合再经过8个S盒分别做非线性压缩最后把32位结果重新排列后输出。5.1 E扩展把32位撑到48位E扩展的作用是让32位的右半区R变成48位这样才能和48位子密钥异或。如果只是简单地加0填充安全性和扩散性都很差。DES的E扩展用的是“重复边界位”的方式把32位分成8组每组4位扩展后每组变成6位——第1位取前一组最后一位最后一位取下一位第一位。E扩展表输出位置 1-632 1 2 3 4 5 输出位置 7-124 5 6 7 8 9 输出位置 13-188 9 10 11 12 13 输出位置 19-2412 13 14 15 16 17 输出位置 25-3016 17 18 19 20 21 输出位置 31-3620 21 22 23 24 25 输出位置 37-4224 25 26 27 28 29 输出位置 43-4828 29 30 31 32 1看到没有第1组的前3位来自R的第32、1、2位最后一位来自第5位边界位被重复使用了。这种扩展方式保证了任何一个输入位的改变会影响至少两个输出组进而影响多个S盒的输出加速雪崩效应。5.2 第1轮跟踪子密钥异或还是用之前的例子。R0 11110000 11001100 10101010 11111111按照E扩展表重排后得到E(R0) 111110 100001 011001 011001 010101 100101 011111 111111然后与K1 000110 110000 001011 101111 111111 000111 000001 110010逐位异或得到8个6位组A 111000 010001 010010 110110 101010 011010 010110 001101这里的异或运算没有技巧可言就是每一位相同取0、不同取1。但这一步是整个F函数里唯一直接与密钥发生混合的地方所以它承担着“把密钥信息渗透进数据”的重任。5.3 S盒非线性就靠它S盒是整个DES里唯一引入非线性的环节也是对抗线性密码分析和差分密码分析的关键。没有S盒整个DES就会退化为一个仿射变换用线性代数就能破解那加密就形同虚设了。E扩展异或后的48位会被切成8个6位组分别进入8个不同的S盒S1到S8。每个S盒的输入是6位最高位和最低位组成2位行号0到3中间4位组成列号0到15输出是4位。每个S盒都是一张4行16列的查找表里面是0到15之间的十进制数。以S1为例标准查找表如下第0行14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7第1行0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8第2行4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0第3行15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13上面那一组A的第一个S盒输入是111000行号取第1位和第6位即10对应第2行列号取中间4位1100即十进制12查S1第2行第12列得到12二进制是1100。八个S盒依次查完输出拼在一起就是32位。在我们的例子里8个S盒查表后依次得到S1输出1100 S2输出1001 S3输出1101 S4输出1010 S5输出1111 S6输出0111 S7输出0111 S8输出1101拼起来是S_out 1100 1001 1101 1010 1111 0111 0111 1101这里有一个初学者容易犯的错查表时把行列搞反或者忘记行号是首尾两位。记住口诀外面两位定行中间四位定列。S盒的输出长度只有输入长度的三分之二6位进、4位出这本身就是信息压缩。8个S盒都设计成非线性的且输出每一位对输入的任何一位都高度敏感。当年美国国家安全局参与了S盒设计的部分过程外界一度怀疑其中藏着后门直到后来公开的差分分析研究证明这些S盒对差分攻击具有相当强的抵抗力这个争议才逐渐平息。5.4 P置换让雪崩效应更彻底S盒输出32位后最后一步是P置换。它的作用是把S盒输出的32位重新打散位置特别是让每个S盒的输出位扩散到多个位置影响下一轮的多个S盒输入。P置换表输出位置 1-416 7 20 21 输出位置 5-829 12 28 17 输出位置 9-121 15 23 26 输出位置 13-165 18 31 10 输出位置 17-202 8 24 14 输出位置 21-2432 27 3 9 输出位置 25-2819 13 30 6 输出位置 29-3222 11 4 25把前面例子的S_out1100 1001 1101 1010 1111 0111 0111 1101按P置换表重排得到最终F函数结果F(R0, K1) 0010 1111 1111 1101 1110 1101 1110 1000到这里轮函数F的完整一次运算就走完了。6. 手把手跑通第一轮教科书数据全流程演示前面已经把每个零件都拆开讲过现在把它们组装起来一起完整看一遍第一轮该怎么算。我选用经典的测试向量明文M 0x0123456789ABCDEF密钥K 0x133457799BBCDFF1最终密文是公开教材里的0x85E813540F0AB405。如果你自己动手算最后能对到这个结果就说明整个流程没问题。6.1 明文与密钥准备把明文转成二进制M 00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111密钥转成二进制K 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001注意密钥共64位但第8、16、24、32、40、48、56、64位是奇偶校验位在PC-1阶段会被丢掉。6.2 初始置换拆出L0和R0按之前IP表操作M得到L0 11001100 00000000 11001100 11111111 R0 11110000 11001100 10101010 11111111这一步值得用纸笔再核对一遍。把M的64个位编号然后逐个对应IP表上的数字你会看到输出前32位组成L0后32位组成R0。6.3 第一轮计算全过程密钥扩展第1轮的子密钥我们前面已经算过K1 000110 110000 001011 101111 111111 000111 000001 110010接下来计算F(R0, K1)E扩展E(R0) 111110 100001 011001 011001 010101 100101 011111 111111异或K1A E(R0) XOR K1 111000 010001 010010 110110 101010 011010 010110 001101八个S盒查表S_out 1100 1001 1101 1010 1111 0111 0111 1101P置换F 0010 1111 1111 1101 1110 1101 1110 1000然后更新左右半区L1 R0 11110000 11001100 10101010 11111111 R1 L0 XOR F 11100011 11111101 00100001 00010111这一轮结束。第二轮开始前R0已经变成L1新的R1继续进下一轮轮函数。如此重复16次。6.4 剩下15轮与最终密文第2轮到第16轮的中间过程我就不展开手算了但流程完全一样每轮先用上一轮的R代入F函数与对应子密钥K_i运算再和上一轮的L异或接下来左右互换。第16轮结束后把左右交换得到R16 || L16最后经过逆置换IP^-1得到密文密文 0x85E813540F0AB405我用这套数据自己跑过完整实现加密结果能精确对上这个值。你可以把它当作最终校验标准如果自己写的代码加密结果对不上优先检查子密钥顺序、左右交换时机和S盒查表索引这三个最容易出错的地方。7. 安全性与工程实现里的那些坑DES本身已经“退休”了但围绕它的安全争议和实现坑到现在依然值得反复念叨。7.1 56位密钥为什么注定被暴力破解56位密钥意味着有2的56次方种可能的密钥组合这个数量大约是7.2乘以10的16次方。在上世纪70年代这看起来是个天文数字但在现代计算环境下专门设计的硬件破解机可以在极短时间内穷举完所有可能。1998年前后专用破解设备就能在几十小时内破解DES。换句话说DES的密钥空间太小无论算法结构多么精巧都已经扛不住现代暴力攻击。正因为如此才有了3DES用三个不同的DES密钥依次做加密-解密-加密相当于把密钥长度提升到112位或168位同时复用DES的成熟实现。3DES到现在某些旧系统里还在服役但它的性能瓶颈和块长限制最终让它被AES取代。这给我们一个重要教训分组密码的安全性算法公开不是问题密钥长度和结构设计才是根本。现代密码学里算法的安全性应当完全取决于密钥而不是算法的保密性。这一点在DES的生态上体现得淋漓尽致。7.2 写DES代码时最容易翻车的三个点第一子密钥顺序。许多人写解密时忘了把子密钥数组倒过来用。哪怕前面加密全对解密结果也会是乱码。正确的做法是先正常生成16个子密钥解密时从K16开始依次用到K1。第二S盒行号取位。S盒输入是6位行号是第1位和第6位拼接。很多人在代码里习惯性取“前四位”作为行号这就全错了。我的经验是用位运算先把第0位和第5位提出来再拼成行号不要留给人肉拼接的机会。第三16轮结束后左右交换。这一点我前面专门提过依然是最容易被忽略的。在第16轮循环的代码外面再交换一次L和R再进逆置换才能得到正确密文。很多教材伪代码里特意标注了这一步就是因为太容易写漏。还有一个小坑是位序问题。DES的位编号习惯是1到64bit 1是最高位。如果你用普通字节数组存数据要明确“数组第一个元素的高位”对应bit 1。不同实现里字节内位序的约定如果不一致表和数据都会错位。这个问题很隐蔽我调试时花了很长时间才定位到。7.3 常常被误解的几个点DES加密每个块互相独立所以相同的明文块在相同密钥下会得到相同密文。这不是BUG而是“电子密码本ECB”模式的特性但它会泄露明文结构信息。实际系统里一般不用ECB而用CBC、CTR等带随机性的工作模式。如果有人说“DES不可靠是因为同一明文加密结果相同”那其实是模式选择问题不是算法本身的问题。DES的密钥不是64位是56位。凡是把密钥位数说成64位的都是把校验位也算进去了。DES已经过时但它的设计思想没有过时。Feistel结构、S盒去线性化、扩散与混淆的拆解这些思路在AES、ChaCha20等现代算法身上依然能看到影子。8. 最后一句经验之谈我自己动手实现DES前后踩了不少坑最大的收获不是“我会写一个DES”而是理解了“分组密码为什么必须这样设计”。当你亲手把一张置换表变成一行行代码把S盒查表变成内存数组索引再看着最终密文和教材对上的那一刻很多算法书里干巴巴的概念才真正有了立体感。如果你想学扎实强烈建议不要只读不写。拿纸笔算第一轮再用任意一门语言实现完整加密解密最后用标准测试向量验证。这个过程走完DES这块硬骨头才算是真正啃下来了。之后再去学AES、SM4这些算法你会发现很多底层观念是相通的——因为它们都是在解决同一个问题如何用公开的算法、够长的密钥安全又高效地守护数据。