【AdC24日目】セキュリティキャンプ2020オンラインに参加しました。

はじめに

みなさん、どうもはじめましての方ははじめまして、そうでない方もはじめまして、19のNです。今回はセキュリティキャンプ2020Lトラック(暗号ファジングトラック)に参加したので、その体験期を書こうと思います。

セキュリティキャンプとは？

セキュリティキャンプとは、セキュリティの様々な分野について学べる合宿なのですが、現状今までの形式で行うのは難しいということもあり、今年はオンラインで開催されています。分野ごとにトラックというものがわかれていて、自分の興味のあるトラックに応募して選考されると受講することができます。

様々な分野がある中でも、僕はLトラックの暗号ファジングトラックというものに参加しました。暗号ファジングトラックとは、暗号そのもの自体や、暗号の脆弱性を突いた攻撃手法などを学ぶトラックです。多分。

セキュキャン△でやったこと

ElGamal暗号の実装

応募課題で題材にした、ということもあり、ElGamal暗号を実装して、その理解を深める、というようなことを最初にやりました。ElGamal暗号とは、離散対数問題の困難性を用いた公開鍵暗号です。

素数 $p$ と $Z / p Z$ の原始元、 $g$ をランダムに生成し、 $0 \leq x \leq p - 2$ となる整数 $x$ をランダムに選び、 $y = g^{x} (m o d p)$ を計算し、公開鍵を $(p, g, y)$ 、秘密鍵を $x$ とします。一般に、十分大きな素数 $p$ に対して、 $y = g^{x} (m o d p)$ を $x$ について解くのは困難であり、これを離散対数問題といいます。

これのKeygen、Encrypto、DecryptoをPythonを用いて実装しました。

ElGamal暗号の拡張

上で述べたElGamal暗号について、一つ問題点を挙げると、巡回群として $Z / p Z$ を用いているので、位数が $p - 1$ となり、これが合成数になってしまいます。 $p$ が合成数だと、ポーリッヒヘルマンのアルゴリズムというアルゴリズムによって、 $p$ の一番大きな素因数の平方根くらいの計算量で離散対数問題が解けてしまいます。これを解決するため、位数が素数の巡回群の上でElGamal暗号をしたい！というお気持ちになるわけです。というわけで、 $p = 2 q + 1 (q は素数)$ という形の $p$ を用いて、 $α = g^{\frac{p - 1}{q}} = g^{2}$ を計算すると、これは位数が $q$ の巡回群の生成元となっています( $α^{q} = 1$ )。そして、この巡回群上で $y = g^{x} (m o d q)$ を計算し、公開鍵として出力すればいいわけです。

これのkeygen Encrypto DecryptoをまたまたPythonを用いて実装しました。

楕円エルガマル暗号の実装

楕円エルガマル暗号とは、楕円曲線上 $(y^{2} = x^{3} + a x + b)$ の $(x, y)$ をプロットしたものに、ある加算演算を定義すると、 $\mod$ のように楕円曲線上の点とその加算演算は巡回群となります。そして、点 $P$ を $n$ 回加算することを $n P$ と書くことにすれば、 $Y = x P$ を $Y$ と $P$ を既知として $x$ について解くことを楕円曲線上の離散対数問題といい、これを利用した暗号です。

楕円曲線上の点への文字割り当てを、楕円曲線上の点を配列に保存した要素数とし、Keygen Encrypto DecryptoをまたまたまたまたPythonを用いて実装しました。

ElGamal暗号への攻撃手法の実装

ポーリッヒヘルマンのアルゴリズム

$ϕ (p)$ の一番大きな素因数を $r$ としたとき、離散対数問題 $y = g^{x} (m o d p)$ を、 $O (r)$ で解けるアルゴリズムです。

ϕ (p) = p_{1} \cdot p_{2} \cdot \dots \cdot p_{k}

と素因数分解できたとすると、 $x = a_{i} p_{i} + b_{i}$ とすれば、

y^{\frac{ϕ ( p )}{p _{i}}} = (g^{\frac{ϕ ( p )}{p _{i}}})^{b_{i}}

となり、 $y^{'} = y^{\frac{ϕ ( p )}{p _{i}}}, g^{'} = g^{\frac{ϕ ( p )}{p _{i}}}, x^{'} = b_{i}$ とすることで、離散対数問題の規模をどんどん小さくしていくアルゴリズムです。この各 $i$ に対して $b_{i}$ が求まれば、 $x = b_{i} (m o d p_{i})$ という連立合同方程式となり、中国剰余定理などで解くことができます。

普通のElGamal暗号を解くものとして、一部次のbaby-step giant-stepアルゴリズムを用い、これをPythonを用いて実装しました。

baby-step giant-stepアルゴリズム

$y = g^{x} (m o d p)$ において、 $x = i m + j$ ( $m = ⌈ p ⌉$ )とすると、 $g^{i m + j} = y \Leftrightarrow y (g^{- m})^{i} (m o d p)$ となり、 $i, j$ を総当たりで求めるというものです。

楕円曲線上のElGamal暗号を解くものとして、これをPythonを用いて実装しました。

終わってみて

サークル内で同期の @temma くんがめちゃめちゃ推してたので、なんとなく応募課題を出してみたところ、通りました。こんな一か月もやるものだとは思っておらず(書いてあるものを読んでから応募しろ。)、思っていたよりめちゃめちゃハードで、忙しい毎日を過ごしましたが、講師の方や、周りの方の進捗具合などにとても助けられながら、なんとか最低限の目標は達成できたのではないかなと思います。オフラインの合宿の方には参加経験がないので比較はできませんが、とても数日で実装できる内容ではなかったですし、Lトラックはゼミ形式ということで、オンラインの環境が適していてよかったのではないかと個人的に思います。勧めてくれたtemma君や、セキュキャンでかかわった方々、本当にありがとうございました。これを見て興味を持った方はぜひ来年応募してみてください！暗号なんて興味ないよ！って人も他にもたくさんのトラックがあるのでぜひ見てみてください！

また、今回実装したものは

こちら

にまとまっているので、よかったら見てみてください。(SECCON2020のthis_is_rsa解いたやつとかも入ってます。)
また、最終成果発表のスライドの方にもっと詳しい実装の内容などが書いてあります。スライドは

Seccamp2020L1 from ChihiroSasaki3

自分で作った暗号を自分で解く、自給自足ホイミ生活ができて楽しかったです。

↓HelloWorld!!という文字列を自分で作って自分で解いてる様子

最後に

明日はtraP激ウマギャグ班の幹部 @NapoliN 君の記事です！お楽しみに！