2018-05-04

蔵書リスト【機械学習・統計編】

我が家の機械学習・統計関連の蔵書リスト。
(マウスオーバーで本のタイトルが見れて、クリックするとAmazonページヘ飛びます。)

蔵書

機械学習

統計・データ分析

ほしいものリスト

2017-01-12

楕円曲線上の離散対数問題に対するアプローチ（Baby-step giant-stepとPollard's rho algorithm）

セキュリティ暗号

本稿では楕円曲線暗号の安全性の根拠とされている離散対数問題について、それを高速に解く方法をまとめる。

過去に「CTFにおける離散対数問題に対するアプローチ - sonickun.log」という記事を書いたが、この記事で言う離散対数問題（主にElGamal暗号で利用される）は、有限体上の離散対数問題と呼ばれるのに対し、今回扱うのは楕円曲線上の離散対数問題というものである。ちなみにこれまで楕円曲線上を離散対数問題を題材としたCTF問題に巡り合ったことはほとんどない（あったら教えてください）。

この楕円曲線上の離散対数問題を高速に解く手法として、Baby-step giant-stepとPollard's rho algorithmを紹介し、実際に実装してみる。なお、楕円曲線の基礎知識や楕円曲線暗号のアルゴリズムの説明については省略する。また、厳密な定義や証明は省き、イメージとして理解することを目指す。

楕円曲線上の離散対数問題（ECDLP: Elliptic Curve Discrete Logarithm Problem）

有限体 $\mathbb{F}p$ 上の楕円曲線 $E$ において、 $E$ 上のある点（ベースポイント） $P$ と整数 $d$ から点 $Q = d × P$ （スカラー倍算）を計算するのは容易である。逆に、点 $P$ 、 $Q$ から $Q = d × P$ を満たす整数 $d$ を求めよ、という問題を楕円曲線上の離散対数問題と呼ぶ。

巡回群の位数が巨大な素数となるような楕円曲線とベースポイントを選んだ場合、この離散対数問題を解くことは非常に困難であることが知られている。その理由の一つには、スカラー倍算の結果が離散的に変化するという性質が挙げられている。

言い換えれば、楕円曲線上の点を巡っていく際に、ある点から $d$ 回たどることは簡単だが、始点と終点を与えられたときに、始点から何回たどって終点にたどり着いたかを求めることは困難である、ということである。

楕円曲線上の離散対数問題は、楕円曲線暗号の安全性の根拠とされている。ちなみに、1024ビット鍵長のRSA暗号やElGamal暗号と同等の安全性を持つためには、楕円曲線暗号では160ビットの鍵長で十分であるといわれている。そのため、暗号化・復号や署名認証用のハードウェア規模やソフトウェアの計算速度は、楕円曲線暗号のほうが数倍も優れており、たとえばICカードなど、コンパクト化・軽量化が要求される場合には、楕円曲線暗号が活用されている。

Baby-step giant-step

楕円曲線上の離散対数問題に対するBaby-step giant-stepは、過去記事で解説した、有限体上の離散対数問題に対するBaby-step giant-stepと根本的な考え方は同じである。

離散対数問題 $Q = dP$ に対し、ベースポイント $P$ の位数 $n$ を用いて $d=im+j$ （ $m=\lceil\sqrt{n}\rceil$ 、 $0 \leq i,j \lt m$ ）として、以下の式を得る。

${ \displaystyle Q = dP \\ Q = (im+j)P \\ Q - imP = jP }$

この式において、両辺が一致するように $i$ 、 $j$ を総当たりし、 $d$ を求める。そうすることで、列挙法で $d$ を求めるよりも少ない試行数で離散対数問題が解ける。

各辺の計算にはそれぞれ $m$ 回ずつのスカラー倍算を必要とするため、全体では $2m$ 回、つまり $2\sqrt{n}$ 回程度のスカラー倍算が必要になる。

以上をSageMathで実装したものが以下である。

def baby_step_giant_step(E, P, Q):
    m = int(E.order()^0.5 + 1)

    baby = []
    b = Q
    for j in range(m):
        baby.append(b)
        b -= P

    giant = m * P
    for i in range(1, m):
        if giant in baby:
            d = i*m + baby.index(giant)
            return d
        else:
            giant += (m * P)
    print "not found"
    return -1

p = 229
a = 1
b = 44

E = EllipticCurve(GF(p), [a, b])
P = E([5, 116])
Q = E([155, 166])

d = 176

assert Q == d * P

print d
print baby_step_giant_step(E, P, Q)

実行結果

# sage elliptic.sage
176
176

Pollard's rho algorithm

離散対数問題 $Q = dP$ （位数は $n$ ）に対し、何らかの方法で

${ \displaystyle a_i P + b_i Q = a_j P + b_j Q }$

となる $a_i, b_i, a_j, b_j (a_i \not= a_j, b_i \not= b_j)$ が見つかったとする。ことのき

${ \displaystyle Q = \frac{a_j - a_i}{b_i - b_j}P }$

となり、

${ \displaystyle d = \frac{a_j - a_i}{b_i - b_j} \pmod{n} }$

となるので、離散対数問題の解 $d$ を求まる。

$R_i = a_i P + b_i Q$ としたとき、このアルゴリズムの目標は $R_i = R_j$ となる点のペア $R_i$ 、 $R_j$ を見つけることである。このような点のペアをコリジョンペアと呼ぶ。

ここでは、コリジョンペアを探索するために、楕円曲線上の点をランダムに選んでいく方法をとる。楕円曲線上の点 $R$ をもとにランダムな点を効率的に求めるために、次のようなRandom Walk関数 $f$ を利用する。

${ \displaystyle \begin{eqnarray} f(R)=\left\{ \begin{array}{ll} R + M_0 & (x(R) \equiv 0 \pmod{4}) \\ R + M_1 & (x(R) \equiv 1 \pmod{4}) \\ R + M_2 & (x(R) \equiv 2 \pmod{4}) \\ R + M_3 & (x(R) \equiv 3 \pmod{4}) \\ \end{array} \right. \end{eqnarray} }$

ここで $x(R)$ は点 $R$ の $x$ 座標を表す。ただし、 $M_i = u_i P + v_i Q$ は楕円曲線上からランダムに選ばれた点である。 $R_{i+1} = f(R_i)$ として次々に楕円曲線上の点を求めていくと、確率的にコリジョンペアが見つかる。

上のRandom Walk関数の例ではランダム性を向上させるために4分割されていた（このパラメータを分割数という）が、Pollard's rho algorithmにより大規模な離散対数問題を解く際には、分割数が20程度の関数が使用される。ちなみに、Pollard's rho algorithmでランダムな点を求める方法は他にもあるらしい（Wikipedia）。

以上をSageMathで実装したものが以下である。

from random import randint

def pollards_rho(E, P, Q, div):

    n = E.order()
    R = []
    Rab = []
    a = randint(0, n)
    b = randint(0, n)
    R.append((a*P) + (b*Q))
    Rab.append([a, b])

    M = []
    Mab = []
    for i in range(div):
        a = randint(0, n)
        b = randint(0, n)
        M.append((a*P) + (b*Q))
        Mab.append([a, b])

    S = R[0]
    i = 0
    while True:
        m = int(S[0]) % div
        S = S + M[m]
        Sa = Rab[i][0] + Mab[m][0]
        Sb = Rab[i][1] + Mab[m][1]

        if S in R:
            Ra, Rb = Rab[R.index(S)]
            d = (Sa - Ra)*inverse_mod((Rb - Sb), n) % n
            return d
        else:
            R.append(S)
            Rab.append([Sa, Sb])
            i += 1

p = 229
a = 1
b = 44

E = EllipticCurve(GF(p), [a, b])
P = E([5, 116])
Q = E([155, 166])

d = 176

assert Q == d * P

print d
print pollards_rho(E, P, Q, 20)

実行結果

# sage elliptic.sage
176
176

誕生日のパラドックスによれば、コリジョンペアを見つけるには $\sqrt{n}$ 個の点を計算・保存する必要があるが、保存する点を特徴点（その点の $x$ 座標がある値 $\theta$ で割り切れる点)に限定することで、記憶すべき点の個数を $1/\theta$ に節約することもできる。

したがって、Pollard's rho algorithmは $\sqrt{n}$ 回のスカラー倍算を必要とするため、Baby-step giant-stepと同程度の計算時間を必要とするが、保存するべき点の数は $\sqrt{n}/\theta$ となり、Baby-step giant-stepよりも少なくて済むというメリットがある。

なお、楕円曲線上の離散対数問題に対してはPollard's rho algorithmが最も優れていることが経験的に知られているが、さらに優れた解法が登場することは否定されていない。楕円曲線上の離散対数問題に対するほかのアプローチは、「ECDLPに対する攻撃手法のまとめ - 一般的攻撃手法 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです」によくまとまっている。

参考

2016-12-19

【CTF】暗号の勉強を始めて1年たったのでWriteupまとめてみた

CTF セキュリティ暗号プログラミング

本稿は「CTF Advent Calendar 2016 - Adventar」19日目の記事です。

去年の冬あたりからCTFの暗号問題を解くようになって、Writeupがだいぶ溜まってきたので整理して公開しました（一部紛失してしまいましたが）。

「あの暗号のあの攻撃ってどうやるんだっけ」ってなったときに（自分が）見返すのに役立つと思います。

といってもほとんどソルバのスクリプトと一言Writeupだけのものなので、今後充実させていこうと思います。

github.com
f:id:sonickun:20161215003828p:plain

ちなみに去年の私の実力は「RSAのアルゴリズムなら知ってる（素因数分解以外に攻撃あるの？）」、「ブロック暗号モードってなに？」ぐらいでしたが、今ではRSAの公開鍵を読めばある程度既知の脆弱性を見つけられますし、パディングオラクルを見つければすぐExploitを書けるくらいにはなりました。

まだまだ世界のトップCryptographerの足下に及びませんが、追い付け追い越せで頑張ります。

2016-12-08

Webトラッキングの大規模調査―Online tracking: A 1-million-site measurement and analysis

セキュリティ研究

本稿は「情報セキュリティ系論文紹介 Advent Calendar 2016 - Adventar」9日目の記事である。

ACM CCS 2016で発表されたWebトラッキングに関する論文を紹介する。なお、本記事で用いられている図表はこの論文から引用したものである。

Online tracking: A 1-million-site measurement and analysis

背景と前提知識

Webトラッキングとは、オンライン上でのユーザーの行動を追跡・分析する営みのことを言う。皆さんも、ショッピングサイトで閲覧したことのある商品（またはそれに関連するもの）の広告が、別のサイトで表示された経験があるのではないだろうか。そういった現象の裏ではWebトラキングの技術が使われている。

Webトラッキングのあまり知識がない場合は、過去に#ssmjpで発表を行った時の資料を参照されたい。

進化するWebトラッキングの話 #ssmjp from sonickun

www.slideshare.net

Webトラッキングはターゲット広告やアクセス解析等に活用さている一方で、ユーザーのプライバシー侵害や不正広告への悪用といったリスクもはらんでいる。学術界でも近年頻繁にWebトラッキング関連の論文が発表されており、大きく分類して以下の3つの論調がある。
・Webトラッキングのメカニズム解明（新たなFingerprinting手法の提案など）
・Webトラッキングの防御（Anti-Fingerprinting手法の提案、ユーザーのプライバシーを保護した広告システムの提案など）
・Webトラッキングの実態調査（Webクローラを用いた大規模調査など）

今回紹介する論文は3つ目のMeasurement系の論文の当たる。Measurement系の研究の意義は”Transparency”を高めることにあり、それによって何らかの示唆や提言を与えることを目指している。

論文紹介

Title: Online Tracking : A 1-million-site Measurement and Analysis
Authors: Steven Englehardt and Arvind Narayanan of Princeton University
Conference: ACM CCS 2016

著者らはこの論文を紹介するためのWebサイトを公開している。

Online tracking: A 1-million-site measurement and analysis

ちなみにACM CCSは、情報セキュリティ系の国際会議（Security Conference Ranking and Statistic）でRank1に位置する、いわゆるTop of Topのカンファレンスである。

※記事が長くなってしまったが、忙しい人には次の「3行で概要」と「Key Findings」だけを読んでいただけばざっくりと論文を理解できるかと思う。

3行で概要

Alexa100万サイトの大規模かつ詳細なWebトラッキングサイトの実態調査を行った。
Cookie/Fingerprintベースのトラッキング、対策ツールの有効性、Cookie Syncingについて調査を行った。
実ブラウザおよびヘッドレスブラウザにより自動的にクロールを行うプラットフォーム「OpenWPM」を開発した。

Key Findings

トラッキングサイトのリンク数の分布は「ロングテール型」になることが分かった。
トラッキング強度の定量化手法を用いて、トラッキング対策ツールであるGhosteryが有効に働くことを示した。
Cookie Syncingが以前よりも広く利用されるようになった。
調査の中で、これまで観測されていなかった新たなFingerprinting手法を観測した。

OpenWPM

OpenWPMは著者らが開発した、実ブラウザとヘッドレスブラウザを用いて自動的にWebクロールを行うプラットフォームである。
f:id:sonickun:20161204181115p:plain

OpenWPMの特徴は以下のとおりである。

Browser automation: ブラウザをプログラムによって制御する
Stateful crawls: セッションごとにCookieやLocal Storageを保存する
Persistent profiles: セッションをまたいでCookieやLocal Strageを維持する
Fine-grained profiles: Flash Cookieなどの補助的な個別の情報を保持する
Advanced plugin support: ブラウザのプラグインを使用することができる
Detect tracking cookies: Cookie Syncで使用されるCookieを検知する
Monitor state changes: Cookieやブラウザ情報に対するアクセスを記録する
JavaScript Instrumentation: JavaScriptが実行可能である

OpenWPMは過去のmeasurement研究で用いられたWebクローラよりも高機能に作られており、より網羅的かつ詳細な分析が可能になっている。
f:id:sonickun:20161204182106p:plain

こういった実態調査のためのツールは研究コミュニティで広く共有されるべきとして、著者らはOpenWPMとそのログデータを公開している。
github.com

実態調査

OpenWPMを用いてAlexaのTop100万サイトをクロールし、Webトラッキングの実態調査を行う。Webサイトにアクセスした際のHTTP request/responseやJavaScriptの実行ログを収集する。今回はトップページにのみアクセスし、エラーハンドリングのために1サイトごとに90秒のタイムアウトを設けている。

前述したKey Findingsにならって実態調査の結果を示す。

トラッキングサイトのリンク数の分布は「ロングテール型」になる

トラッキングサイトにはファーストパーティ（ユーザーが直接アクセスするサイト）とサードパーティ（ファーストパーティからリンクされている外部のサイト）に分類されるが、調査の結果、2つ以上のファーストパーティからリンクされているサードパーティが81,000サイト抽出された。下図のようにリンク数の大きい順にサードパーティを並べると、ロングテール型のグラフになる。最もリンク数の多かったgoogle-analytics.comは、ファーストパーティ100万サイトのうち、約70%という非常に広い範囲にリンクされていることが判明した。また、全体の1%（1万サイト）以上にリンクされているサードパーティはわずか123/81,000サイトしかなく、10%（10万サイト）以上にリンクさているサードパーティに至っては、Google、Facebook、Twitter、AdNexusの4組織しか存在しなかった。このことから、ユーザーは日常的にアクセスするほとんどのWebサイトで同一の組織にトラッキングさている一方で、エンカウントするサードパーティの種類はかなり限定的であることがわかった。
f:id:sonickun:20161204222147p:plain

トラッキング対策ツールであるGhosteryが有効に働く

GhosteryはサードパーティのCookieをブロックできるブラウザのプラグインであり、サードパーティによるトラッキングを防ぐことができる。
chrome.google.com
今回の調査では、Ghosteryを用いて、すべてのサードパーティ Cookieのうち99.6%のCookieをブロックでき（ブロックできなかったのは237サイト）、ツールの有効性を示した。
本論文では独自のロジックでサードパーティのProminence（目立ち具合、影響度）を定量化しており、Prominenceが小さいサードパーティ（マイナーなサードパーティ）であるほど、Ghosteryの検知漏れの割合が高いことが分かった。著者らによれば、Ghosteryの検知ロジックの中にはBlacklistを用いた手法が使わているらしく、マイナーなトラッキングサイトほどBlacklistから漏れやくなっているのではないかと分析している。
f:id:sonickun:20161204225221p:plain

Cookie Syncingが以前よりも広く利用されるようになった

Cookie Syncingとは、前提知識のスライドにもある通り、ユーザーを識別するIDを複数のサードパーティで共有し、Same-Origin Policyを超えてトラッキングができる広告システムである。トラッカーAがトラッカーBとユーザーのIDを共有したいとき、トラッカーBへのリクエストURLの中、あるいはリファラURLの中にIDを埋め込む。したがって、HTTP Request/Response をモニターすることでCookie Syncingを検知できる。

調査の結果、最も顕著なCookie Syncingサードパーティであったdoubleclick.netは、118の他のサードパーティと108のユニークなCookieを共有していることが判明した。また、主要な（Prominenceが大きな）サードパーティの大多数は、少なくとも他の1つのサードパーティとCookieを共有していた。驚くべきことに、ProminenceがTop 50のサードパーティを無作為に2つ選択したとき、両者が互いにCookieを共有している確率は約85%であることが分かった。著者らは過去にも同様の調査を行い論文を発表しているが、今回のこの数字は過去のそれよりも高く、Cookie Syncingがより広範に利用されるようになったことを示唆している。

新たなFingerprintingの発見

Webトラッキングで言うところの”Fingerprint”とは、ブラウザの種類、インストールさているプラグインやフォントの種類、スクリーンのサイズといった、端末に固有の情報の組み合わせのこと言い、毎年のように新しいFingerprintが発見さている。今回の調査ではこれまで見つかっていなかった（公に発表されていなかった）Fingerprintを用いたトラッキングを発見している。いわば「ゼロデイFingerprinting」のようなものである。

発見されたFingerprintingは以下の4つである。
・Canvas Font Fingerprinting
Canvasでフォントを指定して文字を描画した際に、画像のサイズをもとにそのフォントがインストールされているかどうかがわかり、インストール済みフォントのリストが作れる。Canvasの画像データのハッシュ値を識別子とするCanvas Fingerprintとは区別される。

・Web-RTC Fingerprinting
Web-RTCで取得できるNAT配下のローカルネットワークのインターフェースやアドレスの情報がFingerprintとして利用されていた。

・AudioContext Fingerprinting
音声を発信するAPIを使うと音声信号がソフトウェア／ハードウェアに依存して微妙に変化することを利用して、フーリエ変換後の周波数情報をハッシュ化しFingerprintとして利用していた。
f:id:sonickun:20161204235550p:plain

・Battery API Fingerprinting
デバイスのバッテリー残量情報を利用して短時間のユーザー識別を行っていた。たとえば、ユーザーがネットサーフィンの途中でシークレットブラウジングに切り替えた際（Cookieが無効になったとき）、バッテリーの減り具合から、シークレットブラウジング切り替え前後のユーザーを紐づけることができる。

その他の発見

サードパーティのトラッキングサイトのHTTPS非対応により、Mixed-content Errorが頻発していることがわかった
トラッキングサイトを分類した結果、ニュースサイトでトラッキングが多いのに対し、政府組織・教育機関・非営利組織のサイトではトラッキングは少ない(Funding sourcesの存在が関係している)
前回の調査から、最も主要な広告サードパーティ（AddThis）がCanvas Fingerprintingを取りやめた（論文を通して脅威を示したことが効果的であった証明）
既存のツールで新しいFingerprintingをブロックできる割合は低い

まとめと今後の展望

本研究のようなWebプライバシーに関する調査は、プライバシー侵害やユーザー⇔Webサイト間の力の不均衡（たとえば、"ユーザーの意思に反して"プライバシー情報が搾取されている状況など）を監視する役割がある。また、調査のためのツールは研究コミュニティの中で広く共有されるべきであり、今回開発したOpenWPMはオープンソースとして公開している。

今後は機械学種によって自動的にトラッキングサイトを検知・分類することを目指している。

所感

・良かった点
過去のWebトラッキングのMeasurement系の論文と比較しても、かなり網羅的かつ詳細な調査を行っている。トラッキングの手法にもさまざまな種類があるが（Cookieを使ったもの、Fingerprintを使ったものなど）、それぞれを検知するのに必要十分なログが取れるようにシステムを開発している。自分もWebクローラを開発した経験があるが、OpenWPMはかなりの労力と時間をかけて作られている印象を受けた。たとえば、任意のブラウザプラグインを動かしながらクロール（ログ記録）したり、JavaScriptの実行ログをすべて記録したり、といったことは、やろうと思ってもなかなかできないことである。しかも開発したツールや収集したデータが公開されており、さすがトップカンファレンスに採択されるだけの論文だなと思った。

また、これまでのMeasurement系の研究にはない試みとして、ゼロデイFingerprintingの発見に成功している。新しいFingerprintというのはこれまで我々が想像しなかったものになるのが常であり、今回見つかったFingerprintもどれもユニークなものばかりであり、大きな驚きがあった。

・いまひとつな点（コマカイ話）
トラッキングされていることはわかっていてもそれが実際にどれほど脅威になりうるのかということはイメージしにくいが、本論文ではトラッキングサイトの影響度（Prominence）を独自の方法で定量化しそれを指標として用いている。しかし、定量化の数式についての妥当性については言及がなく、個人的にはあまり最適とは言えない印象を持った（Paperを見てもらえばわかるが、Alexa最上位のサイトのスコアが異常に高くなり、Google一強にしか見えなくなる）。おそらく「指標が何もないよりよいだろう」という心情で決め打ちで作ったのだろうけど、今後改良の余地があると思う。

また、ゼロデイのFingerprintingの検知について、どうやって見つけたのか？というと、著者らによれば「JSの実行ログを見てりゃわかる」といった言いっぷりだったが、それだけではいくらProfessionalでも膨大なログから見つけるのは難しいとおもう。おそらく「このへんがFingerprintとして狙われるだろう」というヤマを張っておいて見つけたのだろうと推測する。ヒューリスティックな方法ではなく、ある程度自動的にゼロデイFingerprintingを検知できるような手法（例えば、同じサイトのJSコードの変化を継続的に監視するなど）が共有されればなおよいと思った。

他にも、トラッキング対策ツールを他のものともっと比較検証するとよいのではないか、など、まだまだコマカイ話はあるが、今回はこの辺にしておこうと思う。

2016-12-07

SageMathでPythonの外部ライブラリを使えるようにする

プログラミング

SageMathはPythonベースで作られているが、外部の（標準でない）Pythonライブラリをインポートしようとするとエラーが起きることがある。

たとえばPyCryptoだと、普通のPythonの対話シェルではインポートできているのに、

$ python
Python 2.7.11 (default, Dec  7 2016, 17:13:00)
[GCC 4.4.7 20120313 (Red Hat 4.4.7-17)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from Crypto.Util.number import *
>>>

Sageでは失敗する。ということが起きる。

$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.3, Release Date: 2016-08-04                     │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: from Crypto.Util.number import *
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-3aca3f9edb99> in <module>()
----> 1 from Crypto.Util.number import *

ImportError: No module named Crypto.Util.number

この場合、Pythonライブラリを"Sageから"インストールする必要がある。

Solution

Sageには「シェルモード」というものがあり、そのモードでPythonライブラリのインストールコマンドを打てばよい。シェルモードはsage -shで起動する。

$ sage -sh

Starting subshell with Sage environment variables set.  Don't forget
to exit when you are done.  Beware:
 * Do not do anything with other copies of Sage on your system.
 * Do not use this for installing Sage packages using "sage -i" or for
   running "make" at Sage's root directory.  These should be done
   outside the Sage shell.

Bypassing shell configuration files...

Note: SAGE_ROOT=/path/to/sage-7.3
(sage-sh) $ pip install pycrypto
Collecting pycrypto
  Using cached pycrypto-2.6.1.tar.gz
Installing collected packages: pycrypto
  Running setup.py install for pycrypto ... done
Successfully installed pycrypto-2.6.1
(sage-sh) $ exit

これにてSage上でPyCryptoが使えるようになる。

おわり。

2016-11-20

CTFにおける離散対数問題に対するアプローチ

CTF セキュリティ

CTFの暗号分野では、離散対数問題を利用したアルゴリズム（ElGamal暗号、Diffe-Hellman鍵共有など）がよく扱われる。本稿ではこの離散対数を高速に解く方法を備忘録としてまとめておく。

離散対数問題（DLP: Discrete Logarithm Problem）

素数 $p$ と定数 $g$ が与えられたとき

${ \displaystyle g^x \equiv y\pmod{p} }$

において、 $x$ から $y$ を計算することは容易だが、その逆の、 $y$ から $x$ を求めることは困難であることを、離散対数問題と呼ぶ。公開鍵暗号方式では、このことを安全性の根拠とした暗号アルゴリズムがいくつか考案されている。CTFでは、この離散対数を解き、暗号の秘密鍵を特定する問題が出題される。

離散対数に対するアプローチ

離散対数に対するアプローチとして、列挙法、Baby-step Giant-step algorithm、Pohlig–Hellman algorithmの3つの手法を紹介する。

列挙法

列挙法は最もシンプルな手法であり、上式において、 $x=1,2,3,4,...$ に対して合同式が成り立つかどうかを一つひとつ確認していく方法である。ただし、 $g$ の位数が大きいときは膨大な試行数になるため現実的ではない。オーダーは ${\mathcal{O}(n)}$ 。

Baby-step Giant-step algorithm

Baby-step Giant-step algorithmは列挙法による試行数を削減したアルゴリズムであり、オーダーは ${\mathcal{O}(\sqrt{n}\log n)}$ となる。

${ \displaystyle g^x \equiv y\pmod{p} }$

において、 $x=im+j$ （ $m=\lceil\sqrt{p}\rceil$ 、 $0 \leq i,j \lt m$ ）として、以下の式を得る。

$\begin{align} g^{im+j} &\equiv y\pmod{p} \\ g^j &\equiv y(g^{-m})^i\pmod{p} \end{align}$

このアルゴリズムでは上式の両辺が一致するように $i$ と $j$ を総当たりし、 $x$ を求める。そうすることで、列挙法よりも試行数が少なくて済む。
Baby-step Giant-step algorithmの詳細な手順は以下のとおりである。

1. $m\leftarrow \lceil\sqrt{p}\rceil$
2. $0 \leq j \lt m$ を満たすすべての $j$ について（Baby-step）：
　1. ${g^j \pmod{p}}$ を計算し、 ${(j, g^j \pmod{p})}$ のペアをテーブルに保存する
3. ${g^{-m}}$ を計算する
4. $\gamma\leftarrow y$
5. $i=0$ から $(m-1)$ まで（Giant-step）：
　1. ${\gamma}$ がテーブルの第二要素 ${(g^j \pmod{p})}$ に含まれるかチェックする
　2. もし含まれていれば、 $x=im+j$ を返す
　3. もしそうでなければ、 $\gamma\leftarrow \gamma \cdot g^{-m}$ とする

Pohlig–Hellman algorithm

Pohlig–Hellman algorithmは、

${ \displaystyle g^x \equiv y\pmod{p} }$

に対し、 $\phi(p)$ の素因数が小さいときに有効に働くアルゴリズムである。ここで $\phi(n)$ とはオイラー特性関数であり、 $n$ より小さい自然数のうち $n$ と互いに素なものの個数を示し、特に $n$ が素数の場合は $\phi(n)=n-1$ となる。

Pohlig–Hellman algorithmのアイデアとしては、 $g$ の位数が大きすぎて総当たりが困難だったものを、 $g$ の位数が小さな離散対数問題に分割して解き、後で結合するといったものである。

まず、 $\phi(p)$ を以下のように素因数分解する。

${ \displaystyle \phi(p) = p_1 \cdot p_2 \cdot\cdot\cdot p_n }$

このとき、 $p_i$ の値は小さい（英語では"smooth"という）ことが望ましい。
$x = a_k p_k+b_k$ としたとき、それぞれの $k$ についてオイラーの定理より以下の計算を行う。

$\begin{align} y^{\phi(p)/p_k} &\equiv (g^x)^{\phi(p)/p_k}\pmod{p} \\ &\equiv (g^{\phi(p)})^{a_k}g^{b_k\phi(p)/p_k}\pmod{p} \\ &\equiv (g^{\phi(p)/p_k})^{b_k}\pmod{p} \end{align}$

この合同式は最初に示した離散対数問題の形に帰着されるが、 $b_k$ は $p_k$ よりも小さいため、比較的容易に $b_k$ を求めることが可能である（Baby-step Giant-step algorithmも組み合わせればより高速になる）。
これにより $b_k$ の値が定まると、 $x\equiv b_k \pmod{p_k}$ が求まったことになる。

${ \displaystyle x\equiv b_1 \pmod{p_1} \\ x\equiv b_2 \pmod{p_2} \\ \cdot\cdot\cdot \\ x\equiv b_n \pmod{p_n} \\ }$

について、 $p_1, p_2,..., p_n$ は互いに素なので、中国人剰余定理より、これらを満たす整数 $x$ が $\phi(p) = p_1 \cdot p_2 \cdot\cdot\cdot p_n$ を法として唯一つ定まる。こうして求まった $x \pmod{\phi(p)}$ が最初に示した離散対数問題の解となる（ $p$ は素数であるため、 $g$ の位数は $\phi(p)=p-1$ である）。Pohlig–Hellman algorithmのオーダーは ${\mathcal{O}(\sqrt{n})}$ だが、 $\phi(p)$ が小さいほどより効率的となる。

Pohlig–Hellman algorithmを使った攻撃の回避策として、安全素数を使う方法がある。安全素数は、 $q$ と $2q+1$ がともに素数である場合における $2p+1$ である。このとき、 $q$ のほうはSophie Germain素数と呼ばれる。安全素数 $p$ を使うことで、 $\phi(p)=p-1=2q$ となり、 $\phi(p)$ が大きな素因数を持つことになるため、Pohlig–Hellman algorithmが有効に働かなくなる。安全素数が無限に存在するという予想は未だ証明されていないが、実用的には十分存在するといわれている。

実装例

離散対数問題を安全性の根拠としている暗号方式として、ElGamal暗号を取り上げる。ElGamal暗号では、素数 $p$ 、整数 $g$ 、乱数 $x$ $(0\leq x \lt p)$ を選んで、

${ \displaystyle y = g^x \mod{p} }$

を計算し、 $y, g, p$ を公開鍵、 $x$ を秘密鍵とする。
暗号化フェーズでは、平文 $m$ と乱数 $r$ を用いて、以下のように暗号文 $c_1, c_2$ を計算する。

${ \displaystyle c_1 = g^r \mod{p} \\ c_2 = my^r \mod{p} = mg^{rx} \mod{p} }$

復号フェーズでは、平文 $m$ を以下のように算出する。

${ \displaystyle c_2(c_1^x)^{-1} \mod{p} = mg^{rx}(g^{rx})^{-1} \mod{p} = m }$

以上が、ElGamal暗号のアルゴリズムである。
今回は、ElGamal暗号の例題として、MMA CTF 1st 2015で出題された「Alicegame」という問題を扱う。問題より、ElGamal暗号における以下の値が判明している（本当は鍵がランダムに生成され、最適なpが引けるまでガチャを回す必要があるのだが今回はその部分を割愛）。

c1 = 1851635883910479967256646617880733235123029676545812189105888 
c2 = 2279140729739532482438192630521498934347693926502811537441460 
g = 1828219035112142373387222893932751631772945852477987101590090 
y = 1012750243445446249248731524345776923711031192963358920130436 
p = 3047318456124223787871095946374791137939076290647203431778747 
phi_p = 2 * 3 * 7 * 281 * 585131 * 2283091 * 66558319 * 38812459031 * 8407411055293 * 8899182573469

$\phi(p)$ の素因数が小さいので、Pohlig–Hellman algorithmを用いた攻撃が可能である。今回は、Baby-step Giant-step algorithmも併用して以下のようにソルバーを書いた。
gist.github.com
無事、平文を復号できたことがわかる。