STARK Curve เป็น SafeCurve หรือไม่?

STARK Curve ดูเหมือนจะเป็นทางเลือกที่สมเหตุสมผลสำหรับ ECDSA

เดอะ สตาร์ค เคิร์ฟ กำหนดมากกว่า $\mathbb{F}_p$ กับ $p = 2^{251} + 17*2^{192} +1$ ด้วยสมการไวเออร์สตราสสั้นๆ

$$y^2 = x^3 + A x + B$$

กับ

• $A = 1$, และ
• $B = 3141592653589793238462643383279502884197169399375105820974944592307816406665$

• ลำดับของกลุ่มเส้นโค้ง ( จำนวนจุด) คือ $n = \#E(\mathbf{F}_p )$ เป็น $n= 3618502788666131213697322783095070105526743751716087489154079457884512865583$

  และนี่คือจำนวนเฉพาะที่บ่งบอกว่า

  • ทุกองค์ประกอบยกเว้นตัวตน ( $\mathcal{O})$ สามารถเป็นเครื่องกำเนิดไฟฟ้าได้จำนวนที่ไม่อยู่ในอ้อมแขนของเส้นโค้งนี้ (ขอบคุณ Aria สำหรับการชี้) มาจาก $\pi$.

    ดังนั้น สตาร์กส์ค่อนข้างมีความแข็งกระด้าง อย่างน้อยก็ตอนนี้.

    ในท้ายที่สุด ตัวเลขที่ไม่มีสิ่งใดอยู่ในแขนเสื้อของฉันนั้นค่อนข้างเป็นลักษณะทางสรีรวิทยา

  • ปัจจัยร่วมคือ $h=1$ ซึ่งหมายความว่าไม่มีการเป็นตัวแทนของเส้นโค้งของมอนต์โกเมอรี่ ด้วยเหตุนี้จึงไม่มีบันไดมอนต์โกเมอรีที่เร็ว (ต้องใช้องค์ประกอบลำดับที่ 2 เช่น 2|ปัจจัยร่วม) บันไดจอยซ์ ยังคงเป็นไปได้ด้วยประสิทธิภาพที่ช้าลง ใน ECDSA สิ่งนี้มีประโยชน์ในการคำนวณ $[k]G$ เนื่องจากเท่านั้น $x$ ใช้พิกัด

  • ไม่มีการโจมตีกลุ่มเล็กๆ ให้พิจารณา แม้ว่านี่จะไม่ใช่ปัญหาสำหรับผู้ใช้ ECDSA ที่ถูกกฎหมาย หากผู้ใช้ไม่ถูกต้องตามกฎหมาย พวกเขาสามารถใช้สิ่งนี้เพื่อใช้จ่ายเหรียญซ้ำได้เหมือนที่ทำใน เคิร์ฟ25519 อย่างไรก็ตาม นี่ไม่ใช่กรณีของเส้นโค้ง STARK

  • กลุ่มเส้นโค้งเป็นแบบไอโซมอร์ฟิค $\mathbb{Z_n}$

• เดอะ $n$ มีการแทนเลขฐานสอง 252 บิตและนี่หมายความว่ามีประมาณ $126$บิตการรักษาความปลอดภัยกับปัญหาลอการิทึมไม่ต่อเนื่องคลาสสิกที่ดีที่สุด

• ขนาดของเส้นโค้งทำให้ไม่มีการชนกันของ $k$ หากใช้ตัวสร้างตัวเลขสุ่มที่ดี ถ้าใครยังกลัวสิ่งนี้อยู่ก็สามารถใช้ ECDSA ที่กำหนดขึ้นได้ rfc-6979.

• การรักษาความปลอดภัยแบบบิด (ไม่เกี่ยวข้องกับ ECDSA); การบิดกำลังสองของเส้นโค้งนี้คือ $$y^2 = x^3 + 5^2*x +B*5^3$$ ^*

  • จำนวนของการบิด = "618502788666131213697322783095070105623107215331596699973092056135872020481"
  • ปัจจัยของกลุ่มบิด = "499669 * 26023817775804638430931 * 278275836047110893120702478691334736277272165979" และสิ่งนี้ให้ความปลอดภัยประมาณ 158 บิต ระดับปานกลาง.

• และเรามี $2*p+2 = ออร์ด(E) + ออร์ด(\text{E_quaratic_twist})$

• $n \neq พี$ ดังนั้นจึงไม่ใช่ เส้นโค้งที่ผิดปกติ ซึ่งสามารถแก้ไขบันทึกแยกได้อย่างรวดเร็ว

เอ = 1
b = 3141592653589793238462643383279502884197169399375105820974944592307816406665
p = 2^251 + 17*2^192 +1

E = EllipticCurve(GF(p), [0,0,0,a,b])

พิมพ์(อี)
เอต = E.quadratic_twist()
พิมพ์ (Et)

พิมพ์ ("E abelian =", E.abelian_group())
พิมพ์ ("E บิด = ", Et.abelian_group())

การ์ด = E.cardinality()
cardEt = Et.cardinality()

พิมพ์ ("จำนวนสมาชิก E =",การ์ด)
พิมพ์ ("จำนวนสมาชิก E บิด =",การ์ด)


พิมพ์ ("ปัจจัย E", ปัจจัย (บัตร))
พิมพ์ ("ปัจจัย Et ",ปัจจัย (cardEt))

#ส่วนเครื่องกำเนิดไม่ได้สำหรับบิดกำลังสอง
#G = E(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
#n = G.order()
#print("ลำดับเครื่องกำเนิดไฟฟ้า =", n)

พิมพ์(บันทึก(การ์ด,2).n()+1)

ยืนยัน (2*p+2 == การ์ด + cardEt)

_{^*การบิดกำลังสองที่เกิดขึ้นกับ QNR 5 น่าเสียดายที่มันไม่ได้ผลตามที่ตั้งใจไว้ ขอบคุณ Poncho ที่ชี้ให้เห็นสิ่งนี้ ฉันเก็บสมการไว้เพื่อให้ใครเห็นปัญหา แต่ฉันใช้ กำลังสอง_twist ฟังก์ชั่นของ SageMath ที่ค่อนข้างช้า}