Modulus Amittendus

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. (I didn't realize this for half a day and I was studying Coppersmith's attacks and TWCTF problem Happy!...)

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.