暗号理論（「笑わない数学」より）

2023-06-20

NHKの「笑わない数学」という番組をご存知ですか？今回取り上げさせて頂くのは第９回となる「暗号理論」です。

私たちの生活ではPCやスマホなどでメッセージ、個人情報をやり取りする機会が多く、それには暗号が使われています。どうして安全にそれが出来ているのか？そしてどんな数学が利用されているのか？という謎に番組では挑んでいきます。

暗号の原理は、元の情報を「暗号化の方法」によって暗号化された情報、とし、暗号化された情報を「もどす方法」によって元の情報にする、ということになります。

歴史上有名な暗号方式には、このサイトでもご紹介した「シーザー暗号」があります。

これは、たとえばアルファベットを三文字分後ろにずらして、A→D、B→E、C→F、とすれば意味の通じない文章を作ることができます。中でも13文字ずらす「ROT13」は丁度26文字のアルファベットを半分で折り返すメジャーなものとして知られています。

また番組では「エニグマ」をさらりと紹介しましたが、これは第二次世界大戦時のドイツ軍の暗号機の事で、連合軍はこれを解読するのに心血を注ぎ、終盤ではドイツ軍を追い詰めるのに大きく役立っています。映画にもなりましたよね。

このように「暗号化の方法」をいくら複雑にしても「暗号化の方法そのものが知られてしまうと元の情報が第三者に知られてしまう」ことは避けられず、数学者達は長年苦悩してきたという話。

1976年のアメリカで「暗号化の方法を守り抜くなんてもうやめよう」とマーティン・エドワード・ヘルマンさんとホイットフィールド・ディフィーさんが「暗号の新しい方向性」というタイトルで「公開鍵暗号」の理論を発表しました。

さらにその後現れた３人、ロナルドさん、アディ―さん、レオナルドさんが着目した「素因数分解の困難性」によって、かのRSAが開発されました（RSAは３人のRivest、Shamir、Adlemanの頭文字から来ています）。

RSAは1977年に発明されたもので、この暗号アルゴリズムは、桁数の大きな素数を掛け合わせた数字の素因数分解が難しいことを応用しています。例えば、6,887という数字を素因数分解することを考えてみよう。一般的には、素数である3や7といった数字で割っていき確かめていくことになるはずです。たった4桁の数字でも、97と71という素因数を導き出すことは困難であることが分かるでしょう。RSA暗号を解読するためには、数百桁もの数字の素因数分解を導き出す必要があり、コンピューターを使っても難しいのです。

このように強力な暗号強度をもつRSAは、誕生から30年がたった今でもSSLやTLS、PKIなど、暗号基盤において中心的な役割を果たしています。現在主流となっている2048ビット（617桁）のRSA暗号は、スーパーコンピューターでも解読が困難とされており、今後もしばらくは現役で活用されることになりそうです。

ところが、そんなRSAを脅かす存在になりそうなのが、これまたこのサイトでご紹介させて頂いた量子コンピューター。量子コンピューターを使えば、素因数分解を高速に処理することができるアルゴリズムを使うことができます。今後、量子コンピューターが実用化されると、RSAはその役割を終える可能性が高いとも言われています。

その先にある秘密を守るための鍵は、既に指紋センサーとか、アイセンサーとか生体認証とか・・・視点を変えて登場してはいるものの・・・本人がチェックを受けなければならないものばかりで今一つ実用的ではない様な・・・。今後は、どんな展開が待っているのでしょうねぇ。