暗号化の安全性 (RSA暗号)
- 東京ナノファーム
- 2020年2月24日
- 読了時間: 4分
セキュリテーの基本となる暗号化方式である、RSA暗号のしくみを理解しながら、なぜそれが安全なのか、またそれが未来永劫に保証されているのかを考えてみたいと思います。
１．はじめに
RSA暗号は１９７７年に発明され現在のインターネットのブラウザ、メール、パスワード、くりじっとカードなどの基本暗号化につかわれています。例えばSSL/TLS通信は、共通鍵のAESと公開鍵のRSA暗号を組み合わせをつかっています。この暗号化にによる安全性は、どのように担保されているのか、仕組みを知ることにより理解したいと思います。
２，RSA暗号のしくみ
実際に、公開鍵、秘密鍵を簡単な素数から生成し、それを用いて暗号化し、複合までを計算してみます。
１）まず2つの任意の素数p, qを決めておきます。計算を簡単にするため
p=11
q=13 にします。
２）公開鍵N, eを求めます。
N=p x q
=143
オイラー関数であるφ(N)＝(p-1) x (q-1)=120 になり
e は < φ(N)、かつ互いに素でない任意の小さい自然数ですので、
e=7 を選びます。
３）秘密鍵dを求めます。
e x d mod φ(N) =1 から、
７x d mod 120 = 1
d=103 (最小整数値）になります。
４）メッセージ M=81 を公開鍵(N=143, e=7)を用いて暗号化します
暗号文 C=M^e mod N
=81^7 mod 143
=16
C=16が送られます。
５）秘密鍵(d=103)で復号化します。
復号化するためにはフェルマーの小定理の延長であるオイラーの定理を用います。
復号化 C^d mod N
= 16^103 mod 143 = 81
メッセージM=81が復号できました。
計算機を用いてRSA暗号の鍵生成教材プログラムが下記のURLにありましたのでご参考にしてください。 http://herb.h.kobe-u.ac.jp/RSA.html
３．暗号を破ることができるか
暗号文メッセージCを、秘密鍵を持たない盗聴者が、公開鍵(N, e)のみで破ることができるか、つまり、C^d mod N の複合化を解くアルゴリズが見つけることができるかという問題になります。
言い換えると、素数の積であるNを素因数分解し、素数p, qを求め、秘密鍵dを計算すれば、暗号を破ることができます。もし、この素因数分解が困難であれば、RSA暗号化は安全であると言えます。
桁数が小さい素数の積を、再び素数に分解することは、マトリックス表を作り参照検索で可能であり、また単純に2から順番に√Nまでの素数で商の余りが０になる値を求メル方法があり、さらにポラードのロー法など高速なアルゴリズムでも実現できます。
しかしながら、現在使われるRSA暗号の鍵の長さは1024ビット（208桁）、最長2048ビット（617桁）であり、最大300桁以上の素数の積に素因数分解するためには、スーパコンピュータを用いても解読に１億年以上かかると推定されています。２０１０年にはNTTにより、768ビット（232桁）の素因数分解に成功しています。
今後さらに、鍵のビット長を、コンピュータの性能向上、より高速なアルゴリズムの開発により、3072ビット以上にするなど、理論的には、リーマン予想が真であれば、10^24以下の自然数に184垓以上の素数が存在し、RSA暗号を解読することは不可能であるようには見えます。
しかしながら、この仮説は、量子コンピュータが登場することにより揺らいできます。
４．量子コンピュータでRSA暗号化の安全性はなくなるか
膨大な桁数素数の積の値から素因数分解が困難であることから、公開鍵での暗号の安全性が成り立っているため、素因数分解が量子コンピュータで高速に解くことができれば現代の暗号化は崩壊することになります。
１９９４年のショア(Peter Shor)のアルゴリズムは、量子ゲート型コンピューターを併用することにより、素因数分解の計算の中核である、与えられたa, N から、関数 f(x)=a^x mod Nを解くために、離散フーリエ変換の量子計算を高速にくり返えすことにより実現できるとされています。
以下に、wiki/量子コンピュータより抜粋します。
下記のURLのQuantum part: Period-finding subroutineを参照下さい。
この方式では、鍵ビット長を増やしても、繰り返し周期はあまり増やすことなくRSA暗号化を実用的な時間で解読でき、量子ゲート型コンピュータのハードウエアの発達により安全性の担保がなくなる可能性があります。
また、量子コンピュータにより、グローバーの探査問題を解くアルゴリズム（wiki/グローバーのアルゴリズム）がり、古典コンピュータが2^n時間かかる計算をn-Qbitの量子コンピュータが、√2^nで多項式を処理できることも考えられます。ただし量子ビットが、LogN必要となりnに対して指数関数要素があります。
何れにしても、量子コンピュータのハードウエアが実用段階になるまでは、RSA暗号化は破られることはなさそうです。
５．量子暗号化
遠くない将来、量子コンピュータにより、RSA暗号を用いた公開鍵が破綻したとしても、量子力学の量子テレポーテションを利用した、共通鍵による究極的な通信セキュリティーもすでに実用化が見えています。
電子テレポーテーションを、有名なAliceとBobの話で理解できることができます。
次回は、ブロックチェーンで用いられている、ポストRSA暗号とされている楕円曲線暗号の安全性について考えてみたいと思います。
著者：片山 雅美
本文中に
> 現在使われるRSA暗号の鍵の長さは1024ビット（208桁）
とありますが、これは誤りではないでしょうか。
正しくは1024ビットであれば10進数309桁になるかと思います。
実際その後
> 768ビット（232桁）
と言う文言も有り、1024ビットの際の10進数の桁より多くなっています。