coppersmith Télécharger - coppersmith Code source télécharger

coppersmith

Autre code source

Télécharger

Petites racines de chaudronnier

Méthode des petites racines de Coppersmith (résolution d'équations polynomiales sur le module composite sur de petites limites)

Caractéristiques

prise en charge de plusieurs équations de chaudronnier
- polynôme univarié
- polynôme linéaire multivarié (méthode Herrmann-May)
- polynôme multivarié (méthode heuristique de Jochemsz-May)

Principalement, il s'agit de l'équation applicable de la méthode Coppersmith théoriquement établie. Nous vous recommandons d'utiliser une équation univariée ou linéaire (au lieu d'une heuristique) si vous connaissez le type d'équation.

réglage automatisé des paramètres

Choisissez d’abord les paramètres appropriés en fonction des limites et $bêta$ , puis incrémentez les paramètres jusqu'à terminer pour trouver une équation entière.

méthode LLL/BKZ interne sélectionnable
- fplll (LLL/BKZ)
- flatter
- NTL (via Sagemath LLL/BKZ)
méthode de résolution d'équations entières sélectionnable
- méthode jacobienne de Newton (numérique)
- Hensel levage
- triangulation (base de Groebner + traitement partiel de l'idéal de dimension non nulle)

Installation

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

Si vous utilisez fplll ou plus plat, vous devez créer ces packages. si vous les avez déjà installés, vous pouvez l'utiliser en définissant ces chemins d'installation sur fplll_path ou flatter_path sur lll.py.

Ou vous pouvez créer une image Docker. Il est basé sur sagemath/sagemath:latest image et télécharge également des bibliothèques de treillis bien connues. (Si vous connaissez d'autres bibliothèques, faites-le-nous savoir pour les inclure.)

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

Usage

Appelez coppersmith_onevariable.coppersmith_onevariable ou coppersmith_linear.coppersmith_linear avec Sagemath PolynomialRing sur Zmod(N), limites, bêta.

Voir example.py .

De plus, vous pouvez utiliser uniquement LLL en appelant lll.do_lattice_reduction avec la matrice Sagemath sur ZZ et certains paramètres d'optimisation. Et lll.babai pour le solveur CVP.

Pour integer equations solver , utilisez rootfind_ZZ.rootfind_ZZ avec une liste de polynômes Sagemath sur ZZ et ses limites.

Configuration personnalisée

(La fonctionnalité a été introduite le 2024/3/8.)

Bien que nous ayons configuré des paramètres par défaut intégrés sur la base de nos expériences, certains utilisateurs affirment que ces paramètres ne conviennent pas à leur environnement.

Nous préparons donc un context d'interface de configuration pour lll.py et rootfind_ZZ.py .

Vous pouvez l'utiliser en important context comme dans l'exemple suivant :

 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 )

Vous pouvez consulter la liste des options et leurs valeurs par défaut sur register_options_lll et register_options_rootfind_ZZ sur contextclass.py .

Remarque (use_pari_kernel)

Pour le calcul de LLL, nous utilisons pari.matker pour éliminer les vecteurs linéairement dépendants afin de définir le réseau. Le processus doit utiliser plus plat. Bien que pari.matker soit rapide et génère des résultats corrects dans de nombreux cas, il génère parfois des résultats wrong . (Vous pouvez vérifier cela en exécutant lll.test().) Vous pouvez désactiver l'utilisation de pari.matker en définissant l'option use_pari_kernel=False , où elle force l'utilisation du noyau Sagemath (qui exécute en interne la forme normale Hermite informatique (HNF).) Notez que HNF a tendance à produire de gros éléments, ce qui rend le processus LLL très lent.

Arrière-plan

Voir Pourquoi nous n'avons pas pu résoudre la chronophobie… Analyse pour la méthode Coppersmith plus. (cela pourrait être un vieil article, cependant.)

Comment choisir les paramètres ?

La méthode des petites racines de Coppersmith consiste à trouver une racine de l'équation de type suivante :

$f(r_1,ldots,r_n)=0 pmod{b}$ , où $| r_i | &Lt ; X_i (i=1,ldots,n)$ , pour un polynôme connu $f(r)$ et connu $N$ tel que $b |N$ .

La fonction package nécessite les paramètres suivants.

basepoly : le polynôme $f(r)$ sur Zmod ( $N$ )
limites : la liste $[X_1,ldots,X_n]$ dont les entiers positifs $X_1,ldots,X_n$
bêta : un nombre à virgule flottante positif $bêta$ tel que $b ge N^bêta$

Pour déterminer $bêta$ , nous recommandons la ligne directrice suivante.

Si $b$ est connu, alors $bêta=log_{N}(b)$
Si $b$ est inconnu mais la taille de $b$ est connu, alors $beta=(text{bitsize}(b)-1)/(text{bitsize}(N))$

Par exemple, $N=pq$ et $text{bitsize}(p)=text{bitsize}(q)$ , alors $bêtasimeq 0,499$ .

exhaustivité du package

Q : Pouvez-vous résoudre de nombreux systèmes polynomiaux multivariés de module à l’aide du package ?

R : Peut-être que non. Il semble difficile de créer un solveur polynomial multivarié de module général. Cela dépend des monômes (tels que [ $f=ax^2 + par + c$ ] vs [ $g=ax^2 + bxy + cy + d$ ]), des coefficients (tels que [ $f=ax^2-par+c$ ] vs [ $g=ax^2-ay+c$ ]), et les limites (telles que [ $X simeq Y$ ] vs [ $X simeq Y^2$ ]). De nombreux articles traitent de chaque cas spécifique.

En particulier, nous déconseillons d’utiliser la méthode heuristique sans comprendre le polynôme. La méthode heuristique n'estime pas la condition liée (contrairement au cas univarié ou au cas linéaire), vous seriez donc confus si le solveur n'a pas produit le résultat attendu.

Alternativement, vous pouvez utiliser une stratégie de linéarisation et/ou appliquer directement rootfind_ZZ. Par exemple, si vous souhaitez résoudre $f=ax^2+par pmod{N}$ , définissez d'abord ${f_mathbb{Z}}=ax'+by+kN in mathbb{Z}[x',y,k]$ , puis appliquez rootfind_ZZ (ou un autre solveur polynomial entier) avec une limite $[X^2, Y]$ (on cherche $k$ avec la force brute). Si l'on peut supposer $|k|$ est petit, le système sera résolu. Notez que les méthodes Coppersmith ne trouvent pas nécessairement des ensembles polynomiaux algébriquement indépendants. Vous devrez donc peut-être résoudre le même système polynomial $f_mathbb{Z}$ même si vous êtes obligé d'appliquer la méthode Coppersmith. rootfind_ZZ.solve_root_triangulate essaie de résoudre un système linéaire de dimension non nulle.

Notez que rootfind_ZZ ne trouve pas nécessairement toutes les racines, mais seulement quelques racines. Trouver des racines sur un nombre entier n'est pas facile, vous ne devez donc pas utiliser le package pour le système inclus avec plusieurs racines. Vous pouvez concevoir des méthodes pour éviter plusieurs racines. Une méthode peut consister à réduire la plage des limites en convertissant des variables. Certaines fonctions internes de rootfind_ZZ supposent qu'une racine existe à proximité des limites.

Contribution

Le package ne doit pas être parfait, nous souhaitons que vous le revoyiez et l’amélioriez. Bienvenue pour publier tous les problèmes, demandes d'extraction et forks. Et faites-nous part test cases de n'importe quel CTF ou d'autres ressources. Les cas de test échoués peuvent nous amener à améliorer le package.

Référence

Certains de nos codes sont basés sur les bibliothèques suivantes.

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

méthode de chaudronnerie multivariée : coppersmith.sage

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

méthode Coppersmith multivariée : lbc_toolkit/problems/small_roots.sage . Certains solveurs pour les racines polynomiales entières se trouvent sur lbc_toolkit/common/systems_solvers.sage .

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

diverses méthodes de chaudronnerie (dont Herrmann-May, Blomer-May, Boneh-Durfee, Jochemsz-May, etc.) : shared/small_roots/*.py . Certains solveurs pour les racines polynomiales entières se trouvent sur shared/small_roots/__init__.py .

jvdsn/crypto-attacks est distribué sous :