[HITCON 2019] Lost Modulus Again

output, prob.py가 주어진다.

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)

output에 나오는 n은 사실 n이 아니라, d다.. 우리는 e, d, iqmp, ipmq를 알 수 있다.

Exploit Code

from Crypto.Util.number import *
from gmpy2 import *

e = 1048583
d = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
x = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
y = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331
c = 0x32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703

for k in range(1, e):
    if (e*d-1) % k != 0:
        #print "K is error"
        continue
    a = (e*d-1) // k
    s = (a+y-x)**2-4*(y-1)*(x*a-x+1)
    if not is_square(s):
        #print "s is error"
        continue
    A = (a+y-x)+int(isqrt(s))
    B = 2*(y-1)
    if A % B != 0:
        #print "A B is error"
        continue

    p = A//B
    if size(p) != 1024:
        #print "p is error"
        continue
    else:
        break

q = a // (p-1) + 1
n = p*q
flag = pow(c, d, n)
print long_to_bytes(flag)

Capture the Flag

---