การโจมตีจุดที่ไม่ถูกต้องให้ผลลัพธ์ที่ไม่ถูกต้องสำหรับคะแนนการสั่งซื้อต่ำ

เมื่อเร็ว ๆ นี้ฉันได้พยายามทำซ้ำผลลัพธ์ของคำถามที่ Ruggero ถามและที่ Samuel Neves ตอบที่นี่: ทำความเข้าใจกับ Twist Security เกี่ยวกับเส้นโค้ง Weierstrass สั้น ๆ

ในความพยายามทำซ้ำ ฉันพบว่าการโจมตีใช้ไม่ได้ในบางจุด ตอนแรกฉันสันนิษฐานว่าเป็นเพราะปัจจัยการบิด $d$ ในกรณีของฉันไม่ใช่ $-1 \mod p$. ดังนั้นฉันจึงถามคำถามนี้: การโจมตีจุดที่ไม่ถูกต้องในการบิดกำลังสองของ Elliptic Curve เมื่อ -1 เป็นสารตกค้างกำลังสอง. อย่างไรก็ตาม เมื่อฉันได้สำรวจเพิ่มเติม มันก็ชัดเจนสำหรับฉันว่านี่ไม่ใช่สาเหตุที่การโจมตีไม่ทำงาน แต่ด้วยรหัสของคำตอบดั้งเดิม ฉันยังสามารถแสดงให้เห็นได้อย่างน่าเชื่อถือว่าการนำบันได X-only ไปใช้จริงนั้นใช้ได้กับจุดสั่งซื้อ 100+ แต่ไม่ได้ (เชื่อถือได้) สำหรับจุดที่มีลำดับต่ำกว่า

ฉันได้แก้ไขสคริปต์ของซามูเอลที่นี่เพื่อแสดงพฤติกรรมนี้ในระดับที่กำหนดสำหรับลำดับที่ 7:

# ฟิลด์การตั้งค่า
พี = 2^127-1
d = -1 # ไม่ใช่กำลังสองในฟิลด์
K = GF(พี)
K2.<z> = GF(p^2)

# เส้นโค้งนี้มีลำดับเฉพาะ แต่บิดเรียบ 2 ^ 44
ก = -3
ข = 2045
E = EllipticCurve(K, [a, b])
Et = EllipticCurve(K, [d^2*a, d^3*b])
E2 = EllipticCurve(K2, [a, b])

#พรีคอมพรีออเดอร์
พิมพ์ (E.order().factor());
พิมพ์ (Et.order().factor());
พิมพ์ (E2.order().factor());

# สร้างลอการิทึมที่ไม่ต่อเนื่องเพื่อแก้ปัญหา
s = 123456789123456789123456789
P = E([0, 26743016104147931148362869907315104519])
Q = s * P

P_ = E2.lift_x(K(163965092228135290549051973720749297665))

ข้อเท็จจริง = 7

P_ *= Et.order() // ข้อเท็จจริง

พิมพ์ (P_)

Q_ = s * P_ # แบบสอบถาม -- แสร้งทำเป็นว่าทำได้ด้วยบันได x เท่านั้น

# แก้บันทึกโดยตรงบน E2
x1 = P_[0]
พิมพ์ ("x1_p2", x1)
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))

# แผนที่ไปยัง Et (ไม่บังคับ) และแก้ไข
x1 = d * P_[0]
พิมพ์ ("x1_t", x1)
x2 = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))

สำหรับผลลัพธ์ใน [ 153050600407045353908344231774077597412, 109343643823296263382915152331234715795 ]:
    สำหรับ x ใน [ K(ผลลัพธ์), K(ผลลัพธ์) * d ]:
        สำหรับ c ใน [ Et, E2 ] :
            พยายาม:
                P = c.lift_x(x)
            ยกเว้น ValueError เป็น e:
                พิมพ์ (จ)
                ดำเนินต่อ
            พิมพ์(P, P.order())


พิมพ์ (ข้อเท็จจริง s %)
พิมพ์ (s_, -s_ % ข้อเท็จจริง) # อย่างใดอย่างหนึ่ง
พิมพ์ (s__, -s__ % ข้อเท็จจริง) # อย่างใดอย่างหนึ่ง

ค่า 15305... และ 1093... เป็นค่าที่การใช้บันได X-only ให้เมื่อกำหนดพิกัด x1_p1 หรือ x1_t.

โปรดทราบว่าโค้ดนี้และการใช้แลดเดอร์ X-only ของฉันทำงานได้อย่างสมบูรณ์แบบสำหรับทุกจุดที่มีลำดับที่ 73 ขึ้นไป มันใช้ไม่ได้กับคำสั่ง 3 หรือ 7 นี่คือผลลัพธ์ของสคริปต์:

170141183460469231713519983870624230867
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909 * 170141183460469231713519983870624230867
(31638283026303721859929793126783073834 : 8180858091114185696092778095200036260*z + 4090429045557092848046389047600018130 : 1)
x1_p2 31638283026303721859929793126783073834
x1_t 138502900434165509871757510589101031893
No point with x-coordinate 153050600407045353908344231774077597412 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(153050600407045353908344231774077597412 : 120638375417041763806996747829917991029*z + 145389779438755497769342025772901048378 : 1) 56713727820156410583284874520381326863
(17090583053423877823343071941806508315 : 41244633631159509998704366741778119200 : 1) 56713727820156410583284874520381326863
(17090583053423877823343071941806508315 : 28961826547573943769330362324255518848 : 1) 170141183460469231713519983870624230867
No point with x-coordinate 109343643823296263382915152331234715795 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(109343643823296263382915152331234715795 : 127120934962706688155967022405858199927 : 1) 170141183460469231713519983870624230867
No point with x-coordinate 60797539637172968348772151384649389932 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(60797539637172968348772151384649389932 : 17145369941110587676988010143957064222 : 1) 170141183460469231713519983870624230867
1
1 6
1 6

เหตุใดการโจมตีนี้จึงใช้งานได้ในทางทฤษฎี (เป็นการคูณ Q_ = s * P_ จำลอง) แต่ใช้งานได้จริงสำหรับจุดสั่งซื้อที่สูงพอสมควรเท่านั้น