เราจะเลือกองค์ประกอบแบบสุ่มในการเข้ารหัสได้อย่างไร

ในทางปฏิบัติ เพื่อเลือกการสุ่มแบบสม่ำเสมอ $x\in \mathbb{Z}^*_q$เราลดงานนั้นลงเพื่อแก้ปัญหาการเลือกบิตแบบสุ่มและอิสระอย่างสม่ำเสมอ ในระบบคอมพิวเตอร์สมัยใหม่ จะมีบริการระบบปฏิบัติการบางอย่างที่จัดหาบิตดังกล่าว เช่น /dev/urandom ในอนุพันธ์ Unix จำนวนมาก (เราจะกลับไปที่ปัญหาว่าได้รับบิตดังกล่าวอย่างไรในส่วนที่สอง)

วิธีที่ง่ายที่สุดในการสุ่มแบบสม่ำเสมอ $x\in \mathbb{Z}^*_q$ซึ่งเป็นจำนวนเต็มใน $[0,q)$ซึ่งบางครั้งเรียกว่าการสุ่มตัวอย่างการปฏิเสธ ไปที่:

1. เป็นเบื้องต้นทำครั้งเดียวไม่ว่าจะกี่ $x$ เราต้องการสร้าง: เป็นฟังก์ชัน (กำหนด) ของ $คิว$เลือกบางส่วน $k$ กับ $2^k\ge คิว$, เช่น. $k$ มากกว่าจำนวนบิตเล็กน้อยในนิพจน์ไบนารีของ $คิว$.
2. วาด $k$ บิตสุ่มและอิสระอย่างสม่ำเสมอ $b_i$, สำหรับ $0\le ฉัน<k$
3. ประกอบ $k$ บิตเป็นจำนวนเต็ม $y=\sum b_i\,2^i$
4. ถ้า $y<(2^k\bmod q)$ดำเนินการต่อที่ 2
5. คำนวณและส่งออก $x=y\bmod q$.

ความน่าจะเป็นนั้น $x$ เป็นจำนวนเต็มเฉพาะใดๆ ใน $[0,q)$ เป็นที่แน่นอน $1/คิว$ ภายใต้สมมติฐานบิต $b_i$ เป็นแบบสุ่มและเป็นอิสระ

รูปแบบทั่วไป:

• ผลิตบิต $b_i$ จัดกลุ่มไว้ในคำคอมพิวเตอร์ และ/หรือ $k$ บังคับให้มีหลายขนาดบางคำ
• ความยิ่งใหญ่ที่ 2: $y=\sum b_i\,2^{k-i-1}$; นอกจากนี้ยังช่วยให้ $y$ ที่จะสร้างตามที่เราวาดไว้ $b_i$ เช่น $y_0=0$, $y_{i+1}=y_i+y_i+b_i$ สำหรับ $0\le ฉัน<k$, $y=y_k$.
• เงื่อนไขการทดสอบที่แตกต่างกันที่ 4 เช่น $y\ge2^k-(2^k\bmod q)$.

นอกจากนี้ เรายังสามารถลบขั้นตอนที่ 4 ออก (ซึ่งในกรณีนี้ วิธีการนี้ไม่ใช่การสุ่มตัวอย่างแบบปฏิเสธอีกต่อไป) เว้นเสียแต่ว่า $คิว$ เป็นเลขยกกำลังของ 2 ซึ่งจะทำให้จำนวนเต็มเหลืออยู่ $[0,2^k\bmod q)$ มีโอกาสมากกว่าผู้ที่อยู่ใน $[(2^k\bmod q), q)$ด้วยความน่าจะเป็น $\lceil 2^k/q\rceil/2^k$ ค่อนข้างมากกว่า $\ชั้น 2^k/q\rชั้น/2^k$. แต่ถ้า $k$ มีขนาดใหญ่กว่าจำนวนบิตในอย่างเหมาะสม $คิว$ (พูด, $k\>\lceil\log_2 q\rceil+64$ ) หรือ/และหาก $\min(2^k\bmod q,-2^k\bmod q)/q$ น้อยกว่าขีดจำกัดที่เหมาะสม (เช่น $2^{-128}$ ) ดังนั้นความลำเอียงนี้จึงตรวจไม่พบจากการทดลอง

(มีลักษณะเฉพาะที่ดีกว่าเมื่อเราสามารถลบขั้นตอนที่ 4 ออกได้ และวิธีการที่ซับซ้อนกว่าเพื่อลดจำนวนของ $b_i$ สร้างขึ้นเมื่อสร้างจำนวนมาก $x$แต่ใช้กันไม่ค่อยเป็น)

เรากลับมาที่ปัญหาของการเลือกบิตสุ่มและอิสระอย่างสม่ำเสมอ หรือบางทีคำคอมพิวเตอร์ที่ประกอบด้วยบิตดังกล่าว

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

ตัวอย่างแหล่งที่มา:

• อินพุตรวมถึงการกดแป้น ตำแหน่งเมาส์ ไมโครโฟน อินพุตกล้อง
• เวลาที่เกิดการกดแป้นพิมพ์ การเปลี่ยนตำแหน่งของเมาส์ บล็อกดิสก์ หรือแพ็กเก็ตอีเธอร์เน็ต/Wifi/บลูทูธ/USB มาถึงเมนบอร์ด โดยวัดได้เช่น ในรอบสัญญาณนาฬิกาตั้งแต่คอมพิวเตอร์เริ่มทำงาน
• อุปกรณ์เฉพาะ วิธีหนึ่งเปรียบเทียบแรงดันไฟฟ้าชั่วขณะระหว่าง a ซีเนอร์ไดโอด ค่าเฉลี่ยและสุ่มตัวอย่างผลลัพธ์เป็นระยะๆ อีกตัวอย่างหนึ่งออสซิลเลเตอร์ที่หวังว่าจะวุ่นวายโดยใช้อีกอันที่หวังว่าจะเป็นอิสระ

ควรใช้ความพยายามอย่างมากในการตรวจตราแหล่งที่มา เพื่อให้แน่ใจว่าแหล่งที่มานั้นทำงานอย่างถูกต้อง (หรือหากเรารวมหลายแหล่งเข้าด้วยกัน เพื่อประเมินค่าขั้นต่ำ เอนโทรปี เรามั่นใจได้ว่าพวกเขาร่วมกันส่งมอบ)

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

หากเราต้องการบิตสุ่มจำนวนมาก เราสามารถสร้างได้โดยใช้ต้นทุนต่ำโดยการเพาะ a เครื่องสร้างตัวเลขหลอกหลอกที่ปลอดภัยด้วยการเข้ารหัส โดยการสุ่มที่ได้มาตามวรรคท้าย อย่างไรก็ตาม หากสถานะของ CSPRNG ถูกบุกรุก (เช่น จากช่องด้านข้าง) เอาต์พุตทั้งหมดจะเป็น ด้วยเหตุนี้จึงมีวิธีการที่ซับซ้อนมากขึ้นในการรับบิตสุ่มที่มีความปลอดภัยสูงในอัตราที่สูง ด้วยวิธีที่สามารถกู้คืนได้อย่างดีจากการประนีประนอมของสถานะภายใน

เพิ่มเติม: ในซีพียูสมัยใหม่ มักจะมีแหล่งที่มาของออนไดย์ (ซึ่งบางครั้งอาจอยู่ในชิปเซ็ต) บ่อยครั้ง เอาต์พุตไม่สามารถเข้าถึงได้ด้วยวิธีที่มีการจัดทำเป็นเอกสารอย่างดี ข้อแก้ตัวสำหรับสิ่งนั้นคือผู้คนจะใช้มันโดยตรงหรือ/และโม้เกี่ยวกับการตรวจพบอคติบางอย่างในนั้นแม้ว่าจะเป็นที่คาดหมายก็ตาม โปรแกรมเมอร์ควรใช้เอาต์พุตที่มีเงื่อนไขลึกลับผ่านคำสั่งบางอย่าง (เช่น RDRAND). วิธีการตรวจสอบความสมบูรณ์ของแหล่งที่มามักไม่มีการจัดทำเป็นเอกสาร และ/หรือไม่รองรับในซอฟต์แวร์/ระบบปฏิบัติการ ปัญหาอื่นๆ ที่เป็นไปได้เกี่ยวกับ RNG ที่ใช้ CPU ได้แก่ การปกป้องความลับของเอาต์พุตไม่ดี ดูเช่น นี้. วาด (ตั้งใจเล่นสำนวน) ข้อสรุปของคุณเองว่าควรเชื่อถือได้หรือไม่ว่าเป็นแหล่งเดียวหรือการสุ่มใน crypto