- HOME
- 研究
- サイエンス&テクノロジー
- 数学理論が情報社会を陰で支えるー暗号のしくみを考えてみようー
数学理論が情報社会を陰で支えるー暗号のしくみを考えてみようー
理学部・数理科学科 伊藤 正美教授
暗号の起源は意外に古く、その歴史を紐解くと古代ローマ時代まで遡ることができます。もちろん当時は、国家の機密を扱うなど、ごく一部の人たちだけのものでした。しかし情報社会の現在、暗号は私たちの日常に欠かせないものとなっています。言語の論理的な構造を数学を使って解き明かそうという「形式言語」「オートマトン」などを研究する伊藤 正美先生に、歴史に現れた暗号と、現代の暗号と数学理論との関係を楽しく説明していただきました。
暗号の基礎と古代ローマのシーザー暗号
「暗号の歴史は、文字を他の文字で置き換えることから始まりました。古代ローマ時代にはすでに、アルファベットをa→cというように一様に何文字かずつずらす(zの次はaに戻る)暗号が存在しました。これは有名な皇帝の名前から「シーザー暗号」と呼ばれています。
その後、アルファベットの1番目のAを01、Bを02、…、26番目のZを26、空白を00、と数字に置き換え、送り手と受け手にしか分からない数字を「鍵(パスワード)」として暗号をやりとりする方法も考え出されました(ヴィジュネル暗号ー17世紀フランスの外交官ヴィジュネルの発案)。
これらの暗号は、単純でありながら実用性の高いものですが、いくつかの欠点もあります。それは、「送り手と受け手とが同じ「鍵」を持つ必要がある」。「「鍵」を第三者に知られてしまうとおしまい」。「同じ「鍵」を使い続けているとそのうち推測されてしまう」。「送り手と受け手が1対1でしか使えない」などです。また、暗号文を送るときに「鍵」も受け手にわたす必要がありますが、「鍵」自体を暗号にはできないので、いかに「鍵」を盗まれないようにするかも問題でした。使者の髪の毛を丸刈りにして頭皮に「鍵」を書き込み、髪の毛が十分に伸びてから送り出し、到着した所で髪の毛を剃って「鍵」を確認する、といったことも実際に行われたそうです。
その後、暗号は次第に高度で複雑なものになっていきました。特に20世紀に入り、無線通信が普及すると急速に複雑になります。第2次世界大戦でドイツが使ったエニグマ暗号は、その複雑さと他の国々に与えた影響とによって、あまりにも有名です。
Aさんが”I LOVE YOU”を“09 00 12 15 2205 00 25 15 21”と置き換え、次に「鍵」を例えば“051218”として、(図)のように桁数が揃うよう繰り返して並べ合計します。このとき繰り上がりは無視し(たとえば、9 + 5 = 4、5 +5 = 0)、Bさんに送ります。Bさんは、暗号文から今度は「鍵」を引き算し、元の数字に戻し(復号化)ます。この時も繰り下がりは無視します。
鍵の問題を克服した現代の「公開鍵暗号」
コンピュータのネットワークが発達した現代社会では、暗号のもつ役割は大きく変わり、私たちにもたいへん身近な存在となりました。ネット社会では、第三者に知られると困る重要な情報もその中を行き交います。そこでこれらの情報を暗号化しておこうという考えが生まれてきました。また、インターネットでは、ネットショッピングなどで分かるように送り手と受け手が「1対1」ではなく、「多対1」となることが一般的で、それに対応できることも重要になります。
そこで考え出されたのが、暗号化のための「鍵」は公開しても、元の文章に戻す「鍵」は受け手にしか分からないという「公開鍵」と言われる手法です。果たしてそんな手品のようなことが可能なのでしょうか?秘密を解く鍵はもちろん数学にあります。「RSA暗号」(3人の提唱者(Ronald L. Rivest、Adi Shamir、Leonard M.Adleman)の頭文字から命名)を例にその仕組みを見ていきましょう。
今、AさんがBさんに“ I LOVE YOU”というメッセージを送信するとします。Bさんが公開した暗号化のための「公開鍵」は3と33です。Aさんは、まず“I”を“09”に置き換え、「公開鍵」3でべき乗(93 =729)します。次に、729を「公開鍵」33で割った余り(729÷33=22…3)の3を暗号とします。以下同様にして、“03 00 1209 22 26 00 16 09 21”という暗号を作り送信します。
受け取ったBさんは、まず3から復号していきます。自分だけが知っている「秘密鍵」7でべき乗(37 =2187)し、33で割った余り(2187÷33=66…9)から元の数字“09”を得ます。以下同様にして(ただし00は00のまま)元のメッセージが分かるのです。(解説下図)
実は、「公開鍵」3と33、「秘密鍵」7はいずれも適当に選んだものではありません。また、11乗・21乗すると元の数字に戻るというのも偶然ではなく、数学の法則に基づいています。
まず、「公開鍵」のひとつ33は、2つの素数を掛け合わせて作られます。この場合、素数3と素数11が使われています(実際にはもっと大きな素数を使いますが、説明のため小さくしています)。次に、元の数字が現れる11乗・21乗は、この2つの素数から求められます。3、11から1を引いた数(2、10)の公倍数(10、20、30、40、…)に1を加えた数(11、21、31、41、…)が元の数字が現れるべき乗数なのです。
そして、「公開鍵」3と「秘密鍵」7は、お互いを掛け合わせたときに今求めたべき乗数(11、21、31、41、…)になるように決められます。ここでは、3×7=21ということで3と7が選ばれました。2つの素数を使うことがRSA暗号のポイントのひとつです。2つの素数は掛け算は容易ですが、掛け合わせたものを素因数分解するのは容易ではないのです。33ぐらいであれば直観で3と11と素因数分解ができますが、130217ではどうでしょうか?素因数分解には結構手間取ります。しかし、逆に197×661 = 130217 なら、紙と鉛筆があれば簡単ですね。暗算が得意な人なら見ただけで答えを出せると思います。コンピュータにとっても同様で、十分に大きい(150桁以上)素数を2つ使うと、掛け算ならばコンピュータは一瞬で計算しますが、素因数分解には数万年かかると言われています。そのため公開している数字(2つの素数の積)から元の2つの素数を推測することは事実上不可能で、「元の数字に戻るべき乗数」が知られないわけです。
AさんとBさんのやりとりを表にしてみました。左端は(数字に置き換えた)元のメッセージ、最上段はべき乗数です。各欄の数値は元の数字を最上段の数だけべき乗して33で割った余りを記しています。例えば、9の行の3乗の欄は3ですが、これは先ほど“ I”を暗号化したのと同じように93÷33 = 22…3の「余り3」を表しています。
表を見ると、11乗・21乗の列が一番左の列とまったく同じなのが分かります。この元の数と同じになることが、RSA暗号の仕組みの柱となる数の法則です。
先ほどAさんが暗号として送った“3”をBさんはさらに「秘密鍵」7を使って7乗しました。これは、3乗×7乗= 21乗とするための計算なのです。21乗して33で割った余りは最初の数字に戻るため、Bさんは元の数字を知ることができたのです。
将来の暗号技術
RSA暗号は現代のコンピュータには解読が困難ですが、現在研究されている「量子コンピュータ」が実用化されると、簡単に解読されてしまいます。量子コンピュータは、量子の「観測されるまではいくつもの状態の重ね合わせとして存在する」という性質を応用したコンピュータで、同時にいくつもの計算を並行して行うことができます。そのため、現在のコンピュータでは時間がかかる、大きな素数同士を掛け合わせた数の素因数分解も瞬時に解くことができるのです。
しかし、心配はいりません。量子コンピュータ時代が到来する頃には、またそれで解読されないような暗号技術が開発されることでしょう。実際、傍受されると破壊されるというような暗号の研究がすでに進められています。今後、情報社会が進展すればするほど、暗号の重要性はますます大きくなり、新しい暗号方式の開発もより一層進んでいくことでしょう。
アドバイス
数学者は勤勉でないほうがいい?
これは私の持論ですが、数学者になるためにはあまり勤勉でないほうがいいと思っています。数学はいかに効率良く、美しく問題を解くかが重要な学問です。近年はコンピュータの発達で、全通り当たってみるとか、片っ端から計算してみるといった証明の仕方も見受けられるようになりましたが、それでもやはり数学の本質は、もっとも効率の良い解法を考えることだと思います。
そのためには日頃から、「いかに楽をして大きな成果が得られるか」を考えている人が数学者には向いていると思っています。極端に言えば「苦労をしてでも楽をしてやる」ぐらいの気概があればいいですね。
また、数学的な発見をするためには、思考の柔軟性や独創性がもっとも大切です。教えられたこと、言われたことを勤勉に実践しているだけでは柔軟性や独創性は身につきません。自由な発想を心がけて下さい。
トピックス
大学の数学が扱える広大な世界
高校までの数学が面白くないと感じている人にも、ぜひ大学での数学にはチャレンジして欲しいと思います。大学での数学は、どの分野をとっても一つひとつがそれ自身自立した学問分野となっていて、大きな拡がりをもっていますから、きっと興味深く感じられるにちがいありません。
また、ここで紹介したように、みなさんが考えているよりも遥かに広い分野を論理的に支える役割も担っているのです。
クローズアップ
数字にも特許権がある!
現在主流の暗号方式であるRSA暗号は、桁の大きな素数を用いますが、実は、桁の大きな素数は、見つけ出すのは簡単ではありません。これは、素数を完全に規定する法則・規則が見つかっていないし,そもそもそういった法則・規則があるかどうかも分かっていないからです。ある桁の大きな数を素数と断定するためには膨大な計算が必要で、その計算量は最新のコンピュータでも何日・何年とかかるぐらいなのです。素数という概念はそれぐらい数学的な扱いが難しいものであるということもできるでしょう。
そのため、暗号に使えるような十分に桁の大きな素数というのは、それ自体が特許の対象となり得るのです。単なる数字の列も、150桁を超えた素数となってくると特許権が発生するということです。未だ誰にも発見されていない桁の大きな素数を見つけ出せば、暗号を作る会社に売ることもできるかもしれません。
理学部・数理科学科 伊藤 正美教授
- プロフィール
-
専攻は形式言語、オートマトンおよび計算理論。フランスのポワンカレ研究所に大学院生として滞在中に、ふと立ち寄った本屋でたまたま手にした「数理言語学入門」という一冊の本、その書物に書かれていた未解決の問題を解いて著者であるルーマニアの研究者に送ったことが、現在の専攻分野へと進む第一歩となった。この研究者とは現在でも交流があるという。専攻分野は言語学と数学とが結びつく分野。そこから現在と将来の暗号技術についてや人類の言語の発祥についても深い関心を持つ。