mic
問題
Flags for free!
nc 109.233.61.11 3120
Service source code: mic_server.py
Flag format: CTF{..32 hexes..}
メモ
動作の流れ
$ 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は簡単に得られるので、それを中国余剰定理で合わせてフラグを得た。
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}"
別解
$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$を変えながら中国人剰余定理