Lost Modulus Again (HITCON CTF 2019) writeup by NGG from !SpamAndHex

solve.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
We know that e*d = 1 (mod phi(n)), so there exists a small c (in the order of e) such that:
e*d = (p-1)*(q-1)*c + 1

Also, for ipmq and iqmp the following equation holds (it can be seen from how they can be calculated from the extended Euclidean algorithm):
ipmq*p + iqmp*q = p*q + 1

If we solve this quadratic equation system (eg. with Mathematica) for p and q we get:
p = (-1 + d*e + c*ipmq - c*iqmp ± Sqrt[(1 - d*e - c*ipmq + c*iqmp)^2 - 4*(-c + c*ipmq)*(c - iqmp - c*iqmp + d*e*iqmp)]) / (2*(-c + c*ipmq))
and
q == (p*ipmq - 1)/(p - iqmp)

So we simply try all small c values until we get the flag:
hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}
"""

from sage.all import isqrt
import binascii

e = 1048583
d = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
iqmp = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
ipmq = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331
ct = int('32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703', 16)

for c in range(1, 2*e):
    s = (1 - d*e - c*ipmq + c*iqmp)*(1 - d*e - c*ipmq + c*iqmp) - 4*(-c + c*ipmq)*(c - iqmp - c*iqmp + d*e*iqmp)
    if s < 0:
        continue
    sq = isqrt(s)
    if sq*sq != s:
        continue
    a = -1 + d*e + c*ipmq - c*iqmp
    den = 2*(-c + c*ipmq)
    for nom in (a+sq, a-sq):
        if nom%den == 0:
            p = nom//den
            assert (p*ipmq-1)%(p-iqmp) == 0
            q = (p*ipmq-1)//(p-iqmp)
            flag = pow(int(ct), int(d), int(p*q))
            print(binascii.unhexlify('%x'%flag))