Скачать coppersmith - coppersmith скачать исходный код

coppersmith

Другой исходный код

Скачать

Медник маленькие корни

Метод малых корней Копперсмита (решение полиномиального уравнения по составному модулю на малых границах)

Функции

поддержка нескольких уравнений медников
- одномерный полином
- многомерный линейный полином (метод Херрмана-Мэя)
- многомерный полином (эвристический метод Йохемса-Мая)

В основном речь идет о теоретически установленном применимом уравнении метода Копперсмита. Мы рекомендуем использовать одномерное или линейное уравнение (вместо эвристического), если вы знаете тип уравнения.

автоматическая настройка параметров

Сначала выберите подходящие параметры на основе границ и $бета$ , а затем увеличивайте параметры до завершения, чтобы найти целочисленное уравнение.

выбираемый внутренний метод LLL/BKZ
- fplll (LLL/БКЗ)
- льстить
- NTL (через Sagemath LLL/BKZ)
выбираемый метод решения целочисленного уравнения
- метод Якобиана Ньютона (численный)
- Hensel подъемник
- триангуляция (базис Грёбнера + частичная работа с ненульмерным идеалом)

Установка

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

Если вы используете fplll или Flatter, вам необходимо собрать эти пакеты. если вы их уже установили, вы можете использовать это, установив для этих путей установки значение fplll_path или Flatter_path в lll.py.

Или вы можете создать образ докера. Он основан на образе sagemath/sagemath:latest, а также загружает известные библиотеки решеток. (Если вы знаете другие хорошие библиотеки, сообщите нам, чтобы мы включили их.)

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

Использование

Вызовите Coppersmith_onevariable.coppersmith_onevariable или Coppersmith_linear.coppersmith_linear с помощью Sagemath PolynomialRing по Zmod(N), границам, бета.

См. example.py .

Кроме того, вы можете использовать только LLL , вызвав lll.do_lattice_reduction с матрицей Sagemath поверх ZZ и некоторыми параметрами оптимизации. И lll.babai для решателя CVP.

Для integer equations solver используйте rootfind_ZZ.rootfind_ZZ со списком полиномов Sagemath по ZZ и границам.

Пользовательская конфигурация

(Эта функция была представлена 8 марта 2024 г.)

Хотя мы установили встроенные настройки по умолчанию на основе некоторых наших экспериментов, некоторые пользователи говорят, что эти настройки не подходят для их сред.

Итак, мы подготавливаем context интерфейса конфигурации для lll.py и rootfind_ZZ.py .

Вы можете использовать его, импортировав 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 )

Вы можете проверить список параметров и их значения по умолчанию в register_options_lll и register_options_rootfind_ZZ в contextclass.py .

Примечание (use_pari_kernel)

Для вычисления LLL мы используем pari.matker для исключения линейно зависимых векторов для определения решетки. Процесс необходимо использовать более плоский. Хотя pari.matker работает быстро и во многих случаях выдает правильные результаты, иногда он выдает wrong результаты. (Вы можете проверить это, запустив lll.test().) Вы можете отключить использование pari.matker, установив параметр use_pari_kernel=False , где он принудительно использует ядро Sagemath (которое внутренне выполняет вычисления нормальной формы отшельника (HNF).) Обратите внимание, что HNF имеет тенденцию создавать большие элементы, поэтому процесс LLL становится очень медленным.

Фон

См. «Почему мы не смогли решить проблему хронофобии… Анализ по методу Копперсмита» подробнее. (хотя это может быть старая статья.)

Как выбрать параметры?

Метод малых корней Копперсмита заключается в нахождении корня уравнения следующего типа:

$f(r_1,ldots,r_n)=0 pmod{b}$ , где $| р_и | < X_i (i=1,ldots,n)$ , для известного полинома $f(r)$ и известный $Н$ такой, что $b | N$ .

Функция пакета требует следующих параметров.

basepoly: полином $f(r)$ через Zmod( $Н$ )
границы: список $[X_1,ldots,X_n]$ чьи положительные целые числа $X_1,ldots,X_n$
бета: положительное число с плавающей запятой $бета$ такой, что $b ge N^beta$

Для определения $бета$ , мы рекомендуем следующее руководство.

Если $б$ известно, то $beta=log_{N}(b)$
Если $б$ неизвестно, но битовый размер $б$ известно, то $beta=(text{bitsize}(b)-1)/(text{bitsize}(N))$

Например, $N=pq$ и $text{bitsize}(p)=text{bitsize}(q)$ , затем $betasimeq 0.499$ .

Полнота пакета

Вопрос: Можете ли вы решить множество многомерных полиномиальных систем по модулю с помощью пакета?

А: Может быть, нет. Кажется, сложно создать многомерный полиномиальный решатель общего модуля. Это зависит от мономов (таких как [ $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]$ (мы ищем $к$ с помощью грубой силы). Если мы можем предположить $|к|$ мала, система будет решена. Обратите внимание, что методы Копперсмита не обязательно находят алгебраически независимые множества полиномов. Поэтому вам, возможно, придется решить ту же полиномиальную систему $f_mathbb{Z}$ даже если вы вынуждены применить метод Копперсмита. rootfind_ZZ.solve_root_triangulate пытается решить ненульмерную линейную систему.

Обратите внимание, что rootfind_ZZ не обязательно находит все корни, а только несколько. Найти корни по целым числам непросто, поэтому не следует использовать пакет для системы с несколькими корнями. Вы можете разработать некоторые методы, позволяющие избежать множественных корней. Некоторые методы могут сужать диапазон границ путем преобразования переменных. Некоторые внутренние функции rootfind_ZZ предполагают, что корень существует вблизи границ.

Вклад

Пакет не должен быть идеальным, мы хотим, чтобы вы его рассмотрели и улучшили. Добро пожаловать, чтобы публиковать любые проблемы, запросы на включение и форки. И дайте нам знать test cases из любого CTF или других ресурсов. Неудачные тестовые случаи могут заставить нас улучшить пакет.

Ссылка

Некоторые из наших кодов основаны на следующих библиотеках.

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

многовариантный метод медника: coppersmith.sage

криптоанализ на основе josephsurinlattice (https://github.com/josephsurin/lattice-based-cryptanaанализ)

многомерный метод медника: 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 распространяется под: