銅細工師の攻撃

銅細工攻撃は、銅細工法に基づく公開鍵暗号システムRSAに対する暗号攻撃の一種です。銅細工法が RSA を攻撃する際に特に使用されるのは、公開指数eが小さい場合や、秘密鍵の素因数の一部しか知らない場合です。

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

Håstad は、暗号化の前にに線形 パディングを適用しても、この攻撃から保護されないことも示しました。攻撃者が と何らかの線形関数について であることを学習していると仮定します。つまり、Bob はメッセージを暗号化する前に にパディングを適用し、受信者がわずかに異なるメッセージを受信するようにします。たとえば、がビット長の場合、Bob はこれを暗号化して 人目の受信者に送信する可能性があります。 ${\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}}}}$

Franklin と Reiter は、複数の関連するメッセージが暗号化されている場合の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}}$

Håstad の攻撃や Franklin-Reiter の攻撃と同様に、この攻撃は公開指数を使用したRSAの弱点を悪用します。Coppersmith は、Håstad が提案したランダムなパディングが不適切に使用されると、 RSA暗号化は安全ではないこと を示しました。${\displaystyle e=3}$

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

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

• ROCA攻撃