coppersmith ดาวน์โหลด - coppersmith ดาวน์โหลดซอร์สโค้ด

coppersmith

ซอร์สโค้ดอื่น ๆ

ดาวน์โหลด

Coppersmith รากเล็กๆ

วิธีรากเล็กของคอปเปอร์สมิธ (การแก้สมการพหุนามเหนือโมดูลัสประกอบบนขอบเขตเล็ก)

คุณสมบัติ

รองรับสมการทองแดงหลายรายการ
- พหุนามที่ไม่แปรเปลี่ยน
- พหุนามเชิงเส้นหลายตัวแปร (วิธี Herrmann-May)
- พหุนามหลายตัวแปร (วิธี Jochemsz-May heuristic)

ส่วนใหญ่จะเกี่ยวข้องกับสมการที่ใช้วิธี Coppersmith ที่กำหนดขึ้นตามทฤษฎี เราขอแนะนำให้ใช้ตัวแปรเดียวหรือเชิงเส้น (แทนการศึกษาสำนึก) หากคุณทราบประเภทของสมการ

การปรับพารามิเตอร์อัตโนมัติ

ขั้นแรก เลือกพารามิเตอร์ที่เหมาะสมตามขอบเขตและ $เบต้า$ แล้วเพิ่มค่าพารามิเตอร์จนเสร็จสิ้นเพื่อหาสมการจำนวนเต็ม

วิธี LLL/BKZ ภายในที่เลือกได้
- fplll (LLL/BKZ)
- ประจบ
- NTL (ผ่าน Sagemath LLL/BKZ)
วิธีการแก้สมการจำนวนเต็มแบบเลือกได้
- วิธีจาโคเบียนนิวตัน (เชิงตัวเลข)
- เฮ็นเซลลิฟติ้ง
- สมการ (พื้นฐาน Groebner + การจัดการกับมิติที่ไม่เป็นศูนย์ในอุดมคติบางส่วน)

การติดตั้ง

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

หากคุณใช้ fplll หรือประจบประแจง จำเป็นต้องสร้างแพ็คเกจเหล่านี้ หากคุณติดตั้งไว้แล้ว คุณสามารถใช้สิ่งนี้ได้โดยตั้งค่าพาธการติดตั้งเหล่านี้เป็น fplll_path หรือ flatter_path บน lll.py

หรือคุณสามารถสร้างอิมเมจนักเทียบท่าได้ มันขึ้นอยู่กับ sagemath/sagemath: รูปภาพล่าสุด และยังดาวน์โหลดไลบรารี lattice ที่รู้จักกันดีอีกด้วย (หากคุณรู้จักห้องสมุดอื่นๆ ที่ดี โปรดแจ้งให้เราทราบเพื่อรวมสิ่งเหล่านี้ไว้ด้วย)

$ 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/3/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 (ซึ่งรันการคำนวณในรูปแบบปกติของ Hermite (HNF) ภายใน) โปรดทราบว่า HNF มีแนวโน้มที่จะสร้างองค์ประกอบขนาดใหญ่ ดังนั้นจึงทำให้กระบวนการ LLL ช้ามาก

พื้นหลัง

ดูว่าทำไมเราไม่สามารถแก้ปัญหาโครโนโฟเบียได้… การวิเคราะห์วิธี Coppersmith เพิ่มเติม (อาจเป็นบทความเก่าก็ได้)

จะเลือกพารามิเตอร์ได้อย่างไร?

วิธีรูตเล็กของ Coppersmith คือการค้นหารากของสมการประเภทต่อไปนี้:

$f(r_1,ldots,r_n)=0 pmod{b}$ , ที่ไหน - r_i | < X_i (i=1,ldots,n)$ สำหรับพหุนามที่ทราบ $ฟ(ร)$ และเป็นที่รู้จัก $เอ็น$ เช่นนั้น $ข | N$ -

ฟังก์ชันแพ็คเกจต้องการพารามิเตอร์ต่อไปนี้

basepoly: พหุนาม $ฟ(ร)$ เหนือ Zmod( $เอ็น$ -
ขอบเขต: รายการ $[X_1,ldots,X_n]$ ซึ่งมีจำนวนเต็มบวก $X_1,lจุด,X_n$
เบต้า: จำนวนจุดลอยตัวที่เป็นบวก $เบต้า$ เช่นนั้น $b ge N^เบต้า$

สำหรับการกำหนด $เบต้า$ เราขอแนะนำแนวทางดังต่อไปนี้

ถ้า $ข$ เป็นที่ทราบกันดีอยู่แล้ว $beta=log_{N}(ข)$
ถ้า $ข$ ไม่เป็นที่รู้จักแต่มีขนาดบิตของ $ข$ เป็นที่ทราบกันดีอยู่แล้ว $beta=(text{bitsize}(b)-1)/(text{bitsize}(N))$

ตัวอย่างเช่น, $N=pq$ และ $text{bitsize}(p)=text{bitsize}(q)$ , แล้ว $เบต้าsimeq 0.499$ -

ความสมบูรณ์ของแพ็คเกจ

ถาม: คุณสามารถแก้ระบบพหุนามหลายตัวแปรโมดูลัสหลายตัวแปรด้วยแพ็คเกจได้หรือไม่

ตอบ: อาจจะไม่ ดูเหมือนว่าจะเป็นเรื่องยากที่จะสร้างตัวแก้ปัญหาพหุนามโมดูลัสหลายตัวแปรทั่วไป ขึ้นอยู่กับ monomial (เช่น [ $f=ขวาน^2 + โดย + c$ ] vs [ $g=ขวาน^2 + bxy + cy + d$ ]) ค่าสัมประสิทธิ์ (เช่น [ $f=ขวาน^2-คูณ+c$ ] vs [ $g=ขวาน^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, ย]$ (เราค้นหา $k$ ด้วยความดุร้าย) หากเราสามารถสมมติได้ $|k|$ มีขนาดเล็กระบบจะได้รับการแก้ไข โปรดทราบว่าวิธี Coppersmith ไม่จำเป็นต้องค้นหาเซตพหุนามที่เป็นอิสระจากพีชคณิต คุณอาจต้องแก้ระบบพหุนามเดียวกัน $f_คณิตศาสตร์{Z}$ แม้ว่าคุณจะถูกบังคับให้ใช้วิธี Coppersmith ก็ตาม rootfind_ZZ.solve_root_triangulate พยายามแก้ไขระบบเชิงเส้นตรงที่ไม่ใช่ศูนย์

โปรดทราบว่า rootfind_ZZ ไม่จำเป็นต้องค้นหารากทั้งหมด แต่พบเพียงไม่กี่รากเท่านั้น การค้นหารูทเหนือจำนวนเต็มไม่ใช่เรื่องง่าย ดังนั้นคุณไม่ควรใช้แพ็คเกจสำหรับระบบที่มีหลายรูท คุณสามารถคิดค้นวิธีการบางอย่างในการหลีกเลี่ยงหลาย ๆ รากได้ วิธีการบางอย่างอาจจำกัดขอบเขตขอบเขตให้แคบลงโดยการแปลงตัวแปร ฟังก์ชันภายใน rootfind_ZZ บางอย่างถือว่ารากนั้นอยู่ใกล้ขอบเขต

ผลงาน

แพ็คเกจต้องไม่สมบูรณ์แบบ เราต้องการให้คุณตรวจสอบและปรับปรุงสิ่งนี้ ยินดีต้อนรับสู่การโพสต์ปัญหาใด ๆ ดึงคำขอและส้อม และแจ้งให้เราทราบ test cases จาก CTF หรือแหล่งข้อมูลอื่น ๆ กรณีทดสอบที่ล้มเหลวอาจทำให้เราต้องปรับปรุงแพ็คเกจ

อ้างอิง

รหัสบางส่วนของเราอิงจากไลบรารีต่อไปนี้

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

วิธี coppersmith หลายตัวแปร: coppersmith.sage

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

วิธี coppersmith หลายตัวแปร: lbc_toolkit/problems/small_roots.sage ตัวแก้ปัญหาบางตัวสำหรับรากพหุนามจำนวนเต็มอยู่ที่ lbc_toolkit/common/systems_solvers.sage

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

วิธี coppersmith ต่างๆ (รวมถึง Herrmann-May, Blomer-May, Boneh-Durfee, Jochemsz-May ฯลฯ): shared/small_roots/*.py ตัวแก้ปัญหาบางตัวสำหรับรากพหุนามจำนวนเต็มอยู่ที่ shared/small_roots/__init__.py

jvdsn/crypto-attacks เผยแพร่ภายใต้: