アールエスエー‐あんごう〔‐アンガウ〕【RSA暗号】
RSA暗号
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/26 08:27 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2017年3月) |
| 一般 | |
|---|---|
| 設計者 | ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマン |
| 初版発行日 | 1977 |
| 認証 | PKCS#1, ANSI X9.31, IEEE 1363 |
| 暗号詳細 | |
| 鍵長 | 1,024 to 4,096 bit typical |
| ラウンド数 | 1 |
| 最良の暗号解読法 | |
| 829 bit key (RSA-250)は解読済み | |
RSA暗号（RSAあんごう、Rivest-Shamir-Adleman）とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号の一つである。暗号[1]とデジタル署名を実現できる方式として最初に公開されたものである。
概要
RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる[2](p63)。前年（1976年）にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている[2][要ページ番号]。
RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許（4,405,829号）を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。
なお、RSA暗号を最初に考案したのはGCHQに所属するジェイムズ・エリスとクリフォード・コックスであるという説がある。エリスは1969年に公開鍵暗号に相当する理論を考案したが、エリスは専門の数学者ではなく、GCHQの数学者たちも公開鍵暗号の具体的な方法を提示することはできなかった。1973年にコックスはエリスが考案した暗号の理論を聞かされ、わずか30分程度でリベストの計算式と同様の方法を考案した。しかし、エリスとコックスの業績は機密事項とされたため、1997年までは世間に知られることはなかった[2](p66)。また、当時はRSA暗号を使用するには高価なコンピュータが必要であり、公に知られている限り、実用に供されることは無かった。
暗号方式
鍵生成
p, q を異なる2つの素数とし n = pq とし λ(n) = (p − 1)(q − 1) とする。e を λ(n) と素な正整数とすると α ⋅ e + β ⋅ λ(n) = 1 となる2整数 α, β が存在する[3]。α として1つの正整数 d を選択してそのときの β を −x とすると d ⋅ e = x ⋅ λ(n) + 1 となる。ここで d を秘密鍵とし、n と e を公開鍵とする。
ここで、α ⋅ e + β ⋅ λ(n) = 1 のとき i を整数とすると (α + i ⋅ λ(n)) ⋅ e + (β − i ⋅ e) ⋅ λ(n) = 1 であるから α に λ(n) の整数倍を加えたものも改めて α とできるため、α として正整数 d を選択できるとした。
以下 ℤn を 0 以上 n 未満の整数の集合とする。
暗号化
a ∈ ℤn とし a を暗号化対象の平文とする。b = ae mod n ∈ ℤn を計算し、b を 平文 a の暗号文とする。
復号
a′ = bd mod n ∈ ℤn を計算する。すると a′ = a となり a′ は 平文 a の暗号文 b の復号文となる。
完全性の証明
定義により以下が成立する。
セキュリティパラメータが1024の場合、n は1024ビットという大きな桁数の数となり、d も n とほぼ同じ桁数の数となる。
脆弱な平文
RSA暗号の安全性は素因数分解の困難さ（より正確には素因数が不明な法 n での冪根を求めることの難しさ）に基づいている。 しかし、平文の内容によっては、素因数分解をせずとも暗号文から平文を入手できる。
決まりきった平文
公開鍵暗号全般に言えることであるが、確定的暗号（例えば平文が「はい」か「いいえ」のどちらかしか有り得ない）であれば、それぞれを暗号化したものと暗号文とを比較すれば容易に平文を知ることができる。
実用上は、m の一部に毎回生成する乱数を挿入することで、この攻撃を回避できる（復号側で乱数部分を無視するよう処理すればよい）。
小さなm
平文 m が、n の e 乗根よりも小さいと、暗号文 
カテゴリ
