暗号〜インターネットを守る数学

ネットショッピング、利用していますか？
何でもネットで買えるようになり、ネットバンキングやネット証券も身近になってきました。
年配の方がメールを使うのも珍しくなくなりました。

一方で安全性に不安を感じ、ネットショップなどの利用に踏み切れない方もまだいるでしょう。

ネットの安全性については、ウイルスや架空請求など留意するべき問題が多々あります。
その中から、情報をやり取りするときの秘匿性（盗み見られないようにすること）がどのように守られているのか、どのように数学が役に立っているのかを説明してみます。

ずばり「暗号」のお話です。

人々、特に国家は、通信の安全を守るため古代から暗号を利用してきました。

暗号の歴史から現代の最新の暗号までを記したサイモン・シン著の「暗号解読 上・下巻」は史実・人間ドラマの読み物としても面白く、暗号理論の勉強にもなる優れた本です。お勧めします。

暗号の歴史は情報を隠したい暗号作成者と情報を盗みたい解読者との戦いの歴史です。
古代から続くこの戦いはホンの40年前までは

「ある1つの根源的な問題」

を抱えていました。

正しい受取人が暗号化されたメッセージを読むためには、解読するための 鍵 が必要です。
暗号作成者はメッセージの他に「鍵（どのように暗号化したか）」を伝える必要があり、どれほど巧みに暗号化できても鍵を安全に渡せなければ意味がありませんでした。
この「鍵の配送問題」が暗号の歴史上、常に問題となっていました。

鍵を安全に配送できるとすれば、メッセージもその方法で送信すれば良いわけです。
逆に、メッセージに鍵が必要なら鍵にも鍵が必要になります。

このことから、鍵の配送問題はメッセージの暗号化と同値の問題であり、数千年もの間、鍵の配送問題だけを解決できるという考えには至りませんでした。

鍵はどうしても安全に配送しなければならないと考えられていたわけです。

しかし1970年代になって、ある数学者が次のようなアイデアを思いつきます。
以下の図のような方法であれば鍵を受け渡しする必要はありません。

このような発想から、鍵の配送問題は「原理的に解決できない」わけではないということに気づいたのです。

そして1976年、ついに鍵配送問題を解決できるアイデアが生まれます。

A氏がB氏にメッセージを送る場合を考えます。

受信者であるB氏は、暗号化のための鍵をA氏に渡します。

しかもこの鍵は誰に知られても良いのです。

例えば、B氏は自分専用の鍵でしか開けることのできない南京錠をたくさん作って世界中にバラ撒きます。
B氏にメッセージを送りたいA氏は、入手容易なB氏の南京錠をかけてメッセージを送ればいいのです。

このように鍵を秘密にせず、むしろ積極的に公開する暗号システムを「公開鍵暗号」、従来の＜お互いが同じ鍵を持つ＞暗号システムを「共通鍵暗号」と呼びます。

こうして人類は2000年以上抱えていた鍵の配送問題を解決しました。
インターネットの普及までギリギリ間に合ったとも考えられますが、むしろこの暗号システムが実用化されたことでインターネットは拡がることができたと見るべきだと思います。

さて、アイデアとしてはシンプルで、概念を理解するのは難しくありませんが、この「公開鍵暗号」はどのように実現できるのでしょうか？

公開されている鍵（南京錠B）で暗号化して送り、受信者は秘密にしている鍵（鍵B）で開けることになります。
二つの鍵が同じでは意味がありません。

こんな仕組みが作れるでしょうか？

公開された鍵で暗号化するということは、盗み見ようとする人も暗号化に使われた鍵を知ることができます。
この仕組みが安全に成立するためには

「暗号化に使用した鍵では復号（＝解読）できない」

という性質が必要です。

どんな暗号化処理でも、あるいは暗号に限らずどんな処理でも、何をしたかわかっていれば、その逆の処理をすれば元に戻せるように思われます。

例えば次のような場合。

・初めて行く場所でも、そこに行けたのなら逆にたどって帰ることができる
・窓の開け方を知っているなら閉めることもできる
・時計をバラバラに分解しても、分解の手順や道具があれば元に戻せる

しかし次の処理を考えてみてください。

・塩と砂糖を混ぜる
・青い絵の具と黄色の絵の具を混ぜる

これを元の状態に復元できるでしょうか？
時間やコストを無制限に使えるならいずれ分離することは可能かもしれませんが、常識的な時間やコストでは不可能と言って良いでしょう。

このように、処理の仕方がわかっていたとしても、容易には元に戻せない性質を持つ関数を「一方向性関数」といいます。

現代の暗号はこの「常識的な時間では不可能」ということによって安全性が保たれています。

それを実現しているのは「大きな数の素因数分解」です。

例えば「７」と「13」という素数があります。
７×13は簡単に計算できて、暗算でも電卓を叩いても容易に「91」と答えが出ます。
では逆に「91は何と何のかけ算か」と聞かれて即答できるでしょうか？

できる！

という人もいるかもしれませんね。
でも多くの人はかけ算をして「91」を得るより、かけて「91」になる２つの数を得る方が（ホンの少しでも）時間がかかるはずです。

では「8051」ではどうでしょうか？
「8051」は「83×97」です。
「8051」から「83×97」を見つけるのは試行錯誤が必要なはずです。

「78,856,511」は「7907×9973」です。
これはもう試行錯誤でもなかなか見つけられないはずです。

すべての自然数（1,2,3,4,5,...）は素数の積で表すことができます。
（１は素数ではないので、厳密に言えば１は素数の積で表せませんが）

例えば「55,660」は「2²×5¹×11²×23¹」です。

これを素因数分解といいます。
どんなに大きな数でも素因数分解できます。
しかし、巨大な数を効率的に素因数分解する方法はわかっていません。

おおざっぱに言えば、手当たり次第素数で割ってみるしかありません。
数が大きくなればなるほど素因数分解は極端に時間がかかります。

この「極端に時間がかかる」程度を天文学的な時間にまでしたのが現代の暗号システムです。
現在実用されている「RSA暗号」で使われている巨大な数を素因数分解するには、地球上のすべてのコンピュータを総動員して100億年かけてもまだ足りないくらいの時間が必要と言われています。

巨大な２つの素数を掛け合わせた数を「公開鍵」として公開し、その元の素数を知っている者だけが復号できるという仕組みです。

では、実際に使われている「巨大な数」がどのくらいか確認してみましょう。

amazonでアカウントサービスに入ってみてください。

ブラウザによって違いはありますが、南京錠のようなマークがどこかに現れるはずです。
そこをクリックして「証明書を表示」→「詳細な情報」を表示します。
現れた情報を下にスクロールしていくと「公開鍵情報」というのが見つかります。
そこの「256バイト：C7 3A 85 9E B4 D2 65 2F ...」の部分をクリックすると、実際に使われている公開鍵（16進数512桁）を見ることができます。

C7 3A 85 9E B4 D2 65 2F 51 C6 2A 63 D6 72 3B 84 F9 D6 B4 32 A9 3D ED CE D7 E9 8B 0F CD 3A A0 9D 35 34 4C 3E A1 7F 1F 10 C2 99 C6 DF 8D 2C 84 2F C0 60 55 68 F2 D1 2E B7 8A A8 52 80 3F 1D 20 C2 BB 25 55 02 A6 8D 22 BC B3 A8 DC 8A 50 86 6F 61 BB FA F9 F8 B4 62 AF 35 1B A0 36 DC 02 2B 99 3A 56 FE 07 54 D9 10 8F 3D 0E A3 7B BA 0F B1 6B 92 48 9A 16 F3 49 0B 89 4B 15 1F 8E A6 13 5F B5 1A CD E7 FE 3D 12 B1 23 8D 7F 93 FF 5A 9E 6F C9 D5 27 F7 0C A9 88 1A D5 65 4F 7E 20 00 B7 AE B9 14 C7 4D 84 CE 97 09 62 80 9D A6 69 F7 65 FC D0 58 0A 25 B4 A2 D8 BC 94 12 92 59 1F 8F FE C5 A5 05 34 06 53 6F 1D 2A 29 AE EB F7 42 F4 CF 32 A9 33 91 3C DF C3 26 B6 85 BA FB 4B 40 01 C1 B4 B2 90 6D CC 20 25 76 46 56 CB 63 30 4C 36 37 BA 73 AE 7C 4B 30 26 ED 58 30 A2 57 8B 27 19 2E C8 99 CD

16進数は、16=2⁴（=4ビット）ですから512桁であれば、4ビット×512=2,048ビット（=256バイト）。実際amazonの情報を見ると「鍵のサイズ」は2048ビットとの記述があります。

これを十進数になおすと、600桁を超える数になります。

amazonはこの600桁を超える巨大な数を「公開鍵」として公開しています。
私たちはそれを利用してamazonとの間に一時的に使う「共通鍵」を取り決め、その共通鍵を使って情報の暗号化・復号をしています。

コンピュータの処理能力はますます向上するでしょうし、効率的な計算手法も編み出されるかもしれません。
また、素因数分解の画期的な解法が発見されないとも限りません。
しかし、現段階においては十分安全だと考えて良いようです。