ตัวสร้างเลขสุ่มของเรา
RNG มีหลายประเภท ซึ่งแต่ละแบบมีข้อดีข้อเสียแตกต่างกันไป โดย Rand ได้รวบรวมตัวสร้างสำเร็จรูปที่สะดวกต่อการใช้งานไว้ใน โมดูล rngs โดยส่วนใหญ่แล้ว คุณสามารถเรียกใช้ rand::rng ได้ทันที ซึ่งเป็นฟังก์ชันที่จะสร้างและกำหนดค่าเริ่มต้นให้กับ RNG ประจำหน่วยความจำระดับเธรดโลคอลโดยอัตโนมัติ พร้อมทั้งคืนค่าอ้างอิงกลับมาให้ โดยตัวสร้างนี้ทำงานได้อย่างรวดเร็ว ให้คุณภาพความสุ่มสูง และมั่นคงปลอดภัยในเชิงรหัสลับ (ตามความรู้ทางวิทยาการรหัสลับในปัจจุบัน)
เนื้อหาในเอกสารนี้:
ตัวสร้างต่างๆ
ตัวสร้างเลขสุ่มเทียมพื้นฐาน (PRNG)
เป้าหมายหลักของ PRNG ที่ไม่ใช่เชิงรหัสลับแบบ “มาตรฐาน” คือการสร้างสมดุลที่ลงตัวระหว่างความเรียบง่าย คุณภาพทางสถิติ การประหยัดหน่วยความจำ และประสิทธิภาพความเร็ว ตัวสร้างที่ไม่ใช่เชิงรหัสลับได้รับการพัฒนาขึ้นมาก่อนตัวสร้างเชิงรหัสลับ และในหลายบริบทก็ถูกแทนที่ไปแล้ว แต่ถึงกระนั้น ตัวสร้างที่ไม่ใช่เชิงรหัสลับก็ยังมีข้อได้เปรียบเฉพาะตัวที่โดดเด่นอยู่หลายประการ ได้แก่: ขนาดสถานะภายในกะทัดรัด, เริ่มต้นทำงานได้อย่างรวดเร็ว, โครงสร้างเรียบง่าย, และประหยัดพลังงานเป็นพิเศษบนชิปซีพียูแบบฝังตัว (embedded) (แม้ว่าจะไม่ใช่ PRNG ที่ไม่ใช่เชิงรหัสลับทุกตัวจะมีข้อดีเหล่านี้ครบถ้วน เช่น Mersenne Twister ที่มีขนาดสถานะใหญ่มากแม้จะคาดเดาผลลัพธ์ได้ง่ายก็ตาม)
ขั้นตอนวิธีเหล่านี้มีความสำคัญอย่างยิ่งต่อการจำลองด้วยระเบียบวิธีมอนติคาร์โล (Monte Carlo simulations) ตลอดจนเหมาะกับงานอื่นๆ อีกมากมาย เช่น อัลกอริทึมแบบสุ่มและเกมคอมพิวเตอร์ ซึ่งการที่ผลลัพธ์สามารถทำนายได้นั้นไม่ได้ก่อให้เกิดปัญหา (อย่างไรก็ตาม โปรดทราบว่าสำหรับเกมการพนัน ความสามารถในการทำนายผลลัพธ์ย่อมส่งผลกระทบโดยตรงต่อความปลอดภัย จึงแนะนำให้เลือกใช้ PRNG เชิงรหัสลับเสมอ)
โปรเจกต์ Rand ได้จัดเตรียม PRNG ที่ไม่ใช่เชิงรหัสลับไว้ให้เลือกใช้หลายตัว ซึ่งสามารถสรุปตัวเด่นๆ ได้ดังตารางด้านล่างนี้ นอกจากนี้ คุณยังสามารถศึกษาเพิ่มเติมได้จากเว็บไซต์ pcg-random และ xoshiro
| ชื่อ | ชื่อเต็ม | ประสิทธิภาพ | หน่วยความจำ | คุณภาพ | คาบ | ฟีเจอร์ |
|---|---|---|---|---|---|---|
SmallRng | (ไม่ระบุ) | เร็ว | เล็ก | ★★★☆☆ | ≥ u32 * 264 | พอร์ตไม่ได้ |
Pcg32 | PCG XSH RR 64/32 (LCG) | 5 GB/s | 16 ไบต์ | ★★★☆☆ | u32 * 264 | ก้าวกระโดดลำดับ |
Pcg64 | PCG XSL 128/64 (LCG) | 7 GB/s | 32 ไบต์ | ★★★☆☆ | u64 * 2128 | ก้าวกระโดดลำดับ |
Pcg64Mcg | PCG XSL 128/64 (MCG) | 8 GB/s | 16 ไบต์ | ★★★☆☆ | u64 * 2126 | ก้าวกระโดดลำดับ |
XorShiftRng | Xorshift 32/128 | 7 GB/s | 16 ไบต์ | ★☆☆☆☆ | u32 * 2128 - 1 | — |
Xoshiro256PlusPlus | Xoshiro256++ | 11 GB/s | 32 ไบต์ | ★★★☆☆ | u64 * 2256 - 1 | ก้าวกระโดดลำดับ |
Xoshiro256Plus | Xoshiro256+ | 13 GB/s | 32 ไบต์ | ★★☆☆☆ | u64 * 2256 - 1 | ก้าวกระโดดลำดับ |
SplitMix64 | splitmix64 | 13 GB/s | 8 ไบต์ | ★☆☆☆☆ | u64 * 264 | — |
StepRng | counter | 35 GB/s | 16 ไบต์ | ☆☆☆☆☆ | u64 * 264 | — |
ตัวเลขประสิทธิภาพในตารางเป็นการวัดแบบคร่าวๆ สำหรับการสร้างเอาต์พุต u64 บนซีพียู
AMD Ryzen 9 9950X3D (โปรดทราบว่าตัวเลขนี้อาจแปรผันตามแอปพลิเคชัน โดยทั่วไปแล้ว RNG เชิงรหัสลับจะทำงานได้ดียิ่งขึ้นเมื่อสร้างเอาต์พุตเป็นลำดับไบต์) ส่วนคะแนนคุณภาพอิงตามการวิเคราะห์ทางทฤษฎีและข้อบกพร่องทางสถิติที่ตรวจพบ โดยมีเกณฑ์คร่าวๆ ดังนี้:
- ★☆☆☆☆ = เหมาะกับแอปพลิเคชันพื้นฐานทั่วไป แต่ยังมีข้อบกพร่องอย่างมีนัยสำคัญ
- ★★☆☆☆ = ไม่พบปัญหาสำคัญในการทดสอบคุณภาพทางสถิติ
- ★★★☆☆ = รากฐานทฤษฎีดี และไม่พบปัญหาสำคัญในการทดสอบคุณภาพ
- ★★★★★ = คุณภาพระดับวิทยาการรหัสลับ
ตัวสร้างเลขสุ่มเทียมเชิงรหัสลับ (CSPRNG)
CSPRNG มีมาตรฐานและข้อกำหนดที่เข้มงวดกว่า PRNG พื้นฐานอย่างมาก ปัจจัยหลักที่ต้องให้ความสำคัญสูงสุดคือความปลอดภัย ประสิทธิภาพและความเรียบง่ายยังคงสำคัญ แต่โดยทั่วไป CSPRNG จะมีความซับซ้อนมากกว่าและทำงานช้ากว่า PRNG ทั่วไป ส่วนเรื่องคุณภาพทางสถิตินั้นไม่ใช่ประเด็นที่ต้องกังวลอีกต่อไป เนื่องจากข้อกำหนดพื้นฐานของ CSPRNG ระบุว่าเอาต์พุตที่สร้างขึ้นจะต้องไม่สามารถแยกแยะออกจากความสุ่มแท้จริงได้ เพราะหากมีความลำเอียงหรือความสัมพันธ์ใดๆ ปรากฏขึ้น เอาต์พุตนั้นก็จะถูกคาดเดาได้ง่ายขึ้นทันที
CSPRNG มีความเชื่อมโยงอย่างแนบแน่นกับขั้นตอนวิธีการเข้ารหัส (cipher) โดยไซเฟอร์แบบบล็อก (block cipher) ใดๆ สามารถแปลงให้เป็น CSPRNG ได้ด้วยการเข้ารหัสตัวนับ ในขณะที่ไซเฟอร์แบบสตรีม (stream cipher) โดยแก่นแท้ก็คือ CSPRNG ที่ผนวกเข้ากับการดำเนินการผสมข้อมูล (ซึ่งมักเป็นการ XOR) หมายความว่าเราสามารถนำไซเฟอร์แบบสตรีมใดๆ มาประยุกต์ใช้เป็น CSPRNG ได้อย่างตรงไปตรงมา
ไลบรารีนี้มี CSPRNG ให้เลือกใช้งานดังตารางด้านล่าง (ทั้งนี้ เราไม่สามารถรับประกันข้ออ้างด้านความปลอดภัยใดๆ ได้อย่างสมบูรณ์แบบ) โดยตารางนี้ได้ละคอลัมน์ “คุณภาพ” ออกไป เนื่องจาก CSPRNG ที่ดีจะต้องไม่มีข้อบกพร่องทางสถิติใดๆ ที่สังเกตได้
| ชื่อ | ชื่อเต็ม | ประสิทธิภาพ | การเริ่มต้น | หน่วยความจำ | ความปลอดภัย (การทำนายผลลัพธ์) | การรักษาความลับไปข้างหน้า |
|---|---|---|---|---|---|---|
StdRng | (ไม่ระบุ) | เร็ว | เร็ว | (ไม่ระบุ) | ได้รับความเชื่อถืออย่างกว้างขวาง | ไม่ |
ChaCha20Rng | ChaCha20 | 2.6 GB/s | เร็ว | 320 ไบต์1 | ผ่านการวิเคราะห์อย่างเข้มงวด | ไม่ |
ChaCha12Rng | ChaCha12 | 4.1 GB/s | เร็ว | 320 ไบต์1 | มีระดับความปลอดภัยเผื่อไว้สูงมาก | ไม่ |
ChaCha8Rng | ChaCha8 | 5.8 GB/s | เร็ว | 320 ไบต์1 | มีระดับความปลอดภัยเผื่อไว้เพียงพอ | ไม่ |
Hc128Rng | HC-128 | 4.6 GB/s | ช้า | 4176 ไบต์ | แนะนำโดย eSTREAM | ไม่ |
IsaacRng | ISAAC | 2.1 GB/s | ช้า | 2072 ไบต์ | ไม่ทราบ | ไม่ทราบ |
Isaac64Rng | ISAAC-64 | 3.7 GB/s | ช้า | 4136 ไบต์ | ไม่ทราบ | ไม่ทราบ |
ข้อสังเกต: ตัวสร้าง ISAAC ถูกรวมไว้ด้วยเหตุผลทางประวัติศาสตร์เท่านั้น เนื่องจากอยู่คู่กับภาษา Rust มาตั้งแต่ยุคเริ่มต้น แม้ว่าจะให้เอาต์พุตคุณภาพดีและยังไม่พบช่องโหว่การโจมตีที่สัมฤทธิ์ผล แต่มันกลับได้รับความสนใจจากผู้เชี่ยวชาญด้านวิทยาการรหัสลับค่อนข้างน้อย
บันทึกเกี่ยวกับตัวสร้าง
ประสิทธิภาพ
สิ่งแรกที่ควรทำความเข้าใจคือ PRNG ส่วนใหญ่ทำงานได้เร็วมาก และแทบไม่เคยตกเป็นคอขวดด้านประสิทธิภาพของระบบ
ประสิทธิภาพของ PRNG พื้นฐานเป็นเรื่องที่ค่อนข้างละเอียดอ่อน ขึ้นอยู่กับสถาปัตยกรรมของซีพียู (32 บิต เทียบกับ 64 บิต), การอินไลน์โค้ด (inlining) และจำนวนรีจิสเตอร์ที่พร้อมใช้งานเป็นอย่างมาก ส่งผลให้ประสิทธิภาพมักได้รับอิทธิพลจากโค้ดที่อยู่แวดล้อมอันเนื่องมาจากการอินไลน์และการแย่งใช้รีจิสเตอร์ของซีพียู
เมื่อต้องการเลือก PRNG เพื่อเน้นประสิทธิภาพ สิ่งสำคัญคือการวัดประสิทธิภาพ (benchmark) ภายในแอปพลิเคชันของคุณเอง เนื่องจากผลลัพธ์จริงจะขึ้นอยู่กับปฏิสัมพันธ์ระหว่าง PRNG กับโค้ดโดยรอบ สถาปัตยกรรมซีพียู ตลอดจนขนาดของข้อมูลที่เรียกขอ ด้วยเหตุนี้ เราจึงไม่ระบุตัวเลขประสิทธิภาพแบบเจาะจง แต่ให้คะแนนเชิงคุณภาพแทน
ในทางกลับกัน CSPRNG จะทำงานแตกต่างออกไปเล็กน้อย โดยทั่วไปมันจะสร้างบล็อกของเอาต์พุตเก็บไว้ในแคช แล้วค่อยดึงข้อมูลจากแคชออกมาใช้งาน กลไกนี้ช่วยให้ประสิทธิภาพเฉลี่ยอยู่ในเกณฑ์ดี และช่วยลดหรือขจัดอิทธิพลของโค้ดโดยรอบที่มีต่อความเร็วของ CSPRNG ได้อย่างมีประสิทธิผล
ประสิทธิภาพกรณีแย่ที่สุด
PRNG แบบเรียบง่ายจะสร้างค่าสุ่มแต่ละค่าขึ้นมาทันทีเมื่อมีการร้องขอ ส่วน CSPRNG มักจะสร้างข้อมูลขึ้นมาทั้งบล็อกในคราวเดียว แล้วทยอยอ่านข้อมูลจากแคชนี้จนหมด ทำให้เมื่อมีการเรียกขอข้อมูลสุ่มในปริมาณน้อยๆ ความสม่ำเสมอของเวลาที่ใช้จึงอาจมีความผันผวนมากกว่า
การใช้หน่วยความจำ
PRNG แบบพื้นฐานมักใช้หน่วยความจำน้อยมาก โดยทั่วไปเพียงไม่กี่คำ (words) ของหน่วยความจำ โดยที่หนึ่ง คำ มักมีขนาดเท่ากับ u32 หรือ u64 อย่างไรก็ดี สิ่งนี้อาจไม่เป็นจริงสำหรับ PRNG ที่ไม่ใช่เชิงรหัสลับทุกตัว ตัวอย่างเช่น อัลกอริทึม Mersenne Twister MT19937 ที่มีชื่อเสียงในอดีต ต้องใช้พื้นที่เก็บสถานะถึง 2.5 kB
สำหรับ CSPRNG มักต้องการหน่วยความจำมากกว่า เนื่องจากมีข้อแนะนำว่าขนาดซีดควรมีอย่างน้อย 192 บิต และตัวอัลกอริทึมเองอาจต้องใช้พื้นที่เพิ่มเติมอีกเล็กน้อย โดยขนาด 256 บิตถือเป็นขนาดขั้นต่ำที่ปลอดภัยในทางปฏิบัติ และหลายตัวใช้มากกว่านั้นค่อนข้างมาก ส่วน ChaCha20Rng ถือว่ามีขนาดสถานะที่ค่อนข้างกะทัดรัดเพียง 136 ไบต์
เวลาในการเริ่มต้น
ระยะเวลาที่ใช้ในการเริ่มต้นสร้างอินสแตนซ์ใหม่มีความแตกต่างกันอย่างมีนัยสำคัญ PRNG แบบง่ายหลายตัว ตลอดจนตัวสร้างเชิงรหัสลับบางตัว (รวมถึง ChaCha20Rng) เพียงแค่คัดลอกค่าซีดและค่าคงที่บางค่าลงในสถานะ ทำให้เริ่มต้นทำงานได้เร็วมาก ในทางตรงกันข้าม CSPRNG ที่มีสถานะขนาดใหญ่อาจจำเป็นต้องผ่านกระบวนการขยายคีย์ (key expansion) ซึ่งต้องใช้เวลาประมวลผลสูงกว่า
คุณภาพ
PRNG พื้นฐานจำนวนมากเป็นเพียงการประมวลผลระดับบิตและการคำนวณทางคณิตศาสตร์สั้นๆ ไม่กี่ขั้นตอน ความเรียบง่ายนี้ช่วยให้ทำงานได้เร็วมาก แต่ก็หมายความว่าอาจมีรูปแบบซ้ำซ้อนเล็กๆ ซ่อนอยู่ภายในสตรีมของตัวเลขสุ่มที่ผลิตออกมา
รูปแบบซ้ำซ้อนที่ซ่อนอยู่เหล่านี้มีผลกระทบมากน้อยเพียงใด? เป็นเรื่องยากที่จะระบุได้อย่างตายตัว เพราะขึ้นอยู่กับลักษณะการนำ RNG ไปใช้งาน หากเกิดความสัมพันธ์เชิงสหสัมพันธ์ (correlation) ระหว่างตัวเลขสุ่มกับขั้นตอนวิธีของแอปพลิเคชันที่นำมันไปใช้ ผลลัพธ์ที่คำนวณได้ก็อาจคลาดเคลื่อนหรือผิดเพี้ยนไปอย่างสิ้นเชิง
ตัวสร้างเลขสุ่มที่ดีคือตัวสร้างที่สามารถให้ผลลัพธ์ที่ถูกต้องแม่นยำในแอปพลิเคชันที่หลากหลายมากที่สุดเท่าที่จะเป็นไปได้ โดยคุณภาพของอัลกอริทึม PRNG สามารถประเมินได้ในระดับหนึ่งผ่านการวิเคราะห์ทางทฤษฎี เพื่อหาความยาววัฏจักรและตัดรูปแบบสหสัมพันธ์บางประการออกไป จากนั้นจึงนำไปทดสอบด้วยชุดเครื่องมือทดสอบเชิงประจักษ์ (empirical test suites) เพื่อตรวจดูว่า PRNG นั้นผ่านการทดสอบในสถานการณ์จำลองต่างๆ ได้ดีเพียงใด ซึ่งชุดทดสอบที่ทันสมัยและครอบคลุมที่สุดในปัจจุบันคือ TestU01 และ PractRand
ส่วน CSPRNG จะมีความซับซ้อนสูงกว่า และมีข้อกำหนดบังคับที่ชัดเจนว่าเอาต์พุตจะต้องไม่สามารถคาดเดาได้ ซึ่งหมายความว่าจะต้องไม่มีความสัมพันธ์เชิงสหสัมพันธ์ใดๆ ปรากฏระหว่างค่าเอาต์พุตให้ตรวจจับได้เลย
ดาวคุณภาพ:
PRNG ที่ได้คะแนนระดับ 3 ดาวขึ้นไป ถือว่ามีคุณภาพดีเพียงพอสำหรับงานทั่วไปส่วนใหญ่ที่ไม่ใช่เชิงรหัสลับ ส่วนระดับ 1 หรือ 2 ดาวอาจเพียงพอสำหรับแอปพลิเคชันหรือเกมทั่วไป แต่อาจให้ผลลัพธ์ที่ไม่น่าพึงพอใจกับอัลกอริทึมเชิงคำนวณบางประเภท
คาบ
คาบ (Period) หรือ ความยาววัฏจักร (Cycle length) ของ PRNG คือจำนวนค่าสูงสุดที่ตัวสร้างสามารถผลิตออกมาได้ ก่อนที่มันจะเริ่มวนกลับมาสร้างลำดับตัวเลขสุ่มซ้ำเดิม PRNG หลายตัวมีขนาดคาบที่คงที่แน่นอน ในขณะที่บางตัว (เช่น “RNG แบบเคออติก”) ความยาววัฏจักรอาจขึ้นอยู่กับค่าซีดและอาจมีรอบวัฏจักรที่สั้นลงได้ในบางกรณี
ข้อพึงระวัง: คาบที่ยาวไม่ได้เป็นสิ่งการันตีว่าคุณภาพความสุ่มจะสูงเสมอไป (เช่น วงจรตัวนับที่นับค่า u128 ไปเรื่อยๆ ก็มีคาบที่ยาวมาก แต่ไม่มีความสุ่มเลย) ในทางกลับกัน คาบที่สั้นเกินไปย่อมก่อให้เกิดปัญหาแน่นอน โดยเฉพาะเมื่อมีการเรียกใช้ RNG หลายตัวพร้อมกัน ในทางปฏิบัติเราแนะนำให้เลือกใช้ PRNG ที่มีคาบอย่างน้อย 2128 (หรืออาจใช้ PRNG ที่มีคาบสั้นลงมาอย่างน้อย 264 แต่รองรับการแบ่งหลายสตรีมได้อย่างอิสระ ทว่าสำหรับ PCG นั้น สตรีมย่อยต่างๆ ยังคงมีความสัมพันธ์เชิงสหสัมพันธ์ต่อกันอย่างใกล้ชิด)
หลีกเลี่ยงการใช้ค่าซ้ำ!
บนฮาร์ดแวร์ยุคปัจจุบัน ตัวสร้าง RNG ที่ทำงานเร็วและมีความยาววัฏจักรเพียง 264 สามารถถูกเปิดใช้งานต่อเนื่องได้นานนับศตวรรษก่อนที่ลำดับจะวนซ้ำ ทว่าเมื่อนำ RNG หลายตัวมาทำงานร่วมกันแบบขนาน (โดยแต่ละตัวได้รับค่าซีดที่ต่างกัน) จะมีความเสี่ยงสูงอย่างมีนัยสำคัญที่ลำดับตัวเลขที่แต่ละตัวสร้างขึ้นจะเกิดการทับซ้อนกัน
สำหรับตัวสร้างที่มีคาบขนาดใหญ่ P เมื่อมีตัวสร้างที่ทำงานอิสระต่อกัน n ตัว และแต่ละตัวสร้างลำดับความยาว L โอกาสที่จะเกิดการทับซ้อนกันระหว่างลำดับใดๆ สามารถประมาณได้ด้วยสูตร Ln² / P (เมื่อ nL / P มีค่าเข้าใกล้ศูนย์) สำหรับรายละเอียดเชิงลึกในเรื่องนี้ สามารถอ่านเพิ่มเติมได้จาก
ข้อสังเกตของทีมผู้พัฒนา Xoshiro
การชนกันและปฏิทรรศน์วันเกิด!
สำหรับตัวสร้างที่ขนาดเอาต์พุตเท่ากับขนาดสถานะ มีคำแนะนำว่าไม่ควรเรียกใช้เอาต์พุตเกิน √P ค่า โดยหลักการทั่วไปสำหรับตัวสร้างขนาด w บิตที่มีสถานะ kw บิต คือควรดูแลให้ kL² < P เสมอ ซึ่งข้อกำหนดนี้มีที่มาจาก
ปัญหาวันเกิดแบบทั่วไป (generalised birthday problem) ที่ศึกษาว่าเราสามารถสุ่มตัวอย่างที่ไม่ลำเอียงจากเซตขนาด d = 2^w ได้กี่ค่าก่อนที่ความน่าจะเป็นที่จะพบค่าซ้ำจะมีค่าอย่างน้อยครึ่งหนึ่ง โปรดทราบว่าเมื่อ kL² > P ตัวสร้างที่มีการกระจายตัวแบบสมดุลมิติ kw จะไม่สามารถสร้างจำนวนตัวอย่างซ้ำได้ตรงตามทฤษฎีความน่าจะเป็นที่คาดไว้ ทว่าตัวสร้างที่ขาดคุณสมบัติดังกล่าวก็ไม่มีสิ่งใดรับประกันว่าจะสร้างจำนวนครั้งที่ซ้ำได้ตรงตามที่ควรจะเป็นเช่นกัน
ความปลอดภัย
ความสามารถในการทำนาย
ในบริบทของการวิเคราะห์ PRNG ใดๆ เราสามารถตั้งคำถามสำคัญได้ว่า: หากผู้โจมตีล่วงรู้ค่าเอาต์พุตก่อนหน้าบางส่วนของ PRNG แล้ว จะสามารถทำนายค่าเอาต์พุตที่จะเกิดขึ้นในลำดับถัดไปได้หรือไม่? นี่คือคุณสมบัติชี้ขาดในทุกสถานการณ์ที่มีฝ่ายตรงข้ามคอยจับตาดูระบบอยู่
PRNG ทั่วไปมักจะสามารถทำนายผลลัพธ์ล่วงหน้าได้ แม้ว่าระดับความยากง่ายจะแตกต่างกันไป ในบางกรณีการทำนายทำได้ง่ายดายมาก ตัวอย่างเช่น Xorshift แบบพื้นฐานจะส่งออกส่วนหนึ่งของสถานะภายในออกมาตรงๆ การทำนายผลลัพธ์จึงทำได้ง่ายเพียงแค่ใช้ค่าเอาต์พุต u32 สี่ค่ามาคำนวณย้อนตั้งเป็นค่าซีดใหม่ของตัวสร้างได้ทันที ส่วนตัวสร้างอื่นๆ เช่น
PCG และ Xorshift* แบบตัดทอน
จะทำนายได้ยากกว่า แต่ก็ไม่ได้เกินขีดความสามารถของการคำนวณทางคณิตศาสตร์ทั่วไปบนเครื่องคอมพิวเตอร์ตั้งโต๊ะ
เกณฑ์ความปลอดภัยขั้นพื้นฐานที่สุดที่ CSPRNG ต้องมี คือการไม่สามารถทำนายค่าเอาต์พุตได้อย่างเด็ดขาด ซึ่งข้อกำหนดนี้ได้รับการนิยามอย่างเป็นทางการในชื่อ next-bit test โดยมีใจความสำคัญว่า: เมื่อกำหนดให้ทราบข้อมูล k บิตแรกของลำดับสุ่ม ลำดับนั้นจะผ่านเกณฑ์ next-bit test ก็ต่อเมื่อไม่มีอัลกอริทึมใดๆ ที่สามารถทำนายบิตถัดไปได้อย่างถูกต้องด้วยการใช้ทรัพยากรการคำนวณที่สมเหตุสมผล
คุณสมบัติด้านความปลอดภัยอีกประการหนึ่งที่ CSPRNG บางตัว มอบให้ คือการรักษาความลับไปข้างหน้า (forward secrecy): หมายความว่าหากสถานะภายในของ CSPRNG เกิดรั่วไหลออกไป ณ ขณะใดขณะหนึ่ง ผู้โจมตีจะต้องไม่สามารถคำนวณย้อนกลับเพื่อกู้คืนสถานะหรือค่าเอาต์พุตในอดีตได้ ข้อควรระวังคือ CSPRNG จำนวนมาก ไม่ได้ มีคุณสมบัติการรักษาความลับไปข้างหน้านี้ในการกำหนดค่าตามปกติ
การตรวจสอบและยืนยันข้ออ้างด้านความปลอดภัยของขั้นตอนวิธีทางคณิตศาสตร์ถือเป็นเรื่องที่ ยากและซับซ้อนอย่างยิ่ง ซึ่งเราไม่สามารถรับประกันความปลอดภัยของอัลกอริทึมที่โปรเจกต์นี้นำมาใช้หรือแนะนำได้อย่างสมบูรณ์แบบ เราจึงขอแนะนำให้อ้างอิงมาตรฐานจากสถาบัน NIST และเครือข่ายวิจัย ECRYPT สำหรับคำแนะนำที่เป็นทางการ
สถานะและการซีด
จุดสำคัญที่ต้องเน้นย้ำคือ ความปลอดภัยของ CSPRNG ขึ้นอยู่กับการได้รับค่าซีดจากคีย์สุ่มที่มั่นคงปลอดภัยอย่างแท้จริง หากคีย์ตั้งต้นนั้นเป็นที่ล่วงรู้หรือสามารถคาดเดาได้ เอาต์พุตทั้งหมดของ CSPRNG ก็จะถูกถอดรหัสได้โดยง่าย ซึ่งหมายความว่าค่าซีดจะต้องมาจากแหล่งกำเนิดที่เชื่อถือได้เสมอ โดยทั่วไปคือระบบปฏิบัติการ (OS) หรือจาก CSPRNG ตัวอื่นที่มีความน่าเชื่อถือสูง เพื่อตอบโจทย์นี้ เราแนะนำให้ใช้เครต getrandom ซึ่งเชื่อมต่อกับอินเทอร์เฟซตัวสร้างเลขสุ่มที่ปลอดภัยของ OS โดยตรง หรืออีกทางหนึ่ง คุณสามารถใช้ฟังก์ชันระดับ user-space อย่าง rand::make_rng() หรือ ThreadRng เพื่อป้อนค่าซีดก็ได้ ตัวอย่างเช่น:
#![allow(unused)]
fn main() {
use rand::{rngs::ChaCha12Rng, rngs::SysRng, SeedableRng};
/// Seed explicitly from SysRng:
let mut rng1 = ChaCha12Rng::try_from_rng(&mut SysRng).unwrap();
/// Seed from ThreadRng (or SysRng if ThreadRng is not available):
let mut rng2: ChaCha12Rng = rand::make_rng();
}
นอกจากนี้ สถานะภายในของ CSPRNG จะต้องถูกเก็บรักษาไว้เป็นความลับอย่างเคร่งครัด ด้วยเหตุนี้ การอิมพลีเมนต์ของเราจึงไม่อนุญาตให้เข้าถึงสถานะภายในส่วนใหญ่โดยตรง และการอิมพลีเมนต์เทรต Debug ก็จะไม่มีการพิมพ์ค่าสถานะภายในออกมาให้เห็น อย่างไรก็ดี สิ่งนี้ไม่ได้เป็นการปกป้องสถานะของ CSPRNG ได้อย่างสมบูรณ์แบบ 100% เพราะโค้ดอื่นๆ ที่ทำงานอยู่ภายในโปรเซสเดียวกันยังคงสามารถเข้าถึงหน่วยความจำส่วนนี้ได้ (และเรายังเปิดให้สามารถโคลนหรือซีเรียลไลซ์ CSPRNG ได้เพื่อความสะดวกในการพัฒนา) ยิ่งไปกว่านั้น โปรเซสที่กำลังทำงานอยู่อาจถูกระบบปฏิบัติการทำกระบวนการ fork ซึ่งอาจส่งผลให้ทั้งสองโปรเซสถือครองสำเนาของตัวสร้างที่มีสถานะเหมือนกันทุกประการ
ไม่ใช่ไลบรารีสำหรับการเข้ารหัสข้อมูล
กระบวนการทางวิทยาการรหัสลับ เช่น การเข้ารหัสข้อมูล (encryption) และการรับรองความถูกต้อง (authentication) มีความซับซ้อนสูงมาก และต้องอาศัยการอิมพลีเมนต์ที่ประณีตระมัดระวังอย่างยิ่งเพื่อหลีกเลี่ยงข้อบกพร่องและป้องกันการโจมตีในรูปแบบต่างๆ ดังนั้นสำหรับงานด้านความปลอดภัยโดยตรง จึงแนะนำให้เลือกใช้ไลบรารีเฉพาะทาง เช่น openssl, ring และกลุ่มไลบรารี RustCrypto libraries
เครตของ Rand มุ่งมั่นจัดเตรียมแหล่งข้อมูลสุ่มที่ไม่อาจคาดเดาได้ แต่ก็มีข้อจำกัดที่ควรทราบ: ประการแรก ซอฟต์แวร์นี้เผยแพร่ให้ใช้งาน “ตามสภาพ (as is)” โดยไม่มีการรับประกันใดๆ ประการที่สอง ระบบตั้งสมมติฐานว่าหน่วยความจำของโปรแกรมเป็นพื้นที่ส่วนตัว หากคุณมีความกังวลในจุดนี้ อาจพิจารณาเลือกใช้ตัวสร้างระดับระบบภายนอกอย่าง getrandom แทน นอกจากนี้ แม้กระทั่งความเป็นส่วนตัวของหน่วยความจำหลังจากคืนพื้นที่แล้วก็มีความสำคัญ ซึ่งแม้ว่าเราอาจผนวกมาตรการป้องกันเพิ่มเติมอย่างเครต zeroize เข้ามาในอนาคต แต่วิธีดังกล่าวก็ยังไม่อาจครอบคลุมได้ทั้งหมด และโปรดทราบว่า Rand ไม่ได้มีกลไกป้องกันปัญหาการฟอร์กโปรเซสโดยสมบูรณ์ (เวอร์ชันก่อนหน้าจนถึง 0.8.x เคยมีมาตรการบรรเทาปัญหาเบื้องต้น แต่ก็ไม่สามารถป้องกันได้ทั้งหมด) สุดท้ายนี้ มีปัจจัยอีกมากมายที่อาจทำลายคุณสมบัติความปลอดภัยได้ ตั้งแต่ช่องโหว่ระดับฮาร์ดแวร์ที่ซับซ้อนอย่าง Spectre ไปจนถึงข้อผิดพลาดที่ดูไม่น่าจะเกิดขึ้น (เช่น การเผลอพิมพ์สถานะภายในของตัวสร้างลงในไฟล์ล็อกของระบบ)
ฟีเจอร์เพิ่มเติม
PRNG บางตัวอาจมีความสามารถพิเศษเพิ่มเติม เช่น:
- รองรับหลายสตรีม (stream) ซึ่งช่วยเพิ่มประสิทธิภาพในงานประมวลผลแบบขนาน
- ความสามารถในการก้าวกระโดดลำดับ (jump) หรือเลื่อนตำแหน่งในสตรีมของตัวเลขสุ่ม ซึ่งหากตัวสร้างมีขนาดคาบที่ใหญ่มาก กลไกนี้สามารถนำมาใช้แทนการแบ่งสตรีมได้
อ่านเพิ่มเติม
ยังมีเนื้อหาและรายละเอียดเชิงลึกเกี่ยวกับ PRNG อีกมากมาย โดยบทความ PCG paper เป็นเอกสารที่อ่านเข้าใจง่ายและอธิบายแนวคิดเพิ่มเติมไว้อย่างน่าสนใจ
นอกจากนี้ บทความคุณภาพอีกชิ้นหนึ่งที่กล่าวถึงคุณภาพของตัวสร้างเลขสุ่มคือ “Good random number generators are (not so) easy to find” เขียนโดย P. Hellekalek