Bad62 [100 pts] - Cryptography Write-up#

1
import base62
2

3
flag = input('Flag: ')
4
encoded = base62.encodebytes(flag.encode())
5
print(encoded.lower())

1
cbm6okchgcvxtifbvfd68lmyh38nqxnjxmdtbathtougtkxdmwux9tcmo6rs0j7uuf

1
ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
2
VAL = {c: i for i, c in enumerate(ALPH)}
3
BASE = 62
4

5
def base62_decode(s: str) -> int:
6
    v = 0
7
    for ch in s:
8
        v = v * BASE + VAL[ch]
9
    return v
10

11
def to_bytes_be(n: int, L: int) -> bytes:
12
    b = bytearray(L)
13
    for i in range(L - 1, -1, -1):
14
        b[i] = n & 0xFF
15
        n >>= 8
16
    return bytes(b)
17

18
def is_printable_ascii(bs: bytes) -> int:
19
    score = 0
20
    for b in bs:
21
        if 32 <= b <= 126:
22
            score += 1
23
    return score
24

25
def prefix_bonus(bs: bytes, tgt=b"flag{") -> int:
26
    m = min(len(bs), len(tgt))
27
    bonus = 0
28
    for i in range(m):
29
        if bs[i] == tgt[i]:
30
            bonus += 5
31
    return bonus
32

33
def try_decode_ascii(M: int, L_guess: int):
34
    import re
35
    for dL in (-2, -1, 0, 1, 2, 3):
36
        L = max(1, L_guess + dL)
37
        bs = to_bytes_be(M, L)
38
        try:
39
            s = bs.decode('ascii')
40
        except:
41
            continue
42
        if re.fullmatch(r"^flag\{.*_[0-9]{10}\}$", s):
43
            return s
44
        m = re.search(r"flag\{[^}]+\}", s)
45
        if m:
46
            return m.group(0)
47
    return None
48

49
def solve_bad62_head(encoded: str, group_size=6, keep_top=2000):
50
    N = len(encoded)
51
    letter_positions = [i for i, c in enumerate(encoded) if c.isalpha()]
52

53
    pow62 = [1] * (N + 1)
54
    for k in range(1, N + 1):
55
        pow62[k] = pow62[k - 1] * BASE
56

57
    diffs = {i: 26 * pow62[N - 1 - i] for i in letter_positions}
58
    M0 = base62_decode(encoded)
59
    L_guess = max(1, (M0.bit_length() + 7) // 8)
60

61
    groups = []
62
    pos_sorted = sorted(letter_positions)
63
    for i in range(0, len(pos_sorted), group_size):
64
        groups.append(pos_sorted[i:i + group_size])
65

66
    states = [(0, 0)]
67

68
    for g_index, grp in enumerate(groups):
69
        adds = [0]
70
        for p in grp:
71
            d = diffs[p]
72
            new_adds = []
73
            for a in adds:
74
                new_adds.append(a)
75
                new_adds.append(a + d)
76
            adds = new_adds
77

78
        head_need = min(L_guess, (g_index + 1) * group_size)
79

80
        new_states = []
81
        for (old_score, total_sub) in states:
82
            base_val = M0 - total_sub
83
            if base_val <= 0:
84
                continue
85
            for add in adds:
86
                M = base_val - add
87
                if M <= 0:
88
                    continue
89
                bs = to_bytes_be(M, L_guess)
90
                head = bs[:head_need]
91
                s = is_printable_ascii(head) + prefix_bonus(head)
92
                new_states.append((s, total_sub + add))
93

94
        new_states.sort(key=lambda x: x[0], reverse=True)
95
        states = new_states[:keep_top]
96

97
    for (score, total_sub) in states:
98
        M = M0 - total_sub
99
        flag = try_decode_ascii(M, L_guess)
100
        if flag:
101
            return flag
102

103
    return None
104

105
if __name__ == "__main__":
106
    enc = "cbm6okchgcvxtifbvfd68lmyh38nqxnjxmdtbathtougtkxdmwux9tcmo6rs0j7uuf"
107
    ans = solve_bad62_head(enc, group_size=6, keep_top=2000)
108
    print(ans)