どうも、人には言えない秘密がある吟遊詩人です。
前回に引き続いて、量子コンピュータの解説、やっていきますよ。
前回まで
- 量子コンピュータは量子ビットを使って計算する
- 量子ビットを使って計算すると素因数分解がメッチャ早くできる
- 量子コンピュータで世界がヤバイ
みたいな話をしました。今回は「量子コンピュータで世界がヤバイ」の部分のちょっと詳しい解説をしていきます。
量子コンピュータ が 素因数分解 が得意だとどうなるのかという部分ですが、それは現代の暗号技術に関わっています。
今回は”RSA暗号”についてお話します。
量子コンピュータによって私たちの生活はどう変わるの？
暗号とは
まず、RSA暗号の前に、そもそも暗号とは何かという事です。
暗号とは、セキュア通信の手法の種類で、第三者が通信文を見ても特別な知識なしでは読めないように変換する、というような手法をおおまかには指す。いわゆる「通信」（telecommunications）に限らず、記録媒体への保存などにも適用できる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』:暗号
暗号自体は相当古くからあり、紀元前１世紀ころにはシーザー暗号が開発されています。
シーザー暗号は単一換字式暗号の一種で、平文の各文字を、辞書順に3文字分シフトして暗号文を作る暗号である[4]。古代ローマの軍事的指導者ガイウス・ユリウス・カエサル(英語読みでシーザー)が使用したことから、この名称がついた[3]。文字のシフト数は固定であるが、3に限る必要はない。例えば左に3文字分シフトさせる場合、「D」は「A」に置き換わり、同様に「E」は「B」に置換される。シーザー暗号はヴィジュネル暗号などの部品として使用されることがあるほか、現代でもシフト数を13にした方式としてROT13が使用されることがある[5]。シーザー暗号は他の単一換字式暗号と同様、容易に解読されるため、今日の通信セキュリティにおいては効果的ではない[1]。 極めて単純な暗号であるが、現代の暗号においても重要な、規則（アルゴリズム）および鍵といった2つの要素が既に含まれている。
出典: フリー百科事典『ウィキペディア（Wikipedia）』 : シーザー暗号
大昔から、敵に通信の内容が知られないように暗号が必要だったわけですね。
その後も暗号の技術は科学技術とともに進歩していきます。
第２次世界大戦時にドイツ軍が使用したエニグマなんかが有名ですね。
まあ、いろいろな方法で暗号化するのですが、1976年以前の暗号は、暗号化する送り主と複合化（暗号をもとの文章に戻す作業）する受け手側で、あらかじめ他の人には秘密のルール（秘密鍵）を持っておく、いわゆる秘密鍵暗号方式だったわけです。
昔はそれでよかったかもしれませんが、その方式では対応できない事態が起こります。それがインターネットの普及です。
インターネット上では専用回線を作ることは難しく、プライベートなやり取り（例えばネットバンキング等）をするためには仮想的な専用回線、いわゆるVPN(Virtual Private Network)を構築する必要があります。
VPNを構築しようとした場合、暗号通信をする必要がありますが、不特定多数の接続先があるため、 いちいち 相手と秘密鍵を作るという事が不可能となります。
インターネット上で効率的に暗号通信を行う必要があり、それを実現する手法が考え出されました。公開鍵暗号方式と呼ばれるものです。
公開鍵暗号（こうかいかぎあんごう、Public-key cryptography）とは、暗号化と復号に別個の鍵（手順）を用い、暗号化の鍵を公開できるようにした暗号方式である。 暗号は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いるための障害であった。この問題に対して、暗号化鍵の配送問題を解決したのが公開鍵暗号である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』 ：公開鍵暗号
🤔 ？
鍵を見せたら暗号って駄目じゃないの？
公開鍵暗号のアイデア自体は1976年にはホイットニー・ディフィーらが提唱していたらしいですが、具体的な共通鍵の実装はまだでした。
具体的な共通鍵は1977年に登場しました。それがRSA暗号と呼ばれるものです。
RSA暗号とは？
1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる[2]。当時、ディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている[2]。
出典: フリー百科事典『ウィキペディア（Wikipedia）』 ： RSA暗号
リベスト、シャミア、エーデルマンの頭文字をとってRSA暗号なんですね。
RSA暗号の完成には以下のような逸話が残っています。
- リベストとシャミアが共通鍵の作成を開始 します
- しかしなかなかできずに断念します
- これはひょっとしたら共通鍵というものはそもそも作れないんじゃないかと思い始めて、 共通鍵暗号ができないことを数学的に証明しようと試みるます
- なかなかできずに断念 します
- 試行錯誤を繰り返し、2か月後RSAのひな型が完成します、自信作です 😆
- 毎週LCSで開かれるセミナーで発表 します
- 翌朝同僚のアデルマンが解読してきます
- リベスト、シャミア 「 😱 」
- その後42回暗号を作ります
- 42回アデルマンが解きます
- リベスト、シャミア 「 😱×42 」
- 43回目に作った暗号が アデルマン に解かれませんでした
- RSA暗号の完成です
……えっ？RSA暗号の安全性ってアデルマンが解けない事で保障されてんのか 😨
まあ、現在でも解読法が見つかったという話は聞かないので安全なのでしょう。
RSAは実際にインターネットでの暗号通信や電子署名なんかに使用されてます。
暗号通信してるときに出るアドレスバーのマーク
ちなみに、アデルマンは暗号を解いていただけなので、RSA暗号の論文に名前が載ることを拒否したと言います。（ただテニュアのために論文数を稼ぐ必要があり、結果的に名前を載せています。私も不労所得を得るために記事数を稼いでいます。）
具体的にRSA暗号の手順を説明しますと、
- p,qを素数としn=pqとする
- 最小公倍数をLCMとしてある数e,dを ed mod LCM(p-1,q-1)=1となるように選ぶ
- n,eが公開鍵で、あとは秘密鍵 とします
- 暗号化:C=Memod n で 復号化:M=Cdmod n とします
となります。 フェルマーの小定理（≠フェルマーの予想）と中国人の剰余定理をもとに作成されています。
具体例を挙げますと、今、 n=55(p=11,q=5), e=3とします。
暗号を受け取りたい側は、「これで暗号化して」と n=55 と e=3 を発信者に渡します。
発信者は渡された n=55 と e=3 を使って、メッセージM=４を暗号化します。
暗号化の方は 4^3 mod 55=64 mod 55=9 となり、暗号は9となります。
９を受信者側に返して、受信者は複合化をします。
LCM(p-1,q-1) ＝LCM(10, 4)=20なので、 mod20で1になるdを選ぶと7となります。
複合化の方は 9^7 mod 55=4782969 mod 55=4 となり、元の文M=4が複合できました。
以上がRSA暗号の説明になります。
RSA暗号は因数分解の難しさによって支えられている？
RSA暗号の説明をしてきましたが、RSA暗号が成り立っているのって、公開鍵nを渡しても秘密鍵pとqがバレない事が重要なんですよね。
それってつまりnが因数分解されないことが重要で、さっき例に挙げた55くらいだとすぐに因数分解されてダメです。実際は300~1000桁くらいの素数の積をnとしているようです。
つまり、300桁か1000桁のpとqに対しても
p×q→nは高速でできるけど、n→p×qは非常に時間がかかることが重要なのです。
このようにある計算は楽だけど、逆の計算は難しいというのを一方向関数と呼んだりします。
共通鍵暗号方式は一方向関数を用いれば作れるという事ですね。
……なのですが、
量子コンピュータによって素因数分解 n→p×q が高速にできるようになってしまうと、RSA暗号が使えなくなってしまう可能性が高いと考えられます。
RSA暗号は現在のインターネット通信のセキュリティを支えている重要な技術ですので、これが使えなくなると「世界がヤバイ」という事ができるでしょう。
量子コンピュータができたらもうインターネットで安全な通信はできなくなるの？
さて、量子コンピュータの登場でRSA暗号の安全性が脅かされているのは事実ですが、もう安全な通信ができなくなるというわけでもないと思います。
RSA暗号が使えなければ、別の暗号を使えばいいじゃない
という事になるでしょう。
量子コンピュータに対抗した量子暗号やゼロ知識証明などを利用した暗号通信がポストRSAとして期待できるのではないかと思います。
これらに関してはまた機会があったら解説記事でも書こうと思います。
さて、前回と今回を通して量子コンピュータが現在の暗号技術にどのように影響を与えるかわかってもらえたのではないでしょうか。
次回は最後に残っていた「なんで量子コンピュータができると仮想通貨の価格が下がるの？」という部分の解説をしたいと思います。
今回のまとめ
- インターネットの通信は公開鍵暗号によって支えられているよ
- 公開鍵暗号の方式としては、因数分解の性質を使ったRSA暗号があるよ
- 量子コンピュータができるとRSA暗号が使えなくなるかもだよ
- 量子コンピュータができたら、別の暗号方式が使われるようになるかもね
（なんか今回あんまりネタを挟む暇がなかったな……）
以上です。
そーめんブログ 