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

RSAは、 RSASSA-PSSやRSA-FDHなどのデジタル署名、[5] [6] [7] [ 8] [9] [10]、RSAES-OAEPなどの非常に短いメッセージの公開鍵暗号化（ハイブリッド暗号システムではほとんどの場合、1回限りの対称鍵） 、[11] [12] [13] [10 ] 、および公開鍵カプセル化に使用されます。[14] [15] [16]

RSAベースの暗号では、ユーザーの秘密鍵（メッセージに署名したり、そのユーザーに送信されたメッセージを復号したりするために使用できます）は、ランダムに選択され、秘密に保持される大きな素数のペアです。ユーザーの公開鍵（ユーザーからのメッセージを検証したり、そのユーザーだけが復号できるようにメッセージを暗号化したりするために使用できます）は、素数の積です。

RSA暗号の安全性は、2つの大きな素数の積を因数分解することの難しさ、すなわち「因数分解問題」に関連しています。RSA暗号の解読はRSA問題として知られています。RSA問題が因数分解問題と同じくらい難しいかどうかは未解決の問題です。[17]十分に大きな鍵を用いた場合、このシステムを破る方法は公開されていません。

歴史

RSA の共同発明者であるアディ・シャミール(他の 2 人はロン・リベストとレナード・アドルマン)

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

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

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

Kid-RSA（KRSA）は、1997年に公開された、教育目的で設計された簡略化された安全性の低い公開鍵暗号です。Kid-RSAは、簡略化されたDESに類似したRSAやその他の公開鍵暗号についての理解を深めるのに役立ちます。[23] [24] [25] [26] [27]

特許

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

このシステムは、符号化装置を備えた少なくとも1つの端末と、復号装置を備えた少なくとも1つの端末に接続された通信チャネルを含む。転送されるメッセージは、符号化端末において、所定の集合内の数値Mとして符号化されることにより、暗号文に暗号化される。次に、この数値は、（意図された受信者に関連付けられた）最初の所定の累乗で累乗され、最終的に計算される。剰余Cは、累乗された数値を、（意図された受信者に関連付けられた）2つの所定の素数の積で割ることによって計算される。

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

特許が発行された時点で、特許期間は17年でした。特許は2000年9月21日に失効する予定でしたが、RSAセキュリティ社は2000年9月6日にこのアルゴリズムをパブリックドメインとして公開しました。[28]

手術

RSA アルゴリズムには、キー生成、キー配布、公開キー操作 (暗号化または署名の検証に使用)、秘密キー操作 (メッセージの復号化または署名に使用) の 4 つのステップが含まれます。

RSA の背後にある基本原理は、すべての整数 x ( 0 ≤ x < n )について、( x e ) dとxの両方をnで割ったときの余りが同じになる(これらはnを法として合同である)ような 3 つの非常に大きな正の整数e、d、 n を見つけることが実際的であるという観察です。ただし、eとnだけが与えられた場合、 nを法としてe番目の根を計算することは実行不可能です。つまり、均一ランダムy ( 0 ≤ y < n ) の場合、 x e ≡ y (mod n )となるx を見つけることは非常に困難です。

整数nとeは公開鍵を構成し、dは秘密鍵です。eのべき乗の剰余は暗号化と署名の検証に使用され、dのべき乗の剰余は復号化とメッセージの署名に使用されます。

鍵生成

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

  1. 2 つの大きな素数 pとqを選択します。
    • 因数分解を不可能にするには、pとqを2の10乗の2乗から2の10乗までの素数（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はユークリッドの互除法で計算できる。なぜならlcm( a ,  b ) = ⁠|アブ|/gcd( a ,  b )⁠。
    • λ ( n )は秘密にされます。
  4. 1 < e < λ ( n )かつgcd ( e , λ ( n )) = 1となるような整数eを選択します。つまり、eとλ ( n )は互いに素です。
    • eのビット長が短く、ハミング重みが小さいと、より効率的な暗号化が可能になります。eに最もよく選ばれる値は2 16 + 1 =65 537 。eの最小値（かつ最速値）は3であるが、 eがこのように小さいと、安全でないパディング方式の脆弱性が露呈する可能性がある。 [30] [a]
    • 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の計算後はこれらはすべて破棄することができる。[ 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をdのモジュラー逆数（ φ ( n )を法とする）として計算することで鍵生成を行っています。一方、PKCS#1に準拠したRSAの実装のほとんどは、その逆、つまりeを選択し、そこからdを計算しています。eは小さく固定した値で安全に使用できるのに対し、dは攻撃に耐えられるほど十分に大きな空間から選択する必要があるため、この現代的なアプローチは、セキュリティを損なうことなく公開鍵演算のコストを削減できます。[3] [32]

鍵配布

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

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

暗号化

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

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

これは、非常に大きな数であっても、モジュラー指数法を用いることでかなり高速に実行できます。ボブはcをアリスに送信します。mの値が少なくとも9つあると、暗号文cはmと等しく なりますが[b]、実際にはこのような事態は起こりにくいことに注意してください。

復号化

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

mが与えられれば、パディング方式を逆にすることで元のメッセージMを復元できます。また、パディングが無効な場合は、破損しているものとして破棄することもできます。

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

例

以下はパディングの詳細を無視したRSA暗号化と復号化の例である。[c]

  1. 2つの異なる素数を選択します。
    そして。
  2. n = pqを計算すると
  3. λ ( n ) = lcm ( p − 1, q − 1)の積の カーマイケルのトーシェント関数を計算すると、
  4. 780 と互いに素である1 < e < 780の任意の数を選択します。eに素数を選択すると、e が 780 の約数ではない ことを確認することだけが残ります。
    させて。
  5. e (mod λ ( n ))のモジュラー逆数dを計算すると、次のようになる。

公開鍵は（n = 3233, e = 17）である。パディングされた平文メッセージmの場合、暗号化関数は

秘密鍵は（n = 3233, d = 413）である。暗号化された暗号文 cの場合、復号関数は

例えば、m = 65を暗号化するには、次のように計算する。

c = 2790を解読するには、次のように計算する。

これらの計算はどちらも、べき乗剰余の平方乗算アルゴリズムを用いて効率的に計算できます。現実の状況では、選択される素数ははるかに大きくなります。この例では、 （自由に利用可能な公開鍵から得られる） n = 3233を因数分解して素数pとqに戻すのは簡単です。次に、同じく公開鍵から得られるeを逆数に分解してdを取得し、秘密鍵を取得します。

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

秘密鍵の一部である 値d p、d q、q inv は次のように計算されます。

d p、d q、q inv を効率的な復号化に使用する方法を次に示します(適切なdとe のペアを選択すると暗号化が効率的になります)。

署名

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

検証中

ボブはメッセージmと署名sを受信すると、同じハッシュアルゴリズムとアリスの公開鍵を用いてh = hash( m )を計算します。署名s をe乗（nを法として）し、得られたハッシュ値をメッセージのハッシュ値と比較します。両者が一致すれば、メッセージの送信者はアリスの秘密鍵を所有しており、メッセージは送信後改ざんされていないことがわかります。

この式は、指数規則によりs = h d mod n のときに満たされます。

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

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

正しさの証明

フェルマーの小定理を用いた証明

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

pとqが異なる素数であり、eとdがed≡1 (modλ ( pq ) )を満たす正の整数であるとき 、すべての整数mに対して次のようになることを示します 。

λ ( pq ) = lcm ( p − 1, q − 1)は、構成上、p − 1と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 )の場合、
    ここでフェルマーの小定理を使って、 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 )の場合、

これにより、任意の整数mと整数e、dに対してed≡1 (modλ ( pq ) )が成り立つことが証明される。

注記

  1. ^ pq は素数ではないため、定理 (mod pq )を適用しても RSA を簡単に破ることはできません。
  2. ^ 特に、上記の記述は、 ed ≡ 1 (mod ( p − 1)( q − 1))を満たす任意のeとdに対して成り立ちます。なぜなら、 ( p − 1)( q − 1)はλ ( pq )で割り切れるため、当然のことながらp − 1とq − 1でも割り切れるからです。しかし、RSAの現代的な実装では、より弱いが十分な条件ed ≡ 1 (mod λ ( pq ))のみを満たす、縮小された秘密指数dを使用するのが一般的です。
  3. ^ これは中国剰余定理の一部ですが、その定理の重要な部分ではありません。

オイラーの定理を用いた証明

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と互いに素であると仮定すると、

ここで、最後から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に対する攻撃

以下に説明するように、プレーン RSA に対する攻撃は数多くあります。

  • 低い暗号化指数（例えばe = 3 ）と小さなmの値（つまりm < n 1/ e ）で暗号化する場合、 m eの結果は法nよりも小さくなります。この場合、暗号文のe乗根を整数で割ることで、暗号文は簡単に復号できます。
  • 同じ平文メッセージが暗号化されてe人以上の受信者に送信され、受信者が指数eは同じだがp、q、したがってnが異なる場合、中国剰余定理を用いて元の平文メッセージを簡単に復号化できます。ヨハン・ハスタッドは、平文が等しくなくても、攻撃者がそれらの間の線形関係を知っていても、この攻撃は可能であることに気づきました。[38]この攻撃は後にドン・コッパースミスによって改良されました（コッパースミスの攻撃を参照）。[39]
  • RSA暗号は決定論的な暗号アルゴリズム（つまり、ランダム要素を持たない）であるため、攻撃者は公開鍵を用いて平文を暗号化し、それらが暗号文と一致するかどうかをテストすることで、暗号システムに対して選択平文攻撃を仕掛けることができます。攻撃者が対応する平文を知っている（または選択した）場合でも、2つの暗号を区別できない場合、暗号システムは意味的に安全であると言われています。パディングのないRSAは意味的に安全ではありません。[40]
  • RSA には、2 つの暗号文の積が、それぞれの平文の積の暗号化に等しいという特性があります。つまり、m 1 e m 2 e ≡ ( m 1 m 2 ) 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 を導き出すことができます。[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]は、一部の種類のメッセージではこのパディングでは十分に高いレベルのセキュリティが得られないことを示した。標準の後のバージョンには、これらの攻撃を防ぐ最適非対称暗号化パディング(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] [要出典]次の値は事前に計算され、秘密鍵の一部として保存されます。

  • そして 、鍵生成から得られた素数、

これらの値により、受信者は指数m = c d (mod pq )を 次のようにより効率的に計算できます： 、、、、 [d]。
     
     
     
     

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

整数因数分解とRSA問題

RSA暗号システムの安全性は、2つの数学的問題、すなわち大きな数の因数分解問題とRSA問題に基づいています。これらの問題が両方とも困難である、つまり効率的な解読アルゴリズムが存在しないという仮定のもと、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,400MIPS年に相当する処理能力が必要でした。[46] 2009年までに、ベンジャミン・ムーディは、公開ソフトウェア（GGNFS）とデスクトップコンピュータ（1,900MHz CPUを搭載したデュアルコアAthlon64）のみを使用して、512ビットのRSA鍵を73日で因数分解することができました。ふるい分け処理には、5ギガバイト弱のディスクストレージと約2.5ギガバイトのRAMが必要でした。

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

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

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

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

鍵生成の不具合

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

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

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

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

2017年10月、マサリク大学の研究チームは、インフィニオンのRSALibと呼ばれるライブラリに組み込まれたアルゴリズムによって生成されるRSA鍵に影響を及ぼすROCA脆弱性を発表しました。多数のスマートカードと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のGCDを、発見した他のすべての鍵n 'の積（7億2900万桁の数値）に対して計算しました。各gcd( n , n ′)を個別に計算するのではなく、これにより大幅な高速化を達成しました。大きな除算を一度行えば、GCD問題は通常のサイズになります。

ヘニンガー氏はブログの中で、不正な鍵はほぼすべて、30社以上のメーカーの「ファイアウォール、ルーター、VPNデバイス、リモートサーバー管理デバイス、プリンター、プロジェクター、VOIP電話」を含む組み込みアプリケーションで発生したと述べています。ヘニンガー氏は、2つのグループが発見した単一共有素数問題は、擬似乱数生成器の初期シード値が不適切で、最初の素数生成と2番目の素数生成の間にシード値が再設定される状況に起因すると説明しています。キー入力タイミング、電子ダイオードノイズ、あるいは放送局間のラジオ受信機からの大気ノイズから得られる十分に高いエントロピーを持つシード値を使用することで、この問題を解決できるはずです。[56]

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

タイミング攻撃

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

これらの攻撃を阻止する 1 つの方法は、すべての暗号文に対して復号化操作に一定時間がかかるようにすることです。ただし、このアプローチはパフォーマンスを大幅に低下させる可能性があります。代わりに、ほとんどの 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方式の欠陥により、ブライヘンバッハーはセキュア・ソケット・レイヤー・プロトコルのRSA実装に対して実用的な攻撃を仕掛け、セッション鍵を復元することに成功した。この研究の結果、暗号学者は現在、最適非対称暗号化パディング（OPAEP）などの証明可能な安全性を持つパディング方式の使用を推奨しており、RSA研究所はこれらの攻撃に対して脆弱ではないPKCS #1の新バージョンをリリースしている。

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

サイドチャネル解析攻撃

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

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

フォールトインジェクション攻撃

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

CRT実装はフォールトインジェクション攻撃に対して脆弱です。攻撃者が1つの誤った署名を入手できれば、秘密鍵を計算できます。[62]

難しい実装

RSAを安全に実装するには、考慮すべき点が数多くあります（強力なPRNG 、許容可能な公開指数など）。そのため実装は困難を極め、 「Practical Cryptography With Go」という書籍では、可能な限りRSAを避けることを推奨しています。[63]

実装

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

参照

注記

  1. ^ e = 2も可能です (さらに高速です) が、平方は順列ではないため質的に異なります。これがRabin 署名アルゴリズムの基礎です。
  2. ^ つまり、 pを法として−1、0、または1に等しく、かつqを法として−1、0、または1に等しいmの値。p  − 1またはq  − 1が2以外にもe  − 1と共通の約数を持つ場合、 c = mとなるmの値がさらに多く存在する。これは、それぞれまたはとなるmの値がさらに多く存在するためである。
  3. ^ ここで使用されているパラメータは人為的に小さいですが、OpenSSL を使用して実際のキーペアを生成および検査することもできます。
  4. ^ の場合、一部の[説明が必要]ライブラリではhを として計算します。

参考文献

  1. ^ Rivest, RL ; Shamir, A. ; Adleman, L. (1977). デジタル署名と公開鍵暗号システムを取得する方法(PDF) (技術レポート). MIT コンピュータサイエンス研究所. hdl : 1721.1/148910 . MIT-LCS-TM-082.
  2. ^ ab Gardner, Martin (1977年8月). 「数学ゲーム：解読に数百万年かかる新しい暗号」（PDF） . Scientific American . 第237巻第2号. doi :10.1038/scientificamerican0877-120. 2025年7月11日時点のオリジナル（PDF）からアーカイブ。
  3. ^ abcd Rivest, R.; Shamir, A.; Adleman, L. (1978年2月). 「デジタル署名と公開鍵暗号システムを取得する方法」(PDF) . Communications of the ACM . 21 (2): 120– 126. CiteSeerX 10.1.1.607.2677 . doi : 10.1145/359340.359342 . 2023年1月27日時点のオリジナル(PDF)からのアーカイブ。 2025年7月30日閲覧。 
  4. ^ Smart, Nigel (2008年2月19日). 「Dr Clifford Cocks CB」.ブリストル大学. 2025年6月20日閲覧。
  5. ^ Bellare, Mihir ; Rogaway, Phillip . Maurer, Ueli (編). デジタル署名の正確な安全性：RSAとRabinを用いた署名方法. 暗号学の進歩—EUROCRYPT '96. コンピュータサイエンス講義ノート. Springer. pp.  399– 416. doi : 10.1007/3-540-68339-9_34 . ISBN 978-3-540-61186-8。
  6. ^ Aumasson, Jean-Philippe (2018). 「10. RSA: RSAによる署名」. Serious Cryptography . No Starch Press. pp.  188– 191. ISBN 978-1-59327-826-7。
  7. ^ スティンソン、ダグラス(2006). 「7. 署名スキーム」.暗号理論と実践（第3版）. チャップマン＆ホール/CRC. pp.  281– 318. ISBN 978-1-58488-508-5。
  8. ^ ファーガソン, ニールス;河野忠義;シュナイアー, ブルース(2010). 「12. RSA」.暗号工学. Wiley. pp.  195– 211. ISBN 978-0-470-47424-2。
  9. ^ ガルブレイス、スティーブン (2012). 「§ 24.6: RSAとRabinに基づくデジタル署名」.公開鍵暗号の数学. ケンブリッジ大学出版局. pp.  7– 9. ISBN 978-1-107-01392-6。
  10. ^ ab B. Kaliski; A. Rusch; J. Johnsson; A. Rusch (2016年11月). K. Moriarty (編). PKCS #1: RSA暗号仕様バージョン2.2.インターネット技術タスクフォース. doi : 10.17487/RFC8017 . ISSN  2070-1721. RFC 8017. 情報提供。RFC 3447 を廃止します。
  11. ^ Bellare, Mihir ; Rogaway, Phillip . Santis, Alfredo (ed.).最適非対称暗号化. 暗号学の進歩—EUROCRYPT '94. コンピュータサイエンス講義ノート. Springer. pp.  92– 111. doi : 10.1007/BFb0053428 . ISBN 978-3-540-60176-0。
  12. ^ Aumasson, Jean-Philippe (2018). 「10. RSA: RSAによる暗号化」. Serious Cryptography . No Starch Press. pp.  185– 188. ISBN 978-1-59327-826-7。
  13. ^ ガルブレイス、スティーブン (2012). 「§24.7: RSAとRabinに基づく公開鍵暗号」.公開鍵暗号の数学. ケンブリッジ大学出版局. pp.  511– 512. ISBN 978-1-107-01392-6。
  14. ^ Shoup, Victor (2001)、「公開鍵暗号のISO標準案（バージョン2.1）」、暗号学ePrintアーカイブ、国際暗号研究協会
  15. ^ ファーガソン, ニールス;河野忠義;シュナイアー, ブルース(2010). 「12. RSA」.暗号工学. Wiley. pp.  195– 211. ISBN 978-0-470-47424-2。
  16. ^ R. Housley; S. Turner (2025年2月). 暗号メッセージ構文（CMS）におけるRSA-KEMアルゴリズムの使用.インターネット技術タスクフォース. doi : 10.17487/RFC9690 . RFC 9690. 提案された標準。RFC 5990 を廃止します。
  17. ^ Castelvecchi, Davide (2020-10-30). 「量子コンピューティングのパイオニア、インターネットセキュリティへの甘えに警鐘」 . Nature . 587 (7833): 189. Bibcode :2020Natur.587..189C. doi :10.1038/d41586-020-03068-9. PMID:  33139910. S2CID:  226243008.2020年のピーター・ショアのインタビュー。
  18. ^ Diffie, W. ; Hellman, ME (1976年11月). 「暗号技術の新しい方向性」(PDF) . IEEE Transactions on Information Theory . 22 (6): 644– 654. Bibcode :1976ITIT...22..644D. CiteSeerX 10.1.1.37.9720 . doi :10.1109/TIT.1976.1055638. ISSN 0018-9448. 2014年11月29日時点の オリジナル(PDF)からのアーカイブ。 2025年7月30日閲覧。 
  19. ^ Rivest, Ronald. 「RSAの初期 – 歴史と教訓」(PDF) .
  20. ^ Calderbank, Michael (2007-08-20). 「RSA暗号システム：歴史、アルゴリズム、素数」(PDF) .
  21. ^ ab Robinson, Sara (2003年6月). 「数年にわたる攻撃の後も秘密を守り続けるRSA、創設者に称賛の声」(PDF) . SIAM News . 36 (5). 2022年12月15日時点のオリジナル(PDF)からのアーカイブ。
  22. ^ Cocks, CC (1973年11月20日). 「非秘密暗号化に関する注記」(PDF) . www.gchq.gov.uk . 2018年9月28日時点のオリジナル(PDF)からアーカイブ。 2017年5月30日閲覧。
  23. ^ Jim Sauerberg. 「3つの簡単なステップで秘密鍵暗号から公開鍵暗号へ」
  24. ^ マーガレット・コッツェンズ、スティーブン・J・ミラー著「暗号化の数学：初等入門」180ページ。
  25. ^ アラスデア・マクアンドリュー. 「オープンソースソフトウェアによる暗号化入門」. p. 12.
  26. ^ サレンダー R. チルカ。 「公開鍵暗号化」。
  27. ^ ニール・コブリッツ「教育ツールとしての暗号」Cryptology, Vol. 21, No. 4 (1997).
  28. ^ 「RSA SecurityがRSA暗号化アルゴリズムをパブリックドメインにリリース」。2007年6月21日時点のオリジナルよりアーカイブ。 2010年3月3日閲覧。
  29. ^ シュヴェンダ、ペトル;ネメック、マトゥシュ。セカン、ピーター。クヴァショフスキー、ルドルフ。デビッド・フォルマネク。デビッド・コマレク。マティアーシュ、ヴァシェク（2016年8月）。 100 万鍵の質問 - RSA 公開鍵の起源の調査。第 25 回 USENIX セキュリティ シンポジウム。米国テキサス州オースティン: USENIX Association。ページ 893–910。ISBN​​ 978-1-931971-32-4。
  30. ^ ab Boneh, Dan (1999). 「RSA暗号システムへの20年間の攻撃」アメリカ数学会報46 ( 2): 203– 213.
  31. ^ Applied Cryptography、John Wiley & Sons、ニューヨーク、1996年。Bruce Schneier、467ページ。
  32. ^ ab Johnson, J.; Kaliski, B. (2003年2月). 公開鍵暗号標準 (PKCS) #1: RSA暗号仕様 バージョン2.1. ネットワークワーキンググループ. doi : 10.17487/RFC3447 . RFC 3447. 2016年3月9日閲覧。
  33. ^ ab Bleichenbacher, Daniel (1998). Krawczyk, Hugo (編). RSA暗号化標準PKCS #1に基づくプロトコルに対する選択暗号文攻撃. Advances in Cryptology—CRYPTO '98. Lecture Notes in Computer Science. Springer. pp.  1– 12. doi : 10.1007/BFb0055716 . ISBN 978-3-540-68462-6。
  34. ^ ラビン, マイケル・O. (1978). 「デジタル署名」.デミロ, リチャード・A. ;ドブキン, デビッド・P. ;ジョーンズ, アニタ・K. ;リプトン, リチャード・J. (編). 『セキュアコンピューティングの基礎』 . ニューヨーク: アカデミック・プレス. pp.  155– 168. ISBN 0-12-210350-5。
  35. ^ Rabin, Michael O. (1979年1月). 「デジタル署名と公開鍵関数は因数分解と同じくらい扱いにくい」(PDF) (技術レポート). マサチューセッツ州ケンブリッジ, アメリカ合衆国: MITコンピュータサイエンス研究所TR-212.
  36. ^ Bernstein, Daniel J. (2008年1月31日). RSA署名とラビン・ウィリアムズ署名：最新技術（レポート）.（追加情報は https://cr.yp.to/sigs.html をご覧ください）
  37. ^ Bellare, Mihir ; Rogaway, Phillip (1996年5月). Maurer, Ueli (編).デジタル署名の厳密なセキュリティ：RSAとRabinを使った署名方法. 暗号学の進歩 – EUROCRYPT '96. コンピュータサイエンス講義ノート. 第1070巻. サラゴサ、スペイン: Springer. pp.  399– 416. doi : 10.1007/3-540-68339-9_34 . ISBN 978-3-540-61186-8。
  38. ^ Håstad, Johan (1986). 「公開鍵ネットワークにおける低指数RSA暗号の利用について」. Advances in Cryptology – CRYPTO '85 Proceedings . Lecture Notes in Computer Science. Vol. 218. pp.  403– 408. doi :10.1007/3-540-39799-X_29. ISBN 978-3-540-16463-0。
  39. ^ Coppersmith, Don (1997). 「多項式方程式の小さな解と低指数RSA脆弱性」(PDF) . Journal of Cryptology . 10 (4): 233– 260. CiteSeerX 10.1.1.298.4806 . doi :10.1007/s001459900030. S2CID  15726802. 
  40. ^ Goldwasser, Shafi ; Micali, Silvio (1982-05-05). 「確率的暗号化と、部分的な情報をすべて秘密にしながらメンタルポーカーをプレイする方法」.第14回ACMコンピューティング理論シンポジウム - STOC '82 議事録. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  365– 377. doi :10.1145/800070.802212. ISBN 978-0-89791-070-5. S2CID  10316867。
  41. ^ Davida, George I. (1982). RSA (MIT)公開鍵暗号システムの選択署名暗号解読（技術レポート）. ウィスコンシン大学ミルウォーキー校電気工学・コンピュータサイエンス学部. 技術レポート TR-CS-82-2.
  42. ^ Coron, Jean-Sébastien; Joye, Marc; Naccache, David; Paillier, Pascal (2000). 「PKCS#1 v1.5暗号化に対する新たな攻撃」 Preneel, Bart (編). Advances in Cryptology — EUROCRYPT 2000 . Lecture Notes in Computer Science. Vol. 1807. ベルリン、ハイデルベルク: Springer. pp.  369– 381. doi : 10.1007/3-540-45539-6_25 . ISBN 978-3-540-45539-4。
  43. ^ 「RSAアルゴリズム」。
  44. ^ “OpenSSL bn_s390x.c”. Github . 2024年8月2日閲覧。
  45. ^ マチー、エドモンド・K.（2013年3月29日）. 米国国防総省ネットワークにおけるネットワークセキュリティのトレースバック攻撃と対応. トラフォード. p. 167. ISBN 978-1466985742。
  46. ^ Lenstra, Arjen; et al. (Group) (2000). 「512ビットRSA係数の因数分解」(PDF) . Eurocrypt.
  47. ^ ミラー、ゲイリー・L. (1975). 「リーマン予想と素数性検定」(PDF) .第7回ACM計算理論シンポジウム議事録. pp.  234– 239.
  48. ^ Zimmermann, Paul (2020-02-28). 「RSA-250の因数分解」. Cado-nfs-discuss. 2020年2月28日時点のオリジナルよりアーカイブ。 2020年7月12日閲覧。
  49. ^ ab Kaliski, Burt (2003-05-06). 「TWIRLとRSA鍵サイズ」RSA Laboratories . 2017年4月17日時点のオリジナルよりアーカイブ。 2017年11月24日閲覧。
  50. ^ Barker, Elaine; Dang, Quynh (2015年1月22日). 「NIST特別刊行物800-57 パート3 改訂1：鍵管理に関する推奨事項：アプリケーション固有の鍵管理ガイダンス」（PDF） .米国国立標準技術研究所. p. 12. doi :10.6028/NIST.SP.800-57pt3r1 . 2017年11月24日閲覧.
  51. ^ Sandee, Michael (2011年11月21日). 「RSA-512証明書の悪用事例」Fox-IT Internationalブログ.
  52. ^ Wiener, Michael J. (1990年5月). 「短いRSA秘密指数の暗号解析」(PDF) . IEEE Transactions on Information Theory . 36 (3): 553– 558. Bibcode :1990ITIT...36..553W. doi :10.1109/18.54902. S2CID  7120331.
  53. ^ Nemec, Matus; Sys, Marek; Svenda, Petr; Klinec, Dusan; Matyas, Vashek (2017年11月). 「Coppersmith攻撃の復活：広く利用されているRSA係数の実用的な因数分解」(PDF) . 2017 ACM SIGSAC コンピュータおよび通信セキュリティ会議議事録. CCS '17. doi :10.1145/3133956.3133969.
  54. ^ Markoff, John (2012年2月14日). 「オンライン暗号化方式に欠陥発見」.ニューヨーク・タイムズ.
  55. ^ レンストラ、アリエン K.;ヒューズ、ジェームス P.オジェ、マキシム。ボス、ジョッペ W.クラインジュン、トルステン。クリストフ・ヴァハター (2012)。 「ロンは間違っていた、ホイットは正しい」(PDF)。
  56. ^ Heninger, Nadia (2012年2月15日). 「新研究：因数分解可能なキーについてパニックになる必要はありません。PとQに注意するだけです」. Freedom to Tinker .
  57. ^ Brumley, David; Boneh, Dan (2003). 「リモートタイミング攻撃は実用的である」(PDF) .第12回USENIXセキュリティシンポジウム会議議事録. SSYM'03.
  58. ^ 「Mozilla NSS暗号ライブラリで発見された『BERserk』バグ、FirefoxとChromeに影響」2014年9月25日. 2022年1月4日閲覧。
  59. ^ 「NSSにおけるRSA署名偽造」Mozilla。
  60. ^ Acıiçmez, Onur; Koç, Çetin Kaya; Seifert, Jean-Pierre (2007). 「単純な分岐予測分析の威力について」.第2回ACM情報・コンピュータ・通信セキュリティシンポジウム議事録. ASIACCS '07. pp.  312– 320. CiteSeerX 10.1.1.80.1438 . doi :10.1145/1229285.1266999. 
  61. ^ Pellegrini, Andrea; Bertacco, Valeria; Austin, Todd (2010年3月). 「RSA認証に対するフォールトベース攻撃」. 2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010) . pp.  855– 860. doi :10.1109/DATE.2010.5456933. ISBN 978-3-9810801-6-2。
  62. ^ Boneh, Dan; DeMillo, Richard A.; Lipton, Richard J. (2000年11月). 「暗号計算におけるエラー除去の重要性について」. Journal of Cryptology . 14 (2): 106– 107. doi :10.1007/s001450010016. ISSN  0933-2790.
  63. ^ Isom, Kyle. 「Practical Cryptography With Go」 . 2022年1月4日閲覧。

さらに読む

  • 1977 年 12 月 14 日に Rivest、Ronald L. (マサチューセッツ州ベルモント)、Shamir、Adi (マサチューセッツ州ケンブリッジ)、Adleman、Leonard M. (マサチューセッツ州アーリントン) によって米国特許庁に提出されたオリジナルの RSA 特許、米国特許第 4,405,829 号。
  • RFC 8017: PKCS #1: RSA 暗号化仕様バージョン 2.2
  • YouTubeで色付きランプを使ったRSAの説明
  • RSAの徹底的なウォークスルー
  • 素数の隠れんぼ：RSA暗号の仕組み
  • Onur Aciicmez、Cetin Kaya Koc、Jean-Pierre Seifert: 単純な分岐予測分析の威力について