ฉันสามารถรู้ได้จากรหัสสาธารณะของ Bitcoin ได้หรือไม่ว่ารหัสส่วนตัวนั้นเป็นเลขคี่หรือคู่?
เราหวังว่าคุณจะทำไม่ได้ ถ้าทำได้ คุณจะสามารถแก้ปัญหาบันทึกแยกได้ นั่นคือ ค้นหาคีย์ส่วนตัวทั้งหมด
ในคำศัพท์เกี่ยวกับการเข้ารหัส เรากล่าวว่า lsbit ของคีย์ส่วนตัวเป็นบิต "ฮาร์ดคอร์" เนื่องจากยากต่อการกู้คืนพอๆ กับค่าทั้งหมด
วิธีการทำนั้นตรงไปตรงมา (อย่างน้อยในกรณีที่ไม่น่าจะเป็นไปได้ ซึ่งอัลกอริทึม 'find-the-lsbit' ของคุณจะส่งกลับคำตอบที่ถูกต้องเสมอ) มันทำงานดังนี้ $\log(q)$ ครั้ง:
ใช้รหัสสาธารณะ $Y$ และใช้อัลกอริทึมของคุณเพื่อค้นหา lsbit ของคีย์ส่วนตัว สิ่งนี้ทำให้เรามี lsbit ของคีย์ส่วนตัว $y$.
หากบิตนั้นเป็น '1' ให้แทนที่ $Y := Y - G$; สิ่งนี้มีผลในการแทนที่ $y$ กับ $y-1$
จากนั้นแทนที่ $Y := [2^{-1}] Y$นั่นคือ ทำการคูณจุดด้วยการผกผันของ 2 (ซึ่งมีอยู่ เนื่องจากเส้นโค้งมีลำดับที่คี่); สิ่งนี้มีผลในการแทนที่ $y$ กับ $y/2$.
โดยการทำสิ่งนี้ $\log(p)$ ครั้งนี้จะอ่านบิตของเลขยกกำลังส่วนตัวในลำดับ lsbit-first; ให้คุณค่าทั้งหมดแก่เรา