######私たちにはほんのわずか先しかみえないが、しなければならないことがたくさんあることはわかる
アランチューリング
####0.はじめに
重要だと思う、部分だけをざっくり紹介しておきます。
####1.紹介された９つのアルゴリズム
- 検索エンジンのインデクシング
- ページランク
- 公開式暗号法
- 誤り訂正符号
- パターン認識
- データ圧縮
- データベース
- デジタル著名
- 決定不能性
この九つに関連するアルゴリズムがこの本では紹介されています。
今回はその中でも公開式暗号化について詳しく書いていきます。
####2.暗号化と複合化
「暗号化」とは元となるデータに対して、特別な処理を行うことで、別のデータに変換する処理のことをいいます。それに対し、暗号化されたデータを元のデータに戻す処理のことを「復号化」と言います。
#####課題に向き合う
ラップトップからルーターにそしてamazonのサーバーにクレジットのクレジットの番号を送信するとなると、暗号化されていなければ、ルーターに接続している他のユーザーからも、番号に直接アクセスされ大変ですよね。
暗号化した番号を複合化するために、送信側と受信側で特定の秘密の符牒を使って複合化の方法を共有をすると、ルーターの覗き見は防げますが、ネット上で秘密の符牒の共有をしていれば、その秘密の共有すらも覗き見ができますよね
送信者はルーターの覗き見するものを回避しながら、受信者に送信するために暗号化を用いるが、その複合化の方法も送信しなければいけない、複合化の方法ですらも覗き見されてしまう。
解決するためには、過去に送信者がわと何らかの関係で共通の情報がある場合は加算トリックが使用することができる。しかし加算トリックには、統計的な分析によって鍵を見つけ出すことができるので、役には立ちにくいのです。
そしてこの課題を解決するためには、共有する秘密を、どう完璧に構築するかです、
#####現在のコンピューターの秘密の鍵
残念ですが、数学処理が必要になっていきます。
離散べき乗、離散対数です。数式が嫌いな方はYoutubeかGoogleにでも飛んで、好きなこと(この記事を読んだ時間は無駄になりますが、、)に没頭してください。笑
YouTube
Google
離散べき乗を理解するには二つの単純な数学概念が必要になって行きます。
時計算と累乗です。
#####時計算
時計は１２個の数字しか書かれていないのに１２を過ぎると再び１に戻ります。
10 + 4 = 2 であり 11 + 4 = 3であります。時計はMaxが１２でその後ループしています
時計算ではMaxの値を変更し、計算をおこなえます
max = 7
12 + 6 = 4
#####累乗の記法
これ66666は６を連続して5回かけているだけなので、6^5と書いていいですよね
これは先ほどの時計算とも組み合わせることができます。
3^4 = 3333 = 81 = 4 (max = 11
7^2 = 7 7 = 49 = 5 (max = 11
| n | 2^n | 3^n | 4^n |
|---|---|---|---|
| 1 | 2 | 3 | 6 |
| 2 | 4 | 9 | 3 |
| 3 | 8 | 5 | 7 |
| 4 | 5 | 4 | 9 |
| 5 | 10 | 1 | 10 |
| 6 | 9 | 3 | 5 |
| 7 | 7 | 9 | 8 |
| 8 | 3 | 5 | 4 |
| 9 | 6 | 4 | 2 |
| 10 | 1 | 1 | 1 |
| この表は2.3.6から１０乗までの値をMax11の時計算で示している。 |
この二つの概念が理解できれば、実際にコンピューターに使われている。秘密の鍵を共有する方法を説明できます。
ステップ１
ゆずさんとかりんちゃんが二人で秘密の鍵を共有したいのですが、覗き見しようとする、いちごくんがいます。
ゆずさんには8、かりんちゃんには9が与えられます。いちごくんにも１０が与えられます。(秘密値)
ステップ２
時計のMaxの数字を決めます。(11)基数とゆう数字を決めます。(2)
この11と2は三人に公開されます。
ゆずさんとかりんちゃんといちごちゃんでPPNとゆう公開秘密混合値を作ります。
PPN =基数^秘密値(時計のサイズ)
ゆずPPN = 2^8 = 3 (時計のサイズ11)
かりんPPN = 2^9 = 6 (時計のサイズ11)
いちごPPN = 2^10 = 1 (時計のサイズ11)
ステップ３
共有される秘密鍵= 相手のPPN^秘密値(時計のサイズ)
ゆずとかりんで秘密鍵を作る
ゆず 6^8 = 4
かりん 3^9 = 4
この４が秘密鍵になります。
いちごくんがどれだけ頑張ってもゆず、かりんの秘密値は知ることができません。今回紹介したのは鍵交換アルゴリズムといいます。実際数字のスケールはもっと大きくなり、時計のMAXも数百桁の数字を使うので簡単にシステムは破ることができません。暗号化自体は加算トリックで行われます。そしてこの鍵交換アルゴリズムを応用するものの中で最も面白いデジタル著名については次回紹介します！