Score:2

การโจมตีจุดที่ไม่ถูกต้องในการบิดกำลังสองของ Elliptic Curve เมื่อ -1 เป็นสารตกค้างกำลังสอง

ธง ma

ฉันจำลองการโจมตีจุดที่ไม่ถูกต้องบน ECC โดยใช้เส้นโค้ง Short Weierstrass สำหรับสิ่งนี้ ฉันได้เขียนการใช้งานแบบ "งี่เง่า" ที่ไม่ได้ตรวจสอบจุดที่อยู่บนเส้นโค้งก่อนที่จะเข้าสู่การคูณแบบสเกลาร์ สำหรับเค้าโครงของการโจมตี ฉันขอยืมอย่างมากจากคำอธิบายที่ยอดเยี่ยมของซามูเอล เนเวส ซึ่งเขาให้ไว้ที่นี่: ทำความเข้าใจกับ Twist Security เกี่ยวกับเส้นโค้ง Weierstrass สั้น ๆ

ฉันสามารถทำซ้ำได้โดยไม่มีปัญหาเมื่อ $d = -1$ เป็นกำลังสองที่ไม่ตกค้างใน $\mathbb{F}_p$จากนั้นทุกอย่างจะทำงานนอกกรอบ อย่างไรก็ตามเมื่อ $p$ เป็นอย่างนั้น $-1$ เป็นเศษเหลือกำลังสอง ดังนั้นฉันจึงต้องเลือกค่าอื่นสำหรับ $d$ทุกอย่างแตกสลาย

เพื่อความง่ายในการเรียกใช้ครั้งแรกฉันไม่ได้ใช้เส้นโค้ง $\mathbb{F}_{p^2}$ เพราะสำหรับตัวเล็ก $p$ การแจงนับอย่างถี่ถ้วนเพื่อค้นหาจุดที่สั่งซื้อต่ำไม่ใช่ปัญหา

ตัวอย่างเช่น สมมติว่าเส้นโค้งของฉันถูกกำหนดไว้ $\mathbb{F}_{101}$; ที่นี่, $-1$ เป็น mod กากเศษกำลังสอง $p$, เนื่องจาก $10 \cdot 10 = -1 \mod 101$. เส้นโค้งของฉันถูกกำหนดโดย

$E: y^2 = x^3 + 13x + 29$

และด้วย $d = 2$, mod ที่ไม่ตกค้างกำลังสอง 101

$E^d: y^2 = x^3 + 52x + 30$

คำสั่งของ $E^d$ เป็น $111 = 3 \cdot 37$. ฉันได้เลือกสองจุดบน $E^d$ ซึ่งมีคำสั่งที่ 3 และ 37 ตามลำดับ ดังนี้

$P_1 = (28, 62)$

$P_2 = (8, 7)$

เมื่อฉันเรียกใช้ค่าเหล่านี้ผ่านการคูณสเกลาร์โดยไม่มีการตรวจสอบจุด (สำหรับรหัสส่วนตัว $d = 58$ฉันได้รับผลลัพธ์ต่อไปนี้:

$S_1 = (94, 53)$

$S_2 = (32, 14)$

ไม่ใช่ทั้งสองอย่าง $S_1$ ก็ไม่เช่นกัน $S_2$ เป็นจุดบนการบิดกำลังสอง $E^d$. ฉันสามารถยกพิกัด X อย่างใดอย่างหนึ่งเข้ามา $E^d$แต่แล้วคำสั่งของคะแนนก็ผิด

นี่คือรหัสตัวอย่างของฉัน:

Fp = GF(101)
D = Fp(2)
    
พิมพ์ (D, "เป็นรูปสี่เหลี่ยมจัตุรัส?", D.is_square())
(ก, ข) = (13, 29)

E = EllipticCurve(Fp, [a, b])
Et = EllipticCurve(Fp, [ a*D^2, b*D^3 ])

พิมพ์ ("Et.order ()", ปัจจัย (Et.order ()))

โจมตีจุด = [
    เอต(28, 62),
    เอต(8, 7),
]
พิมพ์(อี)
พิมพ์ (Et)
สำหรับ P ใน Attack_points:
    พิมพ์(P, P.order())

# รหัสส่วนตัว d = 58
mul_results = [ 
    เอต(94, 53), 
    เอต(32, 14), 
]
#พิมพ์(Et.lift_x(94).คำสั่ง())
#พิมพ์(Et.lift_x(32).คำสั่ง())

ผลลัพธ์ใด:

2 เป็นสี่เหลี่ยม? เท็จ
Et.order() 3 * 37
Elliptic Curve กำหนดโดย y^2 = x^3 + 13*x + 29 บน Finite Field ขนาด 101
Elliptic Curve กำหนดโดย y^2 = x^3 + 52*x + 30 บน Finite Field ขนาด 101
(28 : 62 : 1) 3
(8 : 7 : 1) 37
TypeError: พิกัด [94, 53, 1] ไม่ได้กำหนดจุดบน Elliptic Curve ที่กำหนดโดย y^2 = x^3 + 52*x + 30 บน Finite Field ขนาด 101

ฉันจะทำการโจมตีนี้สำหรับการบิดกำลังสองได้อย่างไร $d \neq -1$?

kelalaka avatar
in flag
อาจไม่ใช่ปัญหาของคุณ รหัสดั้งเดิมนั้นใช้ไม่ได้กับ SageMath อีกต่อไป เป็นไปได้สูงที่จะมีการเปลี่ยนแปลงในไลบรารีที่ขัดขวางการคำนวณดังกล่าว...
ma flag
ฉันไม่มีชื่อเสียงมากพอที่จะแสดงความคิดเห็นในโพสต์อื่น แต่โซลูชันของ Neves ใช้งานได้จริง ไม่ใช่แค่นอกกรอบ: คำสั่งการพิมพ์ต้องมีวงเล็บและการเรียก .lift_x(randint(...)) ต้องถูกแทนที่ โดย .lift_x(K(randint(...))) จากนั้นทุกอย่างจะทำงานได้อย่างมีเสน่ห์ ฉันสามารถทำซ้ำได้อย่างสมบูรณ์แบบด้วย d = -1 แต่อย่างที่ฉันเขียน -1 เป็นเศษเหลือกำลังสองในบางฟิลด์ (เช่น GF (101) ดังที่แสดงไว้ที่นี่)
kelalaka avatar
in flag
ฉันได้แก้ไขคำตอบแล้ว คุณช่วยตรวจสอบได้ไหม
ma flag
ขอบคุณ รหัสตรงนั้นใช้งานได้แล้ว แต่ยังไม่ได้ตอบคำถามของฉัน (เช่น มันใช้ d = -1 อย่างชัดเจน) - มีความคิดอย่างไรที่จะทำให้มันทำงานด้วย d อื่น
kelalaka avatar
in flag
ใช่ฉันรู้. เรขาคณิตเกี่ยวกับพีชคณิต (เส้นโค้งวงรีเป็นส่วนหนึ่งของมัน) ควรทำในการปิดพีชคณิต อย่างที่คุณเห็น คำตอบของ Samuel Neves ใช้ได้ผลกับการปิดบัญชี คุณไม่ใช่
kelalaka avatar
in flag
ดูเอกสาร Curve25519'เกี่ยวกับการโจมตีกลุ่มย่อยขนาดเล็ก
Ruggero avatar
kr flag
ฉันคิดว่าด้วย d!=-1 คุณต้องแปลงจุดของคุณจาก $E$ และ $E^{d}$ และคุณไม่สามารถใช้พิกัด x ธรรมดาได้ มันจะช่วยได้ถ้าคุณสามารถโพสต์สคริปต์ปราชญ์สำหรับการคูณสเกลาร์ของคุณ เนื่องจากการใช้ $y$ ทำให้ฉันสับสน ทำไมไม่ทำการโจมตีแบบโค้งที่ไม่ถูกต้อง (โดยไม่ต้องกังวลกับการบิด)
ma flag
@kelalaka ตัวอย่างที่ฉันให้นี้มีไว้เพื่อความเรียบง่ายเท่านั้น - เขาทำงานในฟิลด์ส่วนขยายกำลังสอง แต่นั่นก็ใช้ไม่ได้กับ d != -1 หากคุณแก้ไขสคริปต์ของเขาเพื่อใช้พารามิเตอร์โดเมนอื่น นั่นคือนั่นไม่ใช่สาเหตุของปัญหา ฉันกลัว ฉันละเว้นไว้ที่นี่เพื่อความกระชับเพื่อให้มีตัวอย่างน้อยที่สุดที่แสดงให้เห็นถึงปัญหา
ma flag
@Ruggero ฉันมองข้ามการตอบสนองของคุณ ใช่ ฉันเชื่อว่าจำเป็นต้องมีการแปลงบางอย่าง แต่ฉันไม่สามารถหาวิธีได้: ก่อนใส่เป็นอินพุตไปยังแลดเดอร์หรือหลังเอาต์พุตของแลดเดอร์ (หรืออาจเป็นไปได้ทั้งสองอย่าง) จำเป็นต้องมีการแปลงบางอย่างอย่างแน่นอนที่สุด และโปรดทราบว่า -1^2 = 1 เช่น ถ้าเลขยกกำลังคู่คูณ/หารด้วย เราจะไม่มีทางรู้ในกรณี d=-1 ความคิดเห็นของคุณเกี่ยวกับบันได X-only นั้นถูกต้อง ในความสิ้นหวังของฉัน ฉันพยายามทุกอย่าง: มัลแอนด์แอดอย่างง่าย (ใช้ได้กับ d=-1 ด้วย!), บันได Brier/Joye X และบันไดเสริม X-only พวกเขาทั้งหมดคำนวณอย่างถูกต้อง ดังนั้นฉันจึงพลาดการแปลงอย่างแน่นอน
Score:0
ธง ma

นี่ไม่ใช่ปัญหาของการที่ d เป็น QNR ที่ไม่ใช่ -1

แต่เป็นปัญหาของโมดูลขนาดเล็กแทน ฉันสามารถสาธิตสิ่งนี้ได้อย่างน่าเชื่อถือโดยใช้สคริปต์ที่แก้ไขแล้วของ Samuel Neves: การโจมตีจุดที่ไม่ถูกต้องให้ผลลัพธ์ที่ไม่ถูกต้องสำหรับคะแนนการสั่งซื้อต่ำ

นี่ไม่ตอบโจทย์เลย ทำไม มันใช้งานไม่ได้ แต่อย่างน้อยก็แสดงให้เห็นว่า $d \neq -1$ ไม่ใช่สาเหตุของปัญหาของฉัน

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา