RSA暗号 （RSAあんごう）とは、桁数が大きい合成数 の素因数分解 が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号 の一つである。暗号 [ 1] デジタル署名 を実現できる方式として最初に公開されたものである。
RSA暗号方式は、1977年 に発明され、発明者であるロナルド・リベスト 、アディ・シャミア 、レオナルド・エーデルマン の原語表記の頭文字をつなげてこのように呼ばれる[ 2] (p63) 。前年（1976年）にディフィー とヘルマン によって発表されたばかりの公開鍵暗号という新しい概念 に対し、秘匿 や認証 を実現できる具体的なアルゴリズム を与えた。発明者3氏は、この功績によって2002年 のチューリング賞 を受賞した。この暗号はフェルマーの小定理 に基づいている[ 2] [要ページ番号 。
RSA暗号のアルゴリズムは、1983年 9月20日 にアメリカ合衆国 で特許 （4,405,829号）を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年 9月6日 からは誰でも自由に使用できるようになった。
暗号の用語については暗号#用語 、暗号理論#用語 を参照。
なお、RSA暗号を最初に考案したのはGCHQ に所属するジェイムズ・エリス （英語版 ） クリフォード・コックス （英語版 ） [ 2] (p66) 。また、当時はRSA暗号を使用するには高価なコンピュータが必要であり、公に知られている限り、実用に供されることは無かった。
鍵生成 、暗号化 、復号 の3つのアルゴリズムで定義される。
p , q n = pq λ (n ) = (p − 1)(q − 1)e を λ (n )α ⋅ e + β ⋅ λ (n ) = 1α , β [ 3] α として1つの正整数 d を選択してそのときの β を −x d ⋅ e = x ⋅ λ (n ) + 1d を秘密鍵とし、n と e を公開鍵とする。
ここで、α ⋅ e + β ⋅ λ (n ) = 1i を整数とすると (α + i ⋅ λ (n )) ⋅ e + (β − i ⋅ e ) ⋅ λ (n ) = 1 α に λ (n )α とできるため、α として正整数 d を選択できるとした。
以下 ℤn 0 以上 n 未満の整数の集合 とする。
a ∈ ℤn a を暗号化対象の平文とする。b = a e n ∈ ℤn b を 平文 a の暗号文 とする。
a ′ = b d n ∈ ℤn a ′ = a a ′a の暗号文 b の復号文となる。
定義により以下が成立する。
a
′
≡ ≡ -->
a
(
d
⋅ ⋅ -->
e
)
(
mod
n
)
=
a
(
x
⋅ ⋅ -->
λ λ -->
(
n
)
+
1
)
=
(
a
λ λ -->
(
n
)
)
x
⋅ ⋅ -->
a
{\displaystyle a'\equiv a^{(d\cdot e)}{\pmod {n}}=a^{(x\cdot \lambda (n)+1)}=(a^{\lambda (n)})^{x}\cdot a}
これにより以下も成立する。
a
′
≡ ≡ -->
(
a
λ λ -->
(
n
)
)
x
⋅ ⋅ -->
a
(
mod
p
)
a
′
≡ ≡ -->
(
a
λ λ -->
(
n
)
)
x
⋅ ⋅ -->
a
(
mod
q
)
{\displaystyle {\begin{aligned}a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {p}}\\a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {q}}\end{aligned}}}
a が n と互いに素な整数のときは a が2つの素数 p , q
フェルマーの小定理 により
a
p
− − -->
1
≡ ≡ -->
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}
a
q
− − -->
1
≡ ≡ -->
1
(
mod
q
)
{\displaystyle a^{q-1}\equiv 1{\pmod {q}}}
a
λ λ -->
(
n
)
=
(
a
p
− − -->
1
)
q
− − -->
1
≡ ≡ -->
1
(
q
− − -->
1
)
(
mod
p
)
=
1
a
λ λ -->
(
n
)
=
(
a
q
− − -->
1
)
p
− − -->
1
≡ ≡ -->
1
(
p
− − -->
1
)
(
mod
q
)
=
1
{\displaystyle {\begin{aligned}a^{\lambda (n)}=(a^{p-1})^{q-1}\equiv 1^{(q-1)}{\pmod {p}}=1\\a^{\lambda (n)}=(a^{q-1})^{p-1}\equiv 1^{(p-1)}{\pmod {q}}=1\end{aligned}}}
よって
(
a
λ λ -->
(
n
)
− − -->
1
)
{\displaystyle (a^{\lambda (n)}-1)}
p , q
a
λ λ -->
(
n
)
≡ ≡ -->
1
(
mod
n
)
{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}
a
′
≡ ≡ -->
(
a
λ λ -->
(
n
)
)
x
⋅ ⋅ -->
a
(
mod
n
)
≡ ≡ -->
1
x
⋅ ⋅ -->
a
(
mod
n
)
=
a
{\displaystyle a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {n}}\equiv 1^{x}\cdot a{\pmod {n}}=a}
となるが、
a
,
a
′
∈ ∈ -->
Z
n
{\displaystyle a,a'\in \mathbb {Z} _{n}}
a
′
=
a
{\displaystyle a'=a}
となる。
gcd
(
n
,
a
)
=
p
{\displaystyle \gcd(n,a)=p}
a
∈ ∈ -->
Z
n
− − -->
{
0
}
{\displaystyle a\in \mathbb {Z} _{n}-\{0\}}
a は q − 1集合
{
1
⋅ ⋅ -->
p
,
2
⋅ ⋅ -->
p
,
3
⋅ ⋅ -->
p
,
⋯ ⋯ -->
,
(
q
− − -->
1
)
⋅ ⋅ -->
p
}
{\displaystyle \{1\cdot p,2\cdot p,3\cdot p,\cdots ,(q-1)\cdot p\}}
a が p で割り切れるから
a
≡ ≡ -->
0
(
mod
p
)
{\displaystyle a\equiv 0{\pmod {p}}}
a , q フェルマーの小定理 により
a
q
− − -->
1
≡ ≡ -->
1
(
mod
q
)
{\displaystyle a^{q-1}\equiv 1{\pmod {q}}}
a
λ λ -->
(
n
)
=
(
a
q
− − -->
1
)
p
− − -->
1
≡ ≡ -->
1
(
p
− − -->
1
)
(
mod
q
)
=
1
{\displaystyle a^{\lambda (n)}=(a^{q-1})^{p-1}\equiv 1^{(p-1)}{\pmod {q}}=1}
よって
a
′
≡ ≡ -->
(
a
λ λ -->
(
n
)
)
x
⋅ ⋅ -->
a
(
mod
p
)
≡ ≡ -->
(
a
λ λ -->
(
n
)
)
x
⋅ ⋅ -->
0
(
mod
p
)
=
0
a
′
≡ ≡ -->
(
a
λ λ -->
(
n
)
)
x
⋅ ⋅ -->
a
(
mod
q
)
≡ ≡ -->
1
x
⋅ ⋅ -->
a
(
mod
q
)
=
a
{\displaystyle {\begin{aligned}a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {p}}\equiv (a^{\lambda (n)})^{x}\cdot 0{\pmod {p}}=0\\a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {q}}\equiv 1^{x}\cdot a{\pmod {q}}=a\end{aligned}}}
よって
a
′
≡ ≡ -->
0
(
mod
p
)
≡ ≡ -->
a
(
mod
p
)
a
′
≡ ≡ -->
a
(
mod
q
)
{\displaystyle {\begin{aligned}a'\equiv 0{\pmod {p}}\equiv a{\pmod {p}}\\a'\equiv a{\pmod {q}}\end{aligned}}}
よって a' − a p , q
a
′
≡ ≡ -->
a
(
mod
n
)
{\displaystyle a'\equiv a{\pmod {n}}}
となるが、
a
,
a
′
∈ ∈ -->
Z
n
{\displaystyle a,a'\in \mathbb {Z} _{n}}
a
′
=
a
{\displaystyle a'=a}
となる。
gcd
(
n
,
a
)
=
q
{\displaystyle \gcd(n,a)=q}
a
∈ ∈ -->
Z
n
− − -->
{
0
}
{\displaystyle a\in \mathbb {Z} _{n}-\{0\}}
a' = a
a = 0
b
∈ ∈ -->
{
z
∈ ∈ -->
Z
n
∣ ∣ -->
z
≡ ≡ -->
0
e
(
mod
n
)
}
=
{
0
}
{\displaystyle b\in \{z\in \mathbb {Z} _{n}\mid z\equiv 0^{e}{\pmod {n}}\}=\{0\}}
b = 0
a
′
∈ ∈ -->
{
z
∈ ∈ -->
Z
n
∣ ∣ -->
z
≡ ≡ -->
0
d
(
mod
n
)
}
=
{
0
}
{\displaystyle a'\in \{z\in \mathbb {Z} _{n}\mid z\equiv 0^{d}{\pmod {n}}\}=\{0\}}
a' = 0a ′ = a = 0
以上何れにしても a' = a a の 暗号文 b は 秘密鍵 d と公開鍵の一つ n を用いて平文 a に復号できることが分かる。
n を法とする冪剰余の計算セキュリティパラメータが1024の場合、n は1024ビットという大きな桁数の数となり、d も n とほぼ同じ桁数の数となる。
a
=
b
d
mod
n
{\displaystyle a=b^{d}{\bmod {n}}}
バイナリ法 というアルゴリズムを用いると、剰余乗算 (
1024
b
i
t
× × -->
1024
b
i
t
{\displaystyle 1024\mathrm {bit} \times 1024\mathrm {bit} }
中国の剰余定理 を用いて、
a
p
=
b
d
mod
λ λ -->
(
p
)
mod
p
a
q
=
b
d
mod
λ λ -->
(
q
)
mod
q
a
′
=
a
p
(
q
− − -->
1
mod
p
)
q
+
a
q
(
p
− − -->
1
mod
q
)
p
{\displaystyle {\begin{aligned}ap&=b^{d{\bmod {\lambda }}(p)}{\bmod {p}}\\aq&=b^{d{\bmod {\lambda }}(q)}{\bmod {q}}\\a'&=ap(q^{-1}{\bmod {p}})q+aq(p^{-1}{\bmod {q}})p\end{aligned}}}
として求めることがある。
桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller–Rabinテスト などの確率的素数判定法 によって高速に行える。確率的素数判定法をパスした自然数を確率的素数 (probable prime) という。確率的素数には、素数の他に擬素数 が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる（なお、拡張リーマン予想 が正しければ、Miller–Rabinテストは素数かどうかを正しく判定する、という事実が知られている[要出典 ）。
2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間 で行うAKS素数判定法 を発表した[要出典 が、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。
RSA暗号は、安全性が素因数分解問題と同値 であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。
素因数分解を解けるオラクル を用いれば、n から p および q が計算できるので、鍵生成と同様にして秘密鍵 d を知ることができる。即ち、RSA暗号が解読できる。従って、RSA仮定が証明できれば素因数分解問題の困難性が示せる。しかし、逆が成立するかどうかはよく分かっていない。ある条件下では否定的な結果もでている。
RSA暗号が選択平文攻撃 に対して完全解読できない、ということとRSA仮定 とは同値である。
RSA問題 を解く方法として、現在知られている有力な方法は、素因数分解問題を解くことに使える方法だけである。素因数分解問題を解く方法として、楕円曲線法 や数体篩法 などのアルゴリズムが知られているが、これらの方法はどれも準指数関数時間 アルゴリズムであり、多項式時間 で素因数分解問題を解く方法は知られていない。
暗号理論 の世界では、多項式時間で解読することができない暗号方式を安全であると定義することがある（計算量的安全性）。この意味で、RSA暗号の安全性について、現在知られている範囲では安全であると期待されていて、その反証がないと言える。
RSA問題や素因数分解問題はNP 問題であるので、これらの問題が（決定性のある）多項式時間では解けないことが証明できれば、P≠NP予想 が肯定的に解決することになる。ただし、ハミルトン閉路問題 など他のNP問題（NPかつNP困難 なNP完全 問題を含む）が多項式時間で解けることが証明されればP=NPとなってしまう。
2004年の時点では、インターネットで公募した数多くのPCを用いると512ビット程度の数なら素因数分解できるので、RSA暗号に使用する法 n は1024-4096ビット（10進数で300-1000桁程度）にすることが推奨されている。
しかしシャミアは、RSA問題を解くための専用装置 (TWIRL ) を作成すれば、1024ビットの n に関するRSA問題ですら解くことができると主張している。また、実用的な量子コンピュータ が登場した場合には、素因数分解の桁数増に対する計算時間の増加が緩やかなショアのアルゴリズム と呼ばれる高速な量子コンピュータアルゴリズムが実行可能となるため、たとえ鍵のビット数を増やしてもRSA暗号の安全性が保証されなくなる可能性が指摘されている[ 4]
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桁）
2010年5月8日 RSA-180 (596ビット)
2010年11月8日 RSA-190 (629ビット)
2005年11月2日 RSA-640 (640ビット)
2005年5月9日 RSA-200 (663ビット、10進200桁)
2013年9月26日 RSA-210 (696ビット、10進210桁)
2012年7月2日 RSA-704 (704ビット)
2016年5月13日 RSA-220 (729ビット）
2018年8月15日 RSA-230 (762ビット）
2020年2月17日 RSA-232 (768ビット）
2009年12月12日 RSA-768 (768ビット)
2019年12月2日 RSA-240 (795ビット）
2020年2月28日 RSA-250 (829ビット） 以下は未踏
RSA-896
RSA-1024
RSA-1536
RSA-2048
RSA暗号は選択暗号文攻撃 を行なえば完全解読できる。また、RSA暗号は選択平文攻撃 に対してすらindistinguishable （識別不能）ではない。よってRSA暗号は選択平文攻撃 に対してnon-malleable（頑強性 ）でも semantic secure（強秘匿性 ）でもない。non-malleable と semantic secure の定義は公開鍵暗号 に記されている。
共通の法 n
ユーザー管理等の利便性や素数探索の労を避けるため、法である n を共通として各々に個別の e と d を与えるのは誤りである。もしも法 n とそれに対応する e と d の組を一つでも知ることができれば、法 n の素因数分解 が容易となり安全ではなくなるからである。 同報通信
全く同一の平文 を複数の送信先へ各々の公開鍵で暗号化して同報通信するには適していない。同じ e を持つ公開鍵（ハミング重み HW = 23 や 65537 が好んで用いられる）で暗号化された e 個以上の暗号文を手に入れたなら各々の公開鍵の法に関して中国の剰余定理 を用いることで、通常の冪根 によって平文を復元できるからである。詳しくは下記の同一平文を参照のこと。このため、現在規格化されている暗号への応用においては、パディングとして毎回乱数 を生成して挿入するなどの対策がされている。
RSA暗号の安全性は素因数分解の困難さ（より正確には素因数が不明な法 n での冪根 を求めることの難しさ）に基づいている。
しかし、平文の内容によっては、素因数分解をせずとも暗号文から平文を入手できる。
公開鍵暗号 全般に言えることであるが、確定的暗号（例えば平文が「はい」か「いいえ」のどちらかしか有り得ない）であれば、それぞれを暗号化したものと暗号文とを比較すれば容易に平文を知ることができる。
実用上は、m の一部に毎回生成する乱数 を挿入することで、この攻撃を回避できる（復号側で乱数部分を無視するよう処理すればよい）。
m 平文 m が、n の e 乗根よりも小さいと、暗号文
c
=
m
e
mod
n
=
m
e
{\displaystyle c=m^{e}\;\operatorname {mod} \;n=m^{e}}
冪根 演算によって c の e 乗根を計算するだけで平文 m が復元できてしまう。
実用上は、m の比較的高位のビット に1を挿入することでこの攻撃を回避できる。
法 n における e 乗根が計算できれば、暗号文を復号できる。当然これは（法 n の素因数が分からない限り）非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。
しかし、全く同一の平文を、異なる法において同一の e を用いて暗号化した暗号文を e 個以上集めることで、各々の法に関して中国の剰余定理 を用いれば通常の冪根 演算によって平文を復元できる。これを同報通信の誤用と呼ぶ。
c
1
≡ ≡ -->
m
e
(
mod
n
1
)
c
2
≡ ≡ -->
m
e
(
mod
n
2
)
c
3
≡ ≡ -->
m
e
(
mod
n
3
)
c
e
≡ ≡ -->
m
e
(
mod
n
e
)
{\displaystyle {\begin{aligned}c_{1}&\equiv m^{e}{\pmod {n_{1}}}\\c_{2}&\equiv m^{e}{\pmod {n_{2}}}\\c_{3}&\equiv m^{e}{\pmod {n_{3}}}\\\\c_{e}&\equiv m^{e}{\pmod {n_{e}}}\end{aligned}}}
ここから中国の剰余定理 によって上記式を満たす、
c
≡ ≡ -->
m
e
(
mod
n
1
n
2
n
3
⋯ ⋯ -->
n
e
)
{\displaystyle c\equiv m^{e}{\pmod {n_{1}n_{2}n_{3}\dotsm n_{e}}}}
を求めることができる。このとき
c
<
n
1
n
2
n
3
⋯ ⋯ -->
n
e
{\displaystyle c<n_{1}n_{2}n_{3}\dotsm n_{e}}
m はどの法 n よりも小さいため
m
e
<
n
1
n
2
n
3
⋯ ⋯ -->
n
e
{\displaystyle m^{e}<n_{1}n_{2}n_{3}\dotsm n_{e}}
c
=
m
e
{\displaystyle c=m^{e}}
この c の e 乗根を求めることで平文 m が求められる。
e として 3 や 65537 は、2 進数表示したときに 1 の個数が少なく暗号化処理を高速化できるという理由から好んで用いられるが、上記の問題がある。
実用上は、m の一部に毎回生成する乱数 を挿入することでこの攻撃を回避できる。
RSA暗号の入力は、公開鍵の法を n とすると 0 から n − 1n 以上の値の平文を暗号化する際には、平文を分割して処理することになる。
この時に留意しなければならない点として、例えば、n が1024 ビット （= 128 バイト ）であるとき、平文を同じ 1024 ビット毎に分割処理するのでは十分ではないという点がある。これは、n と m が共に 1024 ビットであったとしても、n < m
m
mod
n
{\displaystyle m{\bmod {n}}}
m は出力されないためである。
平文をビット単位（やバイト単位）で分割する際には、まず、n の下限を定めた上で、平文の全ビットを 1 に（全バイトを
F
F
16
{\displaystyle \mathrm {FF_{16}} }
n より小さくなるビット数（バイト数）で分割しなければならない。例えば、n の下限を
n
≥ ≥ -->
2
1023
{\displaystyle n\geq 2^{1023}}
1023 ビットごとに分割する。こうすることで m < n
一方で、出力となる暗号文は 0 から n − 1n の下限より小さいビット数）1023 ビット毎に分割された m に対応する暗号文の中には、1024 ビットが必要となるものがある。つまり、平文をビット単位で分割する場合には暗号化によってメッセージサイズが増加するといえる。これを回避するにはビット単位で分割するのではなく、平文 m を n 進数表示したときの各桁毎に分割すればよい。
RSA暗号方式は、
平文が小さいと、暗号文から平文が容易に計算できてしまう、
暗号文を分解して、個々の暗号文に対応する平文を入手できる（選択暗号文攻撃）と、元の暗号文に対応する平文を求めることができてしまう、
攻撃者が暗号文を変形して、平文自体を知ることはできないが、平文を変形できてしまう（非展性がない）、 などの脆弱性があり、RSA暗号方式をそのまま利用することは好ましくない。このため、実際のRSA暗号の実装では、暗号化する前に適切なパディングを行っている。代表的なパディングとしてOAEP があり、公開鍵暗号標準であるPKCS #1（バージョン1.5以降）もこれを採用している。OAEPは確率的なパディングであり、すなわち、元の平文が同じであっても、パディングされた平文は時によって異なる（ランダムに選ばれた値に依存）。
OAEPパディングとRSA暗号の併用をRSA_OAEPと呼ぶことがある（これに対して、パディング処理を行わない素のRSA暗号方式を生RSA、教科書的RSAということがある）。RSA_OAEPは、公開鍵暗号における最も高い安全性である「適応的選択暗号文攻撃に対する識別不可能性」を持つことが示されている[ 5]
RSA暗号が実現した公開鍵暗号方式は、従来の暗号方式（共通鍵暗号）とは異なり、暗号化は公開鍵を使って誰でもできるが、復号は秘密鍵を持つ本人だけしかできない方式である。この復号は「本人だけしかできない」という性質を利用すると、デジタル署名 （あるいは認証機能）が実現できる。
そのためには、公開鍵・秘密鍵を次のように使用する。
暗号の場合
平文 → 公開鍵（暗号化）→ 暗号文、暗号文→ 秘密鍵（復号）→ 平文
署名の場合
文書 → 秘密鍵（署名生成）→ 署名値、署名値→ 公開鍵（署名検証）→ 文書 公開鍵と秘密鍵の役割は通常の場合においては上記の通り、公開鍵は暗号化に使われ、秘密鍵は復号に用いられるが、RSA暗号においては平文と暗号文の定義域が同じ（平文空間＝暗号文空間である）ため、任意の文書（メッセージ）を暗号文とみなして復号することができる。つまり秘密鍵を用いて任意の文書について署名値を生成でき、公開鍵を用いてその署名値を暗号化 して元の文書と一致するかを調べることで署名の検証ができる。
ただし、RSA暗号と同様に、生RSAでは、署名の潜在的偽造等の好ましくない性質があるため、パディングなどが必要である。また、暗号文空間よりも大きなメッセージを扱うためにハッシュ関数 と組み合わせて使用する。
このようなパディングなども含めたものとして、
などがある。
RSA-129
1977年 、マーティン・ガードナー がコラムを連載していたサイエンティフィック・アメリカン 誌に129桁の法 n と公開指数 e = 9007[ 6] マサチューセッツ工科大学 から100米ドル を与えるという懸賞金問題だった[ 6] 15 年）は必要だろうと予測されていた[ 6] オックスフォード大学 ポール・レイランド （英語版 ） アイオワ州立大学 マイケル・グラフ、マサチューセッツ工科大学デレク・アトキンス、アリエン・レンストラ （英語版 ） ボランティア の協力を得て、二次ふるい法によってRSA-129に対する大規模攻撃を開始した。8か月で800万以上の下位問題が解かれ、得られた50万行50万列以上の疎行列 から188614行188160列の行列 による連立方程式 を作った。これをスーパーコンピュータMP-1で45時間をかけて構造的ガウスの消去法 によって解き、解読に成功した（1994年4月）[ 7] The magic words are squeamish ossifrage”［ossifrage（ヒゲワシ ）はラテン 語で「骨を折る者」の意。ロナルド・リベスト によると暗号の答えはランダム で決められた。[ 8]
RSA暗号をサポートしているライブラリは以下の通り。
^ 英 : cipher ^ a b c イアン・スチュアート 「おおっぴらにできる暗号」『数学の魔法の宝箱』ソフトバンク クリエイティブ、2010年。ISBN 978-4-7973-5982-4 。
^ このような2整数は、拡張ユークリッド互除法 で簡単に見つけることができる。
^ “量子コンピューターが暗号技術を「破壊」する？その真偽を検証してみた ”. 日経xTECH (2020年1月30日). 2022年9月21日 閲覧。 ^ 藤崎英一郎; 岡本龍明; Pointcheval, David; Stern, Jacques (2001), RSA-OAEP is secure under the RSA assumption Lecture Notes in Computer Science (Springer-Verlag) 2139 : 260-274, http://eprint.iacr.org/2000/061.pdf ^ a b c Gardner, Martin (1977). “Mathematical Games, August 1977” . Scientific American 237 (2): 120–124. doi :10.1038/scientificamerican0877-120 . http://simson.net/ref/1977/Gardner_RSA.pdf .
^ Derek Atkins (1994年4月27日). “RSA-129” . sci.math, sci.crypt, alt.security etc. (Internet news). https://ns1.omnitech.net/data//Books/Math/94/ras129.ans 2020年12月10日 閲覧。 ^ “The Magic Words are Squeamish Ossifrage ”. Advances in Cryptology - ASIACRYPT'94 (July 1994). 28 September 2015 閲覧。
Cocks, Clifford C. (1973-11-20), A Note on Non-Secret Encryption , https://web.archive.org/web/20080227001905/http://www.cesg.gov.uk/site/publications/media/notense.pdf 2015年7月10日 閲覧。 GCHQ の一部局）に提出したメモRivest, Ronald L.; Shamir, Adi; Adelman, Len M. (1977-07-04), “A Method for Obtaining Digital Signature and Public-key Cryptsystems” , MIT-LCS-TM-082 (MIT Laboratory for Computer Science), https://people.csail.mit.edu/rivest/Rsapaper.pdf 2015年7月10日 閲覧。
![[icon]](%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wiki_letter_w_cropped.svg){kind=small}
