feature image

2020年12月6日 | ブログ記事

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

はじめに

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

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

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

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

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

ElGamal暗号の実装

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

素数の原始元、をランダムに生成し、となる整数をランダムに選び、を計算し、公開鍵を、秘密鍵をとします。一般に、十分大きな素数に対して、について解くのは困難であり、これを離散対数問題といいます。

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

ElGamal暗号の拡張

上で述べたElGamal暗号について、一つ問題点を挙げると、巡回群としてを用いているので、位数がとなり、これが合成数になってしまいます。が合成数だと、ポーリッヒヘルマンのアルゴリズムというアルゴリズムによって、の一番大きな素因数の平方根くらいの計算量で離散対数問題が解けてしまいます。これを解決するため、位数が素数の巡回群の上でElGamal暗号をしたい!というお気持ちになるわけです。というわけで、という形のを用いて、を計算すると、これは位数がの巡回群の生成元となっています()。そして、この巡回群上でを計算し、公開鍵として出力すればいいわけです。

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

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

楕円エルガマル暗号とは、楕円曲線上をプロットしたものに、ある加算演算を定義すると、\modのように楕円曲線上の点とその加算演算は巡回群となります。そして、点回加算することをと書くことにすれば、を既知としてについて解くことを楕円曲線上の離散対数問題といい、これを利用した暗号です。

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

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

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

の一番大きな素因数をとしたとき、離散対数問題を、で解けるアルゴリズムです。

と素因数分解できたとすると、とすれば、

となり、とすることで、離散対数問題の規模をどんどん小さくしていくアルゴリズムです。この各に対してが求まれば、という連立合同方程式となり、中国剰余定理などで解くことができます。

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

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

において、()とすると、となり、を総当たりで求めるというものです。

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

終わってみて

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

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

こちら

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

Seccamp2020L1 from ChihiroSasaki3

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

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

最後に

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

N icon
この記事を書いた人
N

物体が接触している他の物体や地面等の固体の面を押しているとき、その力の面に垂直な成分に対し、同じ大きさで反対向きの、固体の面が物体を押し返す力たそ(◞‸◟っ)

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2020年12月4日
【一緒に始めよう】VSTプラグインをつくる【AdC2020 21日目】
liquid1224 icon liquid1224
2020年12月21日
かけだしデザイナーが「ほぼ」1ヵ月間毎日ロゴを描いてみた話【AdC2020 38日目】
WhiteFox icon WhiteFox
2020年12月17日
一人でゲームを作ったハッカソン【AdC2020 34日目】
Komichi icon Komichi
2020年12月17日
JavaScriptの非同期処理についてのメモ【AdC2020 33日目】
reyu icon reyu
2020年12月13日
全方位木DPについて
ebi icon ebi
2020年12月12日
VRSNSのすゝめ【AdC2020 29日目】
wataame89 icon wataame89
記事一覧 タグ一覧 Google アナリティクスについて