RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号(Cipher)とデジタル署名(Digital signature)を実現できる方式として最初に公開されたものである。
目次
1 概要
2 暗号方式
2.1 鍵生成
2.2 暗号化
2.3 復号
2.4 完全性の証明
3 性能
3.1 n を法とするべき剰余の計算
3.2 素数生成
4 安全性
4.1 RSA暗号と素因数分解問題の関係
4.2 素因数分解可能な範囲
4.2.1 RSA Challenge 解読コンテスト結果
4.3 RSA暗号の性質
4.4 RSA暗号の誤用
4.4.1 パラメータの選択
4.4.2 特殊な(誤った)応用
4.5 脆弱な平文
4.5.1 決まりきった平文
4.5.2 小さなm
4.5.3 同一平文
4.6 その他
5 暗号や署名への応用
5.1 RSA暗号
5.2 RSA署名
6 参考文献
6.1 原論文
7 関連項目
//
1977年に発明され、発明者であるロナルド・リベスト(Ron Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Len Adleman) の頭文字をつなげてこのように呼ばれる。 当時、デフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。 発明者3氏は、この功績によって2002年のチューリング賞を受賞した。
RSA暗号は次のような方式である： 鍵ペア（公開鍵と秘密鍵）を作成して公開鍵を公開する。それには、適当な正整数 e（通常は小さな数。65537が良く使われる）を選択し、また大きな桁数の素数2個{p,q}を生成し、それらを暗号文の復号に使用する鍵（秘密鍵）に使用する。次に、生成した2つの素数の積 n を求めて、{e, n}を平文の暗号化に使用する鍵（公開鍵）として公開する。
暗号化：平文mから暗号文cを作成する：c = me(mod n)
復号：暗号文cから元の平文mを得る：m = c1 / e(mod (p ? 1)(q ? 1))(mod pq)
ここで、暗号化（e乗）は{e,n}があれば容易に計算できるのに対して、復号は「e乗根を求めるにはnの素因数がないと難しい（桁数が大きい合成数の素因数分解も難しい）」と考えられている。従って秘密鍵を用いずに暗号文から平文を得ることは難しい、と信じられている。これがRSA暗号の安全性の根拠である。
歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者はジェイムズ・エリスである。彼らはイギリス最高機密機関、英国政府通信本部(GCHQ)の職員であり、その独創的な先見の明は英国政府の隠蔽工作により闇に消えたのである。以下はその概要である。
エリスは1969年にこの理論を発見しているが、数学者ではなかったので具体的方法を模索することができなかった。それから幾人ものGCHQの優秀な数学者が挑戦したが、具体的方式を提示する事はできなかった。過ぎること数年の1973年、ある突拍子も無い暗号のアイデアとしてエリスの「一方向関数(非対称性鍵の概念)・公開鍵」を用いた暗号論の話を聞かされ、その場の思いつきでモジュラー算術と素因数を用いた具体的な方式を考案したのは、若き天才数学者クリフォード・コックスである(コックスは上記のリベストの計算式と同じものを発見した)。が、しかし彼らの発見と発明は秘密主義の名の下に世にひろく知られることはなかった。
RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許（4,405,829号）を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。
鍵生成、暗号化、復号の3つのアルゴリズムで定義される。
k をセキュリティパラメタとする。
p, q を k/2 ビットの素数とし、n = pq とする。e を φ(n) 未満の正の整数で、φ(n) と互いに素な数とし、d を、φ(n) を法としたe の逆数（ de ≡ 1 ( mod φ(n) ) ）とする。 ただしここで φ(n) は n のオイラー関数で、この場合は (p - 1)(q - 1) に等しい。d は、e, φ(n) が既知のときには拡張されたユークリッドの互除法を使えば容易に求まる（ de を φ(n) で割った整数商を x とした場合、de + (-x)φ(n) = 1が成り立ち、かつ e の取り方から gcd(e,φ(n)) = 1 であるのでこれを解けば良い）。p, q, d を秘密鍵とし、n, e を公開鍵とする。
以下では、0 以上 n 未満の整数の集合を で表すことにする。