Coppersmith の小さなルーツ法 (小さな範囲で合成係数に対する多項式を解く)
主に、理論的に確立されたカッパースミス法の適用方程式を扱います。方程式の種類がわかっている場合は、(ヒューリスティックではなく) 単変量または線形を使用することをお勧めします。
まず、境界に基づいて適切なパラメータを選択し、
選択可能な内部 LLL/BKZ 方式
選択可能な整数方程式の解法
$ git clone https://github.com/kionactf/coppersmith --syncfplll または flatter を使用する場合は、これらのパッケージをビルドする必要があります。すでにインストールしている場合は、これらのインストール パスを lll.py の fplll_path または flatter_path に設定することでこれを使用できます。
または、Docker イメージを作成することもできます。これは sagemath/sagemath:latest イメージに基づいており、よく知られた格子ライブラリもダウンロードします。 (他の優れたライブラリをご存知の場合は、これらを含めるようにお知らせください。)
$ docker build -t coppersmith .
$ docker run --rm -it coppersmith /bin/bashZmod(N)、境界、ベータ上で Sagemath PolynomialRing を使用して、coppersmith_onevariable.coppersmith_onevariable またはcoppersmith_linear.coppersmith_linearを呼び出します。
example.py参照してください。
また、ZZ 上の Sagemath 行列といくつかの最適化パラメーターを指定して lll.do_lattice_reduction を呼び出すことにより、 LLLのみを使用することもできます。そしてCVPソルバー用のlll.babai。
integer equations solverの場合は、ZZ および境界上の Sagemath 多項式のリストを指定して rootfind_ZZ.rootfind_ZZ を使用します。
(この機能は2024/3/8に導入されました。)
いくつかの実験に基づいて組み込みのデフォルト設定をセットアップしましたが、一部のユーザーは、その設定が自分の環境に適合しないと言いました。
そこで、 lll.pyとrootfind_ZZ.pyの構成インターフェイスcontextを準備します。
次の例のようにcontextをインポートすることで使用できます。
from coppersmith_linear import * # including context
from lll import FLATTER
from rootfind_ZZ import JACOBIAN , TRIANGULATE
# use flatter
context . lllopt = { 'algorithm' : FLATTER , 'use_pari_kernel' : True }
# use jacobian method and triangulate in order,
# and for jacobian method set the number of iteration(loop) as 32 (much less comparing the default value 1024)
context . rootfindZZopt = { 'algorithm' :( JACOBIAN , TRIANGULATE ), 'maxiternum' : 32 }
# debug output enable
logger . setLevel ( DEBUG )
P = PolynomialRing (...)
f = ...
beta = ...
bounds = [...]
coppersmith_linear ( f , bounds , beta )オプションのリストとそのデフォルト値は、 contextclass.pyのregister_options_lllおよびregister_options_rootfind_ZZで確認できます。
LLL を計算するには、格子を定義するための線形依存ベクトルを除去するために pari.matker を使用します。プロセスではよりフラットを使用する必要があります。 pari.matker は高速で多くの場合正しい結果を出力しますが、場合によってはwrong結果を出力することがあります。 (これは、 lll.test() を実行することで確認できます。) オプションuse_pari_kernel=Falseを設定すると、 pari.matker の使用を無効にすることができます。これにより、 Sagemath カーネルの使用が強制されます (内部でエルミート標準形式 (HNF) の計算を実行します)。 HNF は大きな要素を生成する傾向があるため、LLL プロセスが非常に遅くなることに注意してください。
詳細については、「時間恐怖症を解決できなかった理由…カッパースミス法による分析」を参照してください。 （古い記事かもしれませんが。）
Coppersmith の小さな根法では、次の型方程式の根を見つけます。
パッケージ関数には次のパラメータが必要です。
決定するため
例えば、
Q: パッケージで多くの係数多変量多項式系を解くことができますか?
A: たぶんないでしょう。一般的なモジュラス多変量多項式ソルバーを作成するのは難しそうです。それは単項式 ([ など) に依存します。 vs [ vs [ vs [
特に、多項式を理解せずにヒューリスティックな手法を使用することはお勧めしません。ヒューリスティック手法では (一変量の場合や線形の場合とは異なり) 境界条件を推定しないため、ソルバーが期待どおりの出力をしなかったことに混乱するでしょう。
あるいは、線形化戦略を使用したり、rootfind_ZZ を直接適用したりすることもできます。たとえば、これを解決したい場合は、
rootfind_ZZ は必ずしもすべてのルートを検索するわけではなく、少数のルートのみを検索することに注意してください。整数に対するルートを見つけるのは簡単ではないため、複数のルートが含まれるシステムにはこのパッケージを使用しないでください。複数のルートを避けるためにいくつかの方法を考案できます。メソッドによっては、変数を変換することで境界範囲を狭めている可能性があります。一部の rootfind_ZZ 内部関数は、ルートが境界近くに存在することを前提としています。
パッケージは完璧であってはなりません。これを見直して改善してもらいたいと考えています。問題、プルリクエスト、フォークの投稿を歓迎します。また、CTF またはその他のリソースからのtest casesお知らせください。テストケースが失敗すると、パッケージの改善が必要になる場合があります。
コードの一部は次のライブラリに基づいています。
多変量カッパースミスメソッド: coppersmith.sage
多変量銅細工師メソッド: lbc_toolkit/problems/small_roots.sage 。整数多項式ルートの一部のソルバーはlbc_toolkit/common/systems_solvers.sageにあります。
さまざまな銅細工法 (Herrmann-May、Blomer-May、Boneh-Durfee、Jochemsz-May など): shared/small_roots/*.py 。整数多項式ルートの一部のソルバーはshared/small_roots/__init__.pyにあります。
jvdsn/crypto-attachs は次の場所で配布されます。
MIT ライセンス (https://github.com/jvdsn/crypto-attachs/blob/master/LICENSE)
(c) 2020 ヨアヒム・ヴァンダースミッセン。
このライブラリは、Apache 2.0 ライセンスに基づいて配布されます。 「ライセンス」を参照してください。
(C)2023キオナ
https://github.com/kionactf/coppersmith
再配布の場合は、変更されたことを伝え、ファイルへのリンクをメモしてください。
