[HITCON CTF 2019 Quals] Lost Modulus Again

prob.py

from Crypto.Util.number import *


class Key:
    def __init__(self, bits):
        assert bits >= 512
        self.p = getPrime(bits)
        self.q = getPrime(bits)
        self.n = self.p * self.q
        self.e = 0x100007
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
        self.dmp1 = self.d%(self.p-1)
        self.dmq1 = self.d%(self.q-1)
        self.iqmp = inverse(self.q, self.p)
        self.ipmq = inverse(self.p, self.q)

    def encrypt(self, data):
        num = bytes_to_long(data)
        result = pow(num, self.e, self.n)
        return long_to_bytes(result)

    def decrypt(self, data):
        num = bytes_to_long(data)
        v1 = pow(num, self.dmp1, self.p)
        v2 = pow(num, self.dmq1, self.q)
        result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n
        return long_to_bytes(result)

    def __str__(self):
        return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)

def main():
    key = Key(1024)
    flag = open('flag').read()
    encrypt_flag = key.encrypt(flag)
    assert key.decrypt(encrypt_flag) == flag
    print key
    print encrypt_flag.encode('hex')


if __name__ == '__main__':
    main()

output

6
84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096

In this problem, $e, d, iqmp, ipmq$ is given. To recover flag from encrypt_flag, it is enough to find $n$.

 

Let's consider below three equations.

 

$ed-1= k\phi(n) \; (Equation 1)$

$\phi(n) = n - p - q + 1 \; (Equation 2)$

$p \times ipmq + q \times iqmp = n + 1 \; (Equation 3)$

 

Using this equation, we can get a diophantine equation $(ipmq-1) \times p + (iqmp - 1) \times q = (ed-1)/k$.

 

Since $k < e$, it is enough to check few kinds of $k$.

 

Solver.py

from Crypto.Util.number import *

def gcd(a, b):
  while(b): 
    a,b = b, a % b 
  return a 

def mysqrt(d):
  st = 1
  en = 10**1300
  while st<=en:
    mid = (st+en)//2
    if mid*mid == d: return mid
    if mid*mid < d: st=mid+1
    else: en=mid-1
  return -1

def egcd(a1, a2):
    x1, x2 = 1, 0
    y1, y2 = 0, 1
    while a2:
        q = a1 // a2
        a1, a2 = a2, a1 - q * a2
        x1, x2 = x2, x1 - q * x2
        y1, y2 = y2, y1 - q * y2
    return (x1, y1, a1)

e =   1048583
d =   20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
enc = 6315517144108346181816723099897023675574911374735398936591833706590364258184564710827234427731055048559822607765825888615252018165526396090041236515481884097316115657845863616027191241546872931338194871262588098949428397377758354022592306745947669728354322461011070818767686781572984901259034033895184947744496886943392083163678583781999851929812332715335746883110069495497948728241194518127509291959160766882315610259762352662845983222877441386838765184047248466927144181212035420321292287216414973587365695429489044345623525454703093721722072717560946535366845119502057231317372617085049803374310078177219696035587
xx=  e*d-1


#iqmp bit_length : 1022
iqmp = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
#ipmq bit_length : 1024
ipmq = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331

gg = gcd(iqmp-1,ipmq-1)

for k in range(1,e):
  if (e*d-1) % k == 0:
    phi_n = (e*d-1)//k
    if not (1<<2046) < phi_n < (1<<2048) : continue
    if phi_n % gg != 0: continue
    c = phi_n // gg
    a = (ipmq-1)//gg
    b = (iqmp-1)//gg
    # p*a + q*b = c
    pmod = inverse(a, b)*c%b
    for j in range(100000):
      p = pmod + j*b
      if p > (1<<1024): break
      if not isPrime(p): continue
      q = (c-p*a)//b
      assert(p*a+q*b==c)
      if (iqmp*q-1)%p == 0 and (ipmq*p-1)%q == 0:
        M = pow(enc,d,p*q)
        print(long_to_bytes(M))
        exit()


#p = 135136928230019073146158752709151576119155564982754768027494878210491711363872928718225319693774548227271767324623087432404412585662574641211148315864508708036871556964386141364368797168619283425834644924573664613109609076319077176698754203574237779054129492453503018443013301394555677417140681949745410143477
#q = 166564961597106229342966450443567005929416288372170308009700499465281616388542030734600089639466922805142577582894052957547174764252067983124558747593344882775630971023610755334859287415681252266825395627416912206349590353878868107848653100299011246746851490276537231636534462821659050996145878589643016881929
#M = pow(enc,d,p*q)
#print(long_to_bytes(M))



# hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}