銅細工師の方法

ドン・コッパースミスによって提案されたコッパースミス法は、与えられた整数を法とする一変量または二変量多項式の小さな整数零点を見つける方法です。この方法では、レンストラ-レンストラ-ロヴァース格子基底縮小アルゴリズム(LLL) を使用して、対象多項式と同じ零点を持ちながら係数が小さい多項式を見つけます。

暗号技術において、Coppersmith 方式は主に、秘密鍵の一部が既知である場合のRSAへの攻撃に使用され、 Coppersmith 攻撃の基礎を形成します。

Coppersmith のアプローチは、モジュラー多項式方程式を解くことを整数上の多項式を解くことに簡略化したものです。

とし、ある整数 に対して であると仮定します。Coppersmith のアルゴリズムを使用して、この整数解を見つけることができます。 ${\displaystyle F(x)=x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}}$${\displaystyle F(x_{0})\equiv 0{\pmod {M}}}$${\displaystyle |x_{0}|<M^{1/n}}$${\displaystyle x_{0}}$

Q上の根を見つけることは、例えばニュートン法 を使うと簡単ですが、そのようなアルゴリズムは合成数M を法として機能しません。コッパースミス法の背後にある考え方は、Mを法として同じ根を持ち、係数が小さいFに関連する別の多項式f を見つけることです。係数 と が十分に小さく、整数を法として である場合、 が得られるので、 はQ上のfの根であり、簡単に見つけることができます。より一般的には、 を満たす、Mの何らかの累乗を法として同じ根を持つ多項式を見つけ、上記のように を解くことができます。 ${\displaystyle x_{0}}$${\displaystyle x_{0}}$${\displaystyle |f(x_{0})|<M}$${\displaystyle f(x_{0})=0}$${\displaystyle x_{0}}$${\displaystyle f(x)}$${\displaystyle x_{0}}$${\displaystyle M^{a}}$${\displaystyle |f(x_{0})|<M^{a}}$${\displaystyle x_{0}}$

Coppersmith のアルゴリズムは、Lenstra-Lenstra-Lovász 格子基底簡約アルゴリズム(LLL) を使用して、係数が小さい多項式f を構築します。 Fが与えられると、アルゴリズムは を法としてすべて同じ根を持つ多項式を構築します。ここで、a はFの次数と のサイズに基づいて選択された整数です。これらの多項式の任意の線形結合も を法として根を持ちます。 ${\displaystyle p_{1}(x),p_{2}(x),\dots ,p_{n}(x)}$${\displaystyle x_{0}}$${\displaystyle M^{a}}$${\displaystyle x_{0}}$${\displaystyle x_{0}}$${\displaystyle M^{a}}$

次のステップは、LLL アルゴリズムを使用して、不等式が成り立つよう に の線形結合を構築することです。これで、標準的な因数分解法を使用して、整数上の のゼロを計算できるようになりました。${\displaystyle f(x)=\sum c_{i}p_{i}(x)}$${\displaystyle p_{i}(x)}$${\displaystyle |f(x_{0})|<M^{a}}$${\displaystyle f(x)}$

1変数多項式に対するCoppersmith法は、

• 機能としてのマグマSmallRoots;
• 関数としてのPARI/GPzncoppersmith ;
• SageMath をメソッドとして使用しますsmall_roots。

• Coppersmith, D. ( 1996)。「一変量モジュラー方程式の小さな根を見つける」。暗号学の進歩 — EUROCRYPT '96。コンピュータサイエンスの講義ノート。第 1070 巻。pp. 155–165。doi : 10.1007 / 3-540-68339-9_14。ISBN 978-3-540-61186-8。
• Coppersmith, D. (1996)。「2 変数整数方程式の小さな根を見つける; 上位ビットがわかっている場合の因数分解」。暗号学の進歩 — EUROCRYPT '96。コンピュータ サイエンスの講義ノート。第 1070 巻。pp. 178–189。doi : 10.1007 / 3-540-68339-9_16。ISBN 978-3-540-61186-8。
• Coron, JS (2004)。「二変量整数多項式方程式の小さな根の発見の再考」( PDF)。暗号学の進歩 - EUROCRYPT 2004。コンピュータサイエンスの講義ノート。第 3027 巻。pp. 492–505。doi : 10.1007/978-3-540-24676-3_29。ISBN 978-3-540-21935-4。
• Bauer, A.; Joux, A. (2007)。「3 つの変数に対する Coppersmith アルゴリズムの厳密なバリエーションに向けて」。暗号学の進歩- EUROCRYPT 2007。コンピュータ サイエンスの講義ノート。第 4515 巻。361 ～ 378 ページ。doi : 10.1007 / 978-3-540-72540-4_21。ISBN 978-3-540-72539-8。
• Coron, JS (2007)。「二変量整数多項式方程式の小さな根を見つける: 直接的なアプローチ」(PDF) 。暗号学の進歩 - CRYPTO 2007。コンピュータサイエンスの講義ノート。第 4622 巻。pp. 379–394。doi : 10.1007/978-3-540-74143-5_21。ISBN 978-3-540-74142-8。