RSA暗号

デジタル大辞泉

アールエスエー‐あんごう〔‐アンガウ〕【RSA暗号】

読み方：あーるえすえーあんごう

インターネットで広く使われている、暗号化アルゴリズムの一。公開鍵暗号方式を採用している。

[補説] RSAは、考案者であるリベスト（Rivest）、シャミア（Shamir）、エーデルマン（Adleman）の3人の頭文字から。

ウィキペディア

RSA暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/26 08:27 UTC 版)

RSA

一般
設計者	ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマン
初版発行日	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）とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号の一つである。暗号とデジタル署名を実現できる方式として最初に公開されたものである。

概要

RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。前年（1976年）にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている。

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

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

なお、RSA暗号を最初に考案したのはGCHQに所属するジェイムズ・エリスとクリフォード・コックスであるという説がある。エリスは1969年に公開鍵暗号に相当する理論を考案したが、エリスは専門の数学者ではなく、GCHQの数学者たちも公開鍵暗号の具体的な方法を提示することはできなかった。1973年にコックスはエリスが考案した暗号の理論を聞かされ、わずか30分程度でリベストの計算式と同様の方法を考案した。しかし、エリスとコックスの業績は機密事項とされたため、1997年までは世間に知られることはなかった。また、当時はRSA暗号を使用するには高価なコンピュータが必要であり、公に知られている限り、実用に供されることは無かった。

暗号方式

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

鍵生成

p, q を異なる2つの素数とし n = pq とし λ(n) = (p − 1)(q − 1) とする。e を λ(n) と素な正整数とすると α ⋅ e + β ⋅ λ(n) = 1 となる2整数 α, β が存在する。α として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 = a^e mod n ∈ ℤ_n を計算し、b を 平文 a の暗号文とする。

復号

a′ = b^d mod n ∈ ℤ_n を計算する。すると a′ = a となり a′ は 平文 a の暗号文 b の復号文となる。

完全性の証明

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

$a'\equiv a^{(d\cdot e)}{\pmod {n}}=a^{(x\cdot \lambda (n)+1)}=(a^{\lambda (n)})^{x}\cdot a$

記事参照

冪剰余

セキュリティパラメータが1024の場合、n は1024ビットという大きな桁数の数となり、d も n とほぼ同じ桁数の数となる。 $a=b^{d}{\bmod {n}}$

この節の加筆が望まれています。

脆弱な平文

RSA暗号の安全性は素因数分解の困難さ（より正確には素因数が不明な法 n での冪根を求めることの難しさ）に基づいている。 しかし、平文の内容によっては、素因数分解をせずとも暗号文から平文を入手できる。

決まりきった平文

公開鍵暗号全般に言えることであるが、確定的暗号（例えば平文が「はい」か「いいえ」のどちらかしか有り得ない）であれば、それぞれを暗号化したものと暗号文とを比較すれば容易に平文を知ることができる。

実用上は、m の一部に毎回生成する乱数を挿入することで、この攻撃を回避できる（復号側で乱数部分を無視するよう処理すればよい）。

小さなm

平文 m が、n の e 乗根よりも小さいと、暗号文 $c=m^{e}\;\operatorname {mod} \;n=m^{e}$ カテゴリ

ウィキペディア小見出し辞書

RSA暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/09 02:12 UTC 版)

「ぬるぺた」の記事における「RSA暗号」の解説

桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号。

Wiktionary日本語版（日本語カテゴリ）

RSA暗号

出典:『Wiktionary』 (2021/07/08 10:30 UTC 版)

名詞

RSA暗号（アールエスエーあんごう）

1. (情報)代表的な公開鍵暗号方式の一つで、素因数分解の演算とその逆演算の処理難度の差を利用した方式。暗号とデジタル署名を実現できる方式として最初に公開され、公開鍵暗号方式の先駆けとなった。

語源

発明者であるリベスト（Rivest）、シャミア（Shamir）、エーデルマン（Adleman）の頭文字をつなげたもの。

Weblio日本語例文用例辞書

「RSA 暗号」の例文・使い方・用例・文例

• その暗号を解いた者はまだいない
• 暗号で書く
• 暗号で書かれたメッセージ
• 暗号を解読する
• 暗号学
• 彼が業界標準の暗号技術を用いた
• このフォームは暗号化通信によって、お客様の個人情報を保護しています
• この暗号作成者は天才に違いない。
• 暗号に精通した適任者を見つけた。
• その研究者たちは何年にもわたってその暗号文の解読に取り組んでいる。
• 暗号化すれば、その問題は解ける。
• 私達は暗号を変更したい。
• 犯人は暗号化を無効にしようともするでしょう。
• それはまるで暗号みたいですね。
• これらは何かの暗号だったに違いない。
• 私はこの暗号を解読する。
• 暗号の解除
• 第三者が解読を試みても、この暗号を解読することはできない。
• 暗号技術も、かなり信頼のおけるものに進む。
• フランクは暗号による伝言を残した。