การตัดแต่งอินพุตแบบสุ่มอย่างสม่ำเสมอสำหรับคีย์ส่วนตัวของเส้นโค้งวงรี

ลองนึกภาพว่ามีเครื่องแบบ 256 บิต ป้อนข้อมูล จาก CSPRNG สมมติว่ามีเส้นโค้งเช่น secp256r1 ซึ่งมีลำดับเส้นโค้งน้อยกว่า 256 บิตเล็กน้อย

เราไม่สามารถเพียงแค่ mod (อินพุต, curve_order) เพราะมันจะแนะนำโมดูโลอคติ จะเกิดอะไรขึ้นถ้าเราตัด 256 บิตเป็น 255 บิตซึ่งน้อยกว่าคำสั่งเส้นโค้ง จากนั้นค่าทั้งหมดภายใน 255 บิตจะมีโอกาสปรากฏเท่ากัน

ดูเหมือนว่า ed25519 จะทำเช่นนั้นด้วยคำสั่งโค้ง ~ 252 บิต - ปรับ 3 บิต

การสุ่มตัวอย่างการปฏิเสธจาก NIST SP 800-56A rev 3 หัวข้อ 5.6.1.2.2 ไม่ใช่เวลาคงที่ ดังนั้นจึงควรมองหาสิ่งที่ง่ายกว่า

คำถามเพิ่มเติม: จะเกิดอะไรขึ้นถ้าเราปรับ 1 บิตสุดท้ายด้วยเพื่อให้คีย์นั้น 0 และ 1 จะไม่ปรากฏขึ้นโดยใช้ |= 2 ที่จะบังคับให้เป็น 1 เสมอ (เหมือนกับที่เราบังคับให้เริ่มต้นเป็น 0 เสมอ?

นี่คือวิธีที่ Monero codebase สร้างสเกลาร์แบบสุ่มเพื่อใช้กับ ed25519:

สำหรับเส้นโค้ง ed25519 คำสั่ง $\ell$ ของกลุ่มของจุดฐานคือ $2^{252}+27742317777372353535851937790883648493$.

เพื่อสร้างจำนวนสุ่มที่เป็นกลางน้อยกว่า $\ell$ก่อนอื่นเราจะพิจารณาว่าผลคูณสูงสุดของ $\ell$ ที่สามารถใส่ได้ 32 ไบต์คือ $15$.

ในการสร้างหมายเลขสุ่มที่ไม่เอนเอียง เราสร้างลำดับสุ่ม 32 ไบต์ซ้ำๆ และทดสอบว่ามีค่าน้อยกว่า $15\ell$. เมื่อเราพบจำนวนดังกล่าวแล้ว เราก็ลดจำนวนนี้ลงได้ $mod\ \ell$ โดยไม่แนะนำอคติแบบโมดูโล ความน่าจะเป็นในการหาหมายเลขสุ่มที่เหมาะสมในการวนซ้ำครั้งแรกนั้นมีค่าประมาณ 94%

เทคนิคเดียวกันนี้ใช้กับ secp256r1 ซึ่งคุณจะใช้ $3 \ell$ แทน $15\ell$ เนื่องจากลำดับของกลุ่มของจุดฐานสำหรับ secp256r1 มีขนาดใหญ่กว่า (ดู 2.4.2 พารามิเตอร์ที่แนะนำ secp256r1).ความน่าจะเป็นในการหาหมายเลขสุ่มที่เหมาะสมในการวนซ้ำครั้งแรกนั้นมีค่าประมาณ 95%