2019西湖论剑部分WriteUp

CRYPTO2——哈夫曼之谜

题面如下

1
2
3
4
5
6
7
8
9
10
11
11000111000001010010010101100110110101111101110101011110111111100001000110010110101111001101110001000110

a:4
d:9
g:1
f:5
l:1
0:7
5:9
{:1
}:1

没有什么题目说明,所以直接从题目中获取信息。

之前了解过哈夫曼编码可以用在通讯加密中,用字母和字母出现的顺序进行编码。

所以这道题第一行的加密串应该是利用下方所给出的数据进行哈夫曼加密。

先建树

1
2
3
4
5
6
7
8
9
Character:a freq:4    encoding: 000
Character:d freq:9 encoding: 01
Character:g freq:1 encoding: 00100
Character:f freq:5 encoding: 110
Character:l freq:1 encoding: 00101
Character:0 freq:7 encoding: 111
Character:5 freq:9 encoding: 10
Character:{ freq:1 encoding: 00110
Character:} freq:1 encoding: 00111

得到结果如下,通过解码,得到字符串

f}alg55fd5f50f0ddd0d00adafdd5505d50a5{

那么好,真的很像flag的样子

但是怎么这么怪异???

很显然lg{}这四个字符都只有出现过一次,并且d和5这两个字符都出现过9次,这样在建树的时候就会出现不唯一性。

如果意识到这点就棒极了!!

整理过后这个字符串变成

flag{ddf5dfd0f05550500a5af55dd0d5d0ad}

就这么简单哈哈哈

贴出建树代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#Huffman Encoding

#Tree-Node Type
class 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
#create nodes创建叶子节点
def createNodes(freqs):
return [Node(freq) for freq in freqs]

#create Huffman-Tree创建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 = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N']
#freqs = [10,4,2,5,3,4,2,6,4,4,3,7,9,6]
chars_freqs = [('C', 2), ('G', 2), ('E', 3), ('K', 3), ('B', 4),
('F', 4), ('I', 4), ('J', 4), ('D', 5), ('H', 6),
('N', 6), ('L', 7), ('M', 9), ('A', 10)]
nodes = createNodes([item[1] for item in chars_freqs])
root = createHuffmanTree(nodes)
codes = huffmanEncoding(nodes,root)
for item in zip(chars_freqs,codes):
print 'Character:%s freq:%-2d encoding: %s' % (item[0][0],item[0][1],item[1])

Misc1 最短的路

1
2
3
4
5
6
7
8
9
#资深宅“flag{”在朋友邀请下,参加了一场聚会。
#在聚会上看到了美女“75D}”,一时心花荡漾、不能自己,坚信彼此就是天造地设的一双。
#想通过层层朋友的关系认识她,却无奈性格问题,不敢劳师动众。
#好在朋友帮忙搞到一张聚会人员关系图,如下:

[('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')]

#你能在让最少人知道的情况下,帮助flag先生联系上75D小姐姐吗?
#求节点“flag{”到“75D”的最短路径,即为flag,比如:flag{E3AliceBobXXXXXXXXXXXXXXXX75D}

真的就是最短的路,找出最短的路就好了,可以建图,也可以直接从两边找,挺简单,给的数据中很多无效数据。
最后得到flag是

E3EvelynJeffersonE9FloraPrice75D