Crypto

暗号。一部では数論とか群論とかの知識が必要。

わりとググると攻撃方法が書いてあったりする。論文まで読まなくても、Wikipediaでも十分だったりする。ただ、暗号アルゴリズム名まではどうにかしてたどり着かないとググりようがないかもしれない。

雑な用語解説

• 困難...イマドキのパソコンを回しても、常識的な時間では解けないこと。指数時間とかあのへん。
• 平文(ひらぶん)...一般人が読めるままのデータ。米:plain textのため、記号pとかがつかわれる。
• 暗号文...暗号化されたデータ。cが使われそう。
• 暗号化...元と同じ情報を保ちながら、原型を留めないデータに変換して、一般人にわからなくすること。
• 復号(化)...鍵を知っているまともな者が、暗号文から平文をそれを用いて導くこと。
• 解読...鍵を知らない者が魔法で平文を得ること。
• 鍵...暗号化・復号のために使うパラメータ。通常ユーザごとに新たに生成する。これを変えられるようにすることで、同じ暗号アルゴリズムを公開、使いまわせる。
• 共通鍵(暗号方式)...暗号鍵と復号鍵が同じ暗号方式と、その鍵。事前に何らかの方法で暗号者と復号者で鍵を示し合わせる必要がある。
• 公開鍵(暗号方式)/秘密鍵...暗号鍵と復号鍵が異なり、しかも前者から後者を導き出すことが困難である暗号方式とその鍵。前者が公開鍵、後者が秘密鍵。その名の通り、公開鍵は公開して良い。２つの鍵はペアとして生成される。
• セキュリティパラメータ...公開鍵暗号方式のアルゴリズムにおいて、秘密鍵なしに復号しようとするときに困難さを表す尺度。困難さを自由に決められるようになってて、要はコンピュータの性能が時代とともに上がっていってもこれを大きくすれば同じ暗号を使いまわせる。（大きくしすぎると、普通に使用する人も無駄に計算コストがかかるし、何事も程々が良い。）
• 署名...あるメッセージに対して、それが確かに自分の発行したメッセージであると証明をつけること。他人には偽造できないようにする必要がある。
• メッセージ...まあただのデータ。
• ハッシュ(関数)/メッセージダイジェスト...日本語にするなら要約関数。メッセージを代表する値を導く関数とその値。多価関数でないことがたぶん必要。非単射だけど、あんまり非単射過ぎても困るとか。
• 暗号学的ハッシュ関数...いくつかの要請を加えたハッシュ関数。メッセージをちょっと変えただけで全然違う値が出てくる感じ。
• メッセージ...まあただのデータ。

(狭義)暗号

データを暗号化する意味の暗号。

古典暗号

現代のコンピュータがあればきっとかてる。

換字式暗号

単一換字式暗号

シャーロック・ホームズの黄金虫、踊る人形。

• 頻度分析:http://www7.plala.or.jp/dvorakjp/hinshutu.htm
• 意味ある英語: http://www.quipqiup.com/
• Binary(XOR): https://github.com/hellman/xortool

現代暗号

共通鍵暗号

初期化ベクトル(initial vector; IV)...最初に与えるシード的なにか。

暗号利用モード

ブロック暗号を使うとき、ブロックよりも長い平分を暗号化するときにどうするかという話。暗号利用モード - Wikipedia

これに注目することは、データをちょっと改竄するときに重要になる。問題としてよくあるのは、IV,plain text,cipher textのうち幾つかを操作できるもの。

公開鍵暗号

素因数分解問題根拠

$n=pq (p,q \in \mathbb P)$のとき、(p,q)からnは簡単に求まるけれど、逆は困難なことを仮定する。

Rabin暗号

解が4つから定まらない暗号。

→読んで: Rabin暗号

RSA暗号

みんな知ってる有名暗号。

→読んで: RSA暗号

離散対数問題根拠

バイナリ法(a.k.a 繰り返し二乗法)つよいって話。
$c=a^b (b \in \mathbb N)$で、(a,b)からcは容易だけど（∵バイナリ法)、以下略。

ElGamal暗号

$y=g^x$でy,g,その他を公開して、xを秘密にする。そのまんま。

→読んで: ElGamal暗号

楕円曲線暗号

楕円曲線上の有限体点+無限遠点が可換群をなすので、その上での演算を使ったやつ。
$y=g^x (g,y \in F_q^2∪{O}, x \in N, q=p^n, p \in \mathbb P)$

→読んで: 楕円曲線暗号

他にナップサック問題根拠とか多項式環格子上の最短ベクトル問題根拠とかのがあるらしいよ！

量子暗号

量子状態は観測すると波束の収束しちゃって元に戻せないことから盗聴されたことを確認できたりすごいみたい。
あと量子コンピュータがでてくると素因数分解問題は死ぬみたいだし、指数時間も当てにならなくなってくるからこわい。

広義暗号\狭義暗号

デジタル署名

本人しか知りえない秘密のデータを元に署名を行って、公開されたデータを使って確かに秘密のデータによって署名されたことを確かめられればよいと考えれば、公開鍵暗号方式の中で署名に流用できるものがある。

問題としては、ブラックリストに登録された文字列を含むもの以外には署名してくれる人に対して、適当な文字列に対して署名をさせてからその値から禁止された文字列の署名を得るとか。

ハッシュ関数

求められる要請

1. 原像計算困難性
2. 第2原像計算困難性
3. 強衝突耐性

たとえばWebサービスを作って、ログインシステムを作ったとき、どうしてみたってusernameとpasswordの対応表を作らないといけない。
しかしpasswordをそのまま保存するのは気が引ける。たとえば別の脆弱性(SQL Injection的な)で対応表を盗まれた場合、やっぱりパスワードを複数サービスで使いまわしている人は多いわけで、大変なことになる。そこでパスワードのハッシュ値を求めて、それを保存することをする。認証の際は、入力されたパスワードのハッシュ値と対応表のハッシュ値を比較することにする。
現像計算困難性より、対応表を盗まれたとしても平文のパスワードは守られる。

salt

パスワードを上の様に保存した場合、平文は守られることが多いが、頻度分析に弱い。同じハッシュ値がたくさん現れているなら、そいつらのパスワードはきっと'123456'か'password'だWorst Passwords List。それの対策のために、saltと呼ばれる毎回変わる乱数を使ってハッシュ値を計算し、そのsaltも一緒に保存しておく。これによってたとえ二人が同じパスワードを使っていてもハッシュ値が異なってきて、同じパスワードであることがばれなくなる。

ストレッチング

ハッシュ関数を何度（千単位〜）も通すこと。
$h=MD5^n(m)$
ハッシュ値の計算に時間がかかるようにすることで、単純な総当り攻撃にも時間がかかるようにするという発想。否定的な意見も多い[要出典]。

アルゴリズム

MD5

128bit。強衝突耐性がもはやない。
任意のメッセージから始まる、同じハッシュ値を返す2つのメッセージをわりとはやく求められる。 HashClash

任意のmに対して、$f(m+p1)=f(m+p2)$となるような(p1,p2)を求められる。

SHA-1

160bit。衝突に強くはないらしい。
現役で使われてはいるけど、取り替えるべきっぽい。

SHA-2

SHA-1が強くなった感じ。

SHA-3

公募で選ばれたやつで、今までのからは一新されたらしい。

Length Extension Attack

和: 伸長攻撃。
MD5,SHA-1,SHA-2あたりが対象。

$y=h(m)$において$y,|m|$が既知のとき、任意のデータ$m'$に対して、あるデータ$pad$と$y'=h(m+m'+pad)$を求められる。

→あるメッセージに対するハッシュ値がわかっているとき、メッセージに任意の文字列を含ませたときのハッシュ値が計算できる。

→saltを使いつつ、メッセージとそのハッシュ値の組でメッセージの正当性を検査していたとしても、NULL文字はたくさんくっついちゃうけど任意の文字列をメッセージに含めた正当なデータを作れる。

これらのハッシュ関数のパディングの付け方のせい。

tool: HashPump

誕生日攻撃

誕生日のパラドクスの話。強衝突耐性を破るようなメッセージ組を作るのはそれは大変だけれど、誕生日のパラドクスより、想像したよりは大変じゃないよということ。何度も言うけど、そんなこといったって大変。

further

• 素因数分解
• 電子通貨
• 電子投票
• グループ署名
• ゼロ知識証明
• 量子
• etc...

問題

1. http://ksnctf.sweetduet.info/problem/16

2. ASIS

The flag is encrypted by this code, can you decrypt it after finding the system?