## Trailing Bits

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

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

Flag: `CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}`

## Amsterdam

There are two stages in `encrypt()`

.

- Calculate
`m`

from`msg`

. - 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}\]

```
from Crypto.Util.number import *
from functools import reduce
import operator
from output import enc
# enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493
def comb(n, k):
if k > n :
return 0
k = min(k, n - k)
u = reduce(operator.mul, range(n, n - k, -1), 1)
d = reduce(operator.mul, range(1, k + 1), 1)
return u // d
def enc_to_m(enc):
mbits = ''
two = 0
while enc > 0:
if enc % 3 == 0:
mbits = f'{two}{mbits}'
elif enc % 3 == 1:
mbits = f'{1-two}{mbits}'
two = 0
else:
mbits = f'{1-two}{mbits}'
two = 1
enc //= 3
return int(mbits, 2)
def m_to_msg(m, n, k):
m = bin(m)[2:]
msg = 0
for i in range(2, n+1):
if m[i-1] == '1':
msg += comb(n-i, k)
k -= 1
return msg
m = enc_to_m(enc)
n = len(bin(m)[2:])
for k in range(n):
msg = m_to_msg(m, n, k)
try:
msg = bytes.fromhex(f'{msg:x}')
if b'CCTF{' in msg:
print(msg)
break
except:
pass
```

Flag: `CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}`