Trailing Bits

The description says that both of head and tail bits are lost, so I just tried adding some bits both of them.

 1from itertools import product
 2with open('output.txt') as f:
 3    s = f.read().strip()
 4
 5for i, j in product(range(10), repeat=2):
 6    try:
 7        bits = '1'*i + s + '1'*j
 8        x = bytes.fromhex(f'{int(bits, 2):x}')
 9        if b'CCTF{' in x:
10            print(x)
11            break
12    except:
13        pass

Flag: CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}

Amsterdam

There are two stages in encrypt().

  1. Calculate m from msg.
  2. Calculate c from m.

We need to carry out the inverse operation for each stage.

Decrypt m from c

In encrypt(), c is decided by lower 2 bits of m. Conversely, we can reconstruct m using c. This is the most difficult part in this challenge.

Thinking c in ternary, each trit indicates a piece of information about the lower 2 bits of m. We can reconstruct by comparing m and c from lower digit.

Decrypt msg from m

Now we know m, we can also calculate the value of n because this value is equal to the bit length of m. Furthermore, since n is small enough, we can search for k using brute-force. All that is left is to recover msg by calculating:

$$ {\rm msg} = \sum_{2 \le i \le n, m_i=1} \binom{n-i}{k} $$

 1from Crypto.Util.number import *
 2from functools import reduce
 3import operator
 4from output import enc
 5
 6# enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493
 7
 8def comb(n, k):
 9 if k > n :
10  return 0
11 k = min(k, n - k)
12 u = reduce(operator.mul, range(n, n - k, -1), 1)
13 d = reduce(operator.mul, range(1, k + 1), 1)
14 return u // d 
15
16
17def enc_to_m(enc):
18    mbits = ''
19    two = 0 
20    while enc > 0:
21        if enc % 3 == 0:
22            mbits = f'{two}{mbits}'
23        elif enc % 3 == 1:
24            mbits = f'{1-two}{mbits}'
25            two = 0
26        else:
27            mbits = f'{1-two}{mbits}'
28            two = 1
29        enc //= 3
30    return int(mbits, 2)
31
32
33def m_to_msg(m, n, k):
34    m = bin(m)[2:]
35    msg = 0
36    for i in range(2, n+1):
37        if m[i-1] == '1':
38            msg += comb(n-i, k)
39            k -= 1
40
41    return msg
42
43
44 
45m = enc_to_m(enc)
46n = len(bin(m)[2:])
47for k in range(n):
48    msg = m_to_msg(m, n, k)
49    try:
50        msg = bytes.fromhex(f'{msg:x}')
51        if b'CCTF{' in msg:
52            print(msg)
53            break
54    except:
55        pass

Flag: CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}