Tags: crypto rsa
Rating:
Take 1) 3) 4) modulo q, we have: p^p = c_1, p^{p+q} = c_3, p^q = c_4 thus c_1*c_4=c_3 \pmod q
similarly, we have c_2*c_4=c_3 \pmod p
Now check 4), we have: (p^q+q^p) \bmod p = q^p \bmod p = q and (p^q+q^p) \bmod q = p^q \bmod q = p So c_4 = (p^q+q^p) \bmod (p*q) = p+q combine this with 3), we have c_4^{c_4}=c_3 \pmod {p*q}
Till now we have p|(c_4^{c_4}-c_3, c_2*c_4-c_3) and q|(c_4^{c_4}-c_3, c_1*c_4-c_3) if both GCDs are primes. then we have p=(c_4^{c_4}-c_3, c_2*c_4-c_3) and q=(c_4^{c_4}-c_3, c_1*c_4-c_3). Otherwise, you can use trial division of small primes (<500 is enough) to get prime p and q.
Rest is normal RSA decryption.
let D=(q-p,\phi(p*q)),
set e=q-p and compute d=(e/D)^{-1} \pmod {\phi(p*q)/D}
we have flag^D = c_5^d. \pmod {p*q}
if D is small enough, we have flag^D = c_5^d \bmod (p*q) in Z.
so flag = (c_5^d \bmod (p*q))^{1/D}, and FLAG = long_to_bytes(flag).
from gmpy import *
from Crypto.Util.number import long_to_bytes, size
def get_flag(c1, c2, c3, c4, c5):
p = gcd(c2*c4-c3, pow(c4, c4, c2*c4-c3)-c3)
q = gcd(c1*c4-c3, pow(c4, c4, c1*c4-c3)-c3)
# trial division using primes in range (0,500)
for x in prm500:
while p % x == 0:
p /= x
while q % x == 0:
q /= x
assert(is_prime(p))
assert(is_prime(q))
# decryption
n, e = p*q, q-p
phi = (p-1)*(q-1)/gcd(p-1, q-1)
D = gcd(e, phi)
d = invert(e/D, phi/D)
flagD = pow(c5, d, n) # flag**D (mod n)
flag, bExact = root(flagD, D)
# retry if unlucky
if not bExact:
return None
# Got flag!
return long_to_bytes(flag)
ASIS{Th3_gr0wth_0f_cryp7ogrAphIc_t3chnolo9y_h4s_ra1sed_a_nUmBer_oF_l394l_i55ueS_iN_the_informat1On_Ag3!}