DES子密钥逆推初始密钥详解

1. 简介

DES(数据加密标准)是一种对称加密算法，当两轮或更多轮的子密钥泄漏时，几乎可以完全逆推出初始密钥。由于DES密钥实际有效位为56bit(64bit中8bit为校验位)，因此只能恢复56bit，剩余8bit需要通过暴力破解(共256种可能情况)。

2. DES子密钥生成过程回顾

2.1 初始密钥处理

• 密钥长度：64位(实际有效56位，8位为奇偶校验位)
• 经过PC-1置换(置换选择1)后变为56位数据K'
• 将K'分为两部分：
  • 前28位为C0
  • 后28位为D0

2.2 子密钥生成步骤

1. 根据轮数进行循环左移(移动位数由表决定)
2. 合并Ci和Di
3. 通过PC-2置换(置换选择2)生成48位子密钥Ki
   • PC-2去除了第9,18,22,25,35,38,43,54位

2.3 示例

初始密钥K = 0001001100110100010101110111100110011011101111001101111111110001

经过PC-1置换后：
K' = 11110000110011001010101011110101010101100110011110001111

分为：
C0 = 1111000011001100101010101111
D0 = 0101010101100110011110001111

左移1位后：
C1 = 1110000110011001010101011111
D1 = 1010101011001100111100011110

合并后通过PC-2置换得到K1：
K1 = 000110110000001011101111111111000111000001110010

3. 从子密钥逆推初始密钥

3.1 逆推步骤

1. 对已知子密钥Ki使用逆PC-2盒，得到56位的Ci+Di(可能含未知变量)
2. 对C和D进行循环右移一位，还原netss
3. 使用netss生成带未知变量的十六轮子密钥
4. 将生成的子密钥与题目给定的子密钥比对，获取真实netss
5. 还原逆PC-1盒
6. 对每个字节的最后一位进行爆破(共256种可能)

3.2 关键函数实现

逆PC-2置换

def ReSubstitution_PC_2_Box(keyfield, sub):
    newkeyfield = ['*'] * 56
    for i in range(len(sub)):
        newkeyfield[sub[i]] = keyfield[i]
    newkeyfield = ''.join(newkeyfield)
    return newkeyfield

子密钥生成

def enkey(netss):
    C, D = netss[:28], netss[28:]
    key = []
    for i in range(16):
        C, D, keyone = SubkeyGeneration(i, C, D)
        key.append(keyone)
    return key

密钥还原

def dekey(netss):
    netss = ReSubstitution_PC_2_Box(netss, RE_PC_2)
    C, D = netss[:28], netss[28:]
    C = C[-1:] + C[:-1]
    D = D[-1:] + D[:-1]
    netss = C + D
    real_netss = ''
    num = 0
    for i in netss:
        if i != '*':
            real_netss += i
        else:
            real_netss += alphabet[num]
            num += 1
    keys = enkey(real_netss)
    key_dic = {}
    for i in range(len(keys)):
        for j in range(48):
            if keys[i][j] != real_key[i][j]:
                key_dic[keys[i][j]] = real_key[i][j]
    for i in key_dic:
        real_netss = real_netss.replace(i, key_dic[i])
    key = ReSubstitution_PC_1_Box(real_netss, RE_PC_1)
    return key

暴力破解最后8位

def BruteForce_Lowest_Bytes(key):
    keys = []
    for i in range(8):
        keys.append(key[i*8:i*8+8][:-1])
    for i in range(256):
        num = format(i, '08b')
        key = ''
        for j in range(8):
            key += keys[j] + num[j]
        print(BinToStr(key))

奇偶校验计算

def Parity_Bit_Calculation(key):
    keys = []
    key = ''
    for i in range(8):
        keys.append(key[i*8:i*8+8][:-1])
        num = 0
        for j in keys[i]:
            if j == '1':
                num += 1
        if(num % 2 == 1):
            keys[i] += '0'
        else:
            keys[i] += '1'
        key += keys[i]
    print(BinToStr(key))

3.3 实际应用

给定16轮子密钥，可以通过以下步骤恢复初始密钥：

1. 选择一个子密钥(如K1)开始逆推
2. 使用逆PC-2盒得到56位中间状态
3. 通过循环右移还原netss
4. 生成所有可能的子密钥并与给定子密钥比对
5. 还原PC-1置换
6. 暴力破解最后8位

4. 注意事项

1. DES的第8位bit本应是奇偶校验位，但实际应用中可能不遵循此规则
2. 暴力破解的前提是需要有标志判断结果是否正确
3. 如果只给定一轮子密钥，恢复初始密钥的难度会大大增加

5. 完整实现代码

# -*- coding: utf-8 -*-
hexadecimalcontrast = {
    '0': '0000',
    '1': '0001',
    '2': '0010',
    '3': '0011',
    '4': '0100',
    '5': '0101',
    '6': '0110',
    '7': '0111',
    '8': '1000',
    '9': '1001',
    'a': '1010',
    'b': '1011',
    'c': '1100',
    'd': '1101',
    'e': '1110',
    'f': '1111',
}
alphabet = 'abcdefghijklmnopqrstuvwxyz'

PC_2 = [14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32, ]
PC_1 = [57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4, ]
RE_PC_2 = [13, 16, 10, 23, 0, 4, 2, 27, 14, 5, 20, 9, 22, 18, 11, 3, 25, 7, 15, 6, 26, 19, 12, 1, 40, 51, 30, 36, 46, 54, 29, 39, 50, 44, 32, 47, 43, 48, 38, 55, 33, 52, 45, 41, 49, 35, 28, 31]
RE_PC_1 = [56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3]
movnum = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

def HexToBin(string):
    "Convert sixteen to binary"
    Binstring = ""
    string = string.lower()
    for i in string:
        try:
            Binstring += hexadecimalcontrast[i]
        except:
            return -1
    return Binstring

def BinToStr(strbin):
    "Turn the binary string to a ASCII string"
    strten = ""
    for i in range(len(strbin) // 8):
        num = 0
        test = strbin[i * 8:i * 8 + 8]
        for j in range(8):
            num += int(test[j]) * (2**(7 - j))
        strten += chr(num)
    return strten

def StrToHex(string):
    "Converts a string to HEX"
    hexStr = ''
    for i in string:
        tmp = str(hex(ord(i)))
        if len(tmp) == 3:
            hexStr += tmp.replace('0x', '0')
        else:
            hexStr += tmp.replace('0x', '')
    return hexStr

def Binxor(string1, string2):
    "If the length is different, only the short one is returned."
    strlen = 0
    xorstr = ""
    if len(string1) > len(string2):
        strlen = len(string2)
    else:
        strlen = len(string1)
    for i in range(strlen):
        if string1[i] == string2[i]:
            xorstr += '0'
        else:
            xorstr += '1'
    return xorstr

def SubstitutionBox(keyfield, sub):
    # 置换盒
    newkeyfield = ''
    for i in range(len(sub)):
        newkeyfield += keyfield[sub[i] - 1]  # watch the table
    return newkeyfield

def SubkeyGeneration(freq, C, D):
    # 轮密钥生成函数
    for i in range(movnum[freq]):
        C = C[1:] + C[:1]
        D = D[1:] + D[:1]
    return C, D, SubstitutionBox(C + D, PC_2)

def enkey(netss):
    # 生成子密钥
    C, D = netss[:28], netss[28:]
    key = []
    for i in range(16):  # 十六轮子密钥生成
        C, D, keyone = SubkeyGeneration(i, C, D)
        key.append(keyone)
    return key

def dekey(netss):
    # 还原子密钥
    netss = ReSubstitution_PC_2_Box(netss, RE_PC_2)
    C, D = netss[:28], netss[28:]
    C = C[-1:] + C[:-1]
    D = D[-1:] + D[:-1]
    netss = C + D
    real_netss = ''
    num = 0
    for i in netss:
        if i != '*':
            real_netss += i
        else:
            real_netss += alphabet[num]
            num += 1
    keys = enkey(real_netss)
    key_dic = {}
    for i in range(len(keys)):
        for j in range(48):
            if keys[i][j] != real_key[i][j]:
                key_dic[keys[i][j]] = real_key[i][j]
    for i in key_dic:
        real_netss = real_netss.replace(i, key_dic[i])
    key = ReSubstitution_PC_1_Box(real_netss, RE_PC_1)
    return key

def BruteForce_Lowest_Bytes(key):
    keys = []
    for i in range(8):
        keys.append(key[i*8:i*8+8][:-1])
    for i in range(256):
        num = format(i, '08b')
        key = ''
        for j in range(8):
            key += keys[j] + num[j]
        print(BinToStr(key))

def Parity_Bit_Calculation(key):
    keys = []
    key = ''
    for i in range(8):
        keys.append(key[i*8:i*8+8][:-1])
        num = 0
        for j in keys[i]:
            if j == '1':
                num += 1
        if(num % 2 == 1):
            keys[i] += '0'
        else:
            keys[i] += '1'
        key += keys[i]
    print(BinToStr(key))

def ReSubstitution_PC_1_Box(keyfield, sub):
    newkeyfield = ['*'] * 64
    for i in range(len(sub)):
        newkeyfield[sub[i]] = keyfield[i]
    newkeyfield = ''.join(newkeyfield)
    return newkeyfield

def ReSubstitution_PC_2_Box(keyfield, sub):
    newkeyfield = ['*'] * 56
    for i in range(len(sub)):
        newkeyfield[sub[i]] = keyfield[i]
    newkeyfield = ''.join(newkeyfield)
    return newkeyfield

# 示例使用
real_key = [
    '101000001001011001000110001110110000011110011000',
    '111000000011011001010010100101100011011000100110',
    '011001001101011001110000001111000000101111100100',
    '110001101101000101010010000100001110100011010011',
    '001011101100001101010011011001111010010000010001',
    '001011110101000100001011101010110010010101001010',
    '001010110000000111011001001011001101001100000110',
    '000111010100100010011001010101000100010011100110',
    '000111010100100111001000010000001111100101010100',
    '000100100110100110001101011000011010010010111000',
    '000110010010110100000101111010010001110000001011',
    '010000010010110010101101000011100101001000111110',
    '110100011010010010100100000101010101100111100100',
    '110100001000111010100010100000001000100011110001',
    '111100001011001000100110110000111010111000010101',
    '101000001011111000100110101000011001001000001011'
]

# 从第一个子密钥开始逆推
K1 = real_key[0]
key = dekey(K1)

# 可选：使用奇偶校验计算
# Parity_Bit_Calculation(key)

# 可选：暴力破解最后8位
# BruteForce_Lowest_Bytes(key)

6. 总结

通过DES子密钥逆推初始密钥的过程，我们可以深入理解DES算法的密钥调度机制。这种方法在CTF竞赛和密码学研究中具有重要意义，特别是在已知部分子密钥的情况下恢复完整密钥的场景。需要注意的是，实际应用中DES的密钥选择可能不完全遵循奇偶校验规则，因此暴力破解可能是必要的最后步骤。