Unduhan coppersmith - Unduhan kode sumber coppersmith

coppersmith

Kode sumber lainnya

Unduh

Akar kecil tukang tembaga

Metode akar kecil Coppersmith (menyelesaikan persamaan polinomial pada modulus komposit pada batas kecil)

Fitur

beberapa dukungan persamaan tukang tembaga
- polinomial univariat
- polinomial linier multivariat (metode Herrmann-May)
- polinomial multivariat (metode heuristik Jochemsz-May)

Terutama, berurusan dengan persamaan yang dapat diterapkan metode Coppersmith yang ditetapkan secara teoritis. Kami merekomendasikan penggunaan univariat atau linier (bukan heuristik) jika Anda mengetahui jenis persamaannya.

penyetelan parameter otomatis

Pertama pilih parameter yang sesuai berdasarkan batas dan $beta$ , lalu tingkatkan parameter hingga selesai menemukan persamaan bilangan bulat.

metode LLL/BKZ internal yang dapat dipilih
- fplll (LLL/BKZ)
- memuji
- NTL (melalui Sagemath LLL/BKZ)
metode penyelesaian persamaan bilangan bulat yang dapat dipilih
- metode Jacobian Newton (numerik)
- Hensel mengangkat
- triangulasi (dasar Groebner + menangani sebagian ideal dimensi bukan nol)

Instalasi

$ git clone https://github.com/kionactf/coppersmith --sync

Jika Anda menggunakan fplll atau flat, perlu membuat paket-paket ini. jika Anda sudah menginstalnya, Anda dapat menggunakannya dengan mengatur jalur instalasi ini ke fplll_path atau flat_path di lll.py.

Atau Anda dapat membuat gambar buruh pelabuhan. Ini didasarkan pada sagemath/sagemath: gambar terbaru dan juga mengunduh perpustakaan kisi terkenal. (Jika Anda mengetahui perpustakaan lain yang bagus, beri tahu kami untuk menyertakan perpustakaan ini.)

$ docker build -t coppersmith .
$ docker run --rm -it coppersmith /bin/bash

Penggunaan

Panggil coppersmith_onevariable.coppersmith_onevariable atau coppersmith_linear.coppersmith_linear dengan Sagemath PolynomialRing melalui Zmod(N), batas, beta.

Lihat example.py .

Selain itu, Anda hanya dapat menggunakan LLL dengan memanggil lll.do_lattice_reduction dengan matriks Sagemath melalui ZZ dan beberapa parameter pengoptimalan. Dan lll.babai untuk pemecah CVP.

Untuk integer equations solver , gunakan rootfind_ZZ.rootfind_ZZ dengan daftar polinomial Sagemath di atas ZZ dan batas.

Konfigurasi Kustom

(Fitur ini diperkenalkan pada 8/3/2024.)

Meskipun kami menyiapkan pengaturan default bawaan berdasarkan beberapa eksperimen kami, beberapa pengguna mengatakan pengaturan tersebut tidak sesuai dengan lingkungan mereka.

Jadi kami menyiapkan context antarmuka konfigurasi untuk lll.py dan rootfind_ZZ.py .

Anda dapat menggunakannya dengan mengimpor context seperti contoh berikut:

 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 )

Anda dapat memeriksa daftar opsi dan nilai defaultnya di register_options_lll dan register_options_rootfind_ZZ di contextclass.py .

Catatan (use_pari_kernel)

Untuk menghitung LLL, kami menggunakan pari.matker untuk menghilangkan vektor bergantung linier untuk mendefinisikan kisi. Prosesnya perlu menggunakan lebih datar. Meskipun pari.matker cepat dan memberikan hasil yang benar dalam banyak kasus, terkadang ia memberikan hasil wrong . (Anda dapat memeriksanya dengan menjalankan lll.test().) Anda dapat menonaktifkan penggunaan pari.matker dengan menyetel opsi use_pari_kernel=False , yang memaksa penggunaan kernel Sagemath (yang menjalankan komputasi hermite normal form (HNF) secara internal.) Perhatikan bahwa HNF cenderung menghasilkan elemen yang besar, sehingga menyebabkan proses LLL menjadi super lambat.

Latar belakang

Lihat Mengapa kami tidak dapat mengatasi chronophobia… Analisis untuk metode Coppersmith selengkapnya. (meskipun ini mungkin artikel lama.)

Bagaimana cara memilih parameter?

Metode akar kecil Coppersmith adalah mencari akar dari persamaan tipe berikut:

$f(r_1,ldots,r_n)=0 pmod{b}$ , Di mana $| r_i | < X_i (i=1,ltitik,n)$ , untuk polinomial yang diketahui $f(r)$ dan diketahui $N$ seperti yang $b | N$ .

Fungsi paket memerlukan parameter berikut.

basepoly: polinomial $f(r)$ lebih dari Zmod( $N$ )
batas: daftar $[X_1,ltitik,X_n]$ yang bilangan bulat positifnya $X_1,ltitik,X_n$
beta: bilangan floating point positif $beta$ seperti yang $b ge N^beta$

Untuk menentukan $beta$ , kami merekomendasikan pedoman berikut.

Jika $b$ diketahui, kalau begitu $beta=log_{N}(b)$
Jika $b$ tidak diketahui tetapi berukuran bit $b$ diketahui, kalau begitu $beta=(text{ukuran bit}(b)-1)/(teks{ukuran bit}(N))$

Misalnya, $N=pq$ Dan $teks{ukuran bit}(p)=teks{ukuran bit}(q)$ , Kemudian $betasimeq 0,499$ .

Kelengkapan Paket

T: Bisakah Anda menyelesaikan banyak sistem polinomial multivariat modulus berdasarkan paketnya?

J: Mungkin tidak. Tampaknya sulit untuk membuat pemecah polinomial multivariat modulus umum. Itu tergantung pada monomial (seperti [ $f=ax^2 + oleh + c$ ] vs [ $g=kapak^2 + bxy + cy + d$ ]), koefisien (seperti [ $f=ax^2-oleh+c$ ] vs [ $g=kapak^2-ay+c$ ]), dan batasan (seperti [ $X simeq Y$ ] vs [ $X simeq Y^2$ ]). Banyak surat kabar menangani setiap kasus tertentu.

Secara khusus, kami tidak menyarankan penggunaan metode heuristik tanpa memahami polinomial. Metode heuristik tidak memperkirakan kondisi terikat (tidak seperti kasus univariat atau kasus linier), sehingga Anda akan bingung karena pemecahnya tidak menghasilkan keluaran seperti yang Anda harapkan.

Alternatifnya, Anda dapat menggunakan strategi linearisasi dan/atau menerapkan rootfind_ZZ secara langsung. Misalnya saja jika Anda ingin menyelesaikannya $f=ax^2+oleh pmod{N}$ , tentukan dulu ${f_mathbb{Z}}=ax'+by+kN in mathbb{Z}[x',y,k]$ , lalu terapkan rootfind_ZZ (atau pemecah polinomial bilangan bulat lainnya) dengan terikat $[X^2, Y]$ (kami mencari $k$ dengan kekerasan). Jika kita bisa berasumsi $|k|$ kecil, sistem akan terpecahkan. Perhatikan bahwa metode Coppersmith tidak serta merta menemukan himpunan polinomial yang bebas secara aljabar. Jadi, Anda mungkin harus menyelesaikan sistem polinomial yang sama $f_mathbb{Z}$ bahkan jika kamu terpaksa menerapkan metode Coppersmith. rootfind_ZZ.solve_root_triangulate mencoba menyelesaikan sistem linier berdimensi bukan nol.

Perhatikan bahwa rootfind_ZZ tidak serta merta menemukan semua akar, tetapi hanya beberapa akar. Menemukan akar dari bilangan bulat tidaklah mudah, jadi Anda sebaiknya tidak menggunakan paket untuk sistem yang menyertakan banyak akar. Anda dapat merancang beberapa metode untuk menghindari banyak akar. Beberapa metode mungkin mempersempit rentang batas dengan mengonversi variabel. Beberapa fungsi internal rootfind_ZZ mengasumsikan bahwa akar ada di dekat batas.

Kontribusi

Paketnya tidak boleh sempurna, kami ingin Anda meninjau dan memperbaikinya. Selamat datang untuk memposting masalah apa pun, permintaan tarik, dan garpu. Dan beri tahu kami test cases dari KKP atau sumber lainnya. Kasus uji yang gagal mungkin membuat kami memperbaiki paketnya.

Referensi

Beberapa kode kami didasarkan pada perpustakaan berikut.

defund/coppersmith (https://github.com/defund/coppersmith)

metode tukang tembaga multivariat: coppersmith.sage

kriptanalisis berbasis josephsurinlattice (https://github.com/josephsurin/lattice-based-cryptanalisis)

metode tukang tembaga multivariat: lbc_toolkit/problems/small_roots.sage . Beberapa pemecah akar polinomial bilangan bulat ada di lbc_toolkit/common/systems_solvers.sage .

jvdsn/crypto-actions (https://github.com/jvdsn/crypto-actions)

berbagai metode tukang tembaga (termasuk Herrmann-May, Blomer-May, Boneh-Durfee, Jochemsz-May, dll.): shared/small_roots/*.py . Beberapa pemecah akar polinomial bilangan bulat ada di shared/small_roots/__init__.py .

jvdsn/crypto-serangan didistribusikan di bawah: