Processing math: 0%

Tags: crypto rsa 

Rating:

Facts from server

  1. ppmod
  2. q ^ q \bmod p = c_2
  3. (p+q) ^ {p+q} \bmod (p*q) = c_3
  4. (p ^ q + q ^ p) \bmod (p*q) = c_4
  5. flag ^ {q-p} \bmod (p*q) = c_5
  6. flag = bytes_to_long(FLAG) (c_1,c_2,c_3,c_4,c_5 are some constants)

Get p & q

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.

Decryption

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).

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!}