RSA暗号

RSA暗号とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号の一つである。暗号page=63}}。前年にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいているdate=2023年10月}}。

RSA暗号は次のような方式である。

鍵のペアを作成して公開鍵を公開する。まず、適当な λ}} と互いに素な正整数 e}} を選択する。また、大きな2つの素数の組 mset を生成し、それらの積 1=//n// }} を求めて、e}} と n}} を平文の暗号化に使用する鍵とし、n}} を法、e}} を公開指数という。素数の組 mset から暗号文の復号に使用する鍵d}} を生成し、d}} を私有指数という。すなわち //d// =}} //e//sup となるような mset をとる。//d//}} の生成後、λ}} も p}} も q}} も捨ててよい。ただしここで //λ// =}} lcm}}。式中の mod}} は剰余演算を表し、d}} は λ}} を法とする e}} のモジュラ逆数であり、lcm}} は最小公倍数である。

暗号化：
復号：暗号化は公開鍵 mset があれば容易に計算でき、復号は秘密鍵 d}} と公開鍵 n}} があれば容易に計算できる。しかし、秘密鍵 d}} を知らずに解読するのは、「n}} の素因数を知らないと難しい」と考えられている。つまり、「秘密鍵を用いずに暗号文から平文を得ることは難しい」と信じられている。これがRSA暗号の安全性の根拠である。

RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。

暗号の用語については暗号#用語、暗号理論#用語を参照。

1. 歴史
-----

歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者はジェイムズ・エリスである。彼らはイギリス最高機密機関・英国政府通信本部  の職員であり、その独創的な先見の明は内部文書として長い間公開されなかった。また実用にはコンピュータの性能等から機が熟していなかった。以下はその概要である。

エリスは1969年にこの理論を発見しているが、専門の数学者ではなかったため、具体的な方法を発見できなかった。幾人ものGCHQの優秀な数学者が挑戦したが、具体的な方法を提示することはできなかった。1973年、突拍子もない暗号のアイデアとしてエリスの「一方向関数・公開鍵」を用いた暗号論の話を聞かされ、わずか30分程度でモジュラー算術と素因数を用いた具体的な方法を考案したのは、GCHQ所属の若き数学者クリフォード・コックスである。しかしエリスとコックスの業績は機密事項とされたため、1997年までは世に知られることはなかったpage=66}}。

2. 暗号方式
-------

鍵生成、暗号化、復号の3つのアルゴリズムで定義される。

2.1. 鍵生成
--------

//p//, //q//}} を異なる2つの素数とし 1=//n// = //pq//}} とし //λ// =}} }} とする。e}} を //λ//}} と素な正整数とすると //α// ⋅ //e// + //β// ⋅ //λ// =}} 1}} となる2整数 //α//, //β//}} が存在する。α}} として1つの正整数 d}} を選択してそのときの β}} を −//x//}} とすると //d// ⋅ //e// =}} //x// ⋅ //λ// + 1}} となる。ここで d}} を秘密鍵とし、n}} と e}} を公開鍵とする。

ここで、//α// ⋅ //e// + //β// ⋅ //λ// =}} 1}} のとき i}} を整数とすると ) ⋅ //e// +  ⋅ //λ// =}} 1}} であるから α}} に //λ//}} の整数倍を加えたものも改めて α}} とできるため、α}} として正整数 d}} を選択できるとした。　

以下 ℤsub を 0}} 以上 n}} 未満の整数の集合とする。

2.2. 暗号化
--------

//a// ∈ ℤsub とし a}} を暗号化対象の平文とする。//b// =}} //a//sup を計算し、b}} を 平文 a}} の暗号文とする。

2.3. 復号
-------

//a//′ =}} //b//sup を計算する。すると //a//′ =}} //a//}} となり //a//′}} は 平文 a}} の暗号文 b}} の復号文となる。

2.4. 完全性の証明
-----------

定義により以下が成立する。

これにより以下も成立する。

a}} が n}} と互いに素な整数のときは a}} が2つの素数 //p//, //q//}} のそれぞれと互いに素であるから

フェルマーの小定理 により かつ であり

よって は //p//, //q//}} で割り切れるから となり

となるが、 であるから

となる。

であり、 のときは、a}} は //q// − 1}} 個の整数からなる集合 の元であって、a}} が p}} で割り切れるから であり、//a//, //q//}} が素であるからフェルマーの小定理により であり

よって

よって

よって //a'// − //a//}} は //p//, //q//}} で割り切れるから

となるが、 であるから

となる。

であり のときについても同様に 1=//a'// = //a//}} となる。

1=//a// = 0}} のときは であるから 1=//b// = 0}} であり、 であるから 1=//a'// = 0}} である。つまり 1=//a//′ = //a// = 0}} である。

以上何れにしても 1=//a'// = //a//}} が成り立ち、平文 a}} の 暗号文 b}} は 秘密鍵 d}} と公開鍵の一つ n}} を用いて平文 a}} に復号できることが分かる。

3. 性能
-----

3.1. //n// を法とする冪剰余の計算
----------------------

1=//k// = 1024}} の場合、n}} は1024ビットサイズという大きな数となり、d}} もほぼ n}} と同サイズの数となる。 を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算  を、1500回程繰り返すことで実現できる。これには相当の計算時間を要するため、中国の剰余定理を用いて、

として求めることがある。

3.2. 素数生成
---------

桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller–Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数  という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる。

2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間で行うAKS素数判定法を発表したdate=2023年10月}}が、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。

4. 安全性
------

4.1. RSA暗号と素因数分解問題の関係
---------------------

RSA暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。

素因数分解を解けるオラクルを用いれば、n}} から p}} および q}} が計算できるので、鍵生成と同様にして秘密鍵 d}} を知ることができる。即ち、RSA暗号が解読できる。従って、RSA仮定が証明できれば素因数分解問題の困難性が示せる。しかし、逆が成立するかどうかはよく分かっていない。ある条件下では否定的な結果もでている。

RSA暗号が選択平文攻撃に対して完全解読できない、ということとRSA仮定とは同値である。

RSA問題を解く方法として、現在知られている有力な方法は、素因数分解問題を解くことに使える方法だけである。素因数分解問題を解く方法として、楕円曲線法や数体篩法などのアルゴリズムが知られているが、これらの方法はどれも準指数関数時間アルゴリズムであり、多項式時間で素因数分解問題を解く方法は知られていない。

暗号理論の世界では、多項式時間で解読することができない暗号方式を安全であると定義することがある。この意味で、RSA暗号の安全性について、現在知られている範囲では安全であると期待されていて、その反証がないと言える。

RSA問題や素因数分解問題はNP問題であるので、これらの問題が多項式時間では解けないことが証明できれば、P≠NP予想が肯定的に解決することになる。ただし、ハミルトン閉路問題など他のNP問題が多項式時間で解けることが証明されればP=NPとなってしまう。

4.2. 素因数分解可能な範囲
---------------

2004年の時点では、インターネットで公募した数多くのPCを用いると512ビット程度の数なら素因数分解できるので、RSA暗号に使用する法 n}} は1024-4096ビットにすることが推奨されている。

しかしシャミアは、RSA問題を解くための専用装置  を作成すれば、1024ビットの n}} に関するRSA問題ですら解くことができると主張している。また、実用的な量子コンピュータが登場した場合には、素因数分解の桁数増に対する計算時間の増加が緩やかなショアのアルゴリズムと呼ばれる高速な量子コンピュータアルゴリズムが実行可能となるため、たとえ鍵のビット数を増やしてもRSA暗号の安全性が保証されなくなる可能性が指摘されている。

4.2.1. RSA暗号解読コンテスト
-------------------

RSA社は「RSA Factoring Challenge」を1991年から2007年まで実施し、最新の計算機環境でどの程度のビット数の整数が素因数分解可能かを調べた。

1991年4月1日 RSA-100 
1992年4月14日 RSA-110 
1993年6月9日 RSA-120 
1994年4月26日 RSA-129 
1996年4月10日 RSA-130 
1999年2月2日 RSA-140 
2004年4月16日 RSA-150 
1999年8月22日 RSA-155 
2003年4月1日 RSA-160 
2009年12月29日 RSA-170 
2003年12月3日 RSA-576 (576ビット、10進174桁）