DES

加密原理

加密过程图片

需要注意的是，明文的分组长度需要为64位（8个字节），密钥长度为64位（56位有效位+8位奇偶校验位）。

加密过程简要概括就是：

明文(64位) → IP置换 → 16轮迭代 → $IP^{-1}$逆置换 → 密文(64位)

F是轮函数，它的四个步骤包括：

步骤	操作	输入→输出	说明
1	扩展置换(E盒)	32位 → 48位	将右半部分扩展，使与48位子密钥对齐
2	与子密钥异或	48位 ⊕ 48位	将扩展后的结果与本轮子密钥按位异或
3	S盒替换	48位 → 32位	8个S盒并行，每个将6位压缩为4位（非线性核心）
4	P盒置换	32位 → 32位	对S盒输出进行重排，增加雪崩效应

解密原理

DES最巧妙的设计之一在于：解密过程与加密过程完全相同，只需将16个子密钥的使用顺序反转即可。

加密子密钥顺序：K1, K2, …, K15, K16
解密子密钥顺序：K16, K15, …, K2, K1

加解密代码

# DES 算法实现
# 输入：64bit 明文 / 64bit 密钥
# 输出：64bit 密文（同理可解密）

# 初始置换 IP：将64位明文按固定表重新排列比特位置,明文被分成左半部分F和右半部分R，各32位
IP = [58, 50, 42, 34, 26, 18, 10, 2,
      60, 52, 44, 36, 28, 20, 12, 4,
      62, 54, 46, 38, 30, 22, 14, 6,
      64, 56, 48, 40, 32, 24, 16, 8,
      57, 49, 41, 33, 25, 17, 9, 1,
      59, 51, 43, 35, 27, 19, 11, 3,
      61, 53, 45, 37, 29, 21, 13, 5,
      63, 55, 47, 39, 31, 23, 15, 7]

# 逆初始置换 IP_1:将IP打乱的数据顺序恢复到正常状态，初始置换的逆过程
IP_1 = [40, 8, 48, 16, 56, 24, 64, 32,
        39, 7, 47, 15, 55, 23, 63, 31,
        38, 6, 46, 14, 54, 22, 62, 30,
        37, 5, 45, 13, 53, 21, 61, 29,
        36, 4, 44, 12, 52, 20, 60, 28,
        35, 3, 43, 11, 51, 19, 59, 27,
        34, 2, 42, 10, 50, 18, 58, 26,
        33, 1, 41, 9, 49, 17, 57, 25]

# 扩展置换 E ：消息32位→48位
E = [32, 1, 2, 3, 4, 5,
     4, 5, 6, 7, 8, 9,
     8, 9, 10, 11, 12, 13,
     12, 13, 14, 15, 16, 17,
     16, 17, 18, 19, 20, 21,
     20, 21, 22, 23, 24, 25,
     24, 25, 26, 27, 28, 29,
     28, 29, 30, 31, 32, 1]

# P置换：进行简单的位置置换,32位
P = [16, 7, 20, 21, 29, 12, 28, 17,
     1, 15, 23, 26, 5, 18, 31, 10,
     2, 8, 24, 14, 32, 27, 3, 9,
     19, 13, 30, 6, 22, 11, 4, 25]

# S盒：48位数据分成8组，每个盒进6出4，最终得到32位输出
#第一位和最后一位作为行号，2~5位作为列号
S_BOX = [
    # S1
    [[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
     [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
     [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
     [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]],
    # S2
    [[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10],
     [3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5],
     [0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15],
     [13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]],
    # S3
    [[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8],
     [13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1],
     [13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7],
     [1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]],
    # S4
    [[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15],
     [13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9],
     [10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4],
     [3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]],
    # S5
    [[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9],
     [14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6],
     [4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14],
     [11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]],
    # S6
    [[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11],
     [10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8],
     [9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6],
     [4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]],
    # S7
    [[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1],
     [13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6],
     [1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2],
     [6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]],
    # S8
    [[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
     [1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
     [7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
     [2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]]
]

#PC:生成轮密钥
# 密钥置换 PC1，筛选出64位密钥的56位有效位（除去序号位为8的倍数的数：8，16，24，32，48，56，64)
PC1 = [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]

# 密钥置换 PC2，56位→48位（同样也少了一些序号，目的是删除固定序号位的数，这里不列举了，自己观察）
PC2 = [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]

# 每轮左移位数
SHIFT = [1, 1, 2, 2, 2, 2, 2, 2,
         1, 2, 2, 2, 2, 2, 2, 1]


# 置换函数
def permute(block, table):
    return [block[x - 1] for x in table]


# 左移
def left_shift(key_block, n):
    return key_block[n:] + key_block[:n] #把最左边的n个数字，整体搬到最右边去


# 异或
def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]


# 生成16轮子密钥
def generate_subkeys(key_64):
    key = permute(key_64, PC1)  # 56bit
    C = key[:28] #前28位
    D = key[28:] #后28位
    subkeys = []
    for i in range(16):
        C = left_shift(C, SHIFT[i])
        D = left_shift(D, SHIFT[i])
        combined = C + D
        subkey = permute(combined, PC2)
        subkeys.append(subkey)
    return subkeys #16*48的二维数组


# F函数
def f(R, subkey):
    expanded = permute(R, E) #把右半边32位数据扩展为48位
    xor_val = xor(expanded, subkey) #然后和子密钥异或
    s_out = []
    for i in range(8):
        chunk = xor_val[i * 6:(i + 1) * 6] #分组，每组6位
        row = (chunk[0] << 1) | chunk[5]#第一位和最后一位组成行号
        col = (chunk[1] << 3) | (chunk[2] << 2) | (chunk[3] << 1) | chunk[4] #中间四位组成列号
        val = S_BOX[i][row][col]
        s_out += [int(bit) for bit in f"{val:04b}"]
    return permute(s_out, P)


# 单组 DES 加密
def des_encrypt_block(block_64, subkeys):
    block = permute(block_64, IP)
    L, R = block[:32], block[32:]
    for i in range(16):
        new_L = R #新的左来自旧的右
        new_R = xor(L, f(R, subkeys[i])) #新的右来自旧的左和f函数异或
        L, R = new_L, new_R #不断迭代...
    combined = R + L
    return permute(combined, IP_1)


# 单组 DES 解密
def des_decrypt_block(block_64, subkeys):
    block = permute(block_64, IP)
    L, R = block[:32], block[32:]
    for i in range(15, -1, -1): #密钥顺序倒置即可解密
        new_L = R
        new_R = xor(L, f(R, subkeys[i]))
        L, R = new_L, new_R
    combined = R + L
    return permute(combined, IP_1)


# 字节与比特列表相互转化
def bytes_to_bits(b):
    return [int(bit) for byte in b for bit in f"{byte:08b}"]


def bits_to_bytes(bits):
    return bytes([int(''.join(map(str, bits[i:i + 8])), 2) for i in range(0, len(bits), 8)])


# 对外接口：加密
def des_encrypt(plain_bytes, key_bytes):
    plain_bits = bytes_to_bits(plain_bytes)
    key_bits = bytes_to_bits(key_bytes)
    subkeys = generate_subkeys(key_bits)
    cipher_bits = des_encrypt_block(plain_bits, subkeys)
    return bits_to_bytes(cipher_bits)


# 对外接口：解密
def des_decrypt(cipher_bytes, key_bytes):
    cipher_bits = bytes_to_bits(cipher_bytes)
    key_bits = bytes_to_bits(key_bytes)
    subkeys = generate_subkeys(key_bits)
    plain_bits = des_decrypt_block(cipher_bits, subkeys)
    return bits_to_bytes(plain_bits)


# ==================== 测试示例 ====================
if __name__ == "__main__":
    # 必须 8 字节明文，8 字节密钥
    plain = b"abcdefgh"
    key = b"12345678"

    cipher = des_encrypt(plain, key)
    decrypted = des_decrypt(cipher, key)

    print("明文:", plain)
    print("密文:", cipher.hex())
    print("解密:", decrypted)

通常知道初始密钥key就能解密了，所以我们的目标就是获得key。

攻击方法

暴力破解（Brute Force Attack）

暴力破解是最直接但也是最耗时的一种攻击方式。由于DES使用56位的密钥长度（实际上有8位用于奇偶校验，因此有效密钥长度为48位），理论上可以通过尝试所有可能的密钥组合来解密数据。然而，随着现代计算能力的增强，尤其是并行计算和分布式计算的发展，暴力破解的效率有所提高，但仍然面临巨大的时间成本。对于更长的密钥或更强的加密算法，暴力破解通常变得不切实际。

为了应对这种攻击，建议采用更长、更复杂且随机生成的密钥，以及使用更安全的加密算法（如AES）。

差分密码分析（Differential Cryptanalysis）

差分密码分析是一种基于统计学的分析方法，它通过分析明文对和相应的密文对之间的差异来推断密钥。这种方法利用了DES算法中某些特定的数学特性，使得攻击者能够通过大量已知明文-密文对的比较，逐步缩小可能的密钥范围。

为了防范差分密码分析，加密系统需要设计得更加复杂，以减少或消除这类统计分析的有效性。此外，定期更换密钥和使用不同的加密算法也是有效的防御措施。

线性密码分析（Linear Cryptanalysis）

与差分密码分析类似，线性密码分析也是一种利用统计学原理的攻击方法。它通过寻找明文、密文和密钥之间的线性关系来推测密钥。攻击者会构建多个线性方程，并利用已知明文-密文对来求解这些方程，从而确定密钥的一部分或全部信息。

为了抵御线性密码分析，加密算法应该避免引入明显的线性关系，并增加算法的复杂性。同样地，定期更新密钥和使用更强大的加密算法也是保护数据安全的重要手段。