[LINE CTF 2022] X Factor

You can check that signature is made by $sig = pow(M, d, N)$ without hashing by check $M = pow(sig, e, N)$.

for a given message $M_1, M_2, \dots, M_7$, you have to find $e_1, \dots, e_7$ such that $\prod_{1 \leq i \leq 7} M_i^{e_i} = \text{0x686178656c696f6e}$.

It seems hard but when you factorize $M_1, M_2, \dots, M_7$ and $\text{0x686178656c696f6e}$, you can fit $e_1, \dots, e_7$ by based on each primes. I fit it by hands,,

solver.py

from Crypto.Util.number import *
#from sage.all import *

e = 0x10001

plains = [0x945d86b04b2e7c7, 0x5de2, 0xa16b201cdd42ad70da249, 0x6d993121ed46b, 0x726fa7a7, 0x31e828d97a0874cff, 0x904a515]

target = 7521425229691318126
# 7521425229691318126 = 2 * 197 * 947 * 2098711 * 9605087

#ps = [2,197,947,2098711,9605087]
'''
for p in plains:
print(factor(p))

print("-----------")
'''
x = plains[1] * plains[5] * plains[3] * plains[3] * plains[6] * plains[6] // plains[4] // plains[2] // plains[0]

s4 = 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb

sig = s1 * s5 * s3 * s3 * s6 * s6 * pow(s4,-1,N) * pow(s2,-1,N) * pow(s0,-1,N) % N

print(pow(sig, e, N) == 0x686178656c696f6e)

print(hex(sig))

print('LINECTF{'+hex(sig)[-32:]+'}')

I made a dumb mistakes during ctf, I don't take a modulo operation while recover a signiture🤣

#### 'CTF > Crypto' 카테고리의 다른 글

 [LINE CTF 2022] lazy_stek  (0) 2022.03.27 2022.03.27 2022.03.27 2022.03.27 2022.03.22 2022.03.22 2022.03.22
댓글 쓰기