古典暗号 - 一致指数を用いた多表式暗号の解読

古典暗号 攻撃

この記事は CTF Advent Calendar 2016 - Adventar の22日目の記事です. 21日目の記事は@nolzeさんの どのCTFに出たらいいか分からない人のためのCTF年表 (2016年版) - A602 です.

多表式暗号の解読ではカシスキー・テストを用いた解読法がよく知られているが, 実はFriedman Testと呼ばれる一致指数(Index of coincidence)を用いた方法がこれとは別に存在し, (精度は劣るものの)カシスキー・テストよりも単純な計算で鍵長を推測することができる. この記事では, 一致指数を用いて多表式暗号を解読する手法をVigenere暗号に対して解説した後CTF(Capture the Flag)の暗号カテゴリの過去問題を実際に解いてみる. この記事では通して英語を平文にもつことを仮定するが, 他の言語でも同様に解読が可能である.

今回題材とする問題は 0CTF 2015: oldcrypto である.

一致指数

一致指数(Index of coincidence)とは, 通常の文字列に対して考えると2つの文字列の間の一致の割合を見る計測の手段として用いることの出来る手法である. しかし, 暗号解析の分野では2つの文字列の間ではなく1つの文字列から2つの文字をそれぞれ取ってきた時にどの程度一致するかを見るために使う. 考え方としては, ある文字列$t$とある文字$x$について, $t$の異なる位置から文字$a$, $b$を取ってきた時, $a = b = x$ を満たす割合を求めれば良い. これは$a = x$となる割合が$\frac{tに含まれるxの数}{tの長さ}$, かつ$b = x$となる割合が$\frac{tに含まれるxの数 - 1}{tの長さ - 1}$であることからこれらの積を取ることで求められる. 実際には$x$は文字全体を動く*1ので, 各$x$について総和を取ることでこれを計算する. 定義をちゃんと書き直すなら以下の通りになる.

長さ$N$の文字列$t$とアルファベット$\Omega = \{x_i\}$がある時, $t$に文字$x\in \Omega$が含まれる数を$\phi_t(x)$で表すと, 一致指数$\mathrm{IC} _ \Omega(t)$は次のように定義できる.

$$ \mathrm{IC} _ \Omega (t) := \frac{1}{N(N-1)} \sum_{x \in \Omega} \phi_t(x)(\phi_t(x) - 1) $$

実際にはアルファベットの長さ$|\Omega|$をかけて正規化したりもするが, この記事では正規化はしない.

暗号解読への応用 - シーザー暗号

一致指数の定義は示したが, どう応用されるのかは見当が付かない. なので, まずはシンプルなシーザー暗号について考える.

シーザー暗号は, 鍵文字を1文字決め, その文字を0-indexな数値にした数だけ平文をずらすことで暗号化している. 例えば, 鍵文字をCとし, HELLOWORLDを暗号化する時を考えると, 鍵文字Cは0-indexで2番目の文字なので

H -> J
E -> G
L -> N
O -> Q
W -> Y
R -> T
D -> F

とずらせる. すると, 暗号文はJGNNQYQTNFであることが分かる. ここで重要なのは, 暗号文は常に平文の同じ文字は同じ文字へ動くということで, このことは文字列の頻度解析による解読法の考案に至っている. 頻度解析はここでは扱わないが, 文字通り文字の分布を調べてその分布に従って鍵を推測していく手法だ.

シーザー暗号を解読するために, まずは一般的な平文の一致指数を考える. 自然言語の場合文字分布がある程度偏っている(英語ではeが一番高頻度で出現する等)ことから, その一致指数の値は計算可能であると言える.

英語の頻度表を利用してこの一致指数の値を求めてみる. 文字列の長さは$\infty$とするのが理想だが, 大きな値(ここでは65537)で代用する.

これを動かすと, 0.0661051931653という値が得られる. つまり, 平均的な英語の文字列の一致指数は約0.0661だと言える.

これを利用してシーザー暗号を解いてみる. 考え方としてはある文字$x$を鍵を仮定し, 実際にその鍵で解読した際にその解読文について「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算し, これと標準的な一致指数0.0661との差の絶対値を求める. この差の絶対値が一番小さなものが鍵だと推測できる.

少しわかりづらい説明になってしまったので, プログラムコードを先に示す. サンプルとして, Lady Chatterly's Lover: History of English - van Gelderenのテキストを利用させて頂いた.

このスクリプトは動かすと実際に鍵sを出力し, 平文へと解読ができる.

キモとなるのは,

  table += [abs(0.0661 - sum(map(lambda x: (x[0]-1)*x[1][1] / (len(tmp) - 1), zip(count_alphabet(tmp, alphabet), sorted_freq))))]

の行だ. これはまさに『解読文について「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算し, これと標準的な一致指数0.0661との差の絶対値を求める』という記述をそのまま実装したものだと言える.

一致指数のシグマの中は$\frac{\phi_t(x)}{N} \frac{\phi_t(x) - 1}{N-1}$と書くこともできることから, $\frac{\phi_t(x)}{N}$を英語の頻度表(つまり, 理想的な(平文に一番近いような)値)から直接代入した上で$\frac{\phi_t(x)-1}{N-1}$を解読文から計算し, これを全ての$x$について計算して総和を取ることで「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算している. これは解読文の頻度が平文と言える値になると0.0661に近くなることから, 差の絶対値の中で最小値を取った鍵が実際の鍵だという推測ができる.

暗号解読への応用 - Vigenere暗号

多表式暗号では, まずシーザー暗号では使えた頻度解析が原則的に使えない. なぜなら, 平文と暗号文の文字は一対一ではないため, 頻度解析を行っても平文と同じ頻度表には成り得ないためだ. これを一致指数を用いて考えると, 鍵長$k$の多表式暗号によって暗号化された暗号文$t$から2つ文字を持ってきた時にこの文字が文字$t$と一致する割合は, 鍵長$k - 1$の時よりも低くなる. なぜなら, 平文と暗号文の文字が一対一ではなく一対$k$の対応になることからランダムネスが上がるため, 全体としての一致の割合が低くなるからだ. 逆に考えれば, 多表式暗号の場合、一致指数はその「鍵の長さ」によって変わるとも言えることが分かる. つまり, 文字列全体の一致指数を取ることで鍵長をある程度推測できると言えるのではないか?と考えられる. これがFriedman Testと呼ばれる鍵長推測の手法である.

以下のスクリプトを用いて実際に実験してみる. サンプルテキストは, 上で用いたものと同じものを使う.

このスクリプトは, 鍵の長さごとにランダムな鍵でVigenere暗号を用いて暗号化し, その一致指数の平均値を算出して表示する. 実行結果は以下のようになる.

[+] Key length = 1, IC = 0.0653856
[+] Key length = 2, IC = 0.0510465
[+] Key length = 3, IC = 0.0466506
[+] Key length = 4, IC = 0.04432
[+] Key length = 5, IC = 0.0433219
[+] Key length = 6, IC = 0.0418646
[+] Key length = 7, IC = 0.0413971
[+] Key length = 8, IC = 0.040794
[+] Key length = 9, IC = 0.0403788
[+] Key length = 10, IC = 0.0402034
[+] Key length = 11, IC = 0.0398683
[+] Key length = 12, IC = 0.0396422
[+] Key length = 13, IC = 0.0394859
[+] Key length = 14, IC = 0.0393217
[+] Key length = 15, IC = 0.0392352
[+] Key length = 16, IC = 0.0390873
[+] Key length = 17, IC = 0.039084
[+] Key length = 18, IC = 0.0389093
[+] Key length = 19, IC = 0.038822
[+] Key length = 20, IC = 0.0387942
[+] Key length = 21, IC = 0.0387419
[+] Key length = 22, IC = 0.0386404
[+] Key length = 23, IC = 0.0386087
[+] Key length = 24, IC = 0.0385671
[+] Key length = 25, IC = 0.0384884

鍵長1の時は最初に計算した0.0661に近く, 鍵長毎に差があるのは確かに見て取れる. *2 これを利用して鍵長を推測してみる. 平文は先と同じものを使い, 鍵長3, 5, 7のそれぞれで一致指数を計算し, 一番近い鍵長の一致指数を求めることで鍵長を推測する.

何度か動かすと分かるが, 誤差が$\pm 1$〜$2$ほど存在する. うまく行けば,

[+] K = oau (3)
[+] Guessed key length = 3
[+] K = imryu (5)
[+] Guessed key length = 5
[+] K = qzomygn (7)
[+] Guessed key length = 7

のように綺麗に判定してくれるが,

[+] K = jeg (3)
[+] Guessed key length = 5
[+] K = abfsn (5)
[+] Guessed key length = 6
[+] K = vsbgyqd (7)
[+] Guessed key length = 9

のようにずれることもある. こればかりは鍵長が長くなれば長くなるほど誤差も大きくなるため比較手法について考えるか誤差を大きく判定するしか無いだろう. しかし, こうやって鍵長の候補が求まれば, シーザー暗号と同じように一致指数から平文に一番近い解読文を導出できる. 最終的な解読文の中でも一番一致指数が鍵長1の時の一致指数に近いものが平文に近いと言えるので, 判定も容易そうに思える. 実際, カシスキー・テストでは鍵長の倍数が求まることがあり, この倍数から鍵長を導出するには因数分解しなければならないので, こちらのほうが自動化をしやすいと言える*3.

それも含めて, 上のコードに解読部分のコードを付け加えたものが以下になる. このコードは実質的に任意のVigenere暗号文を解読することのできるコードになっている.

暗号解読への応用 - CTF過去問題

ここでは冒頭に言ったようにCTFの過去問題を一致指数を用いて解く. 問題は0CTF 2015 - oldcryptoを使う. この問題はタイトルからして古典暗号, 配布されている問題ファイルの中身はというと暗号化用スクリプトと暗号文のみというシンプルなもの. 暗号化・復号関数を以下に抜粋する.

def encrypt(plaintext, key):
    ciphertext = ""
    for i in xrange(len(plaintext)):
        p = ord(plaintext[i]) - ord('a')
        k = ord(key[i % len(key)]) - ord('a')
        c = (tr[k][p] + i**7) % 26
        ciphertext += chr(c + ord('a'))
    return ciphertext

def decrypt(ciphertext, key):
    plaintext = ""
    for i in xrange(len(ciphertext)):
        c = ord(ciphertext[i]) - ord('a')
        k = ord(key[i % len(key)]) - ord('a')
        p = tr[k][(c - i**7) % 26]
        plaintext += chr(p + ord('a'))
    return plaintext

tr はファイル中に定義されている変換テーブル. 簡単に暗号化処理をわかりやすく書き直すと,

import string

def encrypt(plaintext, key):
  ciphertext = ""
  keylen = len(key)
  alphabet = string.lowercase
  plaintext = map(lambda x: alphabet.index(x), plaintext)
  key = map(lambda x: alphabet.index(x), key)
  for i in xrange(len(plaintext)):
    k = key[i % keylen]
    p = plaintext[i]
    c = (tr[k][p] + i**7) % 26
    ciphertext += alphabet[c]
  return ciphertext

i**7 は暗号文から簡単に取り除ける上本質的ではないのでこれを取り除く. すると,

import string

def encrypt_without_i7(plaintext, key):
  ciphertext = ""
  keylen = len(key)
  alphabet = string.lowercase
  plaintext = map(lambda x: alphabet.index(x), plaintext)
  key = map(lambda x: alphabet.index(x), key)
  for i in xrange(len(plaintext)):
    k = key[i % keylen]
    p = plaintext[i]
    c = tr[k][p]
    ciphertext += alphabet[c]
  return ciphertext

これは典型的な多表式暗号である. よって, 先の一致指数を用いたVigenere暗号と同じ議論で鍵長を求め, 鍵を導出することができる. これらを踏まえてコードに起こすと, 次のようになる.

しかし, この暗号文は鍵長が長いためか誤差が大きく, $\pm 2$の誤差では解読ができなかった. そのため, 鍵長を導出できた10から今回計算している25まで全て候補に探索してやることで鍵が導出できた. 具体的には132行目の

for L in xrange(guessed_len - 2, guessed_len + 3):

を

for L in xrange(guessed_len - 2, guessed_len + 26):

と書き換える.

> python oldcrypto.py 
[+] Guessed key length = 10 +- 2
skumsnui
snucgshin
iphssisfun
qniqnllggsz
sdussncgscum
gninihcwnsnni
nnwdqiqnunlgxg
ipasniyaunicanl
slkmswumscunsnks
ucnsginhnhinscvzn
snicqnaqknnucgqgis
kishnsniignnqgdwlsg
classicalcipherisfun
hincgiznlgsichunqygzk
qnsdqmsikntinfhindgnin
zazuumqukdlznrzwcgvgiiu
slumsncwncumcniihicgszuv
igankiphnuiuausiyaunilaun
kvxnulcwtslnigaiuiioanurhd
nnucflhiignlgwjgisiniigmcsl
ncgmhnqnnnussknnhdwmsruilguz
lkipitcisirsswglskngdrvngqqqq
cphsrisfucilaisisfuniyhvsicgun
kiwjawqlbjlsznmqcnfnuahhnvionuq
slkmquqinnunsukinokishumscusznis
cogginsnicfqnhlnlsgzlzgnscuglwnso
qwgssilllhspangnnmghniinhdlgnmkvwu
ikaunisauniuzznighsiiraizipannilaes
[+] Guessed Key = classicalcipherisfun
[+] plaintext = incryptanalysiskasiskiexaminationisamethodofattackingpolyalphabeticsubstitutioncipherssuchasthevigenerecipherinpolyalphabeticsubstitutioncipherswherethesubstitutionalphabetsarechosenbytheuseofakeywordthekasiskiexaminationallowsacryptanalysttodeducethelengthofthekeywordusedinthepolyalphabeticsubstitutioncipheroncethelengthofthekeywordisdiscoveredthecryptanalystlinesuptheciphertextinncolumnswherenisthelengthofthekeywordtheneachcolumncanbetreatedastheciphertextofamonoalphabeticsubstitutioncipherassucheachcolumncanbeattackedwithfrequencyanalysisthekasiskiexaminationinvolveslookingforstringsofcharactersthatarerepeatedintheciphertextthestringsshouldbethreecharacterslongormorefortheexaminationtobesuccessfulthenthedistancesbetweenconsecutiveoccurrencesofthestringsarelikelytobemultiplesofthelengthofthekeywordthusfindingmorerepeatedstringsnarrowsdownthepossiblelengthsofthekeywordsincewecantakethegreatestcommondivisorofallthedistancesthereasonthistestworksisthatifarepeatedstringoccursintheplaintextandthedistancebetweencorrespondingcharactersisamultipleofthekeywordlengththekeywordletterswilllineupinthesamewaywithbothoccurrencesofthestringthedifficultyofusingthekasiskiexaminationliesinfindingrepeatedstringsthisisaveryhardtasktoperformmanuallybutcomputerscanmakeitmucheasierhowevercareisstillrequiredsincesomerepeatedstringsmayjustbecoincidencesothatsomeoftherepeatdistancesaremisleadingthecryptanalysthastoruleoutthecoincidencestofindthecorrectlengththenofcoursethemonoalphabeticciphertextsthatresultmustbecryptanalyzedoooooooooooooooooooopsflagisthekeywithoopsprefixandbraces

flagisthekeywithoopsprefixandbraces とあるように, 鍵の前後に 0ctf{ } を付けたものがフラグになる.

よって, 最終的なフラグは 0ctf{classicalcipherisfun} である.

まとめ

一度計算すれば大方の予測がついてしまうため, 一致指数を用いるFriedman Testはカシスキー・テストよりも扱いやすい. しかし, その分誤差も大きく, その意味ではカシスキー・テストのように鍵長の倍数がすぐに出てくるものよりは劣る. 実際に解読するツールにするには, これらを組み合わせて誤差を吸収するような仕組みを作るほうが良いだろう. 一致指数自体は一般に2つの文字列の差とも言えることから, ある程度の平文がわかっている換字式の自動解読コードを書く時には利用できるかも知れない. テクニックとして覚えておくことに損はないので, 是非とも覚えて使ってもらいたい.

参考文献

明日は@hama7230氏によるcamp ctfのwriteupです.

*1:例えばこの記事では英語を扱うのでアルファベットが文字全体となる. 以降, アルファベットという単語で文字全体を表す.

*2:これは実は$k$についての極限値を求めることができて, 鍵長が∞(いわゆる「ワンタイムパッド」の時)は全ての文字が全ての文字へ写される可能性があると言えて, 一致指数は各文字毎に$(\frac{1}{26}) ^ 2$で, この総和は$\frac{1}{26} = 0.0384615384615385$となる

*3:無論, 両方を実装すればより精度の高い導出が可能である.

ECDLPに対する攻撃手法のまとめ - 一般的攻撃手法

数学 楕円曲線

Exhaustive Search法

いわゆる全探索法であり, 力任せな方法. 与えられる楕円曲線$E$とその上の点$P$, $Q$について$m = \#P$とする. この時, ECDLPの解$d$は$1 \leq d \leq m $の不等式を満たす. このため, この$d$の範囲を全て計算してみることでECDLPは解かれる. 計算量的には$O(n)$となり, 一番ナイーブな方法.

Baby-step Giant-step法

一般的に適用できる中で最も有名なアルゴリズムだと思われる. これは任意の巡回群に対して適用することができる方法で, ここではECDLPに限定して解説する. 基本的な考え方としては, $d$を求めたい離散対数とすると, $d$はある$r$について$d = ir+j$と表せるので, これを使って $$ \begin{align} dP &= Q\\ irP + jP &= Q\\ jP &= Q - irP \end{align} $$ とすることができる. ここで, $j < r$となることから次のように考えられる. まず最初に$P, \ldots, rP$を計算して格納しておく. 次に, $T = -rP$は事前に計算できるのでこれを計算する. そして$Q + iT$を$i$を増やしながら計算していくことによっていつかは$jP = Q + iT$となるような$i, j$を手に入れることができる. すると, 最初の式から$d = ir + j$なのでこれでECDLPは解けたことになる.

多くの場合, $r = \lceil\sqrt{\#P}\rceil$が用いられる. このため, 計算量は$O(\sqrt{\#P})$となる. これはExhastive Searchよりも十分良い結果となっている.

Pythonで実装したアルゴリズムは以下の通りである

from ecpy import * # https://github.com/elliptic-shiho/ecpy/
import math

def bsgs(E, P, Q, ordP):
  # m = sqrt(#P) (round up)
  m = int(math.sqrt(ordP) + 0.5)
  # Calculate Baby-step table
  baby = []
  for i in xrange(m):
    baby += [(i, i * P)]
  h = -P * m
  t = Q
  # Main loop: Giant-step
  for j in xrange(m):
    b = filter(lambda x: x[1] == t, baby)
    if len(b) == 1:
      return b[0][0] + j * m
    t = t + h

def main():
  F = FiniteField(17)
  E = EllipticCurve(F, 3, 7)
  P = E(4, 10, 1)
  Q = E(10, 0, 1)
  ordP = 14
  x = bsgs(E, P, Q, ordP)
  assert x*P == Q
  print x # 7

if __name__ == "__main__":
  main()

Pollard Rho法

ECDLPについては最も成果を挙げている手法. Baby-step Giant-stepと同様, これも任意の巡回群について適用できる方法だが, Baby-step Giant-step法とは異なり確率的(乱択)アルゴリズムである. 実際には素因数分解アルゴリズムとしてのPollard Rhoアルゴリズムのほうが有名なので, 考え方をそちらで説明する. 実際の所, 考え方は共通しているので素因数分解の方法のみ理解していればECDLPへの応用もすぐに可能である.

このアルゴリズムでは乱数列を生成しながらその衝突(素因数分解の対象の数との最大公約数が1以外の値であること)を検出し, 衝突時の値から失敗又は素因数を返す. フロイドの循環検出法を用いて, $i$番目と$2i$番目の乱数を生成するのみとすることで, $O(1)$の記憶容量が存在すれば良いように作られている. この衝突する数列の様子を図にした際にギリシャ文字の$\rho$に見えることから, Pollard Rho法と呼ばれるようになった.

素因数分解のアルゴリズムを実装したものを以下に示す.

from gmpy import gcd

def rand(x, n):
  return (x*x+3) % n

def pollard_rho_factor(n):
  x = 2
  y = 2
  d = 1
  while d == 1:
    x = rand(x, n)
    y = rand(rand(y, n), n)
    d = gcd(abs(x-y), n)
  if d == n:
    return False
  return d

def main():
  print pollard_rho_factor(18446744073709551617)
  print pollard_rho_factor(10023859281455311421)

if __name__ == "__main__":
  main()

これは演算を差し替えれば任意の有限巡回群に適用できることが分かる.よって, これをECDLPへ適用することを考える. ECDLPへ適用する際には衝突の定義を変えなければならない. 以降, 楕円曲線$E$上の点$P$, $Q$について$Q = dP$となる$d$を求めるアルゴリズムとして考える.

  • 乱数列$a_i$, $b_i$について $R_i = a_i P + b_i Q$を定義する.
  • $R_i = R_{2i}$となる$i$が存在するとする.
  • $R_i = a_i P + b_i Q = (a_i + b_i d)P$なので, 以下が成り立つ.

$$ R_i = R _ {2i} \iff a_i + b_i d = a _ {2i} + b _ {2i} d \mod \#E $$

  • よって, $d = (a_i - a _ {2i})\cdot(b _ {2i} - b_i)^{-1} \mod \#E$と計算できる.

最後の段階で, 逆元が存在しない場合には失敗を返す.

以上を踏まえてコードにすると以下のようになる. 関数$f$は乱数を生成するために少々ごちゃごちゃしたことをしているが, これについてはPollard's rho algorithm for logarithms - Wikipediaを参考にした. (よく見れば, 先の条件を満たす乱数に見える値を作っているだけということが読み取れる. )

from ecpy import * # https://github.com/elliptic-shiho/ecpy/
from ecpy.util import modinv

def f(alpha, beta, x, a, b, order):
  if x.x % 3 == 0:
    return (beta+x,  a,             (b+1) % order)
  elif x.x % 3 == 1:
    return (x * 2,   (a*2) % order, (b*2) % order)
  elif x.x % 3 == 2:
    return (alpha+x, (a+1) % order, b)

def pollard_rho_ECDLP(alpha, beta, curve, order):
  a, b, x = 0, 0, curve(0, 1, 0)
  A, B, X = a, b, x
  i = 0
  while i < order:
    x, a, b = f(alpha, beta, x, a, b, order)
    X, A, B = f(alpha, beta, X, A, B, order)
    X, A, B = f(alpha, beta, X, A, B, order)
    if x == X and not A == a == b == B == 0: # except x == X == O
      r = (B - b) % order
      return (modinv(r, order) * (a - A)) % order
    i += 1

def main():
  p = 100003
  r = 100379 # order of `E`
  a = -7
  b = 104
  Gx = 91802
  Gy = 58807
  F = FiniteField(p)
  E = EllipticCurve(F, a, b)

  x = 12345

  G = E(Gx, Gy)
  P = G * x

  print pollard_rho_ECDLP(G, P, E, r)

if __name__ == "__main__":
  main()

また, このアルゴリズムは不完全である. 位数が合成数の場合には逆元が計算できなくなってしまうため, もしちゃんとしたECDLP Solverを書くのであれば位数を素因数分解し各因数それぞれについてECDLPを解き, 中国人剰余定理を用いて元の値を計算するような工夫が必要となる.

Pollard Kangaroo法 (Lambda法)

考案者の名前が同じなことから見当が付くかと思うが, このアルゴリズムはRho法とよく似ている. このアルゴリズムも楕円曲線上の点を整数へと写す写像$f$を用いるが, 衝突の判定が微妙に異なる. ここでは, Rho法と同様に楕円曲線$E$上の点$P, Q$について, $Q = xP$を満たすような$a \lt x \lt b$を探すことを目的とする.

  • $N$を決める. これはステップ数とも言える値で, 任意に定めることができる. (ここではまず100とする. )
  • 数列$T$を以下の規則に従って定める. ここで, $f$は楕円曲線上の点から整数へのハッシュ関数である (適当な乱数関数のシード値にx座標を渡すだけでも良い.). $$ \begin{align} T_0 &= b P\newline T _ {i + 1} &= T_i + f(T_i) P\newline \end{align} $$
  • 同様に, 数列$W$を以下の規則に従って定める. $$ \begin{align} W_0 &= Q\newline W _ {i + 1} &= W_i + f(W_i) P\newline \end{align} $$
  • 関数$D_A(k)$を以下のように定める. ただし, $D_A(0) := 0$である. $$ D_A(k) := \sum _ {i = 1} ^ k f(A_i) $$
  • ここで, $T_i = W_j$となるような$i$, $j$が存在したとする. すると, $T_i = (b + D_T(i)) P$, $W_j = (x + D_W(j)) P$であることから$x = b + D_T(i) - D_W(j)$となり, ECDLPが解ける. この時, $D_W(j) \gt b - a + D_T(i)$が成立している時は範囲内に離散対数が存在しないと言えるため, 失敗と判定する.
  • 失敗した時には, $N$や$f$を取り替えて再度最初からやり直す.

これを$T$, $W$をカンガルーに例えた話に言い換える. 手懐けた(Tame)カンガルー$T$と野生の(Wild)カンガルー$W$が居るときに, $W$がどこから来たのかを知るために捕まえることを考える. そこで, $T$を$N$回ジャンプさせ, ジャンプした地点それぞれに罠を仕掛ける. どこかでその罠に$W$が引っかかると, $W$を捕まえることができる. この時, 元の位置からの移動距離$D_T(i)$, $D_W(j)$がわかっているので, その距離を引くことで元の位置が分かる. *1 Lambda($\lambda$)法の名前の由来は, 手懐けたカンガルーがジャンプしていった地点のどこかで野生のカンガルーが罠にかかる様子を図にすると$\lambda$の形のように見えることから来ている.

以下に実際のコードを示す.

from ecpy import * # https://github.com/elliptic-shiho/ecpy/

def f(x, n):
  return int((x.x ** 2 + 5) % n)

def pollard_lambda(curve, P, Q, order, a=0, b=None):
  if b is None:
    b = order - 1

  N = 100
  INCR = 1

  print "[+] Constructing xs/ys..."
  xs = [P * b]
  for i in xrange(1, N):
    xs += [xs[-1] + P * f(xs[-1], order)]

  ys = [Q]
  for i in xrange(N - 1):
    ys += [ys[-1] + P * f(ys[-1], order)]

  while True:
    D = [sum(map(lambda x: f(x, order), xs[:n])) % order for n in xrange(N)]
    ds = [sum(map(lambda x: f(x, order), ys[:n])) % order for n in xrange(N)]

    print "[*] Find Collision"

    for j, d in enumerate(ds):
      Y = ys[j]
      if Y in xs:
        xj = xs.index(Y)
        if d > (b-a + D[xj]):
          print "[-] Failed... Retry with new N"
          break
        else:
          m = (b + D[xj] - ds[j]) % order
          if m * P == Q:
            print "[+] Found!"
            return m
    else:
      print "[-] Failed... Can't tame a 'roo!"

    N += INCR
    # additional xs/ys
    for i in xrange(INCR):
      xs += [xs[-1] + P * f(xs[-1], order)]
    for i in xrange(INCR):
      ys += [ys[-1] + P * f(ys[-1], order)]

def main():
  p = 100003
  r = 100379 # order of `E`
  a = -7
  b = 104
  Gx = 91802
  Gy = 58807
  F = FiniteField(p)
  E = EllipticCurve(F, a, b)

  x = 12345

  G = E(Gx, Gy)
  P = G * x

  print pollard_lambda(E, G, P, r, a=10000, b=20001)

if __name__ == "__main__":
  main()

このアルゴリズムは, ステップ数に比例した記憶領域を必要とする.

指数計算法(Index-Calculus)

離散対数問題(DLP)に対しては非常に効果的だが, そのままではECDLPに対してはそれほど効果がない方法. 複雑な方法になるためここでは実際のコードを書くことはしない.

まず, 因子基底(factor base)と呼ばれる基底を取る. これはDLPの場合は素数を適当にいくつか取ってくれば良い. これらは(基底という名前の通り)$\mathbb{Z}$係数の線形空間をなすことが必要なことに注意する. 以降, 因子基底の集合を$\mathfrak{D} = \{F_1, F_2, \ldots, F_n\}$, 因子基底のなす空間を$\mathcal{F}$と表す. 次に, ランダムに選んだ$\alpha _ i$, $\beta _ i$を用いて$\alpha_i P + \beta_i Q$を計算し, これが$\mathcal{F}$に含まれていることを確認する. もし含まれていないならば$\alpha_i$, $\beta_i$を取り直す. $\alpha_i$, $\beta_i$はそれぞれ$n$個ずつ集める必要がある. そうすると, $\mathbf{\alpha} = (\alpha_1, \ldots, \alpha _ n)$, $\mathbf{\beta} = (\beta_1, \ldots, \beta_n)$というベクトルに対して以下の等式を満たすような$\mathbf{f} _ i = (f _ {1i}, \ldots, f _ {ni})$が存在する. $$ \mathbf{\alpha} P + \mathbf{\beta} Q = \sum _ {i = 1} ^ n \mathbf{f} _ i F _ i $$ 次に, $\mathbf{f} _ i$から$n$次正方行列$ M $を作る.

$$ M := \begin{pmatrix} f _ {11} & f _ {12} & \cdots & f _ {1n}\newline f _ {21} & f _ {22} & \cdots & f _ {2n}\newline \vdots & \vdots & \ddots & \vdots\newline f _ {n1} & f _ {n2} & \cdots & f _ {nn}\newline \end{pmatrix} $$

この$ M $は $M \begin{pmatrix}F _ 1, F _ 2, \ldots, F _ n\end{pmatrix}^T = \mathbf{\alpha} P + \mathbf{\beta} Q$をを満たす. この関係式に対して行基本変形を施し, $ M $の一番下の行が全て0になる(上三角行列になる)ようにする. この変形された行列を$ M' $として, 対応する$\mathbf{\alpha}$, $\mathbf{\beta}$を$\mathbf{\alpha}^\ast$, $\mathbf{\beta}^\ast$とする.

$M'$の一番下の行は全て0であるため, $\mathbf{\alpha}^\ast _ n P + \mathbf{\beta}^\ast _ n Q = \mathbf{0}$という式ができる. この式を$Q$について解くことで, $Q = xP$を満たす$x$を求めることができる.

この指数計算法はDLPでは他と比べて早い(準指数時間)で終了するアルゴリズムであり, 非常に有用と言える. しかし, 今回考えているECDLPでは主に点を分解する段階において非常に時間がかかることが分かっており, 用いられることは少ない.

Pohlig-Hellman法

この方法は巡回群の位数が小さな素因数に分解される時に有効な手法である. 楕円曲線$E$上の点$P$, $Q$について$Q = xP$を満たす$x$を求めることを考える.

  • 楕円曲線$E$の位数$\#E$を素因数分解する. ここでは$\#E = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$と素因数分解されるとする.
  • 各素因数$p_i^{e_i}$について, $\beta_i = \#E / p_i^{e_i}$を計算する.
  • 全探索やRho法等を用いて$x_i \cdot \beta_i P = \beta_i Q$を満たす$x_i$をそれぞれ求める. $\beta_i$をかけたことにより$\beta_i P$, $\beta_i Q$はそれぞれ位数$p_i^{e_i}$を持つ点になるため, 素因数が小さければ$x_i$は非常に高速に求めることができる.
  • 各$x_i$はそれぞれ$\mod p_i^{e_i}$されているので, 中国人剰余定理より全ての$i$について$x \equiv x_i \mod p_i^{e_i}$を満たす$x$を求める. これにより, ECDLPが解ける.

以上を実装したものを以下に示す.

from ecpy import * # https://github.com/elliptic-shiho/ecpy/
from ecpy.util import crt, modinv
from primefac import factorint # pip install primefac

def factor(n):
  ret = []
  factors = factorint(n)
  return factors, sorted([p**factors[p] for p in factors.keys()])

def exhaustive_search(curve, P, Q, a, b):
  i = a
  while i < b:
    if P * i == Q:
      return i
    i += 1
  return None

def pohlig_hellman(curve, P, Q, order):
  if tuple(P) == (0, 1, 0): # P * x == O => x == #P
    return order
  _, factors = factor(order)
  d = []
  for x in factors:
    m = (order / x)
    d += [exhaustive_search(curve, P * m, Q * m, 0, x)]
  return crt(d, factors)

def main():
  p = 100003
  F = FiniteField(p)
  E = EllipticCurve(F, -7, 1)
  order = 100080

  Gx = 71233
  Gy = 31138
  G = E(Gx, Gy)

  x = 12345

  P = G * x
  print pohlig_hellman(E, G, P, order)

if __name__ == "__main__":
  main()

ここでは全探索関数を実装して利用しているが, ここは任意のECDLPを解くアルゴリズムを適用できる.

参考文献

  • The Arithmetic of Elliptic Curves - J.H.Silverman 著
  • クラウドを支えるこれからの暗号技術 - 光成滋生 著
  • Modern Cryptanalysis: Techniques for Advanced Code Breaking - Christopher Swenson 著
  • 暗号理論入門 原書第3版 - J.A.ブーフマン 著 林芳樹 訳
  • Monte Carlo Methods for Index Computation $\pmod p$ - J.M.Pollard
  • デファクト暗号の評価 - 宮地充子
  • Attacks on the Elliptic Curve Discrete Logarithm Problem - Kenneth J.Giuliani

*1:多少わかりづらいかも知れないが, これは元論文にも書かれているちゃんとした解説である

ECDLPに対する攻撃手法のまとめ 概要編

数学 楕円曲線

楕円曲線離散対数問題(Elliptic Curve Discrete Logarithm Problem, 以下ECDLP)が解けるか否か, という問題は暗号理論において楕円曲線が用いられる際の安全性基準として一般的である. 本記事から數回に分けてECDLPに対する攻撃手法についてまとめる.

ECDLPについて

楕円曲線についてかいつまんで述べる. 体$K$の上の楕円曲線$E/K$をWeierstrass標準形$E/K: y^{2} + a_1xy + a_3y = x ^ 3 + a_2x^{2} + a_4x + a_6$で定義する. 体$K$の標数が2, 3のどちらでもない場合は変数変換により$y^{2} = x^{3}+ax+b$と出来るため, 標数が2, 3で無い時にはこれを明示した上で使用する.

点$P, Q \in E/K$について, 群演算を以下のように定める. ここで, $x(P), y(P)$はそれぞれ楕円曲線の点$P$の$x$座標, $y$座標を表す.

演算 $P+Q$: $$ \begin{align} R &:= P+Q\\ x(R) &= \lambda^{2}+a_1\lambda+a_2-x(P)-x(Q)\\ y(R) &= -(\lambda + a_1)x(R) - \nu - a_3\\ \lambda &= \begin{cases} \frac{y(Q) - y(P)}{x(Q) - x(P)} & (P \ne Q)\\ \frac{3x(P)^{2}+2a_2x(P)+a_4-a_1y(P)}{2y(P)+a_1x(P)+a_3} & (P = Q)\\ \end{cases}\\ \nu &= \begin{cases} \frac{y(P)x(Q) - y(Q)x(P)}{x(Q) - x(P)} & (P \ne Q)\\ \frac{-x(P)^{3}+a_4x(P)+2a_6-a_3y(P)}{2y(P)+a_1x(P)+a_3} & (P = Q)\\ \end{cases}\\ \end{align} $$

逆元 $-P$: $$ -P := (x(P), -y(P)-a_1x(P)-a_3) $$

これらの演算により, $E/K$は群となる. この群の位数を$\#E/K$と表す. 単位元は無限遠点 $\cal O$ とする.

また, これらの演算から乗法を定義することが出来る. ここで, $P \in E/K$, $m\in\mathbb{Z}$.

$$ mP := \underbrace{P + P + \cdots + P}_{m\ \mathrm{times\ repeat}} $$

点$P\in E/K$について, その位数$\#P$を$xP = O$となるような$x$と定義する. そのような$x$が存在しない場合, $\#P = \infty$とする.

この時, 楕円曲線離散対数問題(Elliptic Curve Discrete Logarithm Problem, ECDLP)を以下のように定義する.

入力: 楕円曲線$E/K$, 点$P$, $Q$
出力: $Q = dP$を満たす$d$

この$d$を求めることが計算量的に困難であることが楕円曲線を用いた暗号の安全性根拠となっている. 逆に, ECDLPが解けるならばその暗号は安全ではない. 安全性は計算量的なものであるため, 単純に基礎体$K$の位数を増やせば(=体を大きくすれば)安全性は向上する. しかし, 計算自体がかなり複雑なものであるため, 性能と安全性のトレードオフを考える必要がある. 現時点では160bitの素数$p$を用いるのが安全とされている.

ECDLPへの攻撃

一般的手法

一般的な巡回群に対する攻撃の中でECDLPへ適用可能なものとしては, 以下のようなものが挙げられる.

  • Exhaustive Search法
  • Baby-step Giant-step法
  • Pollard Rho法
  • Pollard Lambda法(またはKangaroo法)
  • Index-Calculus法
  • Pohlig-Hellman法

現時点で, 一番成果を挙げているのはPollard Rho法である.

特殊な曲線に対する手法

一般的手法とは違い, ある特性を持っている・ある基礎体上で定義されている等の特殊な条件を持つ楕円曲線に対して定義される手法で, 一般的手法と異なり計算量がかなり低く(SSSA-Attackについては多項式時間!)抑えられることがある.

  • MOV-reduction (Supersingularな楕円曲線に対するWeil-pairingを用いたDLPへの帰着)
  • Frey-Rück Reduction (同上, Tate-pairingを用いる)
  • SSSA-Attack (Anomalous曲線と曲線に付随する形式群を用いた解法で, 多項式時間解法の一つ. )
  • Weil-Descent Attack (有限体の $n$ 次拡大体の上の楕円曲線のECDLPをDLPへ帰着し, Index-calculus法を併用してECDLPを解く. )
  • Xedni-Calculus法 (特定条件下の楕円曲線におけるIndex-Calculusの効率化. XedniはIndexの逆. )
  • Yasuda-Attack ($p$進展開を利用した$p$進数体・有理数体におけるECDLP解法, 名前は特に付けられていないようなので発案者の安田氏の名前とした)

実装上の問題を突いた手法

楕円曲線の利用時にはもちろんコードを実装する必要がある. この計算時に意図しない値を入れて得られる結果からECDLPを解く手法.

  • Small-Subgroup Attack (位数の少ない点を指定し, それぞれについて何度も小さなECDLPを解き, 中国人剰余定理を用いてECDLPを解く. )
  • Invalid-curve Attack (楕円曲線上に存在しない点を代入し, 機械的に計算された結果を見ることで内部情報を読み取る手法)
    • Montgomery-Ladder Fault (Montgomery-Ladder法を用いて乗算処理を行う際, Invalid-curve Attackを用いて存在しない点に対して処理を行わせるとある別の楕円曲線での計算結果に帰着できる. もし, この曲線でPohlig-Hellman Attackのような別の攻撃を用いれる場合, ECDLPは間接的に解けてしまう. )

参考文献