PRESENT密码算法置换步骤的Python实现及逆置换求解

置换（Permutation）实现 #

核心规则（0-based索引） #

PRESENT的置换逻辑基于线性映射：

• 对0~62位的每一位，置换后的目标位置为 (4 * i) % 63（i为原始位置）
• 第63位保持原位不变

代码实现 #

def present_permutation(plain_bits):
    assert len(plain_bits) == 64, "输入必须是64位二进制字符串"
    result = [''] * 64
    for i in range(64):
        if i == 63:
            result[i] = plain_bits[i]
        else:
            target_pos = (4 * i) % 63
            result[target_pos] = plain_bits[i]
    return ''.join(result)

逻辑说明 #

1. 先校验输入长度，避免非法数据
2. 创建64位空列表存储结果，通过遍历原始位置，按规则将每一位放到目标位置
3. 第63位直接保留，无需计算

逆置换（Inverse Permutation）实现 #

核心规则 #

逆置换需要找到置换映射的逆运算：

• 4和63互质，其模63的逆元为16（因4*16=64 ≡1 mod63）
• 对0~62位的每一位，原始位置为 (16 * pos) % 63（pos为置换后的位置）
• 第63位仍保持原位

代码实现 #

def present_inv_permutation(cipher_bits):
    assert len(cipher_bits) == 64, "输入必须是64位二进制字符串"
    result = [''] * 64
    for pos in range(64):
        if pos == 63:
            result[pos] = cipher_bits[pos]
        else:
            original_pos = (16 * pos) % 63
            result[original_pos] = cipher_bits[pos]
    return ''.join(result)

验证方法 #

通过置换后再逆置换，可验证正确性：

test_bits = '1001010001100010000001010100100110100100001100110110001101010000'
permuted = present_permutation(test_bits)
inv_permuted = present_inv_permutation(permuted)
print(inv_permuted == test_bits)  # 输出True表示验证通过

关键注意点 #

1. 索引一致性：确保置换、逆置换与你已实现的代换步骤使用相同的索引规则（0-based/1-based），若代换用1-based，只需将索引加1计算后再减1即可适配
2. 边界处理：第63位是特殊边界，必须单独处理，避免映射错误
3. 逆元计算：线性置换的逆运算核心是求系数的模逆元，这里通过试算得到16，也可通过扩展欧几里得算法自动计算

内容的提问来源于stack exchange，提问作者Rafi Sakib