Crypto講義資料

CpawCTF勉強会のCrypto講義資料です。

Transcript

1. $SZQUPߨٛ
   ぱろっく 1
2. ここまで本当にお疲れさまです！ 2
3. Reversingでかなり疲れてると思いま す、難しいですよね。 3
4. これで最後なので 頑張っていきましょう！ 4
5. 講義概要 —  暗号とは[p5-] —  換字式暗号(シーザー暗号)[p23-] —  換字式暗号(ヴィジュネル暗号)[p29-] —  公開鍵暗号(RSA暗号)[p52-] —  参考資料[p73-] 5
6. 暗号とは —  通信相手以外の第３者に通信の内容を読まれないように する技術。 6
7. A君 Bさん 好きです！ 付き合ってくださ い！ 手 紙 Bさん の下駄 箱 C君 7
8. A君 Bさん 好きです！ 付き合ってくださ い！ 手 紙 Bさん の下駄 箱 C君 A君はBさんの ことが好き だったのか！ 8
9. 暗号化すると？ 9
10. A君 Bさん 魚けぼすまげあ！ ばばぐとろぢざぴむ ん！ 手 紙 Bさん の下駄 箱 C君 何言ってんだ こいつ 10
11. 暗号とは —  通信相手以外の第３者に通信の内容を読まれないように する技術。 —  英語では「Cryptograph」「Cipher」。 —  CTFではよくcrypto(クリプト)と呼ばれています。 11
12. 暗号に似ている技術も紹介 12
13. ハッシュ関数 —  入力したデータを表す数値(ハッシュ値)を返す関数。 —  データ検索の高速化やデータ改ざんの検知に用いられる。 13
14. 暗号学的ハッシュ関数 —  情報セキュリティで用いるのに適しているハッシュ関数。 —  同じハッシュ値が事実上生まれない必要がある。 —  ハッシュ値から元のデータを求められない必要がある。 14
15. 暗号学的ハッシュ関数の例 —  MD5…128bitのハッシュ値を作る。 —  「aaa」 47bce5c74f589f4867dbd57e9ca9f808 —  SHA-1…160bitのハッシュ値をつくる。 —  「aaa」 7e240de74fb1ed08fa08d38063f6a6a91462a815 15
16. 暗号とハッシュ関数 —  文章を読めなくするという行為自体は同じ。 —  暗号は、復号して元のデータをよむのが目的だが、ハッ シュ値は、元のデータに戻せない。 16
17. では、どんな暗号があるか 見ていきましょう。 17
18. 暗号の種類 —  古典暗号 —  換字式暗号 : 別の文字を割り当てる暗号 —  転置式暗号 : 文字を並び替える暗号 —  現代暗号 —  共通鍵暗号 : 一つの鍵で暗号化＆復号する暗号 —  公開鍵暗号 : 暗号化と復号でそれぞれ別の鍵を 使う暗号 18 ※大雑把に分類しています。
19. 暗号の種類 —  古典暗号 —  換字式暗号 : 別の文字を割り当てる暗号 —  転置式暗号 : 文字を並び替える暗号 —  現代暗号 —  共通鍵暗号 : 一つの鍵で暗号化＆復号する暗号 —  公開鍵暗号 : 暗号化と復号でそれぞれ別の鍵を 使う暗号 19 ※大雑把に分類しています。
20. まずは、換字式暗号 20
21. 換字式暗号の種類 —  単一式換字 —  シーザー暗号 —  多表式換字 —  ヴィジュネル暗号 21
22. 換字式暗号の種類 —  単一式換字 —  シーザー暗号 —  多表式換字 —  ヴィジュネル暗号 22
23. シーザー暗号 —  古代ローマの指導者カエサルが使い始めた。 —  シンプルなため、軍事目的では使わず、私的な通信で用い られていた。 23
24. シーザー暗号 —  それぞれの文字をアルファベット順に従って鍵の数だけず らす暗号。 24 画像引用元:wikipedia 鍵=３
25. シーザー暗号 flag is simple_crypto synt vf fvzcyr_pelcgb 25 暗号化（鍵=13）
26. シーザー暗号 —  アルファベット以外は無視することが多い。 —  鍵が26通りしかないためブルートフォース(総当り攻撃)が 容易。 26
27. シーザー暗号 —  CTFでは、頻度分析ができないくらい短い文字列を見かけ たらシーザー暗号を疑ってみるべき。 ※頻度分析…文章に出てくるアルファベットの出現頻度を調べること。英 語の文章では、出現頻度の高いアルファベットがある程度決まっているの で、頻度分析から暗号を解読する手法がある。 27
28. 換字式暗号 —  単一式換字 —  シーザー暗号 —  多表式換字 —  ヴィジュネル暗号 28
29. ヴィジュネル暗号 —  ヴィジュネルさんが作った暗号。 —  単一換字式暗号が安全じゃないよって言われ始めたため 開発された。 —  変換表と鍵を元に、平文を暗号化する。 29
30. ヴィジュネル暗号 —  暗号化：ヴィジュネル方陣に鍵と平文を一文字ずつ当ては め、対応する文字を並べたものを暗号文とする。 —  復号：暗号化の手順を暗号文と鍵を元にたどる。 30
31. ࢀߟ ϰΟδϡωϧํਞ
    31 引用元： wikipedi a
32. 各 行 ー ー 暗 号 ࢀߟ ϰΟδϡωϧํਞ
    32
33. 文で説明しても分かりづらいので、具 体例を見ていきましょう。 33
34. ヴィジュネル暗号 平文 : FLAG 鍵 : TEA とする。 ヴィジュネル方陣を使い暗号化する。 34
35. １文字目 : 平文 FLAG 鍵 TEA 35
36. １文字目 平文=「F」 鍵=「T」 36
37. ２文字目 : 平文 FLAG 鍵 TEA 37
38. ２文字目 平文=「L」 鍵=「E」 38
39. 3文字目 : 平文 FLAG 鍵 TEA 39
40. ３文字目 平文=「A」 鍵=「A」 40
41. 4文字目 : 平文 FLAG 鍵 TEA 41
42. ４文字目 平文=「G」 鍵=「T」 42
43. 暗号文：「YPAZ」 43
44. ヴィジュネル暗号 —  暗号文と鍵を一文字ずつヴィジュネル方陣に当てはめると、 FLAGという文字列になる。 —  鍵長を変えれば無限に鍵が存在することになり、解読は難 しいとされていた。 44
45. 暗号の種類 —  古典暗号 —  換字式暗号 : 別の文字を割り当てる暗号 —  転置式暗号 : 文字を並び替える暗号 —  現代暗号 —  共通鍵暗号 : 一つの鍵で暗号化＆復号する暗号 —  公開鍵暗号 : 暗号化と復号でそれぞれ別の鍵を 使う暗号 45 ※大雑把に分類しています。
46. 公開鍵暗号 —  公開鍵、秘密鍵という２種類の鍵を用意する。 —  暗号化する際は公開鍵、復号する際は秘密鍵で行う。 46
47. ①公開鍵を渡す(他人に見られても問題無い) ②公開鍵で暗号化する ③暗号文を送る(傍受されても読めない) ④秘密鍵で復号する ެ։⓻҉߸ํࣜͷྲྀΕ
    47
48. 公開鍵暗号の種類 —  ElGamal(エルガマル)暗号 —  RSA暗号 —  楕円曲線暗号 48
49. CTFによく出る公開鍵暗号は？ 49
50. 公開鍵暗号の種類 —  ElGamal(エルガマル)暗号 —  RSA暗号 —  楕円曲線暗号 50
51. RSA暗号 —  公開鍵暗号。 —  現在バリバリ現役で活躍している暗号。 —  CTFでよく出題される暗号の一つ。(攻撃手法が沢山ある) 51
52. ここから数学のお話を少しだけ。 数学が苦手な方もいると思いま すが、頑張って下さい！ 52
53. RSA暗号の仕組み 53
54. RSA暗号(鍵生成編) ①　素数を２つ用意する。(p,qとする) ②  　　　　　　　　とする。 ③  　　　　　　　　　　　と互いに素な数(最大公約数が1となる 数)eを決める。 ④  公開鍵完成。（ n と e の２つ） 54 n = p×q φ(n) = (p−1)(q −1) (p−1)×(q −1) ※よく、いろいろなサイトで　　　　　　　　　　　　　　　　と表現 します。これは、オイラーの関数と呼ばれるものです。
55. RSA暗号(鍵生成編) ⑤ 秘密鍵をdとする。 ⑥ dを以下のように設定する。 ⑦ ↑を式変形して、↓の式を作る。 ⑧ 拡張ユークリッド互除法によりdを求める。 ⑨ 秘密鍵完成。 55 ed ≡1(mod(p−1)(q −1)) ed +φ(n)(−x) =1 ※詳細は参考１[p74] ※詳細は参考2,3[p75,76]
56. RSA暗号(暗号化編) ① 平文をxとし、暗号文をcとする。 ②  　　　　　　　　　となる。 ③  おわり。 56 c = xe modn
57. RSA暗号(復号編) ①　　　　　　　　　となる。 ②おわり。 57 x = cd modn
58. RSA暗号 —  仕組みは以上です。 —  式だけでは理解しづらいので、具体的な例を見ていきましょ う。 58
59. RSA暗号 平文c=26とする。 各パラメータを、以下のようにする。 　　　　　　　　　　 59 p = 5,q =11,e = 3 n = p×q n = 55
60. RSA暗号 秘密鍵dを求める。 60 ed ≡1(mod(p−1)(q −1)) 3d ≡1(mod40) d = 27
61. RSA暗号 公開鍵e,nを使い暗号文cを作る。 暗号化完了！ 61 c = 263 mod55 c = 31
62. RSA暗号 次はこれを復号していきます。 といっても、秘密鍵dの数だけ累乗するだけ。 無事復号完了！ 62 x = 3127 mod55 x = 26
63. なぜRSA暗号は安全なのか —  復号するには秘密鍵dが必要。 —  dを求める式は、 —  eは公開鍵なので、pとqが必要。 63 ed ≡1(mod(p−1)(q −1))
64. なぜRSA暗号は安全なのか —  p,qはどこで使われているのか→公開鍵n —  —  攻撃者はnを素因数分解できれば解読できる。 64 n = p×q
65. なぜRSA暗号は安全なのか —  p,qはどこで使われているのか→公開鍵n —  —  攻撃者はnを素因数分解できれば解読できる。 65 巨大な数の素因数分解は困難！ n = p×q
66. RSA暗号への攻撃手法 —  現在512bit程度までなら素因数分解が現実的な時間で可 能。 —  CTFで512bit以下の公開鍵nがあれば素因数分解がほぼ できる。 66
67. RSA暗号への攻撃手法 —  平文xが短く、 のとき、暗号文 のe乗根を求めて あげれば元に戻る。 —  eが３などの小さい数の時は、試してみるとよい。 67 xe < n xe
68. RSA暗号への攻撃手法 —  攻撃手法は本当に沢山あります。 —  CTFでよく出題されるので、暗号やりたいなという方は調べ てみてください。 —  数学の知識が必要となる場合が多いので、先に数学を学 ぶことをお勧めします。 68
69. おすすめの参考書 —  情報数学の基礎　サイエンス社 —  暗号技術入門　SBCreative —  暗号理論と楕円曲線　森北出版株式会社 69
70. 以上です。お疲れさまでした！ 70
71. 参考資料 71
72. (参考1)式変形の詳細 (e× d) /φ(n) = x…1 ed ≡1(mod(p−1)(q −1)) e× d = φ(n)× x +1 これは、eとdを掛け合わせたものをΦ(n)で割った 余りが１という意味なので、以下のようにかける。 φ(n) = (p−1)(q −1) と書くことができる。これを、式変形すると、 ed +φ(n)(−x) =1 72
73. ed +φ(n)(−x) =1 (参考2)拡張ユークリッド互除法できる？ edとΦ(n)はそれぞれ定数なので、例えば以下のよ うな式と同じ形である。 5x + 21y =1 なので、拡張ユークリッド互除法によって、dとxが整 数となる組み合わせを探せばよい。 拡張ユークリッド互除法のやり方については、次頁 を参照。 73
74. 23x + 7y =1 (参考3)拡張ユークリッド互除法の例 上の式を満たす整数の組み合わせ(x,y)を求める。 式の意味などは省略する。 23/ 7 = 3...2 7 / 2 = 3...1 2 /1= 2...0 74 2 = 23− 7×3 1= 7− 2×3 1= 7−(23− 7×3)×3 1= 23×(−3)+ 7×10 23×(−3)+ 7×10 =1 x = −3, y =10 代入
75. 付録 75
76. 擬似乱数のお話 76
77. 擬似乱数 —  プログラムによる計算などによって求めている擬似乱数列 による乱数。 —  擬似乱数を作るアルゴリズムを擬似乱数生成法、擬似乱 数を作る機械やプログラムを擬似乱数生成器と呼ぶ。 77
78. 暗号論的擬似乱数 —  過去の乱数から、次の乱数を予測できないような擬似乱数 列のこと。 —  暗号で用いる鍵を作成するときは、暗号論的擬似乱数でな くてはならない。 —  CTFではわざと暗号論的擬似乱数を用いないで、鍵を推測 させる問題が出ることがある。 78
79. 主な古典的擬似乱数生成法 —  平方採中法（２乗中抜き法） —  線形合同法 79
80. 主な古典的擬似乱数生成法 —  平方採中法（２乗中抜き法） —  線形合同法 80
81. 平方採中法 —  最初の数値を適当に定める。 —  その値を２乗し、間にある必要な桁数を次の乱数とする。 —  桁数が足りない時は最上位に0をつける。 81
82. 平方採中法 —  3桁の乱数を4つ作ってみる。 —  46212 = 21353641 —  35362 = 12503296 —  50322 = 25321024 —  32102 = 10304100 —  乱数列[3536, 5032, 3210, 3041] 82
83. 主な古典的擬似乱数生成法 —  平方採中法（２乗中抜き法） —  線形合同法 83
84. 線形合同法 —  以下の漸化式で与えられる乱数列。 —  A>0, B≧0, M>A, M>B 84 (A× X n + B)modM = X n+1
85. 線形合同法 —  A=13,B=57,M=89とする。 —  シードX 0 を12とすると、X 1 は、 —  このようにして、乱数を求めていく。 85 (13×12 + 57)mod89 = X 1 X 1 = 35
86. 近年の擬似乱数 —  線形合同法などは、周期が短いなどの欠点がある。 —  そのため、メルセンヌ・ツイスタなど新しい擬似乱数が開発 されている。 86
87. メルセンヌ・ツイスタ —  http://www.math.sci.hiroshima-u.ac.jp/~m-mat/ MT/MT2002/CODES/mt19937ar.c —  メルセンヌ・ツイスタは２種類あって、主に使われているの はmt19937というアルゴリズム。 —  周期が219937-1ととても長い。 —  623個の今までに出現した数値があれば予測可能なため、 暗号論的ではない。 —  開発者のソースコード↑。 —  興味のある方は読んでみてください。 87