coppersmith Download - coppersmith Quellcode herunterladen

coppersmith

Anderer Quellcode

Herunterladen

Kupferschmied kleine Wurzeln

Coppersmith-Methode mit kleinen Wurzeln (Lösen einer Polynomgleichung über einen zusammengesetzten Modul auf kleinen Grenzen)

Merkmale

Unterstützung mehrerer Coppersmith-Gleichung
- univariates Polynom
- multivariates lineares Polynom (Herrmann-May-Methode)
- multivariates Polynom (heuristische Methode nach Jochemsz-May)

Beschäftigt sich hauptsächlich mit der theoretisch etablierten Coppersmith-Methode und anwendbaren Gleichungen. Wenn Sie die Art der Gleichung kennen, empfehlen wir die Verwendung einer univariaten oder linearen Gleichung (statt einer Heuristik).

automatisierte Parameterabstimmung

Wählen Sie zunächst geeignete Parameter basierend auf Grenzen und aus $beta$ , und erhöhen Sie dann die Parameter, bis Sie fertig sind, um eine ganzzahlige Gleichung zu finden.

wählbare interne LLL/BKZ-Methode
- fplll (LLL/BKZ)
- schmeicheln
- NTL (über Sagemath LLL/BKZ)
wählbare Lösungsmethode für ganzzahlige Gleichungen
- jakobianische Newton-Methode (numerisch)
- Hensel-Hebung
- Triangulation (Groebner-Basis + teilweise Umgang mit nicht-nulldimensionalen Idealen)

Installation

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

Wenn Sie fplll oder flatter verwenden, müssen Sie diese Pakete erstellen. Wenn Sie sie bereits installiert haben, können Sie dies verwenden, indem Sie diese Installationspfade auf lll.py auf fplll_path oder flatter_path festlegen.

Oder Sie können ein Docker-Image erstellen. Es basiert auf sagemath/sagemath:latest image und lädt auch bekannte Lattice-Bibliotheken herunter. (Wenn Sie gute andere Bibliotheken kennen, lassen Sie es uns wissen, damit wir diese einbeziehen können.)

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

Verwendung

Rufen Sie coppersmith_onevariable.coppersmith_onevariable oder coppersmith_linear.coppersmith_linear mit Sagemath PolynomialRing über Zmod(N), Grenzen, Beta auf.

Siehe example.py .

Sie können auch nur LLL verwenden, indem Sie lll.do_lattice_reduction mit der Sagemath-Matrix über ZZ und einigen Optimierungsparametern aufrufen. Und lll.babai für CVP-Löser.

Verwenden Sie für integer equations solver rootfind_ZZ.rootfind_ZZ mit einer Liste von Sagemath-Polynomen über ZZ und Grenzen.

Benutzerdefinierte Konfiguration

(Die Funktion wurde am 08.03.2024 eingeführt.)

Obwohl wir auf der Grundlage einiger unserer Experimente integrierte Standardeinstellungen eingerichtet haben, sagen einige Benutzer, dass die Einstellung nicht zu ihren Umgebungen passt.

Deshalb bereiten wir einen context für lll.py und rootfind_ZZ.py vor.

Sie können es verwenden, indem Sie context wie im folgenden Beispiel importieren:

 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 )

Sie können die Liste der Optionen und ihre Standardwerte unter register_options_lll und register_options_rootfind_ZZ unter contextclass.py überprüfen.

Hinweis (use_pari_kernel)

Zur Berechnung von LLL verwenden wir pari.matker, um linear abhängige Vektoren zur Definition des Gitters zu eliminieren. Der Prozess muss flacher sein. Obwohl pari.matker schnell ist und in vielen Fällen korrekte Ergebnisse ausgibt, gibt es manchmal wrong Ergebnisse aus. (Sie können dies überprüfen, indem Sie lll.test() ausführen.) Sie können die Verwendung von pari.matker deaktivieren, indem Sie die Option use_pari_kernel=False festlegen, wodurch die Verwendung des Sagemath-Kernels erzwungen wird (der intern die Berechnung der Hermite-Normalform (HNF) ausführt). Beachten Sie, dass HNF dazu neigt, große Elemente zu produzieren, was dazu führt, dass der LLL-Prozess sehr langsam wird.

Hintergrund

Weitere Informationen finden Sie unter Warum wir Chronophobie nicht lösen konnten… Analyse für die Coppersmith-Methode. (Es könnte sich jedoch um einen alten Artikel handeln.)

Wie wähle ich Parameter aus?

Die Methode der kleinen Wurzel von Coppersmith besteht darin, eine Wurzel der folgenden Gleichung zu finden:

$f(r_1,ldots,r_n)=0 pmod{b}$ , Wo $| r_i | < X_i (i=1,ldots,n)$ , für bekanntes Polynom $f(r)$ und bekannt $N$ so dass $b | N$ .

Die Paketfunktion erfordert die folgenden Parameter.

basepoly: das Polynom $f(r)$ über Zmod( $N$ )
Grenzen: die Liste $[X_1,ldots,X_n]$ deren positive ganze Zahlen $X_1,ldots,X_n$
Beta: eine positive Gleitkommazahl $beta$ so dass $b ge N^beta$

Zur Bestimmung $beta$ , empfehlen wir die folgende Richtlinie.

Wenn $b$ ist also bekannt $beta=log_{N}(b)$
Wenn $b$ ist unbekannt, aber die Bitgröße von $b$ ist also bekannt $beta=(text{bitsize}(b)-1)/(text{bitsize}(N))$

Zum Beispiel, $N=pq$ Und $text{bitsize}(p)=text{bitsize}(q)$ , Dann $betasimeq 0,499$ .

Vollständigkeit des Pakets

F: Können Sie mit dem Paket viele modulo-multivariate Polynomsysteme lösen?

A: Vielleicht nein. Es scheint schwierig zu sein, einen multivariaten Polynomlöser mit allgemeinem Modul zu erstellen. Es hängt von Monomen ab (z. B. [ $f=ax^2 + by + c$ ] vs [ $g=ax^2 + bxy + cy + d$ ]), Koeffizienten (z. B. [ $f=ax^2-by+c$ ] vs [ $g=ax^2-ay+c$ ]) und Grenzen (z. B. [ $X simeq Y$ ] vs [ $X simeq Y^2$ ]). Viele Artikel behandeln jeweils spezifische Fälle.

Insbesondere empfehlen wir nicht, die heuristische Methode zu verwenden, ohne das Polynom zu verstehen. Die heuristische Methode schätzt die gebundene Bedingung nicht (im Gegensatz zum univariaten oder linearen Fall), sodass Sie verwirrt wären, wenn der Löser nicht das Ergebnis lieferte, das Sie erwartet hatten.

Alternativ können Sie die Linearisierungsstrategie verwenden und/oder rootfind_ZZ direkt anwenden. Zum Beispiel, wenn Sie lösen möchten $f=ax^2+by pmod{N}$ , zuerst definieren ${f_mathbb{Z}}=ax'+by+kN in mathbb{Z}[x',y,k]$ , dann wenden Sie rootfind_ZZ (oder einen anderen ganzzahligen Polynomlöser) mit gebunden an $[X^2, Y]$ (wir suchen $k$ mit Bruteforce). Wenn wir davon ausgehen können $|k|$ ist klein, das System wird gelöst. Beachten Sie, dass Coppersmith-Methoden nicht unbedingt algebraisch unabhängige Polynommengen finden. Daher müssen Sie möglicherweise dasselbe Polynomsystem lösen $f_mathbb{Z}$ selbst wenn Sie gezwungen sind, die Coppersmith-Methode anzuwenden. rootfind_ZZ.solve_root_triangulate versucht, ein nicht nulldimensionales lineares System zu lösen.

Beachten Sie, dass rootfind_ZZ nicht unbedingt alle Wurzeln findet, sondern nur einige wenige Wurzeln. Das Finden von Wurzeln über Ganzzahlen ist nicht einfach, daher sollten Sie das Paket nicht für Systeme mit mehreren Wurzeln verwenden. Sie können einige Methoden zur Vermeidung mehrerer Wurzeln entwickeln. Bei einigen Methoden kann es sein, dass der Grenzwertbereich durch die Konvertierung von Variablen eingeschränkt wird. Einige interne Funktionen von rootfind_ZZ gehen davon aus, dass eine Wurzel in der Nähe von Grenzen existiert.

Beitrag

Das Paket muss nicht perfekt sein, wir möchten, dass Sie es überprüfen und verbessern. Willkommen zum Posten von Problemen, Pull-Requests und Forks. Und teilen Sie uns test cases von CTF oder anderen Ressourcen mit. Fehlgeschlagene Testfälle können uns dazu veranlassen, das Paket zu verbessern.

Referenz

Einige unserer Codes basieren auf den folgenden Bibliotheken.

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

Multivariate Kupferschmiedemethode: coppersmith.sage

josephsurinlattice-based-cryptanalysis (https://github.com/josephsurin/lattice-based-cryptanalysis)

Multivariate Kupferschmied-Methode: lbc_toolkit/problems/small_roots.sage . Einige Löser für ganzzahlige Polynomwurzeln finden Sie unter lbc_toolkit/common/systems_solvers.sage .

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

verschiedene Kupferschmiedemethoden (einschließlich Herrmann-May, Blomer-May, Boneh-Durfee, Jochemsz-May usw.): shared/small_roots/*.py . Einige Löser für ganzzahlige Polynomwurzeln finden Sie unter shared/small_roots/__init__.py .

jvdsn/crypto-attacks wird vertrieben unter: