Score:3

ปัญหาเกี่ยวกับการเพิ่มจุดเกี่ยวกับ [n-1]+[2]G และ [n-1]+G บน Secp256k1

ธง cn

ฉันขอโทษล่วงหน้าสำหรับคำถามของฉัน ฉันกำลังพยายามทำเครื่องคิดเลข Secp256k1 แบบง่ายๆ ของตัวเอง แค่บวกและลบ ก็มีสิ่งหนึ่งที่ทำให้ฉันสับสน เมื่อฉันบวก 2 คะแนน และฉันรู้ว่าผลลัพธ์ของการบวกใดควรเป็นจำนวนที่มากกว่า $n$และเท่าที่ฉันเข้าใจผลลัพธ์ควรเป็น 0เพราะมันเป็นจุดที่ไม่มีที่สิ้นสุด

อย่างไรก็ตาม เครื่องคิดเลขของฉันแสดงผลต่างออกไป ตัวอย่างเช่น ฉันเพิ่ม:

115792089237316195423570985008687907852837564279074904382605163141518161494336 + 2

และได้รับ 1 ผลลัพธ์. สิ่งเดียวกันนี้เกิดขึ้นกับจุดอื่นๆ ที่มีผลรวมมากกว่า $n$.

แต่เมื่อฉันเพิ่ม

115792089237316195423570985008687907852837564279074904382605163141518161494336 + 1

คำนวณแสดงให้ฉันเห็น 0.

ฉันไม่เข้าใจ เครื่องคิดเลขทำงานถูกต้องไหม และเป็นการเข้าใจผิดของฉันใน ECC หรือไม่ หรือมันเป็นความผิดพลาดในรหัสของฉัน? ผลลัพธ์ควรเป็นอย่างไรเมื่อฉันบวกสองจุดที่มีผลรวมมากกว่า $n$?

kelalaka avatar
in flag
ยินดีต้อนรับสู่ Cryptography.SE. คำถามของคุณไม่ชัดเจน คุณใช้ [กฎหมายกลุ่มการเพิ่มจุด](https://crypto.stackexchange.com/a/66296/18298)หรือไม่
Franko avatar
cn flag
ใช่ฉันคิดว่า
kelalaka avatar
in flag
อ่านคำถามของคุณอีกครั้ง ดูเหมือนว่าคุณมีปัญหาในเลขคณิตจุด ECC คุณสามารถแก้ไขคำถามของคุณเพื่อแสดงว่าคุณเพิ่มคะแนนได้อย่างไร? ทางคณิตศาสตร์หรือทางโปรแกรม ในกรณีหลัง ๆ ที่ควรจะน้อยที่สุด!
Franko avatar
cn flag
ฉันใช้โค้ดจาก https://onyb.gitbook.io/secp256k1-python/point-addition-in-python When i add coordinates for 15792089237316195423570985008687907852837564279074904382605163141518161494336 point 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 and add to this point 2 with coordinates c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee51ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a, i get coordinates of 1 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 as result.
kelalaka avatar
in flag
ฉันไม่เข้าใจจริงๆ $P=(Px,Py)$ และ $Q=(Qx,Qy)$ คืออะไร
Franko avatar
cn flag
มาทำให้ง่ายขึ้นอีกนิด ข้อใดถูกต้องสำหรับการบวกจุดสำหรับสองจุด:115792089237316195423570985008687907852837564279074904382605163141518161494336 และ 2
kelalaka avatar
in flag
จุดใน ECC ในพิกัดใกล้เคียงมีสองพิกัด คุณแน่ใจหรือว่าได้รับสิ่งนี้ มีจุด $$(2, 69211104694897500952317515077652022726490027694212560352756646854116994689233)$$ กับ $x=2$ และ y ถูกคำนวณ...
Franko avatar
cn flag
ฉันเสียใจ. Point 115792089237316195423570985008687907852837564279074904382605163141518161494336 G with coordinates x: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 y: b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 and point 2G x: c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 y :1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
kelalaka avatar
in flag
ฉันคิดว่าคุณขาดแนวคิด จุดที่คุณเรียกควรเป็นคีย์ส่วนตัวและคุณต้องการคำนวณคีย์สาธารณะ คีย์ส่วนตัวเป็นจำนวนเต็มและคีย์สาธารณะคือจุดผ่าน [การคูณสเกลาร์](https://crypto.stackexchange.com/q/68593/18298) $[k]G$
PrincePolka avatar
cn flag
secp256k1 เป็นเส้นโค้งของลำดับเฉพาะ N = 115792089237316195423570985008687907852837564279074904382605163141518161494337 คุณกำลังเพิ่ม (N-1)G + 2G และรับ G ซึ่งถูกต้อง หลักการเดียวกับที่คุณเพิ่ม 1'a 2 ชั่วโมง นาฬิกา
Franko avatar
cn flag
ขอบคุณ!!! ซึ่งหมายความว่างานทั้งหมดถูกต้อง แต่เป็นไปได้อย่างไรที่จะหลีกเลี่ยงการเพิ่มคะแนนรอบที่สองนี้ สำหรับ rpoint การเพิ่มผลลัพธ์ที่มากกว่า n ท้ายที่สุด ผลลัพธ์ของการบวกซึ่งเท่ากับ n (115792089237316195423570985008687907852837564279074904382605163141518161494337) คำนวณได้ถูกต้องเป็น 0 เป็นไปได้ไหมที่ผลลัพธ์อื่นๆ มากกว่า n
kelalaka avatar
in flag
เข้าใจแล้ว. คุณใช้คำศัพท์ไม่ถูกต้องโดยสิ้นเชิง คุณกำลังดำเนินการคูณสเกลาร์ ในกรณีนี้ คุณสามารถใช้ข้อมูลประจำตัวนี้ได้ $[k]P = [ k \mod n]P$
Franko avatar
cn flag
ขอบคุณ จะพยายาม
kelalaka avatar
in flag
และอย่าลืมว่าวิธีของ StackExchange คือการโหวตคำตอบหากมีประโยชน์กับคุณ และยอมรับคำตอบหากตรงกับคำถามของคุณ มีความสุข.
Score:4
ธง in

มีความสับสนเกี่ยวกับคำศัพท์เกี่ยวกับเส้นโค้งวงรีในคำถามนี้ ให้จัดการบางส่วนของพวกเขา

เส้นโค้งวงรี

เส้นโค้งวงรีในทางพีชคณิตคือ

$$E(\mathbb{K}) := \{ (x, y) \in \mathbb{K}^2 \กลาง y^2+a_1xy+a_3y = x^3+a_2x^2+a_4x+a_6\ } \cup \{\mathcal O\}$$

$\{\mathcal O\}$ เป็น จุดที่ไม่มีที่สิ้นสุด เพิ่มเป็นพิเศษที่ไม่มีการแสดงในรูปเรขาคณิตของเส้นโค้ง

ประเด็นคือ $(x,y)$ ทูเพิลนั้น ตอบสนอง สมการเส้นโค้งจึงไม่ใช่จำนวนเต็ม!

การเพิ่มจุด

การบวกจุดมีความหมายทางเรขาคณิตที่ดีมาก ในภาพด้านล่าง $P,Q,R$ แสดงถึงจุดบนเส้นโค้งและ $\{\mathcal O\}$ แสดงเป็น $0$

การตีความทางเรขาคณิตของการบวกบนเส้นโค้งไวเออร์สตราส

และเราดึงเอา สมการเลขคณิต จากนี้ ( กฎคอร์ดสัมผัส). สำหรับรายละเอียดการสกัดดูที่ บทที่ 2 ของหนังสือของวอชิงตัน.

จุดของเส้นโค้งก่อตัวเป็น กลุ่มอาเบลเลียน ภายใต้ตัวดำเนินการบวกจุดที่มีองค์ประกอบเอกลักษณ์ $\{\mathcal O\}$.

การคูณสเกลาร์

เมื่อเราเพิ่มจุด $พี$ สำหรับตัวมันเอง เราพูดว่า สองเท่า บางคนเขียนเป็น $2P$อย่างไรก็ตาม วิธีทั่วไปและดีกว่าในการเขียนคือ $[2]P$. ดังนั้น $[2]P = P + P$.

ในทำนองเดียวกัน เราสามารถพูดถึงการเพิ่มสามครั้ง สี่ครั้ง หรือ $t$ ครั้ง.

$$[t]P : = \underbrace{P + P + \cdots + P}_{t-times}$$

นี่คือสิ่งที่เราเรียกว่า การคูณสเกลาร์ (จริง ๆ แล้วเป็น Z-Module สำหรับกลุ่ม Abelian)

เครื่องกำเนิดไฟฟ้า

เครื่องกำเนิดของกลุ่มวัฏจักรเป็นองค์ประกอบ $G$ เช่นนั้นเมื่อ $G$ เพิ่มตัวเองครั้งแล้วครั้งเล่า มันจะสร้างองค์ประกอบทั้งหมดของกลุ่ม (ขออภัยสำหรับนักทฤษฎีกลุ่ม ตัวพิมพ์ใหญ่ชนกันที่นี่ - องค์ประกอบ $g$ ของกลุ่ม $G$ เป็นเครื่องกำเนิดไฟฟ้าถ้า $\langle g \rangle = G$).

คำสั่ง

คำสั่งมีสองประเพณีใน ECC

  1. ลำดับของเส้นโค้งวงรี $|\#E(\mathbb{K})|$ หมายถึงจำนวนองค์ประกอบของเส้นโค้ง

  2. ลำดับขององค์ประกอบ

    เมื่อเส้นโค้งมีลำดับเฉพาะเช่นเดียวกับใน Secp256k1 ทุกองค์ประกอบจะมีลำดับเดียวกันกับลำดับของเส้นโค้ง และนี่หมายความว่าทุกองค์ประกอบเป็นตัวสร้าง

กลับไปที่คำถามของคุณ

ใน Secp256k1 จุดฐาน

G = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
83121579216557378445487899878180864668798711284981320763518679672151497189239 )

และลำดับของฐาน $n$ เป็น

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

คำสั่งหมายความตามนั้น $[n]G = \mathcal{O}$ และเราสามารถใช้สิ่งนี้เพื่อหาสมการด้านล่าง

$$[k]P = [ k \bmod n]P$$

  • ดังนั้นสิ่งที่คุณทำคือ $+2$ เป็น

    $$[n-1]G + [2]G = [n-1+2]G = [n+1]G = [1]G = G$$

  • ดังนั้นสิ่งที่คุณทำคือ $+1$ เป็น

    $$[n-1]G + [1]G = [n-1]G = [n]G = \mathcal{O}$$


เรามาสิ้นสุดการตรวจสอบด้วย SageMath กัน

#secp256k1
p = จำนวนเต็ม ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC2F")
a = จำนวนเต็ม("0x000000000000000000000000000000000000000000000000000000000000000")
b = จำนวนเต็ม("0x0000000000000000000000000000000000000000000000000000000000000007")

K = GF(พี)
E = EllipticCurve(K,[a,b])
พิมพ์(อี)

G = E(จำนวนเต็ม("0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"),
      จำนวนเต็ม ("0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"))
พิมพ์("\nG =",G)

n = G.คำสั่ง()

พิมพ์ ("\n คำสั่งของ G =",n)

G2 = 2*G
Q = (n-1)*G + 2*G
พิมพ์("\n[n-1]G+[2]G =",Q)
ยืนยัน (Q == G)

R = (n-1)*G +G
พิมพ์("\n[n-1]G+G =",Q)
พิมพ์(R)

และผลลัพธ์คือ

Elliptic Curve กำหนดโดย y^2 = x^3 + 7 บน Finite Field ขนาด 115792089237316195423570985008687907853269984665640564039457584007908834671663

G = (55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)

คำสั่งของ G = 115792089237316195423570985008687907852837564279074904382605163141518161494337

[n-1]G+[2]G = (55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)

[n-1]G+G = (55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)
(0 : 1 : 0)
kelalaka avatar
in flag
ใช่ คุณสามารถพูดถึงจุดเป็นจำนวนเต็มโดยจำนวนเต็มแทนสเกลาร์ที่จำเป็นในการคูณด้วย $G$ อย่างไรก็ตาม สิ่งที่ตรงกันข้ามคือลอการิทึมแบบไม่ต่อเนื่อง เช่น ให้ $P$ find $t \in Z$ เช่นนั้น $P = [t]G$ และนี่คือแกนหลักของความปลอดภัยของ ECC จำนวนมากและเป็นปัญหาที่ยาก เป็นเรื่องปกติที่เราสามารถเก็บดัชนี ( $t$'s สำหรับแต่ละ $P$) เพื่อให้เร็วขึ้นได้ อย่างไรก็ตาม ส่วนใหญ่คุณจะได้รับ $P$ โดยไม่มีดัชนีเหมือนใน Elliptic Curve Diffie-Hellman Key การแลกเปลี่ยน (ECDH)
Franko avatar
cn flag
ขอบคุณมากสำหรับคำตอบโดยละเอียด ขออภัยสำหรับคำอธิบายจุดที่ไม่ถูกต้อง ฉันเข้าใจว่าจุดใดคือพิกัด x y ไม่ใช่จำนวนเต็ม แต่สำหรับฉัน อธิบายจุดเป็นจำนวนเต็มได้ง่ายกว่าเพราะมันแสดงจำนวนที่อยู่หลังจุดนี้ และขอบคุณสำหรับการคำนวณ ตอนนี้ฉันเห็นชัดเจนว่าเกิดอะไรขึ้นเมื่อฉันเพิ่มจุดนี้ แต่ฉันมีคำถามใหม่ มีวิธีที่เป็นไปได้ในการติดตามว่าผลลัพธ์ของการเพิ่มคะแนนใดที่มากกว่า n และคะแนนผลลัพธ์อยู่ใน "รอบที่สอง" หรือไม่ เป็นไปได้ไหม?
kelalaka avatar
in flag
ถ้าคุณให้พิกัด $P$ และ $Q$ แก่ฉัน ก็ไม่มีทางเป็นไปได้สำหรับฉัน อย่างที่ฉันพูดถึงในความคิดเห็นที่แล้ว นั่นคือสิ่งที่จำเป็นต้องแก้ลอการิทึมแบบไม่ต่อเนื่องบน Seckp256k1 โปรดทราบว่าจะไม่มีการปัดเศษเมื่อคุณพิจารณา $P+Q$ เนื่องจากสูตรการบวกไม่จำเป็นต้องใช้ดัชนีและจุดฐาน

โพสต์คำตอบ

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