katagaitai勉強会#7 Cryptoパート writeup
2/25(土)のkatagaitai勉強会に参加してきました。感想文とか書くのは苦手なので、かわりにwriteupを書こうと思います。writeupと言いつつ自分が詰まったりしたところだけをまとめた自分用メモという説もあるけど。
※2017/2/28 22時頃追記:最初は密度が計算できないと書きましたが、できたので修正しました
はじめに
この記事は数学がまったくわからない人が書いています。なので、だいたいフィーリングで書きました。間違っている点が多々あるかもしれませんが、指摘していただけると幸いです。
また、あくまで勉強会に参加した前提で書いており、資料すら見てないとまったくわからないと思うので一応リンクを貼っておきます。
本日のkatagaitai勉強会 #7 暗号編のスライドです。ナップサック暗号の解読方法について解説しています。#katagaitaiCTF https://t.co/6m1yGOuKV6
— trmr (@trmr105) 2017年2月25日
Backpacker's cipher easy modeは以前に解いたことがあり特に疑問点もなかったので省略します。
「数学のお話」以降で、当日理解できなかったところ、後から疑問に思えてきたところをメインに取り扱います。内容は以下の通りです。
・ナップサック問題を最短ベクトル問題に帰着させる
・LO法、CLOS法とは?
・Lazyを解く
・Backpacker's cipher extra modeを解く
・都合の良い格子を思いつく都合の良い頭がほしい
あと、ナップサックなのかナップザックなのかよくわからなので、記事内ではナップサックで統一します。
ナップサック問題を最短ベクトル問題に帰着させる
まずは今回のキモになるところです。ここが脳内でしっくりくるとすごく解きやすくなる気がします。と言っても、スライドp.37〜にほぼ載っていますが、一応。
おそらくここで詰まる場合、以下のように考えていると思います(当日の自分がそうでした)
「ナップサック問題を最短ベクトル問題と見て、それを解いて出てきたものがなんか答え(平文)になってる」
しかし実際はそうではなく、
「求めたい答えが最短ベクトルになりそうな格子を設定して、最短ベクトル問題を解くと答え(平文)が出てくる」
答えから設定してるんだからちゃんと平文が出てくるのは当たり前ですね。ちゃんと資料を読めば書いてあるんですが、なぜか当日の自分はここで一回詰まったので一応書いておきました。
LO法、CLOS法とは?
都合の良い格子の設定方法、ぐらいの感覚で捉えています。具体的な格子の設定方法については下記論文の3--4ページ辺りに書いてありました。
http://www.osakac.ac.jp/labs/yasuyuki/members2004/nasako/tn_files/pdf_files/isec200507.pdf
CLOS法はLO法の改良版で上位互換と捉えているので、基本的にCLOS法を使えば問題ないのかな、と思います。ここで0-1ナップサック問題という言葉がありますが、要は平文が0-1、ビット列であるということです。後で出てきますが、平文がビット列でない場合そのまま適用するのは難しそうです。
また密度の話がありますが、資料に書いてある通りの値を導出することができませんでした。どなたか導出できたら教えてください。
資料通りの計算でちゃんと導出できました。以下の通りに計算できます。
import math
# Lazy
n = len(eval(open("pubkey.text","r").read())[0])
max_a = max(eval(open('pubkey.txt').read()))
a = math.log(max_a,2)
print n/a
# 0.900711404738
# extra mode
n = len(eval(open("pubkey","r").read())[0])
max_a = max(eval(open("pubkey","r").read())[0])
a = math.log(max_a,2)
print n/a
# 1.21176891884
Lazyを解く
当日もらったソルバをそのまま使ってもつまらないので、上のCLOS法に書いてあった行列からやってみました。理解のために必要以上にコメントを入れてます。
元のCLOS法の行列をそのまま再現してるだけなので説明はいらないかと思います。判定条件とかも資料そのままです。特に問題なく解くことができました。
FLAG:lenstra_and_lovasz_liked_lattices
Backpacker's cipher extra modeを解く
色々ごちゃごちゃやってるように見えますが、46--48行目がポイントで、公開鍵aと暗号文encrypted_keyから平文xを求めるだけの問題です。これもLazyのソルバを使い回して解こうと試みましたが、いくつか問題が発生してうまくいきませんでした。
一番の問題は、密度が1を超えるということです。上で密度の導出がわからないということを書きましたが、適当に計算すると1.17くらいになりました。資料とは異なる値でしたが1を超えることはわかります。(ちなみにLazyは0.88になりました) 密度は1.21になります。
密度が1を超えると1つの暗号文に対して複数の平文が存在しうるということが資料にも書いてあります。本来この問題の平文xは0,1のみですが、最短ベクトルとして本来の平文ではないものが出てくる可能性があり、その最短ベクトルは0,1だけではなく適当な値が入っているはずです。(資料p.52より)
つまり、密度が1を超えるということは平文xが0,1だけとは限らないという厄介な状況に帰着します。
まず1つめの厄介な点として、最短ベクトルの判定が難しくなります。Lazyのときは±1、0という値以外とらないため判定に使えましたが、今回はなんでもとりうるためn列目が0という条件しか使えず、最短ベクトル候補がたくさんでてきます。しかしこれだけなら全部確かめればいいのですが、まだ他に根本的な問題が発生します。
2つめの厄介かつ致命的な点として、求めたいベクトルが出てきません。そもそもなぜ求めたいものが最短であったかを振り返ると、0-1ナップサック問題であるためBx-tというベクトルの長さが高々√nであったためです。CLOS法では行列を作る際にrnという変数として√nをかけているため、他のベクトルはすべて長さが√n以上になることが期待でき、それ故に最短ベクトルして導出されていました。
しかし今回は平文が0,1でないため、2x-1という項がそのまま出てきてしまい、求めたいベクトルの長さが比較的長くなってしまうと思われます。そのため最短にならず、CLOS法をそのまま適用しても平文を求めることができません。
というわけでゴチャゴチャ書きましたが、CLOS法を使うのを諦めて、求めたいベクトルが短くなるように頑張ります。
まず、2x-1という項が問題なので2倍することをやめます。次に、1を引く必要もないので引くことをやめます。この時点でxだけになったのでこれ以上は短くできません。また、√nという値をかけていたところを適当に大きな値に変えます。最後に、最短ベクトルの判定条件を増やすために1だけの列を付け加えます。
というわけで以下のような行列を作ります。
1 0 0 0 ... 0 ca1 0 0 1 0 0 ... 0 ca2 0 ⋮ 0 0 0 0 ... 1 can 0 0 0 0 0 ... 0 -cS 1
結果的には資料p.53の基底とほぼ等しいですね。判定条件等も一緒です。以下ソルバです。
結局資料に沿って解く形になってるので解説はいらないかと思います。
FLAG:TWCTF{Hilarious_cruising}
都合の良い格子を思いつく都合の良い頭が欲しい
「都合の良い格子を使えば答えが出るのはわかった。問題は都合の良い格子をどう思いつくか。」
資料を読んでるときに思ったことです。
しかし、extra modeの方を解く際に色々格子をいじってたら、都合の良い格子に帰着することができました。現在の結論ですが、おそらくこんな感じと考えています。
・0-1ナップサック問題はCLOS法を使っておけばいい
・そうでない場合はなるべくベクトルの距離が短くなるように頑張る
今後それで解けなかったらまた考えます。
さいごに
数学がまったくわからず、格子理論という言葉を見ただけで逃げ出していた自分でもここに書いたぐらいのことは理解することができました。家でじっくり資料を読んだらちゃんと理解でき、改めて見てもわかりやすくまとまっていると感じました。本当にありがとうございました。
(SHA-1の宿題とか他のジャンルもこれからがんばります)