Loading [MathJax]/jax/output/HTML-CSS/jax.js

Tags: crypto rsa 

Rating:

Facts from server

  1. ppmodq=c1
  2. qqmodp=c2
  3. (p+q)p+qmod(pq)=c3
  4. (pq+qp)mod(pq)=c4
  5. flagqpmod(pq)=c5
  6. flag = bytes_to_long(FLAG) (c1,c2,c3,c4,c5 are some constants)

Get p & q

Take 1) 3) 4) modulo q, we have: pp=c1, pp+q=c3, pq=c4 thus c1c4=c3(modq)

similarly, we have c2c4=c3(modp)

Now check 4), we have: (pq+qp)modp=qpmodp=q and (pq+qp)modq=pqmodq=p So c4=(pq+qp)mod(pq)=p+q combine this with 3), we have cc44=c3(modpq)

Till now we have p|(cc44c3,c2c4c3) and q|(cc44c3,c1c4c3) if both GCDs are primes. then we have p=(cc44c3,c2c4c3) and q=(cc44c3,c1c4c3). Otherwise, you can use trial division of small primes (<500 is enough) to get prime p and q.

Decryption

Rest is normal RSA decryption.

let D=(qp,ϕ(pq)),

set e=qp and compute d=(e/D)1(modϕ(pq)/D)

we have flagD=cd5.(modpq)

if D is small enough, we have flagD=cd5mod(pq) in Z.

so flag=(cd5mod(pq))1/D, and FLAG = long_to_bytes(flag).

Code

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)

FLAG:

ASIS{Th3_gr0wth_0f_cryp7ogrAphIc_t3chnolo9y_h4s_ra1sed_a_nUmBer_oF_l394l_i55ueS_iN_the_informat1On_Ag3!}