Maojui

Seccon 2017 - Ps & Qs (Crypto, 200)

2017-12-19

Ps and Qs

Challenge

1
2
3
4
5
Ps and Qs
Decrypt it.
update: we fixed the flag, please try to submit again.

psqs1-0dd2921c9fbdb738e51639801f64164dd144d0771011a1dc3d55da6fbcb0fa02.zip (pass:seccon2017)

Given : cipher, pub1, pub2

Load Key

1
2
3
4
5
6
7
import Crypto.PublicKey
from Crypto.PublicKey import RSA

pub1 = open('pub1.pub','r').read()
pub2 = open('pub2.pub','r').read()
pkey1 = RSA.importKey(pub1)
pkey2 = RSA.importKey(pub2)

Solve

I found that, they are same exponent = 65537 (0x10001) with different modulus N

Try found gcd of there N

Bingo!!

1
2
3
4
5
6
7
8
9
10
11
12
13
from libnum import *

p = gcd(pkey1.n,pkey2.n)
q = pkey1.n//p

assert p*q == pkey1.n
e,n = pkey1.e,pkey1.n
phi = (p-1)*(q-1)
d = invmod(e,phi)
c = s2n(open('cipher','rb').read())
m = pow(c,d,n)

print(n2s(m))

At the last line, We get:

SECCON{1234567890ABCDEF}

Tags: RSA factor
← Seccon 2017 - Vigenere3d (Crypto, 100) Codegate 2018 - RSAbaby (Crypto, 349) →