Modulus Amittendus writeup

ModulusAmittendus.md

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.

solve.rb

require 'json'

n, e, cf = 0, 0, 0
File.open("pubkey.json") do |f|
  hash = JSON.load(f)
  n = hash["n"].to_i
  e = hash["e"].to_i
  cf = hash["cf"].to_i
end
d = n
n = nil

enc = 17320751473362084127402636657144071375427833219607663443601124449781249403644322557541872089652267070211212915903557690040206709235417332498271540915493529128300376560226137139676145984352993170584208658625255938806836396696141456961179529532070976247738546045494839964768476955634323305122778089058798906645471526156569091101098698045293624474978286797899191202843389249922173166570341752053592397746313995966365207638042347023262633148306194888008613632757146845037310325643855138147271259215908333877374609302786041209284422691820450450982123612630485471082506484250009427242444806889873164459216407213750735305784

for k in 1...100000
  next if (d*e-1)%k != 0
  phi = (d*e-1)/k
  next if phi.to_s(2).length > 2050

  kn = cf*phi - cf + 1
  next if kn <= 0

  # recover p
  keyp = kn
  for m in 2...10
    keyp = keyp.gcd(m.pow(phi,keyp) - 1)
  end
  next if keyp.to_s(2).length != 1024

  # recover q
  next if phi % (keyp-1) != 0
  keyq = phi / (keyp-1) + 1

  # recover n
  keyn = keyp * keyq

  puts keyn
  flag = enc.pow(d, keyn)
  flaghex = flag.to_s(16)
  flaghex = "0" + flaghex if flaghex.length % 2 == 1
  puts [flaghex].pack("H*")
end