SECCON2013 Quals Cryptanalysis #Ruby

楕円曲線知識ゼロのところから少し勉強してみたのでまとめてみた．

問題概要

本問題では，数式が手書きされた画像が渡されるのでそれを解く．画像から得られる情報は以下である．

$ y^2 = x^3 + 1234577x + 3213242$ $($ mod $7654319)$
$Base = (5234568, 2287747) $
$PublicKey = (2366653, 1424308) $
$CryptedData = ((5081741, 6744615), (610619, 6218)) $
$ PublicKey = Secret Key \times Base$
$ Crypted Data = (Rand() \times Base, Plain + Rand() \times PublicKey)$
答えは，$Plain_x + Plain_y$

基礎知識

楕円曲線($y^2 = x^3 + ax + b$)上の加算は以下のように計算することができる．

$ x_3 = \lambda^2 - x_1 - x_2 $
$ y_3 = \lambda(x_1 - x_3) - y_1$

この時，$\lambda$は加算する2点$P,Q$により計算方法が異なる．

$P \neq Q$の時
- $ \lambda = \frac{y_2 - y_1}{x_2-x_1}$
$P = Q$の時
- $\lambda = \frac{3x_1^2+a}{2y_1} $

減算は，例えば点$P(x,y)$を引きたい場合，$P^{'}(x,-y)$を加算すれば良い．
また，スカラー倍する際には，スカラー$d$を用いて，$d-1$回$P$を加算する．

解き方

$PublicKey=SecretKey \times Base$より$CryptedData_y = Plain + Rand() \times SecretKey \times Base$となる．
$CryptedData_x = Rand() \times Base$より$CryptedData_y = Plain + CryptedData_x \times SecretKey$となる．
つまり$SecretKey$が分かれば$Plain = CryptedData_y - SecretKey \times CryptedData_x$として計算することが可能である．

今回$PublicKey = SecretKey \times Base$なので，ここから$SecretKey$を導き出すことは楕円曲線上における離散対数問題(ECDLP: Elliptic Curve Discrete Logarithm Problem)となる．これに対するアプローチは複数あるが，今回は最も簡単な列挙法を用いる．列挙法は名前通り，順番に$SecretKey$の値を変化させていき上記の数式が成り立つ場合を見つけるものである．

本問題を解くために書いたプログラムが以下である．Rubyで多倍長を計算するgemのgmpを利用している．また加算を計算する際に少し式変形をしているのでそれについて言及しておく．以下のプログラムにおいて変数tは上記の式の$\lambda$に相当するものだが，プログラムでは以下のような計算を行っている．($P \neq Q$の時について取り上げてみる．数学徒にとっては当たり前なのだろうけど気づくまでに時間がかかったので・・・)

$ \lambda = (y_2 - y_1) \times (x_2 - x_1)^{M-2}$ mod $M$
これを少し式変形すると以下のようになる．
$ \lambda = (y_2 - y_1) \times (x_2 - x_1)^{-1} \times (x_2 - x_1)^{M-1}$ mod $M$
$ \lambda = \frac{y_2 - y_1}{x_2 - x_1}\times (x_2 - x_1)^{M-1}$ mod $M$
ここでフェルマーの小定理について思い返してみると，$p$を素数とし，$a$と$p$が互いに素な時は以下が成り立つ．
$a^{p−1} ≡ 1 ($ mod $p)$
したがって，最終的な$\lambda$は同じ答えになるというものである．単純に逆元を取ると途中で計算エラーになってしまったが，こうすることでそれを防げた．
最終的な答えとしては5720914が出てきた．

#!/usr/bin/env ruby
require 'gmp'

# from attached file
A = 1234577
B = 3213242
M = 7654319
base = [5234568, 2287747]
pubic_key = [2366653, 1424308]
crypted_data =  [[5081741, 6744615], [610619, 6218]]

# Public key = Secret key * base
# crypted_data = (rand() * base, plain + rand() * public_key)

def add_on_elliptic_curve(u, v)

  return u if v == [0,0]
  return v if u == [0,0]

  x1, y1 = u
  x2, y2 = v

  if u != v
    t = (y2 - y1) * GMP::Z(x2-x1).powmod(M-2, M)
  else
    t = (3 * x1 * x1 + A) * GMP::Z(2 * y1).powmod(M-2, M)
  end
  x3 = t * t - x1 - x2
  x4 = t * (x1 - x3) - y1

  [x3 % M, x4 % M]

end

x = [0,0]
M.times do |i|
  puts "[+] Calc #{i}"
  if x == pubic_key
    secret_key = i
    puts "Secret key: #{secret_key}" #=> 1584718
    break
  end
  x = add_on_elliptic_curve(x, base)
end

# tmp = secret * base * rand()
# tmp = secret * crypted[0]
tmp = [0, 0]
secret_key.times do |i|
  puts "[+] Calc #{i}"
  tmp = add_on_elliptic_curve(tmp, crypted_data[0])
end

# crypted[1] = plain + tmp
# plain = crypted[1] - tmp
ans = add_on_elliptic_curve(crypted_data[1], [tmp[0], tmp[1] * -1])

puts ans.inject(:+) # [2171002, 3549912].inject(:+) = 5720914