Open‑AdvancedFactorWar [300pts] - Cryptography Write-up#

1
import subprocess, math
2
from sympy import mod_inverse
3

4
out = subprocess.check_output("openssl rsa -in public_main.pem -pubin -modulus -noout", shell=True, text=True)
5
N_main = int(out.strip().split('=')[1],16)
6

7
aux1 = int(subprocess.check_output("openssl rsa -in stage3_pub_aux1.pem -pubin -modulus -noout", shell=True, text=True).split('=')[1],16)
8
aux2 = int(subprocess.check_output("openssl rsa -in stage3_pub_aux2.pem -pubin -modulus -noout", shell=True, text=True).split('=')[1],16)
9

10
p1 = math.gcd(N_main, aux1)
11
p2 = math.gcd(N_main, aux2)
12

13
s_ok=int.from_bytes(open('stage4_sign_ok.bin','rb').read(),'big')
14
s_faulty=int.from_bytes(open('stage4_sign_faulty.bin','rb').read(),'big')
15
G = math.gcd(N_main, s_ok - s_faulty)
16

17
r = G//(p1*p2)
18
p4 = N_main // (p1*p2*r)
19

20
c = int.from_bytes(open('final_cipher.bin','rb').read(),'big')
21
E = 65537
22
primes = [p1,p2,p4]
23

24
d_vals=[]
25
for p in primes:
26
    d = mod_inverse(E, p-1)
27
    d_vals.append(d)
28

29
a=[]
30
for (p,d) in zip(primes,d_vals):
31
    a.append(pow(c, d, p))
32

33
from math import prod
34

35
def crt(values, moduli):
36
    M=1
37
    x=0
38
    for n_i, a_i in zip(moduli, values):
39
        M *= n_i
40
    x=0
41
    m=1
42
    for n_i,a_i in zip(moduli, values):
43
        k = ( (a_i - x) * mod_inverse(m, n_i) ) % n_i
44
        x += m*k
45
        m *= n_i
46
    return x
47

48
m_partial = crt(a, primes)
49
msg_bytes = m_partial.to_bytes((m_partial.bit_length()+7)//8,'big')
50

51
try:
52
    print(msg_bytes.decode())
53
except Exception as e:
54
    print('decode error',e)

1
flag{multi_pr1me_cr4ck_by_RSA_CRT_47e1cc2ddc}