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
frommsg
. - Calculate
c
fromm
.
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!}