Tags: crypto 

Rating: 5.0

Hello every body ! Although I only solved this problem a few hours after the contest ended, I think this is an interesting problem so I want to write it up for everyone to exchange and learn.

First, we will analyze a bit about the code of the challenge.py file

from Crypto.Util.number import *

e = 65537

with open('n', 'rb') as f:
n = int(f.read())

with open('secret', 'rb') as f:
secret_msg = f.read()

pads = [b'\x04', b'\x02', b'\x00', b'\x01', b'\x03']

with open('out.txt', 'w') as f:
for i in range(len(pads)):
for j in range(len(pads)):
msg = pads[j] * (i + 1) + b'TMUCTF' + pads[len(pads) - j - 1] * (i + 1)
enc = pow(bytes_to_long(msg), e, n)
f.write(str(enc) + '\n')

enc = pow(bytes_to_long(secret_msg), e, n)


After studying the code a bit, I decided to print out 25 unmodulated msg values ​​to see what the rule was.

So to do this, I wrote a file thu.py to list all these 25 msg, specifically as follows:

import binascii

from Crypto.Util.number import bytes_to_long, long_to_bytes
a = b'\x01\x00\x00'
# print(ord('T'))
# print(ord('M'))
# print(ord('U'))
# print(ord('C'))
# print(ord('T'))
# print(ord('F'))
# print(binascii.hexlify(a))
# print(bytes_to_long(a))
pads = [b'\x04', b'\x02', b'\x00', b'\x01', b'\x03']
with open('template.txt','w') as f:
for i in range(len(pads)):
for j in range(len(pads)):
msg = pads[j]*(i+1) + b'TMUCTF' + pads[len(pads) - j - 1] * (i + 1)
# print('Thuong: {0} -- Long: {1}'.format(msg,bytes_to_long(msg)))
fi = msg
se = bytes_to_long(msg)
th = str(msg) + "---" + str(se)
f.write(th + '\n')

And the result is:


Let's say these 25 numbers are $FF[1],FF[2],...,FF[25]$. Then, from the values $FF[3],FF[8],FF[13],FF[18],FF[23]$

I have derived the formula to determine the value of n. One of the keys to solving the problem !

First, we have a note as follows: {T,M,U,C,T,F} = {0x84,0x77,0x85,0x67,0x84,0x70}

Set $b=16$ and $G =8b^{11}+4b^{10}+7b^{9}+7b^{8}+8b^{7}+5b^{6}+6b^{5}+7b^{4}+8b^{3}+4b^{2}+7b^{1}+0b^{0}$

Then we have

+ $FF[3]=b^{2}G$
+ $FF[8]=b^{4}G$
+ $FF[13]=b^{6}G$
+ $FF[18]=b^{8}G$
+ $FF[23]=b^{10}G$

Next, we put the first 25 values in the output.txt file as $F[1],F[2],...,F[25]$ respectively.

.Then, we have the following system of modulo equations:


We realize that because $b^{2e}$ is an extremely large value, we cannot calculate that gcd directly, so to find this gcd value, we have to go through a vector, specifically as follows:

Set $fi=(F[3],-F[8]),se=(F[8],-F[13]),th=(F[13],-F[18]),fo=(F[18],-F[23])$

Then we build the algorithm to calculate gccd through vector as follows (The essence of this algorithm is just Euclidean algorithm):

from Crypto.Util.number import GCD
##########Pha an ##############

# Dat b = 16
# Ta co:
# FF[3].b^{2e} = FF[8] (mod n)
# FF[8].b^{2e} = FF[13] (mod n)
# FF[13].b^{2e} = FF[18] (mod n)
# FF[18].b^{2e} = FF[23] (mod n)
# => n | GCD(FF[3].b^{2e}-FF[8],FF[8].b^{2e}-FF[13],...)
# Y tuong: Tim GCD(FF[3].b^{2e}-FF[8],FF[8].b^{2e}-FF[13])
# Dat fi = (FF[3],-FF[8]) ; se = (FF[8];-FF[13])
def GCD_pair(fi,se):
if(fi[0]==se[0] or fi[0]==0 or se[0]==0):

psycholog1stSept. 10, 2021, 10:38 a.m.

Great wu

yuuSept. 10, 2021, 10:42 a.m.

So nice!

LeonardoSept. 10, 2021, 11:02 a.m.

such a detailed writeup. good jobs! keep going

alihvSept. 10, 2021, 12:13 p.m.

what command i should write for solving with rsactftool?
rsacdftool gives me Error!

kontonfonSept. 10, 2021, 11:51 p.m.

I have updated command lines of rsacctftool, you can try it again !