**Tags:** cryptography-rsa crypto

Rating:

# Lost Modulus Again

## Challange

Consider the following class:

```python

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) # ???

```

Looks like a standard `RSA` impelemntation, nothing out of the ordinary in the key generation part... Wait whats this?

We can see that instead of getting `n`, we get `d`! we need to somehow recover `n` in order to decrypt the flag, since we already have `d`.

## Math

So we have the following information: `e`, `d=inv(e,(p-1)*(q-1))`, `p'=inv(p,q)` and `q'=inv(q,p)`.

From the definition of the modular inverse we know there are (positive) integers `k`, `t` and `s` such that:

1) `p' * p = 1 + kq`

2) `q' * q = 1 + tp`

3) `e * d = 1 + s * (p - 1) * (q - 1)`

Now for standard trick: `d` is roughly the size of `n` (most of the time), and so is `(p-1)*(q-1)`, so looking at equation 3, we know that `s` should be roughly the save size as `e`:

```

s = (e*d-1)/((p-1)*(q-1)) ~ (e*d)/((p-1)*(q-1)) ~ e

```

So we can brute `s in range(e - delta, e + delta)`, where `delta` isnt that big. We can check that `e*d - 1` is divisble by our guess for `s` to reduce the range even more.

Now its time for some annoying math. First of all, we can see that `(-t)*p =1-q'*q`, and therefore `-t` is also a modular inverse of `p mod q`, which means that `-t=p' (mod q)`. The same applies for `-k`, and we get the following interesting congruences:

4) `p' + t = i * q`

5) `q' + k = j * p`

for some positive integers `i`, `j`. I claim that actually, `i` = `j`.

Indeed, substituting `p'=i*q-t` in equation 1, we get:

```

p'*p = 1 + k*q

(i*q-t)*p = 1 + k*q

i*p*q - t*p = 1 + k*q

i*n = 1 + k*q + t*p

```

And similarly for `q'=j*p-k` in equation 2, we get: `j*n=1+k*q+t*p`, which means `j*n=i*n` and therefore `i=j`. We will denote the value of `i` and `j` as `l`.

Now we rewritten equations 4 and 5 as:

4) `p' + t = l * q`

5) `q' + k = l * p`

Now, `p'`, `q'`, `p` and `q` are around the same size, and so are `k` and `t` (using the same trick we user for `e` and `s`). Using that we get that:

```

l = (p' + t) / q ~ 2

```

That is, `l` is **really** small. So we can also brute force `l`, if we need too.

Now lets try substitution:

```

p'*p = 1 + k*q # Multiply by l

l*p'*p = l + k*q*l # Substitute lp and lq as in equations 4 and 5

(q'+k)*p' = l + k(p'+t) # Open up the brackets

p'*q' + k*p' = l + k*p' + k*t # Move things around

p'*q' - l = k*t

```

That is interesting, since the left hand side is composed entirely of stuff we can compute.

Now for the real shit, lets try to use equation 3.

```

e*d - 1 = s*(p - 1)*(q - 1) # Divide by s

(e*d - 1) / s = (p - 1)*(q - 1) # Multiply by l^2

l^2 * [(e*d - 1) / s] = (l*p - l)*(l*q - l) # Substitute equations 4,5

l^2 * [(e*d - 1) / s] = (q' + k - l)*(p' + t - l) # Open up RHS

# Move stuff we know to LHS, and group stuff

LHS = q'*p' + q'*t - q'*l + k*p' + k*t - k*l - l*p' - l*t + l^2

# Write the final equation

LHS - q'*p' + l*(q'+p') - l^2 = (q'-l)*t + (p'-l)*k

l^2 * {[(e*d - 1) / s] - 1} - p'*q' - l*(p'+q') = (q'-l)*t + (p'-l)*k

```

Well. This sucks. But notice the LHS is composed entirely of stuff we know (or can brute force) and the right hand size is a linear equation in `t` and `k`, with known coefficients. If we call the monstrosity at the LHS `beta`, and set `alpha = p'*q' - l`, we have the have following equations:

6) `alpha = kt`

7) `beta = (p'-l)*k + (q'-l)*t`

Now, this system of equations is most definetly solvable (actually, its a quadratic equation!), which means we can recover `k` and `t` and then `p` and `q`. I wrote a short script that does exactly that, and lo and behold, it worked!

![Success](flag.PNG)

Original writeup (https://github.com/iamgweej/hitcon2019quals-writeups/tree/master/Lost%20Modulus%20Again).