RSA暗号システム

RSAアルゴリズムの鍵は、以下の方法で生成されます。

1. 異なる2つの大きな素数pとqを選びます。
   • 素因数分解を不可能にするためには、pとq を、2 ¹⁰²³から2 ¹⁰²⁴までのすべての素数 (2,048 ビットの鍵に対応) など、可能性の大きな空間からランダムに選択する必要があります。実際には、素数選択のためのさまざまなアルゴリズムが使用されています。^{[ 29 ]}
   • pとqは秘密にされている。
2. n = pqを計算します。
   • nは公開鍵と秘密鍵の両方の法として使用されます。その長さは通常ビット単位で表され、鍵長となります。
   • nは公開鍵の一部として公開されます。
3. λ ( n )を計算します。ここでλはカーマイケルのトーシェント関数です。n = pqなので、λ ( n ) = lcm ( λ ( p ), λ ( q )) であり、pとqは素数なので、λ ( p ) = φ ( p ) = p − 1、同様にλ ( q ) = q − 1です。したがって、λ ( n ) = lcm( p − 1, q − 1)となります。
   • 最小公倍数は、ユークリッドの互除法によって計算できます。lcm ( a , b ) = ⁠ | ab | / gcd( a , b ) ⁠  です。
   • λ ( n )は秘密にされている。
4. 1 < e < λ ( n )かつgcd ( e , λ ( n )) = 1となるような整数eを選択します。つまり、eとλ ( n )は互いに素です。
   • e のビット長が短く、ハミング重みが小さいと、暗号化がより効率的になります。eに最もよく選ばれる値は2 ¹⁶ + 1 =です。 65 537 。eの最小値 (かつ最速)は 3 ですが、 eの値が小さいと、安全でないパディング スキームの脆弱性が露呈する可能性があります。 ^{[ 30 ] [ a ]}
   • eは公開鍵の一部として公開されます。
5. dを d ≡ e ⁻¹ (mod λ ( n ))と定義します。つまり、dはeのλ ( n )を法とするモジュラー乗法逆数です。
   • これは、方程式de ≡ 1 (mod λ ( n ))をdについて解くことを意味します。eとλ ( n )が互いに素であるため、この方程式はベズーの恒等式の一種であり、dはその係数の 1 つであるため、拡張ユークリッドアルゴリズムを使用してdを効率的に計算できます。
   • dは秘密鍵指数として秘密に保たれます。

公開鍵は法nと公開指数eから構成される。秘密鍵は秘密指数dから構成され、これは秘密に保持されなければならない。p 、q、およびλ ( n )も、 d の計算に使用できるため秘密に保持されなければならない。実際、dが計算された後は、これらはすべて破棄することができる。^{[ 31 ]}

オリジナルの RSA 論文^{[ 3 ]}では、秘密指数dを計算するためにλ ( n )の代わりにオイラーのトーシェント関数φ ( n ) = ( p − 1)( q − 1)が使用されています。φ ( n )は常にλ ( n )で割り切れるため、このアルゴリズムは同様に機能します。オイラーのトーシェント関数を使用できる可能性は、整数の乗法群にpqを法として適用したラグランジュの定理からも得られます。 したがって、d ⋅ e ≡ 1 (mod φ ( n ))を満たす任意のdは、 d ⋅ e ≡ 1 (mod λ ( n ))も満たします。 ただし、dをφ ( n )を法として計算すると、必要以上に大きな結果 (つまりd > λ ( n ) ) が得られる場合があります。 RSAの実装のほとんどは、どちらの方法で生成された指数も受け入れます（ただし、後述する中国剰余定理に基づく最適化された復号方法ではなく、秘密指数dを使用する場合に限ります）。しかし、 FIPS 186-4（セクションB.3.1）などの一部の標準では、 d < λ（n）が要求される場合があります。この基準を満たさない「大きすぎる」秘密指数は、常にλ（n）を法として縮小し、より小さな等価指数を得ることができます。 

注: オリジナルの RSA 論文の著者は、d を選択してからeをφ ( n )を法とするdのモジュラ乗法逆数として計算することで鍵生成を実行しますが、 PKCS#1に従うものなど、現在の RSA の実装のほとんどは逆で、e を選択してからd を計算します。eは安全に小さく固定できますが、d は攻撃に耐えられるほど大きな空間から選択する必要があるため、この最新のアプローチはセキュリティを損なうことなく公開鍵操作のコストを削減できます。^{[ 3 ] [ 32 ]}

ボブがアリスに秘密のメッセージを送信したい、あるいはアリスからのメッセージを検証したいとします。RSA暗号を使う場合、ボブは秘密のメッセージを暗号化したりアリスのメッセージを検証したりするためにアリスの公開鍵を知っている必要があり、アリスはボブの秘密のメッセージを復号したり自分のメッセージに署名したりするために自分の秘密鍵を使う必要があります。

ボブが暗号化されたメッセージを送信したり、アリスの今後のメッセージを検証したりできるようにするため、アリスは公開鍵（n、e）を、信頼できるが必ずしも秘密ではない経路でボブに送信します。アリスの秘密鍵（d）は決して配布されません。

ボブはアリスの公開鍵を入手した後、アリスにメッセージMを送信することができる。

そのため、彼はまず、合意された可逆プロトコルであるパディングスキームを用いて、 0 ≤ m < nを満たす整数 m（パディングされた平文）に変換します。次に、アリスの公開鍵eを用いて、暗号文cを次のように計算します。

$${\displaystyle c\equiv m^{e}{\pmod {n}}.}$$

これは、モジュラべき乗を使用すれば、非常に大きな数でもかなり速く実行できます。次に、ボブはc をアリスに送信します。m の少なくとも 9 つの値で、暗号文cがmと等しく なります^{[ b ]}が、実際にはこのようなことはまず起こりません。

アリスは、秘密鍵指数dを使用して計算することで、cからmを復元できます。

$${\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m{\pmod {n}}.}$$

mが与えられた場合、彼女はパディング方式を反転させることで元のメッセージMを復元するか、パディングが無効な場合は破損したメッセージとして破棄することができる。

アリスは、パディングが無効な場合はmを破棄しなければならない。無効なパディングがあるmに関する情報をアリスが漏らした場合、攻撃者はこれを悪用して、ランダムまたは悪意を持って作成された暗号文をアリスに送信し、アリスの反応を観察することで、秘密鍵を知らなくてもメッセージを復号（または署名）することができる。^{[ 33 ]}

パディングの詳細は無視して、RSA暗号化と復号の例を以下に示します。^{[ c ]}

1. 異なる素数を 2 つ選びます。

   ${\displaystyle p=61}$そして${\displaystyle q=53}$。

2. n = pqを計算すると、

   ${\displaystyle n=61\times 53=3233.}$

3. 積のカーマイケルのトーシェント関数をλ ( n ) = lcm ( p -1, q -1)として計算すると、

   ${\displaystyle \lambda (3233)=\operatorname {lcm} (60,52)=780.}$

4. 1 < e < 780の範囲で、780 と互いに素な任意の数を選択します。eに素数を選択すれば、あとはeが 780 の約数でないことを確認するだけです。

   させて${\displaystyle e=17}$。

5. eのモジュラー乗法逆元d （mod λ（n））を計算すると、次のようになる。$${\displaystyle d=413,}$$として${\displaystyle 1=(17\times 413){\bmod {7}}80.}$

公開鍵は( n = 3233, e = 17)です。パディングされた平文メッセージmの場合、暗号化関数は次のようになります。 $${\displaystyle {\begin{aligned}c(m)&=m^{e}{\bmod {n}}\\&=m^{17}{\bmod {3}}233.\end{aligned}}}$$

秘密鍵は( n = 3233, d = 413)です。暗号化された暗号文cの復号関数は $${\displaystyle {\begin{aligned}m(c)&=c^{d}{\bmod {n}}\\&=c^{413}{\bmod {3}}233.\end{aligned}}}$$

例えば、m = 65を暗号化するには、次のように計算します。 $${\displaystyle c=65^{17}{\bmod {3}}233=2790.}$$

c = 2790を復号するには、以下を計算する。 $${\displaystyle m=2790^{413}{\bmod {3}}233=65.}$$

これらの計算はどちらも、モジュラべき乗の二乗乗算アルゴリズムを使用して効率的に計算できます。実際の状況では、選択される素数ははるかに大きくなります。この例では、n = 3233 (自由に利用可能な公開鍵から取得) を素数pとqに素因数分解するのは簡単です。同じく公開鍵から得られるeを反転してdを取得し、秘密鍵を取得します。

実際の実装では、中国剰余定理を使用して、因数の法則（mod pと mod qを使用した mod pq ）による計算を高速化します。

秘密鍵の一部である 値d _p、d _q、q _{inv は、次のように計算されます。}$${\displaystyle {\begin{aligned}d_{p}&=d{\bmod {(}}p-1)=413{\bmod {(}}61-1)=53,\\d_{q}&=d{\bmod {(}}q-1)=413{\bmod {(}}53-1)=49,\\q_{\text{inv}}&=q^{-1}{\bmod {p}}=53^{-1}{\bmod {6}}1=38\\&\Rightarrow (q_{\text{inv}}\times q){\bmod {p}}=38\times 53{\bmod {6}}1=1.\end{aligned}}}$$

d _p、d _q、q _{inv は}、効率的な復号化のために以下のように使用されます（暗号化は、適切なdとe のペアを選択することによって効率的になります）。 $${\displaystyle {\begin{aligned}m_{1}&=c^{d_{p}}{\bmod {p}}=2790^{53}{\bmod {6}}1=4,\\m_{2}&=c^{d_{q}}{\bmod {q}}=2790^{49}{\bmod {5}}3=12,\\h&=(q_{\text{inv}}\times (m_{1}-m_{2})){\bmod {p}}=(38\times -8){\bmod {6}}1=1,\\m&=m_{2}+h\times q=12+1\times 53=65.\end{aligned}}}$$

アリスが署名付きメッセージm をボブに送信したいとします。アリスはメッセージmのハッシュ値h = hash( m )を生成し、それをd乗(mod n ) し、s = h ^d mod nを「署名」としてメッセージに添付します。

ボブはメッセージmと署名sを受け取ると、アリスの公開鍵と組み合わせた同じハッシュアルゴリズムを使用してh = hash( m )を計算します。彼は署名sをe乗（nを法とする）し、結果として得られたハッシュ値をメッセージのハッシュ値と比較します。$${\displaystyle s^{e}\mathrel {\stackrel {?}{\equiv }} h{\pmod {n}}}$$両者が同意すれば、彼はメッセージの送信者がアリスの秘密鍵を所持していたこと、そしてメッセージが送信後に改ざんされていないことを知る。

指数法則により、s = h ^d mod nの場合、この式は満たされます。 $${\displaystyle s^{e}=(h^{d})^{e}=h^{de}=h^{ed}=(h^{e})^{d}\equiv h{\pmod {n}}.}$$

署名と検証のためのモジュラべき乗は、復号と暗号化のための基礎となる数学と同じですが、安全な公開鍵暗号化のためのパディング方式と安全なデジタル署名のためのハッシュ化のその他の詳細はすべて異なります。^{[ 32 ]}

ハッシュの使用は、1978 年にMichael O. Rabinが関連するRabin 署名アルゴリズムで初めて提案したもので、^{[ 34 ] [ 35 ]} ハッシュのセキュリティは署名のセキュリティに不可欠です。^{[ 36 ] [ 37 ]}アリスとボブがハッシュをスキップし、ボブが代わりにs ^e ≡ m (mod n )をチェックした場合、誰でもメッセージm = 1に署名s = 1を偽造したり、アリスから 2 つの署名付きメッセージ( m ₁、s ₁ )と( m ₂、s ₂ )を取得して、秘密鍵を知らなくても乗算によって 3 番目のメッセージ( m ₁ m ₂、s ₁ s ₂ )を偽造することができます。

RSAの正当性の証明は、任意の整数aと素数p（aを割り切らない）に対してa ^{p − 1} ≡ 1 (mod p )となるというフェルマーの小定理に基づいている。^{[注1 ]}

私たちはそれを示したい $${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}$$pとqが異なる素数であり、ed≡1 ( modλ ( pq ) )を満たす正の整数eとdを持つすべての整数m について。

λ ( pq ) = lcm ( p -1, q -1)は、定義上、p -1とq -1の両方で割り切れるので、次のように書くことができます。 $${\displaystyle ed-1=h(p-1)=k(q-1)}$$ ある非負整数hとkに対して。^{[注 2 ]}

m ^edとmのような 2 つの数がmod pq で合同であるかどうかを確認するには、それらがmod p とmod q でそれぞれ合同であることを確認するだけで十分であり、実際には同等である。^{[注 3 ]}

m ^ed ≡ m (mod p )を示すために、次の2つのケースを考えます。

1. m ≡ 0 (mod p )の場合、mはpの倍数です。したがって、m ^edはpの倍数です。よって、m ^ed ≡ 0 ≡ m (mod p )となります。
2. m ≢ 0 (mod p )の場合、

   ${\displaystyle m^{ed}=m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^{h}m\equiv 1^{h}m\equiv m{\pmod {p}},}$

   ここで、フェルマーの小定理を用いてm ^{p −1} mod p を1 に置き換えた。

m ^ed ≡ m (mod q )の検証は、全く同様の方法で行われます。

1. m ≡ 0 (mod q )の場合、m ^edはqの倍数です。したがって、m ^ed ≡ 0 ≡ m (mod q )となります。
2. m ≢ 0 (mod q )の場合、

   ${\displaystyle m^{ed}=m^{ed-1}m=m^{k(q-1)}m=(m^{q-1})^{k}m\equiv 1^{k}m\equiv m{\pmod {q}}.}$

これにより、任意の整数mと、ed ≡ 1 (mod λ ( pq ))を満たす整数e、dに対して、次のことが証明される。 $${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}.}$$

Rivest、Shamir、およびAdlemanによる元の論文では、RSAが機能する理由を説明するためにフェルマーの小定理が使用されていましたが、代わりにオイラーの定理に依拠する証明が見られることもよくあります。

m ^ed ≡ m (mod n )を示す。ここでn = pqは 2 つの異なる素数の積であり、eとdはed ≡ 1 (mod φ ( n ))を満たす正の整数である。eとd は正であるため、ある非負の整数hに対してed = 1 + h φ ( n )と書ける。mがnと互いに素であると仮定すると、次の ようになる。$${\displaystyle m^{ed}=m^{1+h\varphi (n)}=m(m^{\varphi (n)})^{h}\equiv m(1)^{h}\equiv m{\pmod {n}},}$$

ここで、最後から2番目の合同式はオイラーの定理から導かれる。

より一般的には、ed ≡ 1 (mod λ ( n ))を満たす任意のeとdに対して、カーマイケルのオイラーの定理の一般化から同じ結論が導かれる。この定理は、 nと互いに素なすべてのmに対してm ^{λ (n)} ≡ 1 (mod n )であると述べている。

mがnと互いに素でない場合、先ほど述べた議論は無効になります。これは非常に起こりにくいことですが ( 1/ p + 1/ q − 1/( pq )の数のうち、この性質を持つのは一部だけです)、この場合でも、求める合同式は依然として成り立ちます。m ≡ 0 (mod p) または m ≡ 0 (mod q) のいずれかであり、これらのケースは前の証明を使用して処理できます。

以下に説明するように、平文RSA暗号に対する攻撃手法は数多く存在する。

• 低い暗号化指数（例えば、e = 3 ）と小さなmの値（つまり、m < n ^{1/ e} ）で暗号化する場合、 m ^eの結果は法nよりも厳密に小さくなります。この場合、暗号文のe乗根を整数で求めることで、暗号文を簡単に復号できます。
• 同じ平文メッセージが暗号化された方法でe人以上の受信者に送信され、受信者が同じ指数eを共有しているが、 p、q、したがってnが異なる場合、中国剰余定理を使用して元の平文メッセージを簡単に復号できます。Johan Håstad は、平文が等しくなくても、攻撃者がそれらの間に線形関係を知っている場合、この攻撃が可能であることを発見しました。^{[ 38 ]}この攻撃は後にDon Coppersmithによって改良されました( Coppersmith の攻撃を参照)。^{[ 39 ]}
• RSA暗号化は決定論的暗号化アルゴリズム（つまり、ランダムな要素がない）であるため、攻撃者は公開鍵で可能性のある平文を暗号化し、それらが暗号文と等しいかどうかをテストすることで、暗号システムに対して選択平文攻撃を成功裏に実行できます。攻撃者が対応する平文を知っている（または選択した）場合でも、2つの暗号化を区別できない場合、暗号システムは意味的に安全であると呼ばれます。パディングなしのRSAは意味的に安全ではありません。^{[ 40 ]}
• RSAには、2つの暗号文の積が、それぞれの平文の積の暗号化と等しいという性質があります。つまり、m ₁ ^e m ₂ ^e ≡ ( m ₁ m ₂ ) ^e (mod n )です。この乗法的な性質のため、選択暗号文攻撃が可能です。例えば、暗号文c ≡ m ^e (mod n )の復号を知りたい攻撃者は、秘密鍵dの所有者に、攻撃者が選択した値rに対して、疑わしくないように見える暗号文c ′ ≡ cr ^e (mod n )を復号​​するように依頼することができます。乗法的な性質により、c ′ はmr (mod n )の暗号化です。したがって、攻撃者が攻撃に成功すれば、mr (mod n ) を知ることができ、mrにrの法nの法逆数を掛けることでメッセージmを導き出すことができます。^{[ 33 ] [ 41 ]}
• 秘密指数dが与えられれば、法n = pqを効率的に因数分解できます。また、法n = pqの因数分解が与えられれば、公開鍵 ( e ', n ) に対して生成された任意の秘密鍵 ( d ', n )を取得できます。^{[ 30 ]}  

これらの問題を回避するため、実際のRSA実装では、暗号化前に値mに何らかの構造化されたランダムなパディングを埋め込むのが一般的です。このパディングにより、 mが安全でない平文の範囲に入らないことが保証され、パディングされたメッセージは、多数の異なる暗号文のいずれかに暗号化されます。

PKCS#1などの標準は、RSA 暗号化の前にメッセージを安全にパディングするように慎重に設計されています。これらの方式では平文mに一定数の追加ビットをパディングするため、パディングされていないメッセージMのサイズは多少小さくなければなりません。RSA パディング方式は、予測可能なメッセージ構造によって容易になる可能性のある高度な攻撃を防ぐように慎重に設計する必要があります。PKCS#1 標準の初期バージョン (バージョン 1.5 まで) では、RSA を意味的に安全にすると思われる構造が使用されていました。しかし、Crypto 1998 で Bleichenbacher は、このバージョンが実用的な適応型選択暗号文攻撃に対して脆弱であることを示しました。さらに、Eurocrypt 2000 で Coron ら^{[ 42 ]}は、一部のタイプのメッセージでは、このパディングでは十分なレベルのセキュリティが提供されないことを示しました。標準の後のバージョンには、これらの攻撃を防ぐOptimal Asymmetric Encryption Padding (OAEP) が含まれています。そのため、新規アプリケーションではOAEPを使用し、PKCS#1  v1.5のパディングは可能な限り置き換える必要があります。PKCS#1規格には、RSA署名に追加のセキュリティを提供するように設計された処理方式も組み込まれています。例えば、RSA用確率的署名方式（RSA-PSS）などです。

RSA-PSS のような安全なパディング方式は、メッセージの暗号化と同様に、メッセージの署名のセキュリティにとっても不可欠です。PSS に関する米国特許が 2 件 (米国特許第 6,266,771 号および第 7,036,014 号) 取得されましたが、これらの特許はそれぞれ 2009 年 7 月 24 日と 2010 年 4 月 25 日に失効しました。PSS の使用はもはや特許によって妨げられることはないようです。暗号化と署名に異なる RSA キー ペアを使用することで、潜在的にセキュリティが向上することに注意してください。^{[ 43 ]}

効率化のため、多くの一般的な暗号ライブラリ（ OpenSSL、Java、.NETなど）は、復号化と署名に中国剰余定理に基づく以下の最適化を使用しています。^{[ 44 ]}以下の値は事前に計算され、秘密鍵の一部として保存されます。

• ${\displaystyle p}$そして${\displaystyle q}$ –キー生成からの素数、
• ${\displaystyle d_{P}=d{\pmod {p-1}},}$
• ${\displaystyle d_{Q}=d{\pmod {q-1}},}$
• ${\displaystyle q_{\text{inv}}=q^{-1}{\pmod {p}}.}$

これらの値により、受信者は指数計算m = c ^d (mod pq )を次のようにより効率的に計算できます。   ${\displaystyle m_{1}=c^{d_{P}}{\pmod {p}}}$、   ${\displaystyle m_{2}=c^{d_{Q}}{\pmod {q}}}$、   ${\displaystyle h=q_{\text{inv}}(m_{1}-m_{2}){\pmod {p}}}$, ^{[ d ]}  ${\displaystyle m=m_{2}+hq}$。

これは、2つのモジュラべき乗を計算する必要があるにもかかわらず、2乗によるべき乗計算よりも効率的です。その理由は、これら2つのモジュラべき乗はどちらもより小さな指数とより小さな法を使用するからです。

RSA暗号システムのセキュリティは、大きな数の素因数分解の問題とRSA問題という2つの数学的問題に基づいています。これらの問題はどちらも難しい、つまり効率的なアルゴリズムが存在しないという仮定の下では、RSA暗号文の完全な復号は不可能だと考えられています。部分的な復号に対するセキュリティを提供するには、安全なパディング方式を追加する必要があるかもしれません。^{[ 45 ]}

RSA問題は、合成数nを法とするe乗根を取るタスクとして定義されます。つまり、 c ≡ m ^e (mod n )となる値mを復元することです。ここで、( n , e )はRSA公開鍵、cはRSA暗号文です。現在、RSA問題を解決する最も有望なアプローチは、法nを素因数分解することです。素因数を復元できる能力があれば、攻撃者は公開鍵( n , e )から秘密指数dを計算し、標準的な手順でcを復号できます。これを実現するために、攻撃者はnをpとqに因数分解し、eからdを決定できるlcm( p -1, q -1)を計算します。古典コンピュータで大きな整数を因数分解する多項式時間の方法はまだ見つかっていませんが、存在しないことは証明されていません。この問題については、整数因数分解を参照してください。

1999年に行われた最初のRSA-512素因数分解では、数百台のコンピュータが使用され、約7か月かけて8,400 MIPS年相当の処理能力が必要でした。^{[ 46 ]} 2009年までに、ベンジャミン・ムーディは、公開ソフトウェア（GGNFS）とデスクトップコンピュータ（ 1,900 MHz CPUを搭載したデュアルコアAthlon64 ）のみを使用して、73日で512ビットRSA鍵を素因数分解できるようになりました。必要なディスクストレージは5ギガバイト弱、篩分け処理には 約2.5ギガバイトのRAMが必要でした。 

Rivest、Shamir、およびAdlemanは^{[ 3 ]} 、拡張リーマン予想が正しいと仮定すると、 nとeからdを見つけることは、nをpとqに因数分解することと同じくらい難しい（多項式時間の差を除いて）ことをMillerが示したと指摘した^{[ 47 ]} 。しかし、Rivest、Shamir、およびAdlemanは、論文のセクションIX/Dで、RSAの反転が因数分解と同じくらい難しいという証明は見つかっていないと指摘した。

2020年現在これまで一般に知られている最大の因数分解されたRSA 数は829 ビット (10 進数で 250 桁、RSA-250 ) でした。^{[ 48 ]}最先端の分散実装による因数分解には、約 2,700 CPU 年かかりました。実際には、RSA キーは通常 1024 ビットから 4096 ビットの長さです。2003 年にRSA Security は、 1024 ビットのキーは 2010 年までに解読可能になる可能性が高いと推定しました。 ^{[ 49 ]} 2020 年現在、そのようなキーが解読可能かどうかはわかりませんが、最低限の推奨事項は少なくとも 2048 ビットに変わりました。^{[ 50 ]}量子コンピューティング以外では、 nが十分に大きい場合、RSA は安全であると一般的に考えられています。

nが 300ビット以下であれば、既に無料で入手可能なソフトウェアを使用して、パーソナル コンピュータで数時間で因数分解できます。512 ビットの鍵は、数百台のコンピュータを使用してRSA-155 が因数分解された1999 年に、事実上解読可能であることが示されており、現在では一般的なハードウェアを使用して数週間で因数分解できます。因数分解された可能性のある 512 ビットのコード署名証明書を使用したエクスプロイトが 2011 年に報告されました。^{[ 51 ]} 2003 年に Shamir と Tromer によって記述されたTWIRLと呼ばれる理論上のハードウェア デバイスは、1024 ビットの鍵のセキュリティに疑問を投げかけました。^{[ 49 ]}  

1994年、ピーター・ショアは、量子コンピュータが（もし実用的に作られるならば）多項式時間で因数分解を行い、RSA暗号を破ることができることを示した。ショアのアルゴリズムを参照のこと。

大きな素数pとqを見つけるには、通常、適切なサイズの乱数を確率的な素数判定法でテストし、素数でない数をほぼすべて迅速に排除する方法が用いられる。

nのフェルマー因数分解が成功しないよう、 pとq の数は「近すぎない」必要があります。p − qが2 n ^1/4 ( n = p ⋅ q )より小さい場合、 nの値が「小さい」 1024 ビットであっても、3 × 10 ⁷⁷ ) の場合、 pとqを求めるのは簡単です。さらに、p − 1またはq − 1のいずれかが小さな素因数しか持たない場合、n はPollard のp − 1 アルゴリズムによって素早く因数分解できるため、そのようなpまたはqの値は破棄する必要があります。

プライベート指数dが十分に大きいことが重要です。Michael J. Wiener は、pがqと2qの間(これは非常に一般的です) でd < n ^1/4 /3の場合、d はnとeから効率的に計算できることを示しました。^{[ 52 ]} 

適切なパディングが使用されている限り、e = 3のような小さな公開指数に対する既知の攻撃はありません。Coppersmithの攻撃は、特に公開指数eが小さく、暗号化されたメッセージが短くパディングされていない場合に、 RSA を攻撃する際に多くの用途があります。65537は、 eによく使用される値です。この値は、潜在的な小さな指数攻撃を回避することと、効率的な暗号化 (または署名検証) を可能にすることの間の妥協点とみなすことができます。NIST のコンピュータ セキュリティに関する特別刊行物 (SP 800-78 Rev. 1、2007 年 8 月) では、65537 より小さい公開指数eは許可されていませんが、この制限の理由は述べられていません。   

2017年10月、マサリク大学の研究者チームがROCA脆弱性を発表しました。この脆弱性は、インフィニオンのRSALibライブラリに組み込まれたアルゴリズムによって生成されたRSA鍵に影響を与えます。多数のスマートカードとトラステッドプラットフォームモジュール（TPM）が影響を受けることが示されています。脆弱なRSA鍵は、チームが公開したテストプログラムを使用して簡単に特定できます。^{[ 53 ]}

暗号学的に強力な乱数発生器を使用し、適切なエントロピーでシードを設定して、素数pとqを生成する必要があります。インターネットから収集した数百万の公開鍵を比較する分析が、2012 年初頭にArjen K.  Lenstra、James P.  Hughes、Maxime Augier、Joppe W.  Bos、Thorsten Kleinjung、Christophe Wachter によって実施されました。彼らは、ユークリッドのアルゴリズムのみを使用して、鍵の 0.2% を素因数分解することができました。^{[ 54 ] [ 55 ]}

彼らは、整数因数分解に基づく暗号システムに特有の弱点を悪用した。n = pqが一方の公開鍵で、n ′ = p ′ q ′がもう一方の公開鍵である場合、偶然p = p ′（ただしq はq ′と等しくない）であれば、 gcd( n , n ′) = pという単純な計算でnとn ′ の両方を因数分解でき、両方の鍵が完全に危険にさらされる。Lenstra らは、この問題は、意図したセキュリティレベルの 2 倍のビット長を持つ強力な乱数シードを使用するか、 pとqを独立して選択する代わりに、pが与えられた場合にq を選択する決定論的な関数を使用することで最小限に抑えることができると指摘している。

ナディア・ヘニンガーは、同様の実験を行ったグループの一員でした。彼らは、ダニエル・J・バーンスタインのアイデアを用いて、各RSA鍵nと、彼らが発見した他のすべての鍵n 'の積（7億2900万桁の数）との最大公約数を計算しました。これは、各gcd( n , n ')を個別に計算する代わりに、大きな除算を1回行った後、最大公約数の問題が通常のサイズになるため、非常に大幅な高速化を実現しました。

ヘニンガー氏は自身のブログで、不正なキーはほぼすべて組み込みアプリケーションで発生しており、30社以上のメーカーの「ファイアウォール、ルーター、VPNデバイス、リモートサーバー管理デバイス、プリンター、プロジェクター、VOIP電話」などが含まれると述べている。ヘニンガー氏は、2つのグループによって発見された1つの共有素数問題は、擬似乱数発生器の初期シードが不適切で、最初の素数と2番目の素数の生成の間に再シードされる状況から生じると説明している。キーストロークのタイミング、電子ダイオードノイズ、または局間で同調したラジオ受信機からの大気ノイズから得られる十分に高いエントロピーのシードを使用すれば、問題は解決するはずだ。^{[ 56 ]}

強力な乱数生成は、公開鍵暗号のあらゆる段階において重要です。例えば、RSAによって配布される共通鍵に弱い乱数生成器が使用されている場合、盗聴者はRSAを迂回して共通鍵を直接推測できてしまう可能性があります。

コッハーは1995年にRSAに対する新たな攻撃を説明した。攻撃者イブがアリスのハードウェアを十分に詳細に知っており、既知のいくつかの暗号文の復号時間を測定できる場合、イブは復号鍵dを迅速に推測できる。この攻撃はRSA署名方式にも適用できる。2003年、ボーンとブラムリーは、ネットワーク接続（例えば、セキュアソケットレイヤー（SSL）対応のウェブサーバーから）を介してRSA因数分解を復元できる、より実用的な攻撃を実証した。^{[ 57 ]}この攻撃は、多くのRSA実装で使用されている中国剰余定理最適化によって漏洩した情報を利用する。

これらの攻撃を防ぐ一つの方法は、復号処理にかかる時間をすべての暗号文に対して一定に保つことです。しかし、この方法ではパフォーマンスが著しく低下する可能性があります。そのため、ほとんどのRSA実装では、暗号学的ブラインディングと呼ばれる別の手法が用いられています。RSAブラインディングは、RSAの乗法特性を利用します。アリスは、 c ^d (mod n )を計算する代わりに、まず秘密の乱数 r を選択し、 ( r e c ) d (mod n ) を計算します。この^計算結果は^、オイラーの定理を適用するとrc d ⁽ mod n )となり、 rの影響は逆数を乗じることで除去できます。各暗号文に対して、新しい r の値が選択されます。ブラインディングを適用すると、復号時間は入力暗号文の値と相関しなくなるため、タイミング攻撃は失敗します。

1998年、ダニエル・ブライヒェンバッハーは、PKCS #  1  v1パディング方式（パディング方式はRSA暗号化されたメッセージをランダム化して構造を追加することで、復号されたメッセージが有効かどうかを判定できるようにする）を用いたRSA暗号化メッセージに対する、最初の実用的な適応型選択暗号文攻撃について記述した。PKCS #1方式の欠陥により、ブライヒェンバッハーはSecure Sockets Layer プロトコルのRSA実装に対して実用的な攻撃を仕掛け、セッションキーを復元することができた。この研究の結果、暗号学者は現在、Optimal Asymmetric Encryption Paddingなどの証明可能な安全性を持つパディング方式の使用を推奨しており、RSA Laboratoriesはこれらの攻撃に対して脆弱でないPKCS #1の新しいバージョンをリリースしている。 

この攻撃の亜種である「BERserk」は2014年に再び出現した。^{[ 58 ] [ 59 ]}これは、特にFirefoxとChromeで使用されていたMozilla NSS Crypto Libraryに影響を与えた。

分岐予測解析（BPA）を用いたサイドチャネル攻撃について説明しました。多くのプロセッサは、プログラムの命令フローにおける条件分岐が実行される可能性が高いかどうかを判断するために分岐予測器を使用します。これらのプロセッサは、多くの場合、同時マルチスレッド処理（SMT）も実装しています。分岐予測解析攻撃は、スパイプロセスを使用して、これらのプロセッサで処理される際に（統計的に）秘密鍵を発見します。

単純分岐予測分析（SBPA）は、非統計的な方法でBPAを改善すると主張している。SBPAの著者（Onur AciicmezとCetin Kaya Koc）は、論文「単純分岐予測分析の力について」 ^{[ 60 ]} の中で、 10回の反復でRSA鍵の512ビットのうち508ビットを発見したと主張している。

RSA実装に対する電源障害攻撃は2010年に報告された。^{[ 61 ]}著者はCPU電源電圧を制限範囲外に変化させることで鍵を復元した。これによりサーバー上で複数の電源障害が発生した。

CRTの実装はフォールトインジェクション攻撃に対して脆弱である。攻撃者が1つの不正な署名を入手できれば、秘密鍵を計算できる。^{[ 62 ]}

RSAを安全に実装するには、多くの詳細事項（強力な擬似乱数生成器、許容可能な公開指数など）を考慮する必要があります。そのため、実装は困難であり、書籍「Practical Cryptography With Go」では、可能であればRSAの使用を避けることを推奨しています。^{[ 63 ]}