CTF比赛中的random shuffle

井九

发布于 2024-10-12 10:41:54

3160

文章被收录于专栏：四楼没电梯四楼没电梯

在CTF（Capture The Flag）比赛中，随机洗牌题型的变形多种多样，不仅考验选手的逻辑推理和编程能力，还能考验对算法和数据结构的理解。本文将通过几个不同的场景，详细解析随机洗牌的变形及其解题思路。

随机洗牌的基本概念

随机洗牌通常指对一个序列进行重排，使得每个元素都有可能出现在任意位置。洗牌过程常常依赖于一个seed（种子），以确保每次洗牌的随机性和可预测性。

示例代码：反序洗牌

下面是一个简单的反序洗牌实现，使用给定的seed和已洗牌的消息来还原原始消息：

import random

def unshuffle(seed, msg):
    msg = list(msg)
    leth = len(msg)
    lis = []
    random.seed(seed)
    
    for i in range(leth):
        lis.append(i)
        
    random.shuffle(lis)
    tplist = [0] * leth

    for i in range(len(lis)):
        e = lis.index(i)
        tplist[i] = msg[e]

    return "".join(tplist)

if __name__ == "__main__":
    seed = "M0n4rch1"
    unflag = "53cfce1d1c3g{e}84565f20eef7alfe482165c"
    print(unshuffle(seed, unflag))

CTF题型实例分析

1. 题目一：基础洗牌还原

在某次CTF中，给出一段经过洗牌的字符串，要求还原成原始字符串。洗牌过程使用了一个特定的seed。例如，已知洗牌后的字符串为 53cfce1d1c3g{e}84565f20eef7alfe482165c，seed为 M0n4rch1。

解题思路：

通过调用反序洗牌函数，传入已洗牌的字符串和seed，获取原始字符串。

示例结果

运行代码后，输出的结果将是原始字符串，这样我们就能够获得“Flag”。

2. 题目二：复杂洗牌解密

在另一场CTF中，给出的字符串经过多次洗牌，且包含了多个随机seed。选手需要通过分析已知的洗牌规律和seed，逆推还原原始字符串。

解题思路：

记录每次洗牌的seed和洗牌过程。
使用循环和反序洗牌逻辑，逐步还原字符串。

示例代码

def multi_unshuffle(seeds, msg):
    for seed in seeds:
        msg = unshuffle(seed, msg)
    return msg

if __name__ == "__main__":
    seeds = ["M0n4rch1", "An0therSeed"]
    unflag = "53cfce1d1c3g{e}84565f20eef7alfe482165c"
    original_message = multi_unshuffle(seeds, unflag)
    print(f"Restored message: {original_message}")

3. 题目三：带有条件的洗牌

有些CTF题目会引入条件洗牌，比如根据某些特定字符或规则对洗牌进行限制。例如，给定的字符串中某些字符不能移动，选手需要在洗牌过程中考虑这些条件。

解题思路：

先找到不动的字符位置，并记录它们。
对其他字符进行洗牌，并在最终结果中将不动的字符放回原位。

示例代码

def conditional_unshuffle(seed, msg, fixed_positions):
    msg = list(msg)
    leth = len(msg)
    lis = []
    random.seed(seed)
    
    for i in range(leth):
        if i not in fixed_positions:
            lis.append(i)
            
    random.shuffle(lis)
    tplist = [''] * leth

    for i in range(leth):
        if i in fixed_positions:
            tplist[i] = msg[i]
        else:
            e = lis.pop(0)
            tplist[i] = msg[e]

    return "".join(tplist)

if __name__ == "__main__":
    seed = "M0n4rch1"
    unflag = "53cfce1d1c3g{e}84565f20eef7alfe482165c"
    fixed_positions = [2, 5]  # 固定位置
    print(conditional_unshuffle(seed, unflag, fixed_positions))

4. 题目四：多维度洗牌

在一些更复杂的CTF题目中，洗牌不仅局限于一维字符串，可能会涉及多维数据结构，如矩阵或列表的列表。这种情况下，洗牌的实现和逆操作会更加复杂。

解题思路：

将多维数据结构展平，进行洗牌操作，然后在还原时再将数据结构恢复成原来的形态。

示例代码

def matrix_unshuffle(seed, matrix):
    flattened = [elem for row in matrix for elem in row]
    original_len = len(flattened)
    random.seed(seed)
    
    indices = list(range(original_len))
    random.shuffle(indices)

    unshuffled = [''] * original_len
    for i, index in enumerate(indices):
        unshuffled[index] = flattened[i]

    # 重建矩阵
    size = int(len(unshuffled) ** 0.5)
    return [unshuffled[i * size:(i + 1) * size] for i in range(size)]

if __name__ == "__main__":
    seed = "M0n4rch1"
    matrix = [['a', 'b'], ['c', 'd']]
    shuffled_matrix = matrix_unshuffle(seed, matrix)
    print(f"Unshuffled Matrix: {shuffled_matrix}")