Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

ชนิดของตัวสร้าง

ในบทก่อนหน้า เราได้รู้จักกับ RngCore ซึ่งเป็นเทรตหลักที่แหล่งข้อมูลสุ่ม ทุกตัวจำเป็นต้องอิมพลีเมนต์ แต่คำว่าแหล่งข้อมูลสุ่มแท้จริงแล้วคืออะไร และมีรูปแบบใดบ้าง?

เนื้อหาในบทนี้จะเน้นทฤษฎีพื้นฐาน หากต้องการศึกษาตัวสร้างเฉพาะตัวที่ Rand มีให้ใช้งาน โปรดดูเพิ่มเติมได้ที่บท ตัวสร้างเลขสุ่ม

use rand::{RngExt, SeedableRng};

fn main() {
// prepare a non-deterministic random number generator:
let mut rng = rand::rng();
println!("{}", rng.random::<i32>()); // prints an unknown value

// prepare a deterministic generator:
let mut rng = rand::rngs::ChaCha8Rng::seed_from_u64(123);
println!("{}", rng.random::<i32>()); // prints -416273517
}

ตัวสร้างเลขสุ่มแท้

ตัวสร้างเลขสุ่มแบบแท้ หรือ TRNG (True Random Number Generator) คือกลไกที่สร้างตัวเลขสุ่มโดยการตรวจวัดสัญญาณทางกายภาพจากปรากฏการณ์ธรรมชาติ เช่น การสลายตัวของสารกัมมันตรังสี หรือสัญญาณรบกวนทางความร้อน (thermal noise) (ทั้งนี้ ไม่ว่าปรากฏการณ์เหล่านี้จะสุ่มอย่างแท้จริง หรือแท้จริงแล้วเป็นระบบดีเทอร์มินิสติก — เช่น ในสมมติฐานว่าจักรวาลนี้คือแบบจำลองคอมพิวเตอร์ — ก็ไม่ใช่ประเด็นสำคัญในที่นี้ เพราะสำหรับการใช้งานของเรา ขอเพียงผลลัพธ์ที่ได้ไม่สามารถแยกแยะออกจากความสุ่มแท้จริงได้ก็เพียงพอแล้ว)

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

ตัวสร้างเลขสุ่มเทียม

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

  • สถานะภายใน (internal state) เริ่มต้น
  • ฟังก์ชันสำหรับคำนวณสร้างค่าสุ่มจากสถานะปัจจุบัน
  • ฟังก์ชันสำหรับเลื่อนสถานะภายในก้าวไปยังสถานะถัดไป
  • (ทางเลือก) ฟังก์ชันสำหรับแปลงค่า ซีด (seed) หรือ คีย์ (key) ให้กลายเป็นสถานะเริ่มต้น

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

จุดเด่นสำคัญอีกประการของ PRNG คือความเร็วที่สูงมาก: ขั้นตอนวิธีบางตัวใช้คำสั่ง CPU เพียงไม่กี่คำสั่งต่อการสุ่มหนึ่งค่า จึงสามารถผลิตข้อมูลสุ่มตามต้องการได้เร็วกว่า TRNG ส่วนใหญ่หลายเท่าตัว

อย่างไรก็ดี PRNG ยังมีข้อจำกัดสำคัญหลายประการที่ต้องคำนึงถึง:

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

ตัวสร้างเลขสุ่มเทียมเชิงรหัสลับ

ตัวสร้างเลขสุ่มเทียมเชิงรหัสลับ หรือ CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) คือกลุ่มย่อยของ PRNG ที่ผ่านเกณฑ์ความปลอดภัยระดับสูง กล่าวคือ:

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

การสร้างเลขสุ่มที่ปลอดภัยอย่างแท้จริง ไม่ได้อาศัยเพียงขั้นตอนวิธีที่มั่นคงปลอดภัย (CSPRNG) เท่านั้น แต่ยังต้องมีค่าซีดที่ปลอดภัยและมีขนาดใหญ่เพียงพอด้วย (โดยทั่วไปคือ 256 บิต) ตลอดจนมีระบบป้องกันการโจมตีผ่านช่องทางด้านข้าง (side-channel attacks เพื่อป้องกันไม่ให้ผู้โจมตีแอบอ่านสถานะภายใน)

นอกจากนี้ CSPRNG ชั้นดียังมีคุณสมบัติประการที่สามเพิ่มเติมด้วย นั่นคือ:

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

ตัวสร้างเลขสุ่มแบบฮาร์ดแวร์

ตัวสร้างเลขสุ่มแบบฮาร์ดแวร์ หรือ HRNG (Hardware Random Number Generator) ในทางทฤษฎีคืออุปกรณ์แปลงสัญญาณจาก TRNG ทางกายภาพมาเป็นข้อมูลดิจิทัล แต่ในทางปฏิบัติ อุปกรณ์เหล่านี้มักผนวกเอา PRNG เข้ามาช่วยขจัดความลำเอียง (debias) ของสัญญาณจาก TRNG ด้วย แม้ว่า HRNG จะอาศัยฐานจาก TRNG แต่ก็ไม่ได้แปลว่าจะปลอดภัยเสมอไป: เพราะตัว TRNG เองอาจผลิตเอนโทรปีได้ไม่เพียงพอ (ทำให้สุ่มเดาได้ง่ายเกินไป) หรือกระบวนการขยายสัญญาณและการขจัดความลำเอียงอาจมีข้อบกพร่อง

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

เนื่องจาก PRNG จำเป็นต้องมีค่าซีดที่สุ่มจริงจึงจะปลอดภัย การมี HRNG จึงช่วยป้อนค่าซีดดังกล่าวได้ ทว่าเป้าหมายส่วนใหญ่ของการใช้งานคือ “เพียงแค่” ต้องการค่าสุ่มที่ไม่สามารถทำนายล่วงหน้าได้ จึงมีทางเลือกอื่นที่ยอมรับได้และนำมาใช้ทดแทนตัวสร้างเลขสุ่มแท้ (ดูหัวข้อถัดไป)

เอนโทรปี

ดังที่ได้ระบุไว้ข้างต้น การที่ CSPRNG จะปลอดภัยได้นั้น ค่าซีดของมันก็ต้องมีความปลอดภัยด้วย คำว่า เอนโทรปี (entropy) สามารถใช้ได้ในสองบริบท:

  • ในแง่การวัดปริมาณข้อมูลที่ไม่ทราบค่า (ความไม่แน่นอน) ที่บรรจุอยู่ในชุดข้อมูลนั้นๆ
  • ในแง่ของก้อนข้อมูลที่ไม่ทราบค่าโดยตรง

ในทางอุดมคติ ค่าสุ่มแบบบูลีนหรือการโยนเหรียญหนึ่งครั้งจะมีเอนโทรปี 1 บิตเต็ม แต่หากเหรียญนั้นมีความลำเอียง ปริมาณเอนโทรปีก็จะลดลง โดยมีทฤษฎีเอนโทรปีของแชนนอน (Shannon Entropy) ทำหน้าที่วัดปริมาณความไม่แน่นอนนี้

ตัวอย่างเช่น ค่าเวลา Unix timestamp (จำนวนวินาทีนับตั้งแต่ต้นปี 1970) ประกอบด้วยทั้งข้อมูลความละเอียดต่ำและสูง โดยทั่วไปจะเป็นตัวเลขขนาด 32 บิต แต่ปริมาณเอนโทรปีที่แท้จริงจะขึ้นอยู่กับว่าผู้โจมตีในทางทฤษฎีสามารถคาดเดาตัวเลขนั้นได้แม่นยำเพียงใด หากผู้โจมตีสามารถเดาได้ใกล้เคียงในระดับนาที เอนโทรปีของมันอาจเหลือเพียงประมาณ 6 บิต (2^6 = 64) แต่หากผู้โจมตีสามารถเดาได้แม่นยำถึงระดับวินาที เอนโทรปีจะกลายเป็น 0 บิตทันที ทั้งนี้ เครต JitterRng ได้ประยุกต์ใช้แนวคิดนี้เพื่อรวบรวมเอนโทรปีโดยไม่ต้องพึ่งพา HRNG (โดยอาศัยตัวจับเวลาความละเอียดระดับนาโนวินาที และตั้งสมมติฐานแบบรัดกุมว่ามีเอนโทรปีเพียงไม่กี่บิตต่อหนึ่งค่าเวลา หลังจากผ่านการทดสอบคุณภาพของตัวจับเวลาหลายขั้นตอนแล้ว)