Descarga coppersmith - Descarga del código fuente coppersmith

coppersmith

Otro código fuente

Descargar

Calderero raíces pequeñas

Método de raíces pequeñas del calderero (resolución de ecuaciones polinomiales sobre módulo compuesto en límites pequeños)

Características

soporte de ecuaciones múltiples de calderero
- polinomio univariado
- polinomio lineal multivariado (método de Herrmann-May)
- polinomio multivariado (método heurístico de Jochemsz-May)

Principalmente, se trata de la ecuación aplicable al método Calderero teóricamente establecido. Recomendamos utilizar univariante o lineal (en lugar de heurístico) si conoce el tipo de ecuación.

ajuste automático de parámetros

En primer lugar, elija los parámetros adecuados en función de los límites y $beta$ y luego incremente los parámetros hasta terminar para encontrar una ecuación entera.

método interno LLL/BKZ seleccionable
- fplll (LLL/BKZ)
- halagar
- NTL (a través de Sagemath LLL/BKZ)
Método de resolución de ecuaciones enteras seleccionable.
- método jacobiano de Newton (numérico)
- levantamiento hensel
- triangulación (base de Groebner + tratamiento parcial del ideal de dimensión distinta de cero)

Instalación

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

Si usa fplll o flatter, necesitará crear estos paquetes. Si ya los instaló, puede usarlos configurando estas rutas de instalación en fplll_path o flatter_path en lll.py.

O puedes crear una imagen acoplable. Se basa en sagemath/sagemath:latest image y también descarga bibliotecas de celosía conocidas. (Si conoce otras bibliotecas interesantes, háganoslo saber para incluirlas).

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

Uso

Llame a coppersmith_onevariable.coppersmith_onevariable o coppersmith_linear.coppersmith_linear con Sagemath PolynomialRing sobre Zmod(N), límites, beta.

Ver example.py .

Además, puede usar solo LLL llamando a lll.do_lattice_reduction con la matriz Sagemath sobre ZZ y algunos parámetros de optimización. Y lll.babai para el solucionador de CVP.

Para integer equations solver , use rootfind_ZZ.rootfind_ZZ con una lista de polinomios de Sagemath sobre ZZ y límites.

Configuración personalizada

(La función se introdujo el 8/3/2024).

Aunque configuramos configuraciones predeterminadas integradas basadas en algunos experimentos, algunos usuarios dicen que la configuración no se adapta a sus entornos.

Entonces preparamos un context de interfaz de configuración para lll.py y rootfind_ZZ.py .

Puede usarlo importando context como en el siguiente ejemplo:

 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 )

Puede consultar la lista de opciones y sus valores predeterminados en register_options_lll y register_options_rootfind_ZZ en contextclass.py .

Nota (use_pari_kernel)

Para calcular LLL, utilizamos pari.matker para eliminar vectores linealmente dependientes para definir la red. El proceso necesita ser más plano. Aunque pari.matker es rápido y genera resultados correctos en muchos casos, a veces genera resultados wrong . (Puede comprobar esto ejecutando lll.test().) Puede desactivar el uso de pari.matker configurando la opción use_pari_kernel=False , donde fuerza el uso del kernel Sagemath (que ejecuta internamente la forma normal de Hermite Computing (HNF).) Tenga en cuenta que HNF tiende a producir elementos grandes, por lo que hace que el proceso LLL sea muy lento.

Fondo

Ver Por qué no pudimos resolver la cronofobia… Análisis del método Coppersmith más. (Aunque podría ser un artículo antiguo).

¿Cómo elegir los parámetros?

El método de raíz pequeña del calderero consiste en encontrar una raíz de la siguiente ecuación de tipo:

$f(r_1,ldots,r_n)=0 pmod{b}$ , dónde $| r_i | < X_i (i=1,ldots,n)$ , para polinomio conocido $f(r)$ y conocido $N$ tal que $b | N$ .

La función del paquete requiere los siguientes parámetros.

basepoly: el polinomio $f(r)$ sobre Zmod( $N$ )
límites: la lista $[X_1,ldots,X_n]$ cuyos enteros positivos $X_1,lpuntos,X_n$
beta: un número de punto flotante positivo $beta$ tal que $b ge N^beta$

Para determinar $beta$ , recomendamos la siguiente pauta.

Si $b$ se sabe, entonces $beta=log_{N}(b)$
Si $b$ se desconoce pero el tamaño de bits de $b$ se sabe, entonces $beta=(text{tamaño de bits}(b)-1)/(text{tamaño de bits}(N))$

Por ejemplo, $N=pq$ y $text{tamaño de bits}(p)=text{tamaño de bits}(q)$ , entonces $betasimeq 0.499$ .

Integridad del paquete

P: ¿Puedes resolver muchos sistemas polinomiales multivariados de módulo mediante el paquete?

R: Quizás no. Parece difícil crear un solucionador polinómico multivariado de módulo general. Depende de monomios (como [ $f=ax^2 + por + c$ ] vs [ $g=ax^2 + bxy + cy + d$ ]), coeficientes (como [ $f=ax^2-por+c$ ] vs [ $g=ax^2-ay+c$ ]), y límites (como [ $X simeq Y$ ] vs [ $X simeq Y^2$ ]). Muchos periódicos abordan cada caso específico.

Especialmente, no recomendamos utilizar el método heurístico sin comprender el polinomio. El método heurístico no estima la condición ligada (a diferencia del caso univariado o el caso lineal), por lo que se confundiría si el solucionador no arrojara el resultado esperado.

Alternativamente, puede utilizar una estrategia de linealización y/o aplicar rootfind_ZZ directamente. Por ejemplo, si quieres resolver $f=ax^2+por pmod{N}$ , primero define ${f_mathbb{Z}}=ax'+por+kN in mathbb{Z}[x',y,k]$ , luego aplique rootfind_ZZ (u otro solucionador de polinomios enteros) con límite $[X^2,Y]$ (buscamos $k$ con fuerza bruta). Si podemos suponer $|k|$ es pequeño, el sistema se resolverá. Tenga en cuenta que los métodos de Coppersmith no necesariamente encuentran conjuntos de polinomios algebraicamente independientes. Entonces quizás tengas que resolver el mismo sistema polinomial. $f_mathbb{Z}$ incluso si te obligaste a aplicar el método Coppersmith. rootfind_ZZ.solve_root_triangulate intenta resolver un sistema lineal de dimensiones distintas de cero.

Tenga en cuenta que rootfind_ZZ no necesariamente encuentra todas las raíces, sino solo unas pocas raíces. Encontrar raíces sobre números enteros no es fácil, por lo que no debe utilizar el paquete para el sistema incluido de raíces múltiples. Puede idear algunos métodos para evitar raíces múltiples. Algún método podría ser reducir el rango de límites mediante la conversión de variables. Algunas funciones internas de rootfind_ZZ suponen que existe una raíz cerca de los límites.

Contribución

El paquete no debe ser perfecto, queremos que lo revises y lo mejores. Bienvenido a publicar cualquier problema, solicitud de extracción y bifurcación. Y háganos saber test cases de cualquier CTF u otros recursos. Los casos de prueba fallidos pueden obligarnos a mejorar el paquete.

Referencia

Algunos de nuestros códigos se basan en las siguientes bibliotecas.

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

método multivariante de calderero: coppersmith.sage

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

método multivariante de calderero: lbc_toolkit/problems/small_roots.sage . Algunos solucionadores de raíces polinómicas enteras se encuentran en lbc_toolkit/common/systems_solvers.sage .

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

varios métodos de calderería (incluidos Herrmann-May, Blomer-May, Boneh-Durfee, Jochemsz-May, etc.): shared/small_roots/*.py . Algunos solucionadores de raíces polinómicas enteras se encuentran shared/small_roots/__init__.py .

jvdsn/crypto-attacks se distribuye en: