RSA暗号
RSA社は「RSA Factoring Challenge」を1991年から2007年まで実施し、最新の計算機環境でどの程度のビット数の整数が素因数分解可能かを調べた。
1991年4月1日 RSA-100 (330ビット)
1992年4月14日 RSA-110 (364ビット)
1993年6月9日 RSA-120 (397ビット)
1994年4月26日 RSA-129 (426ビット)
1996年4月10日 RSA-130 (430ビット)
1999年2月2日 RSA-140 (463ビット)
2004年4月16日 RSA-150 (496ビット)
1999年8月22日 RSA-155 (512ビット)
2003年4月1日 RSA-160 (530ビット)
2009年12月29日 RSA-170 (563ビット)
2003年12月3日 RSA-576 (576ビット、10進174桁)
RSA暗号(RSAあんごう)とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号の一つである。暗号とデジタル署名を実現できる方式として最初に公開されたものである。
式中の mod は剰余演算を表し、d は λ を法とする e のモジュラ逆数であり、lcm は最小公倍数である。
暗号化(平文 m から暗号文 c を作成する):c = m mod n
復号(暗号文 c から元の平文 m を得る):m = c mod n
暗号化(e 乗)は公開鍵 {e, n} があれば容易に計算でき、復号(d 乗)は秘密鍵 d と公開鍵 n があれば容易に計算できる。しかし、秘密鍵 d を知らずに解読する(法 n の下で e 乗根を計算する)のは、「n の素因数を知らないと難しい(大きい合成数の素因数分解も難しい)」と考えられている。つまり、「秘密鍵を用いずに暗号文から平文を得ることは難しい」と信じられている。これがRSA暗号の安全性の根拠である。
RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許(4,405,829号)を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。
暗号の用語については暗号#用語、暗号理論#用語を参照。