ความสุ่มและภาวะสุ่มเทียม

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

Definition

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

Scope

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

Core questions

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

Key concepts

• เอนโทรปีและความสุ่มจริง
• เครื่องกำเนิดตัวเลขสุ่ม
• เครื่องกำเนิดสุ่มเทียม (PRG)
• ฟังก์ชันสุ่มเทียม (PRF)
• การเรียงสับเปลี่ยนสุ่มเทียม (PRP)
• การไม่สามารถแยกแยะได้ด้วยการคำนวณ
• การสร้างเมล็ดพันธุ์และกุญแจ
• ความล้มเหลวจากการนำความสุ่มกลับมาใช้ซ้ำ
• การปรับสภาพเอนโทรปี

Key theories

เครื่องกำเนิดสุ่มเทียม

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

ฟังก์ชันและเรียงสับเปลี่ยนสุ่มเทียม

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

Mechanisms

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

Clinical relevance

ความล้มเหลวของความสุ่มเป็นสาเหตุที่เกิดขึ้นซ้ำๆ ของการโจมตีที่ร้ายแรงในโลกแห่งความเป็นจริง: ข้อผิดพลาดของ Debian OpenSSL ในปี 2008 ทำให้การสร้างกุญแจใช้งานไม่ได้, นอนซ์ ECDSA ที่คาดเดาได้ทำให้กุญแจส่วนตัวรั่วไหล (Sony PlayStation 3, กระเป๋าเงิน Bitcoin บางส่วน), และเอนโทรปีของอุปกรณ์ฝังตัวที่อ่อนแอทำให้เกิดกุญแจที่คาดเดาได้ในวงกว้าง ดังนั้น ความสุ่มที่แข็งแกร่ง — การรวบรวมเอนโทรปีที่เหมาะสมและเครื่องกำเนิดสุ่มเทียมที่ผ่านการตรวจสอบ — จึงเป็นสิ่งจำเป็นสำหรับการใช้งานการเข้ารหัสลับทุกประเภท

Evidence & guidelines

NIST SP 800-90A/B/C ระบุเครื่องกำเนิดบิตสุ่มแบบกำหนดเองที่ได้รับการอนุมัติ, การตรวจสอบแหล่งเอนโทรปี, และแนวทางการสร้าง แนวปฏิบัติที่ดีที่สุดคือการใช้ RNG การเข้ารหัสลับที่ผ่านการตรวจสอบของระบบปฏิบัติการ (แทนที่จะสร้างขึ้นเอง), ตรวจสอบให้แน่ใจว่ามีเอนโทรปีเพียงพอก่อนที่จะสร้างกุญแจ, และไม่นำนอนซ์กลับมาใช้ซ้ำ ชุดทดสอบทางสถิติช่วยตรวจจับข้อบกพร่องร้ายแรง แต่ไม่สามารถสร้างความแข็งแกร่งทางคณิตศาสตร์ได้

History

ทฤษฎีการคำนวณของภาวะสุ่มเทียมก่อตั้งโดย Blum และ Micali และโดย Yao ประมาณปี 1982 โดยกำหนดความไม่สามารถคาดเดาได้และการไม่สามารถแยกแยะได้ Goldreich, Goldwasser, และ Micali แสดงให้เห็นถึงวิธีการสร้างฟังก์ชันสุ่มเทียมจากเครื่องกำเนิดในปี 1986 และ Hastad, Impagliazzo, Levin, และ Luby ได้พิสูจน์ในภายหลังว่าเครื่องกำเนิดสุ่มเทียมมีอยู่จริงหากฟังก์ชันทางเดียวมีอยู่จริง ภัยพิบัติทางปฏิบัติที่เกิดขึ้นซ้ำๆ จากความสุ่มที่อ่อนแอทำให้คุณภาพของเอนโทรปีและ RNG เป็นข้อกังวลหลักทางวิศวกรรม

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

เหตุใดฉันจึงไม่สามารถใช้ฟังก์ชันสุ่มปกติ เช่น rand() สำหรับการเข้ารหัสลับได้?

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

ความแตกต่างระหว่างความสุ่มจริงกับภาวะสุ่มเทียมคืออะไร?

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