銅細工師の攻撃

コッパースミス攻撃は、コッパースミス法に基づく公開鍵暗号システムRSAに対する暗号攻撃の一種である。コッパースミス法は、公開指数eが小さい場合や秘密鍵の素因数が部分的にしか分かっていない場合にRSA攻撃に用いられる。

RSAの基礎

RSAシステムの公開鍵は整数 の組であり、Nは2つの素数pとqの積です。秘密鍵は、を満たす整数dで与えられます。同様に、秘密鍵はで与えられ、中国剰余定理を用いて復号速度を向上させる場合は、 CRT-RSAを参照してください。メッセージMを暗号化すると暗号文が生成され、これを計算することで復号できます。 ${\displaystyle (N,e)}$ ${\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}$ ${\displaystyle d_{p}\equiv d{\pmod {p-1}}}$ ${\displaystyle d_{q}\equiv d{\pmod {q-1}}}$ ${\displaystyle C\equiv M^{e}{\pmod {N}}}$ ${\displaystyle d}$ ${\displaystyle C^{d}\equiv M{\pmod {N}}}$

低公開指数攻撃

暗号化や署名の検証時間を短縮するには、小さな公開指数( )を使用すると便利です。^[1]実際には、 の一般的な選択肢は3、17、65537 です。eのこれらの値はフェルマー素数であり、それぞれ およびと呼ばれることもあります。これらが選択される理由は、指数モジュラー演算が高速になるためです。また、このような を選択すると、鍵生成のステップ 1 で素数を生成およびテストする際に、および であるかどうかをテストするのが簡単になります。このテストに合格しないまたはの値は、その場で拒否できます。(さらに良いことに、e が素数で 2 より大きい場合は、よりコストのかかるテスト を このテストに置き換えることができます。) ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle (2^{16}+1)}$ ${\displaystyle F_{0},F_{2}}$ ${\displaystyle F_{4}}$ ${\displaystyle (F_{x}=2^{2^{x}}+1)}$ ${\displaystyle e}$ ${\displaystyle \gcd(e,p-1)=1}$ ${\displaystyle \gcd(e,q-1)=1}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p{\bmod {e}}\neq 1}$ ${\displaystyle \gcd(p-1,e)=1}$

公開指数が小さく、平文 が非常に短い場合、RSA 関数の反転が容易になる可能性があり、特定の攻撃が可能になります。 パディング スキームにより、メッセージの長さは完全になりますが、さらに公開指数を選択することをお勧めします。この値を使用すると、署名の検証には 17 回の乗算が必要ですが、同様のサイズの乱数を使用する場合は約 25 回です。低い秘密指数 (ウィーナーの攻撃を参照) とは異なり、小さい秘密指数を使用する場合に適用される攻撃は、秘密鍵dを復元できる完全な破綻からは程遠いものです。低い公開指数RSAに対する最も強力な攻撃は、ドン コッパースミスによる次の定理に基づいています。 ${\displaystyle m}$ ${\displaystyle e=2^{16}+1}$ ${\displaystyle e}$ ${\displaystyle e}$

ハスタッドの放送攻撃

理解を容易にするために、Håstadの攻撃の最も単純な形式が提示されています。^[2]一般的なケースでは、Coppersmith法が使用されます。

ある送信者が、同じメッセージを暗号化した形で多数の人 に送信し、各人が同じ小さな公開指数（たとえば）と異なる法 を使用するとします。簡単な議論から、暗号文が知られるやいなや、メッセージは安全ではなくなることがわかります。イヴが、および（ ）を傍受したとします。すべての に対して と仮定できます（そうでない場合は、を計算することで、いずれかの数の因数を計算することができます）。中国式剰余定理により、イヴはとなる計算を行う可能性があります。すると となります。ただし、すべての に対してとなるため、 となります。したがって、整数 に対して が成り立ち、イヴはの立方根を計算して を得ることができます。 ${\displaystyle M}$ ${\displaystyle P_{1};P_{2};\dots ;P_{k}}$ ${\displaystyle e}$ ${\displaystyle e=3}$ ${\displaystyle \left\langle N_{i},e\right\rangle }$ ${\displaystyle k\geq 3}$ ${\displaystyle M}$ ${\displaystyle C_{1},C_{2}}$ ${\displaystyle C_{3}}$ ${\displaystyle C_{i}\equiv M^{3}{\pmod {N_{i}}}}$ ${\displaystyle \gcd(N_{i},N_{j})=1}$ ${\displaystyle i,j}$ ${\displaystyle N_{i}}$ ${\displaystyle \gcd(N_{i},N_{j})}$ ${\displaystyle C\in \mathbb {Z} _{N_{1}N_{2}N_{3}}^{*}}$ ${\displaystyle C\equiv C_{i}{\pmod {N_{i}}}}$ ${\displaystyle C\equiv M^{3}{\pmod {N_{1}N_{2}N_{3}}}}$ ${\displaystyle M<N_{i}}$ ${\displaystyle i}$ ${\displaystyle M^{3}<N_{1}N_{2}N_{3}}$ ${\displaystyle C=M^{3}}$ ${\displaystyle C}$ ${\displaystyle M}$

の値が大きくなると、より多くの暗号文が必要になりますが、特に、の暗号文で十分です。 ${\displaystyle e}$ ${\displaystyle e}$

一般化

ハスタッドはまた、暗号化前に に線形 パディングを適用しても、この攻撃から保護されないことを示しました。攻撃者がと何らかの線形関数についてを学習していると仮定します。つまり、ボブはメッセージを暗号化する前にパディングを適用し、受信者がわずかに異なるメッセージを受信するようにします。例えば、がビット長の場合、ボブはこれを暗号化して- 番目の受信者に送信する可能性があります。 ${\displaystyle M}$ ${\displaystyle C_{i}=f_{i}(M)^{e}}$ ${\displaystyle 1\leq i\leq k}$ ${\displaystyle f_{i}}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle m}$ ${\displaystyle M_{i}=i2^{m}+M}$ ${\displaystyle i}$

十分に大規模なグループが関与している場合、攻撃者は同様の方法ですべての暗号文から平文を復元できます。より一般的には、Håstadは、任意の固定 多項式を適用するなど、互いに素な合成数を法とする一変数方程式系は、十分な数の方程式が与えられれば解けることを証明しました。この攻撃は、 RSA暗号においてランダムパディングを使用すべきであることを示唆しています。 ${\displaystyle M_{i}}$ ${\displaystyle g_{i}(M)\equiv 0{\pmod {N_{i}}}}$

フランクリン・ライター関連メッセージ攻撃

フランクリンとライターは、複数の関連するメッセージが暗号化されている場合のRSA攻撃を特定しました。2つのメッセージが既知の固定差のみで、同じRSA係数でRSA暗号化されている場合、両方のメッセージを復元することが可能です。この攻撃は当初、公開指数を用いて記述されていましたが、より一般的に機能します（が大きくなるにつれてコストも増加します）。 ${\displaystyle N}$ ${\displaystyle e=3}$ ${\displaystyle e}$

をアリスの公開鍵とします。2つの異なるメッセージが、ある公開多項式を満たすとします。ボブは、と をアリスに送信するために、これらのメッセージを単純に暗号化し、その結果得られる暗号文を送信します。イブは、 が与えられた場合、次の定理を用いてを簡単に復元できます。 ${\displaystyle \left\langle N;e_{i}\right\rangle }$ ${\displaystyle M_{1};M_{2}\in \mathbb {Z} _{N}}$ ${\displaystyle M_{1}\equiv f(M_{2}){\pmod {N}}}$ ${\displaystyle f\in \mathbb {Z} _{N}[x]}$ ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle C_{1};C_{2}}$ ${\displaystyle M_{1};M_{2}}$ ${\displaystyle C_{1};C_{2}}$

コッパースミスのショートパッド攻撃

ハスタッド攻撃やフランクリン・ライター攻撃と同様に、この攻撃は公開指数を用いたRSAの脆弱性を悪用します。コッパースミスは、ハスタッドが提案したランダムパディングが不適切に使用されると、 RSA暗号は安全ではないことを示しました。 ${\displaystyle e=3}$

ボブがアリスに、暗号化する前に小さなランダムパディングを使ってメッセージを送信したとします。攻撃者のイヴが暗号文を傍受し、宛先への到達を阻止します。アリスがメッセージに応答しなかったため、ボブはアリスに再送信することにしました。彼は再びランダムパディングを行い、その結果得られた暗号文を送信します。これでイヴは、同じメッセージを2つの異なるランダムパディングを使って暗号化した2つの暗号文を持つことになります。 ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

イブは使用されているランダム パッドを知りませんが、ランダム パディングが短すぎる場合は、次の定理を使用して メッセージを復元できます。${\displaystyle M}$

参照

• ROCA攻撃

参考文献

1. ボネ、ダン (1999). 「RSA暗号システムへの20年間の攻撃」アメリカ数学会報46 (2): 203–213 .
2. Glenn Durfee、「代数法と格子法を用いた RSA の暗号解読」