RSA（暗号システム）

RSA (リベスト・シャミール・エーデルマン) は公開鍵暗号システムであり、安全なデータ送信に広く使用されている最も古いシステムの 1 つです。頭文字の「RSA」は、1977 年にアルゴリズムを公開したロン・リベスト、アディ・シャミール、レナード・エーデルマンの姓に由来しています。同等のシステムは、1973 年にイギリスの数学者クリフォード・コックスによってイギリスの信号諜報機関である政府通信本部(GCHQ)で秘密裏に開発されました。このシステムは1997 年に機密解除されました。 ^[2]

公開鍵暗号システムでは、暗号化鍵は公開されており、復号化鍵は秘密（非公開）に保持されます。RSAユーザーは、2つの大きな素数と補助値に基づいて公開鍵を作成し、公開します。素数は秘密に保持されます。メッセージは公開鍵を介して誰でも暗号化できますが、復号化できるのは秘密鍵を知っている人だけです。^[1]

RSA のセキュリティは、 2 つの大きな素数の積を因数分解する実際的な難しさ、つまり「因数分解問題」に依存しています。RSA 暗号化を解読することはRSA 問題として知られています。これが因数分解問題と同じくらい難しいかどうかは未解決の問題です。^[3]十分に大きなキーが使用されている場合、システムを無効にする方法は公開されていません。

RSA は比較的遅いアルゴリズムです。このため、ユーザー データを直接暗号化するためには一般的に使用されません。RSA は、多くの場合、対称キー暗号化の共有キーを送信するために使用され、その後、一括暗号化と復号化に使用されます。

非対称公開鍵暗号システムのアイデアは、 1976年にこの概念を発表したホイットフィールド・ディフィーとマーティン・ヘルマンに帰せられる。彼らはまた、デジタル署名を導入し、数論の応用を試みた。彼らの定式化では、素数を法として、ある数の累乗から作成された共有秘密鍵を使用した。しかし、一方向性関数を実現するという問題は未解決のままであった。これはおそらく、当時は因数分解の難しさが十分に研究されていなかったためである。^{[4]さらに、}ディフィー・ヘルマンと同様に、RSAは剰余累乗に基づいている。

マサチューセッツ工科大学のロン・リベスト、アディ・シャミア、レナード・エイドルマンは、逆関数を作るのが困難な関数を作るために、1年かけて何度も試みた。リベストとシャミアはコンピュータ科学者として、多くの潜在的な関数を提案し、エイドルマンは数学者として、それらの弱点を見つける責任を負った。彼らは、「ナップザックベース」や「順列多項式」など、多くのアプローチを試した。しばらくの間、彼らは、矛盾した要件のために、自分たちが達成したいことは不可能だと考えていた。^[5] 1977年4月、彼らは過越祭を学生の家で過ごし、大量のワインを飲んでから、真夜中頃に帰宅した。^[6]眠れなかったリベストは、数学の教科書を持ってソファに横になり、一方向性関数について考え始めた。彼は残りの夜を自分のアイデアを形式化することに費やし、夜明けまでに論文の大部分を完成させた。このアルゴリズムは現在RSAとして知られています。これは彼らの姓の頭文字を論文と同じ順序で並べたものです。^[7]

イギリスの諜報機関政府通信本部（GCHQ）に勤務していたイギリスの数学者クリフォード・コックスも、1973年に内部文書で同様のシステムについて説明している。^[8]しかし、当時はそれを実装するために比較的高価なコンピュータが必要だったため、ほとんど好奇心の対象とみなされ、公に知られている限りでは、実際に導入されることはなかった。彼のアイデアとコンセプトは、極秘扱いだったため、1997年まで明らかにされなかった。

Kid-RSA (KRSA) は、1997 年に公開された、教育目的で設計された簡略化された安全でない公開鍵暗号です。Kid-RSA を学ぶことで、簡略化された DESに類似した RSA やその他の公開鍵暗号についての理解が深まると考える人もいます。^{[9] [10] [11] [12] [13]}

RSA アルゴリズムを記述した特許が 1983 年 9 月 20 日に MIT に付与されました:米国特許4,405,829 「暗号化通信システムおよび方法」。DWPIの特許概要 から引用:

このシステムには、エンコード装置を備えた少なくとも 1 つの端末と、デコード装置を備えた少なくとも 1 つの端末に接続された通信チャネルが含まれます。転送されるメッセージは、エンコード端末で、所定のセット内の数値 M としてエンコードすることにより、暗号文に暗号化されます。次に、その数値は、最初の所定の累乗 (意図された受信者に関連付けられている) で累乗され、最終的に計算されます。剰余または残余 C は、累乗された数値を、2 つの所定の素数 (意図された受信者に関連付けられている) の積で割ったときに計算されます。

このアルゴリズムの詳細な説明は、1977年8月にサイエンティフィック・アメリカン誌の「数学ゲーム」欄に掲載されました。^[7]これは、1977年12月の特許出願日より前のことでした。その結果、この特許は米国外で法的効力を持ちませんでした。コックスの研究が公に知られていた場合、米国での特許も合法ではなかったでしょう。

特許が発行されたとき、特許期間は17年でした。特許は2000年9月21日に期限切れになる予定でしたが、RSA Securityは2000年9月6日にアルゴリズムをパブリックドメインにリリースしました。^[14]

RSA アルゴリズムには、キー生成、キー配布、暗号化、復号化の 4 つのステップが含まれます。

RSA の基本的な原理は、すべての整数 m ( 0 ≤ m < n ) について、 と を で割ったときの余りが同じになる ( を法として合同である) ような 3 つの非常に大きな正の整数 e、d 、 nを見つけることが現実的であるという観察です。ただし、eとnだけが与えられた場合、dを見つけることは非常に困難です。 ${\displaystyle (m^{e})^{d}}$${\displaystyle m}$${\displaystyle n}$ ${\displaystyle n}$$${\displaystyle (m^{e})^{d}\equiv m{\pmod {n}}.}$$

整数nとe は公開鍵、d は秘密鍵、m はメッセージを表します。eとdのモジュラー指数は、それぞれ暗号化と復号化に対応します。

さらに、2 つの指数を交換できるため、秘密鍵と公開鍵も交換でき、同じアルゴリズムを使用して メッセージの署名と検証が可能になります。

RSA アルゴリズムのキーは次のように生成されます。

1. 2 つの大きな素数 pとq を選択します。
   • 因数分解を難しくするには、pとqをランダムに選択し、両方とも大きく、大きな差を持つようにする必要があります。^[1]これらを選択するための標準的な方法は、ランダムな整数を選択し、2つの素数が見つかるまで素数判定を使用することです。
   • 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はユークリッドの互除法によって計算できる。なぜならlcm( a ,  b ) = ⁠|アブ|/gcd( a ,  b ) は、⁠ .
   • λ ( n )は秘密にされます。
4. 1 < e < λ ( n )かつgcd ( e , λ ( n )) = 1となるような整数eを選択します。つまり、eとλ ( n )は互いに素です。
   • eのビット長が短く、ハミング重みが小さいと、暗号化の効率が上がります。eに最もよく選ばれる値は2 ¹⁶ + 1 =です。65 537。eの最小値（かつ最速値）は3であるが、 eの値がこのように小さいと、設定によっては安全性が低下することが分かっている。 ^[15]
   • e は公開鍵の一部として公開されます。
5. dをd≡e − 1 ⁽ modλ ( n ) )と決定する。つまり、dはλ ( n )を法としたeのモジュラー逆数である。
   • これは、方程式de ≡ 1 (mod λ ( n ))を dについて解くことを意味します。eとλ ( n ) は互いに素であるため、この方程式はベズーの恒等式 （ dは係数の 1 つ）の形式であるため、拡張ユークリッド互除法を使用してdを効率的に計算できます。
   • d は秘密鍵指数として秘密に保持されます。

公開鍵は係数nと公開（または暗号化）指数eから構成されます。秘密鍵は秘密（または復号）指数dから構成され、秘密にしておく必要があります。p、q、およびλ ( n )もd の計算に使用できるため秘密にしておく必要があります。実際、dが計算された後、これらはすべて破棄できます。^[16]

オリジナルの RSA 論文^[1]では、秘密指数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 )を法として縮小され、より小さい同等の指数が得られます。

( p − 1)と( q − 1)の共通因数はn − 1 = pq − 1 = ( p − 1)( q − 1) + ( p − 1) + ( q − 1)の因数分解に存在するため、^{[17] [自費出版ソース? ] 、} ( p − 1)と( q − 1)には必要な 2 以外に非常に小さな共通因数しか存在しないことが推奨されます。^{[1] [18] [19] [検証失敗] [20] [検証失敗]}

注: オリジナルの RSA 論文の著者は、d を選択し、dを法とするφ ( n )のモジュラー逆数としてe を計算することで鍵生成を行っていますが、 PKCS#1に従うものなど、現在の RSA 実装のほとんどは逆を行っています ( e を選択してd を計算)。選択された鍵は小さくなる可能性があるのに対し、計算された鍵は通常小さくないため、RSA 論文のアルゴリズムは暗号化と比較して復号化を最適化しますが、現代のアルゴリズムは代わりに暗号化を最適化します。^{[1] [21]}

Bob がAliceに情報を送信したいとします。RSA を使用する場合、Bob はメッセージを暗号化するために Alice の公開鍵を知る必要があり、Alice はメッセージを復号化するために自分の秘密鍵を使用する必要があります。

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

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

それを実行するために、彼はまず、合意された可逆プロトコルであるパディング方式を使用して、M （厳密に言えば、パディングされていない平文）を0 ≤ m < nとなる整数m（厳密に言えば、パディングされた平文）に変換する。次に、アリスの公開鍵eを使用して、次の式に対応する 暗号文cを計算する。

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

これは、非常に大きな数であっても、モジュラー指数法を使用してかなり速く行うことができます。次に、ボブはc をアリスに送信します。少なくとも 9 つのmの値がmに等しい 暗号文c を生成することに注意してください^[a]。ただし、これは実際にはほとんど発生しません。

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

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

mが与えられれば、パディング方式を逆にすることで 元のメッセージM を復元できます。

RSA暗号化と復号化の例を次に示します。^[b]

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. 780 と互いに素である2 < e < 780の任意の数を選択します。eに素数を選択すると、eが780 の約数ではない ことを確認するだけです。

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

5. e (mod λ ( n ))のモジュラー逆数d を計算すると、次のようになる。
   $${\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{整列}}}$$

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}}}$$

アリスがボブの公開鍵を使用して暗号化されたメッセージをボブに送信するとします。メッセージではアリスが自分はアリスだと主張しますが、ボブの公開鍵を使用して暗号化されたメッセージをボブに送信することは誰でも可能なので、ボブにはメッセージがアリスからのものであることを確認する方法がありません。メッセージの送信元を確認するために、RSA を使用してメッセージ に署名することもできます。

アリスがボブに署名付きメッセージを送信したいとします。アリスは自分の秘密鍵を使用してこれを行うことができます。アリスはメッセージのハッシュ値を生成し、それをd (モジュロn ) 乗して (メッセージを復号化するときと同じように)、それをメッセージに「署名」として添付します。ボブは署名付きメッセージを受信すると、同じハッシュ アルゴリズムをアリスの公開鍵と組み合わせて使用​​します。ボブは署名をe (モジュロn ) 乗して (メッセージを暗号化するときと同じように)、結果のハッシュ値をメッセージのハッシュ値と比較します。両者が一致すれば、ボブはメッセージの作成者がアリスの秘密鍵を所有しており、メッセージが送信されてから改ざんされていないことがわかります。

これは指数規則により機能します: $${\displaystyle h=\operatorname {hash} (m),}$$ $${\displaystyle (h^{e})^{d}=h^{ed}=h^{de}=(h^{d})^{e}\equiv h{\pmod {n}}.}$$

したがって、一般性を失うことなくキーを交換できます。つまり、キー ペアの秘密キーは次のいずれかの目的で使用できます。

1. 受信者のみに向けたメッセージを復号化します。このメッセージは公開鍵を持つ人なら誰でも暗号化できます (非対称暗号化トランスポート)。
2. 誰でも復号化できるが、暗号化できるのは 1 人だけというメッセージを暗号化します。これによりデジタル署名が提供されます。

RSA の正しさの証明はフェルマーの小定理に基づいており、任意の整数aと素数pに対してa ^{p − 1} ≡ 1 (mod p )であり、 a を割り切れないことを述べています。^{[注 1]}

pとq が異なる素数であり、eとd がed ≡ 1 (mod λ ( pq ))を満たす正の整数であるとき、 任意の整数mに対して次のことを示します 。 $${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}$$

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

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 \not \equiv}$の場合、

   ${\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 \not \equiv}$の場合、

   ${\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が異なる場合、中国剰余定理によって元の平文メッセージを簡単に復号化できます。ヨハン・ハスタッドは、平文が等しくなくても、攻撃者がそれらの間の線形関係を知っていてもこの攻撃が可能であることに注目しました。^{[22]この攻撃は後に}ドン・コッパースミスによって改良されました（コッパースミスの攻撃を参照）。^[23]
• RSA 暗号は決定論的暗号化アルゴリズム(ランダム要素がない) であるため、攻撃者は公開鍵で平文を暗号化し、暗号文と等しいかどうかをテストすることで、暗号システムに対して選択平文攻撃を成功させることができます。攻撃者が対応する平文を知っている (または選択した) 場合でも、攻撃者が 2 つの暗号化を区別できない場合、暗号システムは意味的に安全であると呼ばれます。パディングのない RSA は意味的に安全ではありません。^[24]
• 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 ) を知ることができ、そこからrのモジュラー逆数をmrに乗じてメッセージm を導き出すことができます。^[要出典]
• 秘密指数dが与えられれば、法n = pqを効率的に因数分解することができる。また、法n = pqの因数分解が与えられれば、公開鍵（e '、  n ）に対して生成された任意の秘密鍵（d '、  n ）を得ることができる。^[15]

これらの問題を回避するために、実際の RSA 実装では通常、値mを暗号化する前に、何らかの構造化されたランダムなパディングを値mに埋め込みます。このパディングにより、 m が安全でないプレーンテキストの範囲に入らないことが保証され、パディングされた特定のメッセージは、多数の異なる暗号文の 1 つに暗号化されます。

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

RSA-PSS などの安全なパディング方式は、メッセージの暗号化と同様に、メッセージ署名のセキュリティにも不可欠です。 PSS に関する 2 つの米国特許が付与されました (米国特許 6,266,771および米国特許 7,036,014 )。ただし、これらの特許はそれぞれ 2009 年 7 月 24 日と 2010 年 4 月 25 日に失効しました。PSS の使用はもはや特許によって妨げられることはないようです。^{[独自の研究? ]}暗号化と署名に異なる RSA キー ペアを使用すると、より安全になる可能性があります。^[26]

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

• ${\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 )を次のようにより効率的に計算できます： 、、、 ^[c]。
     ${\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}}}$
     ${\displaystyle m=m_{2}+hq}$

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

RSA暗号システムのセキュリティは、2つの数学的問題、すなわち大きな数の因数分解問題とRSA問題に基づいています。これらの問題は両方とも困難であり、つまり、それらを解決するための効率的なアルゴリズムが存在しないという仮定の下で、RSA暗号文の完全な復号化は実行不可能であると考えられています。部分的な復号化に対するセキュリティを提供するには、安全なパディングスキームの追加が必要になる場合があります。^[28]

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)を計算します。古典的コンピュータで大きな整数を因数分解する多項式時間の方法はまだ見つかっていませんが、存在しないことが証明されていません。この問題については、 整数の因数分解を参照してください。

多重多項式二次ふるい (MPQS) を使用して、公開係数n を因数分解できます。

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

リベスト、シャミール、アデルマンは^{[1] 、ミラーが}拡張リーマン予想が正しいと仮定すると、nとeからdを見つけることは、 nをpとqに因数分解するのと同じくらい難しいことを示したと指摘した（多項式時間差まで）。^[30]しかし、リベスト、シャミール、アデルマンは、論文のセクションIX/Dで、RSAの逆行列を求めることが因数分解と同じくらい難しいという証明を見つけていないと指摘した。

2020年現在^[update]、公に知られている最大のRSA因数分解数は829ビット（250桁の10進数、RSA-250）である。^[31]最先端の分散実装によるその因数分解には、約2,700CPU年を要した。実際には、RSAキーの長さは通常1024〜4096ビットである。2003年、RSA Securityは、1024ビットのキーは2010年までに解読可能になる可能性が高いと推定した。^[32] 2020年現在、そのようなキーが解読可能かどうかは不明であるが、最小推奨事項は少なくとも2048ビットに変更されている。^{[33]量子コンピューティング以外では、} nが十分に大きい 場合、RSAは安全であると一般に推定されている。

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

1994 年、ピーター・ショアは、量子コンピュータが実際にその目的で作成されれば、多項式時間で因数分解が可能になり、RSA を破ることができることを示しました。ショアのアルゴリズムを参照してください。

大きな素数pとq を見つけるには、通常、確率的素数判定テストを使用して正しいサイズの乱数をテストし、事実上すべての非素数を素早く排除します。

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

秘密指数dが十分に大きいことが重要です。マイケル・J・ウィーナーは、 pがqと2qの間（これは非常に典型的）でd < n ^1/4 /3の場合、dはnと eから効率的に計算できることを示しました。^[35]

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

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

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

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

ナディア・ヘニンガーは、同様の実験を行ったグループの一員でした。彼らは、ダニエル・J・バーンスタインのアイデアを使用して、各 gcd( n , n ′)を個別に計算するのではなく、各 RSA キーnと、発見した他のすべてのキーn ' の積 (7 億 2,900 万桁の数字) に対するGCD を計算しました。これにより、1 回の大きな除算の後、GCD 問題は通常のサイズになるため、大幅なスピードアップが実現しました。

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

強力な乱数生成は、公開鍵暗号化のあらゆる段階において重要です。たとえば、RSA によって配布されている対称鍵に弱いジェネレータが使用されている場合、盗聴者は RSA をバイパスして対称鍵を直接推測することができます。

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

これらの攻撃を阻止する 1 つの方法は、暗号文ごとに復号化操作に一定の時間がかかるようにすることです。ただし、このアプローチではパフォーマンスが大幅に低下する可能性があります。代わりに、ほとんどの RSA 実装では、暗号ブラインド化と呼ばれる代替手法が使用されています。RSA ブラインド化では、RSA の乗法特性を利用します。c ^d (mod n )を計算する代わりに、アリスは最初に秘密のランダム値r を選択し、( r ^e c ) ^d (mod n )を計算します。オイラーの定理を適用した後のこの計算の結果はrc d ⁽ mod n )なので、rの影響はその逆数を乗算することで除去できます。各暗号文に対してrの新しい値が選択されます。ブラインド化を適用すると、復号化時間は入力暗号文の値と相関しなくなり、タイミング攻撃は失敗します。

1998 年、Daniel Bleichenbacher は、 PKCS #1 v1パディング スキーム(パディング スキームは RSA 暗号化メッセージをランダム化して構造を追加するため、復号化されたメッセージが有効かどうかを判断できる) を使用した、RSA 暗号化メッセージに対する最初の実用的な適応型選択暗号文攻撃を説明しました。PKCS #1 スキームの欠陥により、Bleichenbacher はSecure Sockets Layerプロトコルの RSA 実装に対して実用的な攻撃を仕掛け、セッション キーを復元することができました。この研究の結果、暗号学者は現在、最適非対称暗号化パディングなどの証明可能なセキュリティ パディング スキームの使用を推奨しており、RSA 研究所はこれらの攻撃に対して脆弱ではない PKCS #1 の新しいバージョンをリリースしました。

この攻撃の亜種である「BERserk」は2014年に再び現れました。^{[41] [42]}これは、FirefoxとChromeで特に使用されていたMozilla NSS暗号ライブラリに影響を与えました。

分岐予測分析 (BPA) を使用したサイドチャネル攻撃について説明しました。多くのプロセッサは、プログラムの命令フローで条件分岐が行われるかどうかを判断するために分岐予測を使用します。多くの場合、これらのプロセッサは同時マルチスレッド(SMT) も実装しています。分岐予測分析攻撃は、これらのプロセッサで処理されるときにスパイ プロセスを使用して (統計的に) 秘密キーを検出します。

シンプル分岐予測分析 (SBPA) は、非統計的な方法で BPA を改善すると主張しています。論文「シンプル分岐予測分析の威力について」^[43]で、 SBPA の著者 (Onur Aciicmez と Cetin Kaya Koc) は、10 回の反復で RSA キーの 512 ビットのうち 508 ビットを発見したと主張しています。

RSA実装に対する電源障害攻撃は2010年に説明されました。^[44]作者はCPU電源電圧を制限外に変化させることで鍵を回復しましたが、これによりサーバー上で複数の電源障害が発生しました。

RSAを安全に実装するためには、多くの詳細事項（強力なPRNG、許容可能な公開指数など）を念頭に置く必要があります。このため実装は困難であり、書籍「Practical Cryptography With Go」では、可能であればRSAを避けることを推奨しています。^[45]

RSA をサポートする暗号化ライブラリには次のようなものがあります。

• ぼたん
• バウンシーキャッスル
• クリプトライブラリ
• 暗号++
• ライブラリgcrypt
• イラクサ
• オープンSSL
• ウルフクリプト
• TLS の
• mbed TLS
• リブレSSL

• 音響暗号解読
• 計算複雑性理論
• ディフィー・ヘルマン鍵交換
• デジタル署名アルゴリズム
• 楕円曲線暗号
• 鍵交換
• キー管理
• キーサイズ
• 公開鍵暗号
• ラビン暗号システム
• トラップドア機能