**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

```py

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)

f.write(str(enc))

```

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:

```py

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:

![Imgur](https://i.imgur.com/kDsZXho.png)

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:

![Imgur](https://i.imgur.com/nTKeF6M.png)

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

```py

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

while(True):

if(fi[0]==se[0] or fi[0]==0 or se[0]==0):

return

else:

if(fi[0]

Great wu

yuu – Sept. 10, 2021, 10:42 a.m.

So nice!

Leonardo – Sept. 10, 2021, 11:02 a.m.

such a detailed writeup. good jobs! keep going

alihv – Sept. 10, 2021, 12:13 p.m.

what command i should write for solving with rsactftool?

rsacdftool gives me Error!

kontonfon – Sept. 10, 2021, 11:51 p.m.

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