2019 西湖论剑 CTF 解题笔记

# Tree-Node Typeclass Node:    def __init__(self, freq):        self.left = None        self.right = None        self.father = None        self.freq = freq    def isLeft(self):        return self.father.left == self# 创建叶子节点def createNodes(freqs):    return [Node(freq) for freq in freqs]# 创建 Huffman 树def createHuffmanTree(nodes):    queue = nodes[:]    while len(queue) > 1:        queue.sort(key=lambda item: item.freq)        node_left = queue.pop(0)        node_right = queue.pop(0)        node_father = Node(node_left.freq + node_right.freq)        node_father.left = node_left        node_father.right = node_right        node_left.father = node_father        node_right.father = node_father        queue.append(node_father)    queue[0].father = None    return queue[0]# Huffman 编码def huffmanEncoding(nodes, root):    codes = [''] * len(nodes)    for i in range(len(nodes)):        node_tmp = nodes[i]        while node_tmp != root:            if node_tmp.isLeft():                codes[i] = '0' + codes[i]            else:                codes[i] = '1' + codes[i]            node_tmp = node_tmp.father    return codes

if __name__ == '__main__':    chars_freqs = [('a', 4), ('d', 9), ('g', 1), ('f', 5), ('l', 1),                   ('0', 7), ('5', 9), ('{', 1), ('}', 1)]    nodes = createNodes([item[1] for item in chars_freqs])    root = createHuffmanTree(nodes)    codes = huffmanEncoding(nodes, root)    dit = {}    for item in zip(chars_freqs, codes):        dit[item[1]] = item[0][0]        print('Character:%s freq:%-2d   encoding: %s' % (item[0][0], item[0][1], item[1]))        line = "11000111000001010010010101100110110101111101110101011110111111100001000110010110101111001101110001000110"    flag = ""    while line:        for key, value in dit.items():            if key == line[:len(key)]:                line = line[len(key):]                flag = flag + value    print(flag)

dit = {    "000": "a",    "01": "5",    "00100": "{",    "110": "f",    "00101": "g",    "111": "0",    "10": "d",    "00110": "}",    "00111": "l"}line = "11000111000001010010010101100110110101111101110101011110111111100001000110010110101111001101110001000110"flag = ""while line:    for key, value in dit.items():        if key == line[:len(key)]:            line = line[len(key):]            flag = flag + valueprint(flag)

#coding:utf-8map_edges = [('FloraPrice','E11'),('FloraPrice','E9'),('FloraPrice','75D}'),('NoraFayette','E11'),('NoraFayette','E10'),('NoraFayette','E13'),('NoraFayette','E12'),('NoraFayette','E14'),('NoraFayette','E9'),('NoraFayette','E7'),('NoraFayette','E6'),('E10','SylviaAvondale'),('E10','MyraLiddel'),('E10','HelenLloyd'),('E10','KatherinaRogers'),('VerneSanderson','E7'),('VerneSanderson','E12'),('VerneSanderson','E9'),('VerneSanderson','E8'),('E12','HelenLloyd'),('E12','KatherinaRogers'),('E12','SylviaAvondale'),('E12','MyraLiddel'),('E14','SylviaAvondale'),('E14','75D}'),('E14','KatherinaRogers'),('FrancesAnderson','E5'),('FrancesAnderson','E6'),('FrancesAnderson','E8'),('FrancesAnderson','E3'),('DorothyMurchison','E9'),('DorothyMurchison','E8'),('EvelynJefferson','E9'),('EvelynJefferson','E8'),('EvelynJefferson','E5'),('EvelynJefferson','E4'),('EvelynJefferson','E6'),('EvelynJefferson','E1'),('EvelynJefferson','E3'),('EvelynJefferson','E2'),('RuthDeSand','E5'),('RuthDeSand','E7'),('RuthDeSand','E9'),('RuthDeSand','E8'),('HelenLloyd','E11'),('HelenLloyd','E7'),('HelenLloyd','E8'),('OliviaCarleton','E11'),('OliviaCarleton','E9'),('EleanorNye','E5'),('EleanorNye','E7'),('EleanorNye','E6'),('EleanorNye','E8'),('E9','TheresaAnderson'),('E9','PearlOglethorpe'),('E9','KatherinaRogers'),('E9','SylviaAvondale'),('E9','MyraLiddel'),('E8','TheresaAnderson'),('E8','PearlOglethorpe'),('E8','KatherinaRogers'),('E8','SylviaAvondale'),('E8','BrendaRogers'),('E8','LauraMandeville'),('E8','MyraLiddel'),('E5','TheresaAnderson'),('E5','BrendaRogers'),('E5','LauraMandeville'),('E5','CharlotteMcDowd'),('E4','CharlotteMcDowd'),('E4','TheresaAnderson'),('E4','BrendaRogers'),('E7','TheresaAnderson'),('E7','SylviaAvondale'),('E7','BrendaRogers'),('E7','LauraMandeville'),('E7','CharlotteMcDowd'),('E6','TheresaAnderson'),('E6','PearlOglethorpe'),('E6','BrendaRogers'),('E6','LauraMandeville'),('E1','LauraMandeville'),('E1','BrendaRogers'),('E3','TheresaAnderson'),('E3','BrendaRogers'),('E3','LauraMandeville'),('E3','CharlotteMcDowd'),('E3','flag{'),('E2','LauraMandeville'),('E2','TheresaAnderson'),('KatherinaRogers','E13'),('E13','SylviaAvondale')]class DijkstraExtendPath():    def __init__(self, node_map):        self.node_map = node_map        self.node_length = len(node_map)        self.used_node_list = []        self.collected_node_dict = {}    def __call__(self, from_node, to_node):        self.from_node = from_node        self.to_node = to_node        self._init_dijkstra()        return self._format_path()    def _init_dijkstra(self):        self.used_node_list.append(self.from_node)        self.collected_node_dict[self.from_node] = [0, -1]        for index1, node1 in enumerate(self.node_map[self.from_node]):            if node1:                self.collected_node_dict[index1] = [node1, self.from_node]        self._foreach_dijkstra()    def _foreach_dijkstra(self):        if len(self.used_node_list) == self.node_length - 1:            return        for key, val in self.collected_node_dict.items():            if key not in self.used_node_list and key != self.to_node:                self.used_node_list.append(key)            else:                continue            for index1, node1 in enumerate(self.node_map[key]):                if node1 and index1 in self.collected_node_dict and self.collected_node_dict[index1][0] > node1 + val[0]:                    self.collected_node_dict[index1][0] = node1 + val[0]                    self.collected_node_dict[index1][1] = key                elif node1 and index1 not in self.collected_node_dict:                    self.collected_node_dict[index1] = [node1 + val[0], key]        self._foreach_dijkstra()    def _format_path(self):        node_list = []        temp_node = self.to_node        node_list.append((temp_node, self.collected_node_dict[temp_node][0]))        while self.collected_node_dict[temp_node][1] != -1:            temp_node = self.collected_node_dict[temp_node][1]            node_list.append((temp_node, self.collected_node_dict[temp_node][0]))        node_list.reverse()        return node_listdef set_node_map(node_map, node, node_list):    for x, y in node_list:        node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] = 1

if __name__ == "__main__":    node = []    node_list = map_edges    for x, y in node_list:        node.append(x)        node.append(y)    node = list(set(node))    node_map = [[0 for val in range(len(node))] for val in range(len(node))]    set_node_map(node_map, node, node_list)        from_node = node.index('flag{')    to_node = node.index('75D}')        dijkstrapath = DijkstraExtendPath(node_map)    path = dijkstrapath(from_node, to_node)        flag = ""    for x, y in path:        flag = flag + node[x]    print(flag)