AsisCTF 2015 - Simple Algorithm

Score: 100

根据下面的加密算法和给出的密文解出flag

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
#!/usr/bin/python

flag = '[censored]'
hflag = flag.encode('hex')
iflag = int(hflag[2:], 16)

def FAN(n, m):
    i = 0
    z = []
    s = 0
    while n > 0:
        if n % 2 != 0:
            z.append(2 - (n % 4))
        else:
            z.append(0)
        n = (n - z[i])/2
        i = i + 1
    z = z[::-1]
    l = len(z)
    for i in range(0, l):
        s += z[i] * m ** (l - 1 - i)
    return s

i = 0
r = ''
while i < len(str(iflag)):
    d = str(iflag)[i:i+2]
    nf = FAN(int(d), 3)
    r += str(nf)
    i += 2

print r

密文为

1
2712733801194381163880124319146586498182192151917719248224681364019142438188097307292437016388011943193619457377217328473027324319178428

FAN函数中使用多项式进行变换，因为这里m=3，对于相同的n产生的数字是一样的，而每次输入的数只会是0-99，所以生成个表然后暴力密文就好了。

本来其实我们并不知道每个字符对应的是2位数还是3位数，我这里直接贪心按照3位处理，结果也解出来了。

这里还有个小小的坑，算法中每次会取2个字符进行转换，那么如果字符是奇数个最后就剩下了1个字符，那么在解密的时候需要稍稍判断一下这种情况。题目中给的密文正好就是这种情况。

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
#!/usr/bin/python
# coding: utf-8

def FAN(n, m=3):
    i = 0
    z = []
    s = 0
    while n > 0:
        if n % 2 != 0:
            z.append(2 - (n % 4))
        else:
            z.append(0)
        n = (n - z[i])/2
        i = i + 1
    z = z[::-1]
    l = len(z)
    for i in range(0, l):
        s += z[i] * m ** (l - 1 - i)
    return s

cipher = '2712733801194381163880124319146586498182192151917719248224681364019142438188097307292437016388011943193619457377217328473027324319178428'
iflag = 41420276958143763286534983262388590617348245863283796564325543769593976761661865423288189
table = {}

def generate_table():
    global table
    for i in range(100):
        cipher = FAN(i)
        table[str(cipher)] = '%02d' % i

def solve(s):
    result = []

    # the segment mustn't start with 0
    if s == '':
        return ['']
    if s[0] == '0':
        return []

    for i in range(4,0,-1):
        if s[:i] in table:
            sub_result = solve(s[i:])
            for sub in sub_result:
                result.append(table[s[:i]]+sub)
            break

    return result

generate_table()
print solve('2712733801194381163880124319146586498182192151917719248224681364019142438188097307292437016388011943193619457377217328473027324319178428')

# should know the last digit can be only one bit
# don't need the first character because it must be A ~ haha !
print hex(iflag)[2:-1].decode('hex')