Rating:
You can see that n, e, cf are exported in pubkey.json.
These values are a bit strange:
def initialize
# ...
@cf = modinv(@q, @p) # (1)
end
def pubkey
privkey.to_a[..2].to_h
end
def privkey
{
e: @e,
n: @d, # (2)
cf: @cf,
# ...
}
end
First, you can see that cf is q^{-1} mod p.
Second, this is important, n is NOT n, butd.
Therefore, the problem is: Given e, d, cf, calculate n.
First observation, from definition, ed = 1 + k(p-1)(q-1). Comparing the bit length, k should be the same bit length as e.
This is small enough to bruteforce. From this, we can get phi(n) = (p-1)(q-1) = (ed-1)/k.
Second, to use cf*q = 1 (mod p) condition, let the above equation be in mod p.
That will be phi(n) = -(q-1) (mod p), and from these 2 equations, 1 + cf*phi(n) - cf = 0 (mod p).
This means x := 1 + cf*phi(n) - cf is a multiple of p.
Finally, because we know phi(n), for some integer m, m^{phi(n)} - 1 = 0 (mod n).
These can be written as m^{phi(n)} - 1 = 0 (mod p), so m^{phi(n)} - 1 are also multiples of p.
So, we can get p by simply gcd of these values.
m^{phi(n)} will be huge numbers, so we should calculate as pow(m, phi(n), x).
From p and phi(n), we can recover q and n, and decrypted flag using n, d.
