Rating:
You can see that `n, e, cf` are exported in `pubkey.json`.
These values are a bit strange:
```rb
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`, but`d`.
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`.
