Labor Insurance Management System |
|
|
Labor Insurance Management System |
|
暗号化においては、「鍵」が重要な意味を持つことが解りました。
では、コンピュータ世界の暗号化技術で言う「鍵」とは一体何なのでしょう。
「鍵」のエッセンスだけ紹介します。
例えば、ある自動車メーカーの鍵が10種類程度しか無かったとしたらどうしましょう？
手当たり次第近所の車の鍵を開けて廻れば、すぐに適合する車は見つかるでしょう。
これでは鍵を掛けている意味が無いのと等しいですね。
(実は15〜6年前の話ですが、私の車の鍵で、兄の車の鍵が開きました。恐ろしい...。)
つまり、鍵を生成する上で最も重要なのは、「鍵の総数」です。これを「鍵空間の大きさ」と言います。
コンピュータの世界では、「鍵空間の大きさ」は、ビット長で決まります。ビットというのは、「0」と「1」の並びです。つまり「鍵」は「0」と「1」だけで構成されています。
「それだけ？」と仰る方もいると思いますが、それだけです。
「それなら簡単に同じ鍵を作れるのでは？」と思うかもしれません。果たしてそうでしょうか!?
ここに「1ビット」の長さの鍵があるとします。1ビットは「0」か「1」のどちらかですので、「2種類」の鍵があることが解ります。
では「2ビット」だったらどうでしょう。「0」か「1」の数字が2つ並んでいる状態ですから、総当りすると下記のようになります。
| 1 | 00 |
| 2 | 01 |
| 3 | 10 |
| 4 | 11 |
つまり、2ビットの空間では4種類の鍵があることが解ります。では、つづけて「4ビット」だとどうでしょうか。
| 1 | 0000 | 5 | 0100 | 9 | 1000 | 13 | 1100 |
| 2 | 0001 | 6 | 0101 | 10 | 1001 | 14 | 1101 |
| 3 | 0010 | 7 | 0110 | 11 | 1010 | 15 | 1110 |
| 4 | 0011 | 8 | 0111 | 12 | 1011 | 16 | 1111 |
0000〜1111まで16種類あります。「ビット長」は2倍になっただけなのに、鍵の個数(鍵空間)は、4倍になっていることが解ります。
これ以上総当りするのは私も面倒なので、式を使って計算したいと思います。
1ビットで「2個の鍵」、2ビットで「4個の鍵」、4ビットで「16個の鍵」ですから「2のn乗」であることがわかりますね。
では少し計算してみましょう。
| ビット | 鍵空間(鍵の個数) | 桁数 |
| 8 | 256 | 3 |
| 16 | 65,536 | 5 |
| 32 | 4,294,967,296 | 10 |
| 64 | 18,446,744,073,709,551,616 | 20 |
| 128 | 340,282,366,920,938,463,463,374,607,431,768,211,456 | 39 |
| ... | ||
| 1024 | 179,769,313,...,624,224,137,216 | 308 |
32ビットでは約42億、64ビットでは...。私には読み方が解りません。とにかく「20桁」の整数です。
社会保険労務士の鍵ペアを作成された方も多数いらっしゃると思いますが、1024ビットの「鍵空間」を利用しています。ちなみに、この1024ビットでは約「300桁」という途方もなく巨大な整数になります。
もしここに、1024ビットの共通鍵で暗号化されたデータがあったとします。共通鍵暗号ですから、同じ鍵を探せば復号化できます。つまり300桁の巨大な整数個の鍵の種類から1つの鍵(ビット列)を見つけなければならない訳です。
「コンピュータで探せば簡単じゃないの？」と思われがちですが、答えは「ノー」です。
総当りで1つずつ試していく方法(ブルートフォースアタック)を用いて、皆さんがお使いのパソコンよりも、とんでもない能力があるコンピュータで並列処理しても、数百億年掛かるという計算が出ています。
公開鍵暗号の「ペアとなるどちらかの鍵で暗号化したものは、一方の鍵でしか復号化できない」という不思議な性質を説明する場合、少しむずかしい数学的な話をしなければなりませんので、もし「詳しく聞きたい！」とのご要望があれば、また今度の機会に書きたいと思います。
でも、それで終わってしまっては、せっかくこのページをご覧の皆さんにも申し訳ないので、ごく単純に、考え方だけ見てみましょう。
公開鍵暗号では「RSA」や「Elgamal」、「Rabin」、「楕円曲線暗号」など様々ありますが、ここでは、その1つである「RSA」のエッセンスだけ紹介します。
突然ですが...。
3×11=33
であることは、私の娘(小学校4年生)でも解ります。
では...。
9,719×8,069=78,422,611
であることは、安い電卓さえあれば計算できます。
それでは、その反対に...。
○×□=747,836,491
の「○」と「□」を求めよ。「○」と「□」は素数である。
上記の問題をどう求めるでしょうか。要するに、747,836,491の素因数分解です。
ちょっと難しいですね。たった9桁の整数ですけどね。(この程度であれば、コンピュータで総当りすればすぐ見つかりますが、人間の頭だけで考えるには少々面倒な数です。)
つまり、
巨大な整数を効率的に素因数分解する方法が見つかっていない。
ことがRSA暗号のエッセンスなのです。
更に、
素因数分解が本当に難しい問題なのか、或いは素因数分解を効率的に行う方法が存在するのかさえも証明されていない。
のです。
結論を言いますと、
素因数分解の難しさが「RSA」暗号を保証している。
ことになりますね。
