# Crypto CTF 2020 Writeup

14-01-2021 - 1 minute, 50 seconds -

## 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:

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().

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}$

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!}