RSA暗号
RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。前年(1976年)にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている。
RSA暗号は次のような方式である。
鍵のペア(公開鍵と秘密鍵)を作成して公開鍵を公開する。まず、適当な λ と互いに素な正整数 e を選択する。また、大きな2つの素数の組 {p, q} を生成し、それらの積 n (= pq) を求めて、e と n を平文の暗号化に使用する鍵(公開鍵)とし、n を法、e を公開指数という。素数の組 {p, q} から暗号文の復号に使用する鍵(秘密鍵)d を生成し、d を私有指数という。すなわち d = e mod λ となるような {p, q} をとる。d の生成後、λ も p も q も捨ててよい。ただしここで λ = lcm(p − 1, q − 1)。
これは公開鍵暗号全般に言えることであるが、確定的暗号であれば、例えば平文が「はい」か「いいえ」のどちらかしか有り得ないなら、それぞれを暗号化したものと暗号文とを比較すれば平文を知ることができる。
実際の暗号への応用においては、フォーマットとして m の一部に毎回生成する乱数を挿入することで、この攻撃を回避している(復号側で乱数部分を無視するよう処理すればよい)。
a′ = b mod n ∈ Zn を計算する。すると a′ = a となり a′ は 平文 a の暗号文 b の復号文となる。
RSA暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。
素因数分解を解けるオラクルを用いれば、n から p および q が計算できるので、鍵生成と同様にして秘密鍵 d を知ることができる。即ち、RSA暗号が解読できる。従って、RSA仮定が証明できれば素因数分解問題の困難性が示せる。しかし、逆が成立するかどうかはよく分かっていない。ある条件下では否定的な結果もでている。
RSA暗号が選択平文攻撃に対して完全解読できない、ということとRSA仮定とは同値である。
RSA問題を解く方法として、現在知られている有力な方法は、素因数分解問題を解くことに使える方法だけである。素因数分解問題を解く方法として、楕円曲線法や数体篩法などのアルゴリズムが知られているが、これらの方法はどれも準指数関数時間アルゴリズムであり、多項式時間で素因数分解問題を解く方法は知られていない。
暗号理論の世界では、多項式時間で解読することができない暗号方式を安全であると定義することがある(計算量的安全性)。この意味で、RSA暗号の安全性について、現在知られている範囲では安全であると期待されていて、その反証がないと言える。
RSA問題や素因数分解問題はNP問題であるので、これらの問題が(決定性のある)多項式時間では解けないことが証明できれば、P≠NP予想が肯定的に解決することになる。ただし、ハミルトン閉路問題など他のNP問題(NPかつNP困難なNP完全問題を含む)が多項式時間で解けることが証明されればP=NPとなってしまう。
RSA暗号をサポートしているライブラリは以下の通り。
Botan
Bouncy Castle
cryptlib
Crypto++
Libgcrypt
Nettle
OpenSSL
wolfCrypt
GnuTLS