Tags: crypto rsa
Rating:
Take 1) 3) 4) modulo q, we have: pp=c1, pp+q=c3, pq=c4 thus c1∗c4=c3(modq)
similarly, we have c2∗c4=c3(modp)
Now check 4), we have: (pq+qp)modp=qpmodp=q
Till now we have p|(cc44−c3,c2∗c4−c3)
Rest is normal RSA decryption.
let D=(q−p,ϕ(p∗q)),
set e=q−p and compute d=(e/D)−1(modϕ(p∗q)/D)
we have flagD=cd5.(modp∗q)
if D is small enough, we have flagD=cd5mod(p∗q) in Z.
so flag=(cd5mod(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!}