从DES最后一轮48位轮密钥推导64位主密钥：可行性与算法问询

答案是可行，不过你没法得到唯一的主密钥——最多会有256个有效的候选密钥。下面我会解释原因，以及具体的推导步骤：

先回顾DES密钥扩展的正向流程 #

要逆向推导，得先搞清楚DES是怎么从主密钥生成轮密钥的：

• 64位主密钥里包含8位奇偶校验位（每个字节的第8位，也就是第8、16…64位），实际有效密钥位是56位。
• 主密钥先经过PC-1置换，去掉奇偶校验位，得到56位数据，再拆分成左右两个28位的分组：C0（左半部分）和D0（右半部分）。
• 每一轮（共16轮）的操作：
  1. Cn和Dn分别进行循环左移，移位次数是固定的：第1、2、9、16轮移1位，其余轮次移2位（移位序列：1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1）。
  2. 将移位后的Cn和Dn合并成56位数据，再经过PC-2置换——从56位中挑选48位，就得到了该轮的轮密钥Kn。

最后一轮的轮密钥K16，是由经过15次左移后的C15和D15合并后，经PC-2置换得到的。我们的逆向过程就是把这个步骤倒过来走。

具体推导算法步骤 #

1. 逆向PC-2置换，得到候选的C15D15 #

PC-2是固定的置换规则，它从56位的CnDn中选48位生成Kn。逆向操作的话：

• 先创建一个空的56位缓冲区。
• 根据PC-2置换表的逆映射，把K16的每一位填到56位缓冲区对应的位置上。
• 缓冲区里剩下的8个位置（PC-2没选中的位）是未知的——它们可以是0或1，这就导致我们会得到2^8=256个可能的C15D15候选值。

2. 逆向循环左移，得到C0D0 #

接下来要把15次左移的操作逆回去——循环左移的逆操作是循环右移，移位次数和对应轮次的左移次数一致，而且要从最后一轮往第一轮逆推：

• 拿一个候选的C15和D15（各28位）开始。
• 还原第16轮的移位：把C15和D15分别循环右移1位，得到C14和D14。
• 还原第15轮的移位：把C14和D14分别循环右移2位，得到C13和D13。
• 按照这个逻辑，依次还原剩下的轮次（第14轮到第1轮），对应的右移次数就是原轮次的左移次数。
• 完成所有逆向移位后，就能得到最初的C0和D0（合并起来是56位有效密钥）。

3. 逆向PC-1置换，得到64位主密钥 #

PC-1的作用是从64位主密钥中去掉奇偶校验位，重新排列剩下的56位得到C0D0。逆向操作：

• 创建一个空的64位缓冲区。
• 根据PC-1置换表的逆映射，把C0D0的每一位填到64位缓冲区对应的位置上。
• 填充奇偶校验位：每个字节的第8位（也就是第8、16…64位）需要设置为使得该字节的1的个数为奇数（这是DES密钥的合规要求）。如果不需要合规，也可以随便填0或1，但这样的密钥可能无法被标准DES实现接受。

关键说明：为什么会有多个候选密钥？ #

因为第一步里存在8个未知位，所以最终会生成256个不同的64位主密钥。这些密钥在经过正向的DES密钥扩展后，都会得到完全相同的K16。如果你有额外的信息（比如已知的明文-密文对），可以通过测试这些候选密钥来找到真正有效的那个。

内容的提问来源于stack exchange，提问作者Surya Teja Togaru