download coppersmith - download do código-fonte coppersmith

coppersmith

Outro código-fonte

Baixar

Raízes pequenas de latoeiro

Método de raízes pequenas de Coppersmith (resolvendo equações polinomiais sobre módulo composto em limites pequenos)

Características

suporte a múltiplas equações de cobreiro
- polinômio univariado
- polinômio linear multivariado (método Herrmann-May)
- polinômio multivariado (método heurístico Jochemsz-May)

Principalmente, lidando com a equação aplicável do método Coppersmith teoricamente estabelecida. Recomendamos usar univariada ou linear (em vez de heurística) se você conhece o tipo de equação.

ajuste automatizado de parâmetros

Em primeiro lugar, escolha parâmetros adequados com base em limites e $beta$ e, em seguida, incremente os parâmetros até terminar para encontrar uma equação inteira.

método LLL/BKZ interno selecionável
- fplll (LLL/BKZ)
- embelezar
- NTL (via Sagemath LLL/BKZ)
método de equação inteira de resolução selecionável
- método jacobiano de Newton (numérico)
- Levantamento Hensel
- triangulação (base de Groebner + lidar parcialmente com ideal de dimensão diferente de zero)

Instalação

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

Se você usa fplll ou flatter, precisa compilar esses pacotes. se você já os instalou, poderá usar isso definindo esses caminhos de instalação como fplll_path ou flatter_path em lll.py.

Ou você pode criar uma imagem docker. É baseado na imagem sagemath/sagemath:latest e também baixa bibliotecas de treliça bem conhecidas. (Se você conhece outras bibliotecas boas, informe-nos para incluí-las.)

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

Uso

Chame coppersmith_onevariable.coppersmith_onevariable ou coppersmith_linear.coppersmith_linear com Sagemath PolynomialRing sobre Zmod(N), limites, beta.

Veja example.py .

Além disso, você pode usar apenas LLL chamando lll.do_lattice_reduction com matriz Sagemath sobre ZZ e alguns parâmetros de otimização. E lll.babai para solucionador de CVP.

Para integer equations solver , use rootfind_ZZ.rootfind_ZZ com uma lista de polinômios Sagemath sobre ZZ e limites.

Configuração personalizada

(O recurso foi introduzido em 8/03/2024.)

Embora tenhamos definido configurações padrão integradas com base em alguns experimentos, alguns usuários dizem que a configuração não se ajusta aos seus ambientes.

Portanto, preparamos um context de interface de configuração para lll.py e rootfind_ZZ.py .

Você pode usá-lo importando context assim como no exemplo a seguir:

 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 )

Você pode verificar a lista de opções e seus valores padrão em register_options_lll e register_options_rootfind_ZZ em contextclass.py .

Nota (use_pari_kernel)

Para calcular LLL, usamos pari.matker para eliminar vetores linearmente dependentes para definir a rede. O processo precisa ser mais plano. Embora pari.matker seja rápido e produza resultados corretos em muitos casos, às vezes produz resultados wrong . (Você pode verificar isso executando lll.test().) Você pode desabilitar o uso de pari.matker definindo a opção use_pari_kernel=False , onde força o uso do kernel Sagemath (que executa internamente a computação da forma normal hermite (HNF).) Observe que o HNF tende a produzir elementos grandes, por isso faz com que o processo LLL fique super lento.

Fundo

Veja Por que não conseguimos resolver a cronofobia… Análise para o método Coppersmith mais. (pode ser um artigo antigo, no entanto.)

Como escolher parâmetros?

O método da raiz pequena de Coppersmith consiste em encontrar uma raiz do seguinte tipo de equação:

$f(r_1,ldots,r_n)=0 pmod{b}$ , onde $| r_i | < X_i (i=1,ldots,n)$ , para polinômio conhecido $f(r)$ e conhecido $N$ tal que $b |N$ .

A função de pacote requer os seguintes parâmetros.

basepoli: o polinômio $f(r)$ sobre Zmod( $N$ )
limites: a lista $[X_1,ldots,X_n]$ cujos inteiros positivos $X_1,ldots,X_n$
beta: um número de ponto flutuante positivo $beta$ tal que $b ge N^beta$

Para determinar $beta$ , recomendamos a seguinte diretriz.

Se $b$ é conhecido, então $beta=log_{N}(b)$
Se $b$ é desconhecido, mas o tamanho do bit $b$ é conhecido, então $beta=(text{tamanho de bits}(b)-1)/(text{tamanho de bits}(N))$

Por exemplo, $N=pq$ e $text{tamanho de bits}(p)=text{tamanho de bits}(q)$ , então $betasimeq 0,499$ .

Completude do Pacote

P: Você pode resolver muitos sistemas polinomiais multivariados de módulo pelo pacote?

R: Talvez não. Parece ser difícil criar um solucionador polinomial multivariado de módulo geral. Depende de monômios (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$ ]) e limites (como [ $X simeq Y$ ] vs [ $X simeq Y^2$ ]). Muitos artigos tratam de cada caso específico.

Especialmente, não recomendamos o uso do método heurístico sem compreender o polinômio. O método heurístico não estima a condição vinculada (ao contrário do caso univariado ou do caso linear), portanto, você ficaria confuso se o solucionador não produzisse o resultado esperado.

Alternativamente, você pode usar a estratégia de linearização e/ou aplicar rootfind_ZZ diretamente. Por exemplo, se você quiser resolver $f=ax^2+por pmod{N}$ , primeiro defina ${f_mathbb{Z}}=ax'+by+kN in mathbb{Z}[x',y,k]$ , em seguida, aplique rootfind_ZZ (ou outro solucionador polinomial inteiro) com limite $[X^2, Y]$ (procuramos $k$ com força bruta). Se pudermos assumir $|k|$ for pequeno, o sistema estará resolvido. Observe que os métodos de Coppersmith não encontram necessariamente conjuntos polinomiais algebricamente independentes. Então você pode ter que resolver o mesmo sistema polinomial $f_mathbb{Z}$ mesmo se você for forçado a aplicar o método Coppersmith. rootfind_ZZ.solve_root_triangulate tenta resolver um sistema linear de dimensão diferente de zero.

Observe que rootfind_ZZ não encontra necessariamente todas as raízes, mas apenas algumas raízes. Encontrar raízes sobre números inteiros não é fácil, então você não deve usar o pacote para sistema incluído com múltiplas raízes. Você pode desenvolver alguns métodos para evitar raízes múltiplas. Algum método pode estar estreitando o intervalo dos limites convertendo variáveis. Algumas funções internas rootfind_ZZ assumem que existe uma raiz próxima aos limites.

Contribuição

O pacote não deve ser perfeito, queremos que você o revise e melhore. Bem-vindo a postar quaisquer problemas, pull requests e forks. E conte-nos test cases de qualquer CTF ou outros recursos. Casos de teste com falha podem nos levar a melhorar o pacote.

Referência

Alguns de nossos códigos são baseados nas seguintes bibliotecas.

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

método multivariado de caldeireiro: coppersmith.sage

Criptoanálise baseada em josephsurinlattice (https://github.com/josephsurin/lattice-based-cryptanálise)

método multivariado de latoeiro: lbc_toolkit/problems/small_roots.sage . Alguns solucionadores para raízes polinomiais inteiras estão em lbc_toolkit/common/systems_solvers.sage .

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

vários métodos de latoeiro (incluindo Herrmann-May, Blomer-May, Boneh-Durfee, Jochemsz-May, etc.): shared/small_roots/*.py . Alguns solucionadores para raízes polinomiais inteiras estão em shared/small_roots/__init__.py .

jvdsn/crypto-attacks é distribuído em: