lost_modulus

Lost modulus (crypto, 200p, 64 solved)

In the task we get source code and its output. The code is simply RSA encryption of the flag.

Analysis

The key observation from the code is:

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

Second output parameter is self.d even though it's labelled as n = {1}. This means that we know e, d, iqmp and ipmq, but we don't know n.

As name of the challenge suggests, they goal is to recover n to complete the private key and decrypt the flag.

Solution equation

In order to do that we need to do a bit of math. There is not much to go with, since the only values related to n we have are iqmp and ipmq.

Let's use their definition:

ipmq = modinv(p,q)
ipmq*p == 1 mod q
ipmq*p = 1 + k*q [some integer k with bound k<q]
k*q = ipmq*p - 1 [some integer k with bound k<q]

Same for iqmp:

iqmp = modinv(q,p)
iqmp*q == 1 mod p
iqmp*q = 1 + m*p [some integer m with bound m<p]
m*p = iqmp*q - 1 [some integer m with bound m<p]

Let's now multiply those 2 equations:

(ipmq*p) * (iqmp*q) = (1+k*q) * (1+m*p)
ipmq*iqmp*p*q = k*m*p*q + k*q + m*p + 1
ipmq*iqmp*N = k*m*N + k*q + m*p + 1

Let's move N to one side:

N*(ipmq*iqmp - k*m) = k*q + m*p + 1

On the left side of the equation we have N*x and since those are all integer equations, it means x has to be integer as well. This means that the right side of the equations has to also be a multiple of N.

Now the key observation in this task:

Let's remember the bounds for k and m -> k<q and m<p.

On the right side we have k*q + m*p + 1. What is the upper bound? It has to be smaller than q*q + p*p +1. We can assume, from the task setup, that p and q are of similar bitlength, and thus q*q and p*p can't be much bigger than N, and therefore the whole right side of the equation can't be much bigger than 2*N even in the most pessimistic case (with k=q and m=p), and since it's all integers it can be either N or 2*N and nothing more. It's very unlikely that we hit the upper bound, so we can safely assume that in reality it's equal to N.

So we have now:

k*q + m*p + 1 = N

Now let's substitute back k*q = ipmq*p - 1 and m*p = iqmp*q - 1:

(ipmq*p - 1) + (iqmp*q - 1) + 1 = N
ipmq*p + iqmp*q - 1 = N

Let's now look into another relation:

N = p*q
phi(N) = (p-1)*(q-1)

From this we know that:

phi(N) = N - p - q + 1
N = phi(N)+p+q-1

Let's modify a bit our previous result:

ipmq*p + iqmp*q - 1 = N
ipmq*(p-1+1) + iqmp*(q+1-1) - 1 = N
ipmq*(p-1) + ipmq + iqmp*(q-1) + iqmp - 1 = N

And combine this with relation between N and phi:

ipmq*(p-1) + ipmq + iqmp*(q-1) + iqmp - 1 = phi(N) + p + q - 1

For simplicity let's introduce:

p-1 = X
q-1 = Y
phi(N) = phi

And thus:

phi = X*Y
X = phi/Y

And now:

phi = ipmq*X + ipmq + iqmp*Y + iqmp -1 -(X+1+Y)
phi = ipmq*(phi/Y) + ipmq + iqmp*Y + iqmp - 1 -(phi/Y + 1 + Y)

Let's now multiply this by Y:

phi*Y = ipmq*phi + ipmq*Y + iqmp*Y^2 + iqmp*Y - Y -(phi + Y + Y^2)
phi*Y = ipmq*phi + ipmq*Y + iqmp*Y^2 + iqmp*Y - Y - phi - Y - Y^2

Move this to one side and combine:

Y^2*(iqmp-1) + Y(ipmq + iqmp - phi - 2) + ipmq*phi - phi = 0

Now we have simply an equation a*x^2 + bx + c == 0 and we can directly solve it, assuming we know the value of phi.

Phi(n) recovery

Fortunately we can easily calculate phi one using the fact that:

e*d mod phi == 1
e*d == 1+k*phi
k*phi == e*d-1

Now although the value of k may be big, we can approximate it using some value which should be of similar bitlen to phi we're looking for. Once such value would of course be N, but we don't know that. Other such value is for example d, since it was calculated as inverse(self.e, (self.p-1)*(self.q-1)) so it has to be smaller than phi.

We iterate over possible phi using:

def find_phi(e, d):
    kfi = e * d - 1
    k = kfi / (int(d * 3))
    print('start k', k)
    while True:
        fi = kfi / k
        try:
            d0 = gmpy2.invert(e, fi)
            if d == d0:
                yield fi
        except:
            pass
        finally:
            k += 1

Keep in mind there can be many values phi where d == modinv(e,phi), so we need to test all of them, but with our start approximation for k we should hit the right one quite fast.

Solving quadratic equation

Now that we can provide possible phi values, we can get back to our quadratic equation and solve it:

def solve_for_phi(ipmq, iqmp, possible_phi):
    a = iqmp - 1
    b = ipmq + iqmp - 2 - possible_phi
    c = ipmq * possible_phi - possible_phi
    delta = b ** 2 - 4 * a * c
    if delta > 0:
        r, correct = gmpy2.iroot(delta, 2)
        if correct:
            x1 = (-b - r) / (2 * a)
            x2 = (-b + r) / (2 * a)
            if gmpy2.is_prime(x1 + 1):
                q = x1 + 1
                p = possible_phi / x1 + 1
                return p, q
            elif gmpy2.is_prime(x2 + 1):
                q = x2 + 1
                p = possible_phi / x2 + 1
                return p, q

Now if we plug this all together:

def main():
    e = 1048583
    d = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
    ipmq = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
    iqmp = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331
    ct = 0x32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703
    for potential_phi in find_phi(e, d):
        res = solve_for_phi(ipmq, iqmp, potential_phi)
        if res:
            p, q = res
            n = p * q
            print(long_to_bytes(pow(ct, d, n)))
            break

We get the flag: hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}

Complete solver here