# Lost Modulus Again
## Challange
Consider the following class:
```pythonclass 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*qi*p*q - t*p = 1 + k*qi*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 ll*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 bracketsp'*q' + k*p' = l + k*p' + k*t   # Move things aroundp'*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^2l^2 * [(e*d - 1) / s] = (l*p - l)*(l*q - l)         # Substitute equations 4,5l^2 * [(e*d - 1) / s] = (q' + k - l)*(p' + t - l)   # Open up RHS
# Move stuff we know to LHS, and group stuffLHS = q'*p' + q'*t - q'*l + k*p' + k*t - k*l - l*p' - l*t + l^2
# Write the final equationLHS - 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)