<<EnableMathJax(doller)>>
= mic =
== 問題 ==
Flags for free!

nc 109.233.61.11 3120

Service source code: mic_server.py

Flag format: CTF{..32 hexes..}

[[attachment:mic_server.py]]

== メモ ==
=== 動作の流れ ===
 *`$ 2^{256} < e < 2^{512}$` (フラグを$e$とした。)
 *ユーザーは素数`$ p (2^{100} < p < 2^{200}) $`と、基数$ g (2 < g < p - 1) $を送信する
  * 素数は乱択を用いたミラーラビン素数判定法によってチェックされる。
 *プログラムは$ (e(ge)^{e}+e) \mod p $を返却する
  * `$ = (e g^e e^e + e) \mod p $`
=== 解法メモ ===
 *$ p $が素数でなければ $ g ^ e \mod p = 0 $になるような$g$を探すことが出来るかもしれない。
  *ミラーラビン素数判定法の施行回数は100回なので$ 4 ^ {-100} $の確率で間違える……無理っぽい
 *`$ g^e = 1$`にすると戻ってくるのは、`$ (e^{e+1} + e) \mod p $` 
  *$ p $を任意の値に出来るので、離散対数問題は解くことが出来るが、最後のeが邪魔
 *メモ：素数
{{{
33452526613163807108170062053440751665152000000001
}}}
 *$ e $は5の倍数
== 解法 ==
小さめのpに対して、FLAG % pは簡単に得られるので、それを中国余剰定理で合わせてフラグを得た。
{{{#!highlight ruby
require 'gmp'
require 'set'
require 'prime'
require 'socket'
def chinese(m1,m2,a,b)
  return (m2 * a * GMP::Z(m2).invert(GMP::Z(m1)).to_i + m1 * b * GMP::Z(m1).invert(GMP::Z(m2)) ) % (m1 * m2)
end

# 5とp を-1したときの約数に含む素数を生成する
def gen_prime(p)
  m = p * GMP::Z(5)
  while true
    n = GMP::Z(rand(2**199 / m.to_i)) * m + 1
    if n.to_s(2).size > 100 && n.to_s(2).size < 200
      return n if n.probab_prime?(10000) > 0
    end
  end
end

def get(g,n)
  TCPSocket.open('109.233.61.11', 3120) do |s|
    s.puts n
    s.puts g
    until /(\d+)/ =~ s.gets
      p $_
    end
    return $1.to_i
  end
end

m = GMP::Z(5)
res = GMP::Z(0)

Prime.each do |p|
  next if p == 2 # cannot use
  next if p == 5 # already
  n = gen_prime(p)
  s = Set.new
  for i in 1..100
    s << GMP::Z(i).powmod((n-1).to_i / 5, n).to_i
  end
  s = s.to_a.sort[1..-1]
  b = get(s[0], n)
  s = Set.new
  for i in 2..1000
    s << GMP::Z(i).powmod((n-1).to_i / p.to_i, n).to_i
  end
  s = s.to_a.sort[1..-1]
  m1 = (get(s[0], n) - b + n) % n
  m2 = (get(s[1], n) - b + n) % n
  div = ((GMP::Z(m1) * GMP::Z(m2).invert(GMP::Z(n))) % GMP::Z(n)).to_i
  t = []
  for i in 0...p
    t <<= i if div == ((s[0] ** i - 1) * GMP::Z(s[1] ** i - 1).invert(GMP::Z(n)).to_i) % n
  end
  if t.size == 1
    puts "E % #{p} = #{t[0]}"
    res = chinese(m, p, res, t[0])
    m *= p
    puts [res,m].inspect
  end
end
}}}
{{{
$ irb
irb(main):003:0> [33484375882498836878212229293130163752541914367103862741117889225946575451905614736078205.to_s(16)].pack('H*')
=> "CTF{cf5246e06b13432b9e1116ddef226455}"
}}}


別解
 * $p$一つに対して$g$を四つ取り、四本の式に対して((1)-(2))/((3)-(4))を考えると `$\frac{g_1^e - g_2^e}{g_3^e - g_4^e}\mod{p}$` が得られる。ここで`$g_1 = x^3, g_2 = x^2, g_3 = x^2, g_4 = x$`とおけば`$x^e\mod{p}$`が得られる。
 * `$(g_2^e(e^{e+1}g_1^e+e) - g_1^e(e^{e+1}g_2^e+e)) / (g_2^e - g_1^e) = e \mod{p}$`
 * 最後に$p$を変えながら中国人剰余定理