Score:2

Modulo p ในการเข้ารหัสแบบ Elliptic Curve

ธง vn

ในการดำเนินการเข้ารหัส Elliptic Curve ระหว่างฝ่ายต่างๆ สมการเส้นโค้งวงรีทั้งหมดถือว่าอยู่ในรูป $\bmod p$?

ตัวอย่างเช่น, $secp256k1$ เส้นโค้ง Bitcoin ของสมการ $y^2=x^3+7$ ใช้ $\bmod p$, ที่ไหน $p=2^{256}-2^{32}-977$.

Score:5
ธง ng

ในการดำเนินการเข้ารหัส Elliptic Curve ระหว่างฝ่ายต่างๆ สมการเส้นโค้งวงรีทั้งหมดถือว่าอยู่ในรูป $\bmod p$?

ใช่สำหรับ secp256k1 เมื่อเป็นเรื่องของพิกัดจุด แต่ไม่ใช่สำหรับทุกเส้นโค้ง.

Elliptic Curves ที่ใช้สำหรับการเข้ารหัสทำงานกับพิกัดใน สนามกาลัวส์ $\mathbb F_q$. มันต้องถือ $q=p^m$ สำหรับนายกรัฐมนตรีบางคน $p$, และ $ม\ge1$. เดอะ $\bmod p$ กรณีสอดคล้องกับ $m=1$และเป็นที่นิยมและรู้จักมากที่สุด (เอ็ด25519, secp256k1, secp256r1 เป็นตัวอย่าง) อีกทางเลือกที่ค่อนข้างธรรมดาคือ $q=2^m$ดูเช่น sec2v2 ส่วนที่ 3. นอกจากนี้ยังใช้ค่าอื่นๆ เช่น $q=9767^{19}$ ที่นั่น.

$2^m$ มีข้อดีด้านความเร็วในฮาร์ดแวร์หรือเมื่อการคูณจำนวนเต็มมีค่าใช้จ่ายสูงเนื่องจากการเผยแพร่ข้ามบิต ให้เป็นปกติมากกว่านี้, $p^m$ ด้วยขนาดที่สมดุลของ $p$ และ $m$ สามารถดำเนินการแบบขนานได้ง่ายขึ้น


นอกจากนี้: แม้แต่เส้นโค้งด้วย พิกัด ใน $\mathbb F_p$ กับ $p$ ไพรม์เป็น secp256k1 การคำนวณบางอย่างเกี่ยวกับสเกลาร์ที่คูณจุดโค้ง (รวมถึงการคำนวณที่เกี่ยวข้องกับคีย์ส่วนตัว) จะดำเนินการตามคำสั่งของเส้นโค้งแบบโมดูโล $n$ และเฉพาะ และแตกต่างของ $p$.

poncho avatar
my flag
ได้ คุณสามารถใช้ Elliptic Curves ที่กำหนดเหนือฟิลด์ส่วนขยาย (ซึ่งสำหรับผู้ชม คือฟิลด์ $\mathbb{F}_{p^k}$ สำหรับ $k > 1$); ในทางกลับกัน เส้นโค้ง secp256k1 ที่เขาถามถึง และสำหรับเรื่องนั้น สำหรับเส้นโค้งที่เราใช้อยู่ 99% ของเวลาทั้งหมดนั้นเป็นเส้นโค้งเฉพาะ นั่นคือ เส้นโค้งที่เราสามารถทำการคำนวณด้วยโมดูล $p$
Score:3
ธง in

จำนวนเฉพาะในนิยามของเส้นโค้ง Secp256k1

นายกรัฐมนตรี $p$ เป็นส่วนหนึ่งของการออกแบบเส้นโค้ง การวิเคราะห์ และคำจำกัดความที่กำหนด $\mathbb{F_P}$. ถ้าใครใช้แบบอื่น $p$ จากนั้นจะมีเส้นโค้งต่างๆ ที่ต้องวิเคราะห์ จากนั้นจึงเผยแพร่และแจกจ่ายเพื่อสื่อสารกับเส้นโค้งนี้

เพื่อที่จะสื่อสาร $p$, สมการเส้นโค้ง ( ที่นี่ $(ก,ข)$) จุดฐาน $G$, จุดที่ไม่มีที่สิ้นสุด, ลำดับเส้นโค้ง $n$และปัจจัยร่วม $h$ ได้กำหนดไว้ในมาตรฐาน

นี่คือเซ็กส์ทอย $T = (p,a,b,G,n,h)$ และสำหรับ Secp256k1 เป็น;

  • ''p'' = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • = $2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

ทางโค้ง $E: y^2 = x^3+ขวาน+b$ เกิน $\mathbb{F}_p$ ถูกกำหนดโดย:

  • ''a'' = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  • ''ข'' = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007

จุดฐาน G ในรูปแบบบีบอัดคือ:

  • ''G'' = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 และในรูปแบบที่ไม่บีบอัดคือ:
  • ''G'' = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D48B FB10D48B ในที่สุดลำดับ ''n'' ของ ''G'' และตัวประกอบคือ:
  • ''n'' = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • ''h'' = 01

เดอะ $a,b,p,G$ เพียงพอที่จะสื่อสารได้ แต่ที่เหลือไม่ต้องคำนวณใหม่


ตัวอย่างเล็กๆ น้อยๆ ที่แสดงให้เห็นว่าแตกต่างกันอย่างสิ้นเชิง

K = GF(19)
E = EllipticCurve(K,[0,7])
พิมพ์(อี)
พิมพ์ (E.order ())
พิมพ์ (E.abelian_group ())

แล้ว $n = 12$ และกลุ่มเส้นโค้งเป็นแบบไอโซมอร์ฟิค $\mathbb{Z}_6 \oplus \mathbb{Z}_2$

K = GF(31)
E = EllipticCurve(K,[0,7])
พิมพ์(อี)
พิมพ์ (E.order ())
พิมพ์ (E.abelian_group ())

แล้ว $n = 21$ และกลุ่มเส้นโค้งเป็นแบบไอโซมอร์ฟิค $\mathbb{Z}_{21}$

แน่นอน มันเป็นไปได้ที่จะหาสองสิ่งอันดับ $(p_1,a_1,b_1)$ และ $(p_2,a_2,b_2)$ เพื่อให้มีจุดกลุ่มเดียวกันนี่ไม่ใช่ความกังวล เราแค่ต้องการเซ็กซ์ทูเพิลที่เป็นมาตรฐาน

เราถูกจำกัดให้ $\mathbb{F}_p$?

หากคุณถูกถาม เราควรใช้ฟิลด์ไพรม์เสมอ $\mathbb{F}_p$ แล้วคำตอบคือไม่ เขตข้อมูล จำกัด ใด ๆ $\mathbb{F}_{p^m}$ ใช้ได้ตราบใดที่ปลอดภัยและรวดเร็ว ดู Fgrieu's คำตอบสำหรับรายละเอียด

คำสั่งกลุ่มโค้ง

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

เราไม่ต้องการให้ลำดับเส้นโค้งเท่ากับ $p$ ในกรณีนี้ เส้นโค้งเป็นเส้นโค้งที่ผิดปกติและไม่ปลอดภัย

โมดูลัสในการคูณสเกลาร์

เดอะ การคูณสเกลาร์ $[k]P$ นี่หมายถึงการเพิ่ม $พี$ นั่นเอง $k$- ครั้ง เป็นทางการมากขึ้น

อนุญาต $k \in \mathbb{N}\แบ็กสแลช\{ 0\}$

\begin{จัด} [k]:& E \ถึง E\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ ครั้ง}}.\end{align}

และด้วยความเป็นตัวตน $[0]P = \mathcal{O}$.

ในขณะที่คำนวณสิ่งนี้เราใช้ลำดับของจุด $พี$ถ้าเส้นโค้งมีลำดับเฉพาะเช่น secp256k1 องค์ประกอบทั้งหมดยกเว้นเอกลักษณ์จะมีลำดับเฉพาะเหมือนกัน เรามีความเท่าเทียมกันนี้

$$[k]P = [k \bmod \text{ord}(P)]P$$

และเราใช้ $พี$มีคำสั่งสำคัญเพื่อลดการโจมตี

โพสต์คำตอบ

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