手把手复现：用Python从零实现PRESENT-80分组加密算法（附完整代码）

在当今数据安全需求日益增长的背景下，轻量级加密算法因其在资源受限环境中的出色表现而备受关注。PRESENT算法作为SPN（Substitution-Permutation Network）结构的经典代表，以其简洁高效的设计成为物联网设备、嵌入式系统等场景的理想选择。本文将带领读者从零开始，用Python完整实现PRESENT-80版本，通过代码实践深入理解其核心机制。

1. 算法基础与设计准备

PRESENT算法的精妙之处在于其简洁而严谨的结构设计。作为分组密码，它采用64位分组大小和80位密钥长度（PRESENT-80版本），通过31轮迭代实现数据混淆和扩散。在开始编码前，我们需要明确几个关键设计决策：

• 位序处理 ：现代计算机通常采用小端序存储，而密码算法常按大端序处理比特流
• 模块化设计 ：将S盒、P盒置换等核心操作封装为独立函数
• 状态可视化 ：在关键步骤打印中间状态，便于调试和理解算法流程

先准备基础工具函数，处理比特级操作：

def int_to_bits(n, length):
    """将整数转换为指定位长的比特列表"""
    return [int(b) for b in format(n, f'0{length}b')]

def bits_to_int(bits):
    """将比特列表转换为整数"""
    return int(''.join(map(str, bits)), 2)

def rotate_left(bits, n):
    """循环左移n位"""
    return bits[n:] + bits[:n]

2. 核心组件实现

2.1 S盒代换层

PRESENT使用4×4的S盒实现非线性变换，其真值表如下：

输入	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
输出	C	5	6	B	9	0	A	D	3	E	F	8	4	7	1	2

Python实现时，我们可以用字典高效实现查表：

SBOX = {
    0x0: 0xC, 0x1: 0x5, 0x2: 0x6, 0x3: 0xB,
    0x4: 0x9, 0x5: 0x0, 0x6: 0xA, 0x7: 0xD,
    0x8: 0x3, 0x9: 0xE, 0xA: 0xF, 0xB: 0x8,
    0xC: 0x4, 0xD: 0x7, 0xE: 0x1, 0xF: 0x2
}

def sbox_layer(state):
    """应用S盒代换到64位状态"""
    new_state = []
    for i in range(0, 64, 4):
        nibble = bits_to_int(state[i:i+4])
        substituted = SBOX[nibble]
        new_state.extend(int_to_bits(substituted, 4))
    return new_state

注意：实际应用中应考虑S盒的实现安全性，防止旁路攻击。此处为教学目的采用简明的查表法。

2.2 P盒置换层

P盒实现比特位置的线性扩散，其置换规则可用数学表达式描述：

P(i) = (i × 16) mod 63, 当i ∈ [0,62]
P(63) = 63

Python实现可预计算置换表：

def generate_pbox():
    """生成P盒置换表"""
    pbox = [0] * 64
    for i in range(64):
        if i == 63:
            pbox[i] = 63
        else:
            pbox[i] = (i * 16) % 63
    return pbox

PBOX = generate_pbox()

def pbox_layer(state):
    """应用P盒置换到64位状态"""
    return [state[PBOX[i]] for i in range(64)]

3. 轮密钥生成与加密流程

3.1 密钥扩展算法

PRESENT-80的密钥扩展通过循环移位、S盒代换和轮计数器异或实现：

def key_schedule(key, round_counter):
    """生成下一轮密钥"""
    # 1. 循环左移61位
    key = rotate_left(key, 61)
    
    # 2. 高4位通过S盒
    high_nibble = bits_to_int(key[:4])
    substituted = SBOX[high_nibble]
    key[:4] = int_to_bits(substituted, 4)
    
    # 3. 与轮计数器异或
    counter_bits = int_to_bits(round_counter, 5)
    for i in range(5):
        key[19-i] ^= counter_bits[4-i]
    
    return key

3.2 完整加密流程

将各组件组合成完整的加密流程：

def present_encrypt(plaintext, master_key):
    """PRESENT-80加密算法"""
    # 初始化状态和密钥
    state = int_to_bits(plaintext, 64)
    key = int_to_bits(master_key, 80)
    
    for round in range(1, 32):  # 1-31轮
        # 提取64位轮密钥
        round_key = key[:64]
        
        # 轮密钥加
        state = [s ^ k for s, k in zip(state, round_key)]
        
        # S盒代换
        state = sbox_layer(state)
        
        # P盒置换（最后一轮除外）
        if round != 31:
            state = pbox_layer(state)
        
        # 更新密钥
        key = key_schedule(key, round)
    
    # 最终轮密钥加
    final_key = key[:64]
    ciphertext = [s ^ k for s, k in zip(state, final_key)]
    
    return bits_to_int(ciphertext)

4. 测试验证与性能优化

4.1 单元测试验证

使用标准测试向量验证实现正确性：

def test_present():
    """测试加密算法正确性"""
    # 测试向量来自官方文档
    plaintext = 0x0000000000000000
    key = 0x00000000000000000000
    expected = 0x5579C1387B228445
    assert present_encrypt(plaintext, key) == expected
    
    plaintext = 0xFFFFFFFFFFFFFFFF
    key = 0xFFFFFFFFFFFFFFFFFFFF
    expected = 0xE72C46C0F5945049
    assert present_encrypt(plaintext, key) == expected

4.2 性能优化技巧

虽然Python不是高性能加密实现的首选语言，但仍有优化空间：

• 预计算轮密钥 ：提前计算所有轮密钥，减少加密时的计算量
• 位操作优化 ：使用整数的位运算替代列表操作
• 并行处理 ：对独立操作（如S盒代换）可采用多线程

优化后的轮密钥加示例：

def add_round_key_optimized(state, round_key):
    """优化后的轮密钥加"""
    state_int = bits_to_int(state)
    key_int = bits_to_int(round_key)
    return int_to_bits(state_int ^ key_int, 64)

实现PRESENT算法不仅加深了对SPN结构的理解，也为后续研究更复杂密码算法奠定了基础。在实际项目中，建议使用经过专业审计的加密库，而非自行实现的版本。