تحميل coppersmith - تنزيل كود مصدر coppersmith

coppersmith

شفرة المصدر الأخرى

تنزيل

النحاسي جذور صغيرة

طريقة الجذور الصغيرة لصانع النحاس (حل معادلة متعددة الحدود على المعامل المركب على الحدود الصغيرة)

سمات

دعم معادلة النحاس المتعددة
- متعدد الحدود أحادي المتغير
- متعددة الحدود الخطية متعددة المتغيرات (طريقة هيرمان ماي)
- متعدد الحدود متعدد المتغيرات (طريقة يوتشيمسز-ماي الإرشادية)

بشكل أساسي، يتم التعامل مع المعادلة المعمول بها بطريقة كوبر سميث نظريًا. نوصي باستخدام أحادي المتغير أو الخطي (بدلاً من الاستدلال) إذا كنت تعرف نوع المعادلة.

ضبط المعلمة الآلي

أولاً، اختر المعلمات المناسبة بناءً على الحدود و $بيتا$ ، ثم قم بزيادة المعلمات حتى الانتهاء للعثور على معادلة عدد صحيح.

طريقة LLL/BKZ داخلية قابلة للتحديد
- fplll (LLL/BKZ)
- تملق
- NTL (عبر Sagemath LLL/BKZ)
اختيار طريقة حل المعادلة عدد صحيح
- طريقة جاكوبيان نيوتن (عددية)
- رفع هنسل
- التثليث (أساس جروبنر + التعامل مع الأبعاد غير الصفرية المثالية جزئيًا)

تثبيت

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

إذا كنت تستخدم fplll أو flatter، فستحتاج إلى إنشاء هذه الحزم. إذا قمت بتثبيتها بالفعل، فيمكنك استخدام ذلك عن طريق تعيين مسارات التثبيت هذه على fplll_path أو flatter_path على lll.py.

أو يمكنك إنشاء صورة عامل إرساء. وهو يعتمد على sagemath/sagemath: أحدث الصور ويقوم أيضًا بتنزيل مكتبات الشبكة المعروفة. (إذا كنت تعرف مكتبات أخرى جيدة، فأخبرنا بإدراجها.)

$ 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 وبعض معلمات التحسين. وllll.babai لحلالا CVP.

لحل integer equations solver ، استخدم rootfind_ZZ.rootfind_ZZ مع قائمة Sagemath متعددة الحدود على ZZ والحدود.

التكوين المخصص

(تم تقديم الميزة بتاريخ 2024/3/8.)

على الرغم من أننا قمنا بإعداد الإعدادات الافتراضية المضمنة بناءً على بعض تجاربنا، إلا أن بعض المستخدمين يقولون إن الإعداد لا يتناسب مع بيئاتهم.

لذلك قمنا بإعداد 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 kernel (الذي يقوم بتشغيل الحوسبة العادية داخليًا (HNF).) لاحظ أن HNF يميل إلى إنتاج عناصر كبيرة، لذا فهو يجعل عملية LLL بطيئة للغاية.

خلفية

انظر لماذا لم نتمكن من حل رهاب الزمن... تحليل لطريقة كوبرسميث أكثر. (قد يكون مقالًا قديمًا، رغم ذلك).

كيفية اختيار المعلمات؟

طريقة الجذر الصغير لـ Coppersmith هي إيجاد جذر المعادلة النوعية التالية:

$f(r_1,ldots,r_n)=0 pmod{b}$ ، أين $| r_i | < X_i (i=1,ldots,n)$ ، لكثيرة الحدود المعروفة $و(ص)$ ومعروفة $ن$ مثل هذا $ب | ن$ .

تتطلب وظيفة الحزمة المعلمات التالية.

بولي بولي: كثير الحدود $و(ص)$ على زمود( $ن$ )
الحدود: القائمة $[X_1,ldots,X_n]$ الذين الأعداد الصحيحة الإيجابية $X_1,ldots,X_n$
بيتا: رقم النقطة العائمة الموجب $بيتا$ مثل هذا $b ge N^beta$

لتحديد $بيتا$ ، نوصي بالمبادئ التوجيهية التالية.

لو $ب$ ومن المعروف إذن $beta=log_{N}(ب)$
لو $ب$ غير معروف ولكن حجم البت $ب$ ومن المعروف إذن $beta=(text{حجم البت}(b)-1)/(text{حجم البت}(N))$

على سبيل المثال، $N=pq$ و $text{حجم البت}(ع)=نص{حجم البت}(ف)$ ، ثم $بيتاسيمق 0.499$ .

اكتمال الحزمة

س: هل يمكنك حل العديد من أنظمة متعددة الحدود متعددة المتغيرات بواسطة الحزمة؟

ج: ربما لا. يبدو أنه من الصعب إنشاء حل متعدد الحدود لمعامل عام متعدد المتغيرات. يعتمد ذلك على أحاديات الحد (مثل [ $f=ax^2 + بواسطة + 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+بواسطة 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 أو موارد أخرى. حالات الاختبار الفاشلة قد تجعلنا نحسن الحزمة.

مرجع

تعتمد بعض رموزنا على المكتبات التالية.

ديفوند/كوبرسميث (https://github.com/defund/coppersmith)

طريقة النحاس متعدد المتغيرات: coppersmith.sage

تحليل التشفير المعتمد على josephsurinlattice (https://github.com/josephsurin/lattice-based-cryptana Analysis)

طريقة النحاس متعدد المتغيرات: 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 تحت: