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).