coppersmith 다운로드 - coppersmith 소스 코드 다운로드

coppersmith

기타 소스코드

다운로드

구리 세공인 작은 뿌리

Coppersmith 작은 뿌리 방법(작은 경계의 복합 계수에 대한 다항 방정식 풀기)

특징

다중 구리세공 방정식 지원
- 일변량 다항식
- 다변량 선형 다항식(Herrmann-May 방법)
- 다변량 다항식(Jochemsz-May 휴리스틱 방법)

주로 이론적으로 확립된 Coppersmith 방법을 적용할 수 있는 방정식을 다룬다. 방정식 유형을 알고 있는 경우 일변량 또는 선형(휴리스틱 대신)을 사용하는 것이 좋습니다.

자동화된 매개변수 튜닝

먼저 경계를 기준으로 적합한 매개변수를 선택하고 $베타$ , 정수 방정식 찾기가 끝날 때까지 매개변수를 증가시킵니다.

내부 LLL/BKZ 방식 선택 가능
- fplll(LLL/BKZ)
- 즐겁게 하다
- NTL(Sagemath LLL/BKZ를 통해)
선택 가능한 해결 정수 방정식 방법
- 야코비안 뉴턴 방법(수치)
- 헨젤리프팅
- 삼각 측량(Groebner 기초 + 부분적으로 0차원이 아닌 이상 처리)

설치

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

fplll 또는 flatter를 사용하는 경우 이러한 패키지를 빌드해야 합니다. 이미 설치한 경우 lll.py에서 설치 경로를 fplll_path 또는 flatter_path로 설정하여 이를 사용할 수 있습니다.

아니면 도커 이미지를 생성할 수도 있습니다. sagemath/sagemath:최신 이미지를 기반으로 하며 잘 알려진 격자 라이브러리도 다운로드합니다. (다른 좋은 라이브러리를 알고 계시다면 이를 포함시켜 알려주세요.)

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

용법

Zmod(N), 경계, 베타에 대한 Sagemath PolynomialRing을 사용하여 Coppersmith_onevariable.coppersmith_onevariable 또는 Coppersmith_linear.coppersmith_linear를 호출합니다.

example.py 참조하세요.

또한 ZZ에 대한 Sagemath 행렬과 일부 최적화 매개변수를 사용하여 lll.do_lattice_reduction을 호출하여 LLL 만 사용할 수 있습니다. 그리고 CVP 솔버용 lll.babai.

integer equations solver 의 경우 ZZ 및 경계에 대한 Sagemath 다항식 목록과 함께 rootfind_ZZ.rootfind_ZZ를 사용합니다.

맞춤 구성

(해당 기능은 2024년 3월 8일에 도입되었습니다.)

일부 실험을 바탕으로 내장된 기본 설정을 설정했지만 일부 사용자는 해당 설정이 자신의 환경에 맞지 않는다고 말합니다.

따라서 lll.py 및 rootfind_ZZ.py 에 대한 구성 인터페이스 context 준비합니다.

다음 예시처럼 context 가져와서 사용할 수 있습니다.

 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 )

옵션 목록과 해당 기본값은 contextclass.py 의 register_options_lll 및 register_options_rootfind_ZZ 에서 확인할 수 있습니다.

참고(use_pari_kernel)

LLL을 계산하기 위해 격자 정의를 위한 선형 종속 벡터를 제거하기 위해 pari.matker를 사용합니다. 프로세스는 더 평평하게 사용해야 합니다. pari.matker는 빠르고 정확한 결과를 출력하는 경우가 많지만 때로는 wrong 결과를 출력하는 경우도 있습니다. (lll.test()를 실행하여 이를 확인할 수 있습니다.) use_pari_kernel=False 옵션을 설정하여 pari.matker 사용을 비활성화할 수 있습니다. 여기서 Sagemath 커널(HNF(컴퓨팅 Hermite Normal Form)을 내부적으로 실행합니다.)을 강제로 사용합니다. HNF는 큰 요소를 생성하는 경향이 있으므로 LLL 프로세스가 매우 느려집니다.

배경

시간공포증을 해결할 수 없는 이유… Coppersmith 방법에 대한 분석 자세히 보기. (오래된 글일 수도 있습니다.)

매개변수를 선택하는 방법은 무엇입니까?

Coppersmith 작은 근 방법은 다음 유형 방정식의 근을 찾는 것입니다.

$f(r_1,ldots,r_n)=0 pmod{b}$ , 어디 $| r_i | < X_i (i=1,ldots,n)$ , 알려진 다항식의 경우 $f(r)$ 그리고 알려진 $N$ 그렇게 $b |N$ .

패키지 함수에는 다음 매개변수가 필요합니다.

베이스폴리: 다항식 $f(r)$ Zmod( $N$ )
경계: 목록 $[X_1,ldots,X_n]$ 누구의 양의 정수 $X_1,ldots,X_n$
베타: 양의 부동 소수점 수 $베타$ 그렇게 $b ge N^beta$

결정을 위해 $베타$ , 다음 지침을 권장합니다.

만약에 $b$ 알려져있다면 $beta=log_{N}(b)$
만약에 $b$ 알 수 없지만 비트 크기는 $b$ 알려져있다면 $beta=(text{비트 크기}(b)-1)/(text{비트 크기}(N))$

예를 들어, $N=pq$ 그리고 $text{비트 크기}(p)=text{비트 크기}(q)$ , 그 다음에 $betasimeq 0.499$ .

패키지의 완성도

Q: 패키지로 많은 모듈러스 다변량 다항식 시스템을 풀 수 있나요?

A: 어쩌면 그렇지 않을 수도 있습니다. 일반 계수 다변량 다항식 솔버를 만드는 것은 어려운 것 같습니다. 이는 단항식(예: [ $f=ax^2 + by + c$ ] vs [ $g=ax^2 + bxy + cy + d$ ]), 계수(예: [ $f=ax^2-by+c$ ] vs [ $g=ax^2-ay+c$ ]) 및 경계(예: [ $X simeq Y$ ] vs [ $X simeq Y^2$ ]). 많은 논문이 각각의 특정 사례를 다루고 있습니다.

특히, 다항식을 이해하지 못한 채 휴리스틱 방법을 사용하는 것은 권장하지 않습니다. 휴리스틱 방법은 (단변량 케이스나 선형 케이스와는 달리) 경계 조건을 추정하지 않으므로 솔버가 예상한 대로 출력하지 않아서 혼란스러울 수 있습니다.

또는 선형화 전략을 사용하거나 rootfind_ZZ를 직접 적용할 수도 있습니다. 예를 들어, 문제를 해결하고 싶다면 $f=ax^2+by pmod{N}$ , 먼저 정의 ${f_mathbb{Z}}=ax'+by+kN in mathbb{Z}[x',y,k]$ , 그런 다음 경계가 있는 rootfind_ZZ(또는 다른 정수 다항식 솔버)를 적용합니다. $[X^2, Y]$ (우리는 검색 $k$ 무차별 대입으로). 가정할 수 있다면 $|k|$ 작으면 시스템이 해결될 것입니다. Coppersmith 방법은 반드시 대수적으로 독립된 다항식 집합을 찾는 것은 아닙니다. 따라서 동일한 다항식 시스템을 풀어야 할 수도 있습니다. $f_mathbb{Z}$ Coppersmith 방법을 강제로 적용하더라도. rootfind_ZZ.solve_root_triangulate는 0이 아닌 차원 선형 시스템을 해결하려고 시도합니다.

rootfind_ZZ는 반드시 모든 루트를 찾는 것이 아니라 몇 개의 루트만 찾는다는 점에 유의하세요. 정수에 대한 근을 찾는 것은 쉽지 않으므로 다중 근 포함 시스템에 패키지를 사용해서는 안됩니다. 여러 루트를 방지하기 위한 몇 가지 방법을 고안할 수 있습니다. 일부 방법은 변수를 변환하여 경계 범위를 좁힐 수 있습니다. 일부 rootfind_ZZ 내부 함수는 루트가 경계 근처에 존재한다고 가정합니다.

기부금

패키지가 완벽할 수는 없으므로 이를 검토하고 개선해 주시기 바랍니다. 문제, 풀 요청 및 포크 게시를 환영합니다. 그리고 CTF나 기타 리소스의 test cases 알려주세요. 실패한 테스트 사례로 인해 패키지가 개선될 수 있습니다.

참조

우리 코드 중 일부는 다음 라이브러리를 기반으로 합니다.

디펀드/coppersmith (https://github.com/defund/coppersmith)

다변량 구리세공 방법: coppersmith.sage

josephsurinlattice 기반-암호 분석 (https://github.com/josephsurin/lattice-based-cryptanalytic)

다변량 구리세공 방법: lbc_toolkit/problems/small_roots.sage . 정수 다항식 근에 대한 일부 솔버는 lbc_toolkit/common/systems_solvers.sage 에 있습니다.

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

다양한 구리세공 방법(Herrmann-May, Blomer-May, Boneh-Durfee, Jochemsz-May 등 포함): shared/small_roots/*.py . 정수 다항식 근에 대한 일부 솔버는 shared/small_roots/__init__.py 에 있습니다.

jvdsn/crypto-attacks는 다음 위치에 배포됩니다.