Login
Immutable PageDiscussionInfoAttachments
ytoku/CTF/Wiki-Example/mic

MMA

mic

問題

Flags for free!

nc 109.233.61.11 3120

Service source code: mic_server.py

Flag format: CTF{..32 hexes..}

mic_server.py

メモ

動作の流れ

解法メモ

33452526613163807108170062053440751665152000000001

解法

小さめのpに対して、FLAG % pは簡単に得られるので、それを中国余剰定理で合わせてフラグを得た。

   1 require 'gmp'
   2 require 'set'
   3 require 'prime'
   4 require 'socket'
   5 def chinese(m1,m2,a,b)
   6   return (m2 * a * GMP::Z(m2).invert(GMP::Z(m1)).to_i + m1 * b * GMP::Z(m1).invert(GMP::Z(m2)) ) % (m1 * m2)
   7 end
   8 
   9 # 5とp を-1したときの約数に含む素数を生成する
  10 def gen_prime(p)
  11   m = p * GMP::Z(5)
  12   while true
  13     n = GMP::Z(rand(2**199 / m.to_i)) * m + 1
  14     if n.to_s(2).size > 100 && n.to_s(2).size < 200
  15       return n if n.probab_prime?(10000) > 0
  16     end
  17   end
  18 end
  19 
  20 def get(g,n)
  21   TCPSocket.open('109.233.61.11', 3120) do |s|
  22     s.puts n
  23     s.puts g
  24     until /(\d+)/ =~ s.gets
  25       p $_
  26     end
  27     return $1.to_i
  28   end
  29 end
  30 
  31 m = GMP::Z(5)
  32 res = GMP::Z(0)
  33 
  34 Prime.each do |p|
  35   next if p == 2 # cannot use
  36   next if p == 5 # already
  37   n = gen_prime(p)
  38   s = Set.new
  39   for i in 1..100
  40     s << GMP::Z(i).powmod((n-1).to_i / 5, n).to_i
  41   end
  42   s = s.to_a.sort[1..-1]
  43   b = get(s[0], n)
  44   s = Set.new
  45   for i in 2..1000
  46     s << GMP::Z(i).powmod((n-1).to_i / p.to_i, n).to_i
  47   end
  48   s = s.to_a.sort[1..-1]
  49   m1 = (get(s[0], n) - b + n) % n
  50   m2 = (get(s[1], n) - b + n) % n
  51   div = ((GMP::Z(m1) * GMP::Z(m2).invert(GMP::Z(n))) % GMP::Z(n)).to_i
  52   t = []
  53   for i in 0...p
  54     t <<= i if div == ((s[0] ** i - 1) * GMP::Z(s[1] ** i - 1).invert(GMP::Z(n)).to_i) % n
  55   end
  56   if t.size == 1
  57     puts "E % #{p} = #{t[0]}"
  58     res = chinese(m, p, res, t[0])
  59     m *= p
  60     puts [res,m].inspect
  61   end
  62 end

$ irb
irb(main):003:0> [33484375882498836878212229293130163752541914367103862741117889225946575451905614736078205.to_s(16)].pack('H*')
=> "CTF{cf5246e06b13432b9e1116ddef226455}"

別解

ytoku/CTF/Wiki-Example/mic (last edited 2014-07-11 19:10:06 by ytoku)