Score:0

การบีบอัดคีย์ Elliptic Curve

ธง in

ฉันมีเส้นโค้งวงรี y2 = x3 -x + 3 บนฟิลด์จำกัดที่ 127 ฉันกำลังพยายามบีบอัดจุดโดยใช้มาตรฐาน X9.62 ฉันรู้เกี่ยวกับการบีบอัดคีย์ที่คุณควรตรวจสอบว่าค่า y เป็นคู่หรือคี่เพื่อกำหนดว่าด้านใดของเส้นโค้งอยู่สำหรับจุดส่วนใหญ่บนเส้นโค้งนั้น จุดบนจะเป็นเลขคู่ และจุดล่างจะเป็นเลขคี่ อย่างไรก็ตาม สำหรับคู่ (16, 20) และ (16, 107) และคู่อื่นๆ จุดล่างจะเป็นเลขคู่และจุดบนเป็นเลขคี่

นี่หมายความว่าคุณไม่สามารถใช้การบีบอัดคีย์บนเส้นโค้งเฉพาะนี้หรือมีวิธีอื่นอีกหรือไม่

Score:2
ธง my

ฉันรู้เกี่ยวกับการบีบอัดคีย์ที่คุณควรตรวจสอบว่าค่า y เป็นคู่หรือคี่เพื่อกำหนดว่าด้านใดของเส้นโค้งอยู่

เพื่อให้แม่นยำยิ่งขึ้น คุณต้องตัดสินใจว่า $y$ เป็นคู่หรือคี่เพื่อให้คุณสามารถให้คำแนะนำเพียงพอสำหรับการคลายการบีบอัดเพื่อให้รู้ว่าสิ่งใด $y$ มูลค่าในการสร้างใหม่

สำหรับค่าใด ๆ ของ $x$มี (อย่างมากที่สุด) สองค่าสำหรับ $y$ ที่เป็นไปตามสมการเส้นโค้ง (ซึ่งในกรณีของคุณ $y^2 = x^3 - x + 3$). และปรากฎว่า (สำหรับฟิลด์ลักษณะคี่ ซึ่งก็คือ) หนึ่งในสองโซลูชันสำหรับ $y$ จะเป็นคู่และหนึ่งจะเป็นคี่ - ดังนั้นเพียงแค่ระบุว่า $y$ เป็นคู่หรือคี่เป็นข้อมูลที่เพียงพอสำหรับตัวคลายการบีบอัดที่จะรู้ว่าหมายถึงตัวใด

สำหรับจุดส่วนใหญ่บนเส้นโค้งนั้น จุดบนจะเป็นเลขคู่ และจุดล่างจะเป็นเลขคี่

ไม่ว่าเส้นโค้งจะอยู่ที่ "ครึ่งบน" (ซึ่งฉันคิดว่าหมายถึง $y > p/2$) หรือ "ครึ่งล่าง" ไม่เกี่ยวข้อง เราใช้ lsbit ไม่ว่าจะมีขนาดเท่าใดก็ตาม $y$ เกิดขึ้น

ตอนนี้ เราสามารถกำหนดอัลกอริธึมการบีบอัดทางเลือกที่ขึ้นอยู่กับว่า $y > p/2$แทนที่จะเป็น lsbit ของ $y$. ท้ายที่สุดแล้ว ในฟิลด์สำคัญ หนึ่งในวิธีแก้ปัญหาจะมี $y > p/2$ และอื่น ๆ จะมี $y < p/2$. อย่างไรก็ตาม นั่นไม่ใช่สิ่งที่ผู้คนทำกันจริงๆ (สาเหตุหนึ่งที่เป็นไปได้คือเนื่องจากการทดสอบบิตเดียวง่ายกว่าการเปรียบเทียบค่าเต็ม)

fgrieu avatar
ng flag
การบวก: เพื่อพิจารณาว่า $x\pmod p$ เป็นคู่หรือคี่ เราจะหาจำนวนเต็ม $a$ ในช่วง $[0,p)$ กับ $a\equiv x\pmod p$ นั่นคือ $a$ คำนวณเป็น $ a\gets x\bmod p$ และทดสอบว่า $a$ เป็นคู่หรือคี่ ตัวอย่างเช่น $129\pmod{127}$ เป็นเลขคู่ เนื่องจาก $2\equiv129\pmod{127}$ และ $0\le2

โพสต์คำตอบ

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