ตัวเลขสุ่มเทียมคือหมายเลขพิเศษที่สร้างโดยเครื่องกำเนิดพิเศษ Deterministic Random Bit Generator (PRNG) หรือที่รู้จักในชื่อ Deterministic Random Bit Generator (DRBG) เป็นอัลกอริทึมสำหรับการสร้างลำดับของตัวเลขที่มีคุณสมบัติใกล้เคียงกับลักษณะของลำดับตัวเลขสุ่ม ลำดับ PRNG ที่สร้างขึ้นไม่ใช่การสุ่มอย่างแท้จริง เนื่องจากถูกกำหนดโดยค่าเมล็ดพันธุ์ที่เรียกว่า PRNG seed ซึ่งอาจรวมถึงค่าสุ่มอย่างแท้จริง แม้ว่าลำดับที่ใกล้เคียงกับการสุ่มจะถูกสร้างขึ้นได้โดยใช้ตัวสร้างตัวเลขสุ่มของฮาร์ดแวร์ แต่ตัวสร้างตัวเลขสุ่มเทียมก็มีความสำคัญในทางปฏิบัติสำหรับความเร็วของการสร้างตัวเลขและความสามารถในการทำซ้ำ
แอปพลิเคชัน
PRNGs เป็นศูนย์กลางของแอปพลิเคชัน เช่น การจำลอง (เช่น สำหรับ Monte Carlo) เกมอิเล็กทรอนิกส์ (เช่น สำหรับการสร้างตามขั้นตอน) และการเข้ารหัส แอปพลิเคชั่นเข้ารหัสต้องการเอาต์พุตข้อมูลไม่สามารถคาดเดาได้จากข้อมูลก่อนหน้านี้ ต้องใช้อัลกอริธึมที่ซับซ้อนมากขึ้นซึ่งไม่สืบทอดความเป็นเชิงเส้นของ PRNG อย่างง่าย
ข้อกำหนดและเงื่อนไข
คุณสมบัติทางสถิติที่ดีคือข้อกำหนดหลักสำหรับการได้รับ PRNG โดยทั่วไปแล้ว จำเป็นต้องมีการวิเคราะห์ทางคณิตศาสตร์อย่างรอบคอบเพื่อให้แน่ใจว่า RNG สร้างตัวเลขที่ใกล้เคียงพอที่จะสุ่มให้เหมาะสมกับการใช้งานที่ต้องการ
จอห์น ฟอน นอยมันน์ เตือนว่าอย่าตีความ PRNG ผิดๆ ว่าเป็นเครื่องกำเนิดสัญญาณแบบสุ่มอย่างแท้จริง และพูดติดตลกว่า "ใครก็ตามที่พิจารณาวิธีเลขคณิตเพื่อสร้างตัวเลขสุ่มย่อมอยู่ในสถานะบาปอย่างแน่นอน"
ใช้
PRNG สามารถเปิดใช้ได้จากสถานะเริ่มต้นตามอำเภอใจ มันจะสร้างลำดับเดียวกันเสมอเมื่อเริ่มต้นด้วยสถานะนี้ ระยะเวลา PRNG ถูกกำหนดดังนี้: สูงสุดเหนือสถานะเริ่มต้นทั้งหมดของความยาวของคำนำหน้าลำดับที่ไม่ซ้ำ ระยะเวลาถูกจำกัดด้วยจำนวนสถานะ ปกติวัดเป็นบิต เนื่องจากระยะเวลาอาจเพิ่มขึ้นเป็นสองเท่าเมื่อเพิ่มบิต "สถานะ" แต่ละบิต จึงง่ายที่จะสร้าง PRNG ที่มีระยะเวลามากพอสำหรับการใช้งานจริงจำนวนมาก
หากสถานะภายในของ PRNG มี n บิต ระยะเวลาของมันจะต้องไม่เกิน 2n ผลลัพธ์ จะสั้นกว่ามาก สำหรับ PRNG บางรายการ สามารถคำนวณระยะเวลาได้โดยไม่ต้องข้ามระยะเวลาทั้งหมด ลิเนียร์ Feedback Shift Registers (LFSRs) มักจะถูกเลือกให้มีคาบเท่ากับ 2n − 1.
เครื่องกำเนิดเชิงเส้นตรงมีช่วงเวลาที่คำนวณได้โดยใช้แฟคตอริ่ง แม้ว่า PPP จะทำซ้ำผลลัพธ์ของตนหลังจากสิ้นสุดช่วงเวลา แต่ผลลัพธ์ที่เกิดซ้ำไม่ได้หมายความว่าถึงจุดสิ้นสุดของช่วงเวลาแล้ว เนื่องจากสถานะภายในของ PPP อาจมากกว่าผลลัพธ์ สิ่งนี้ชัดเจนโดยเฉพาะสำหรับ PRNG ที่มีเอาต์พุตบิตเดียว
ข้อผิดพลาดที่เป็นไปได้
ข้อผิดพลาดที่พบโดย PRNG ที่มีข้อบกพร่องมีตั้งแต่เล็กน้อย (และไม่ทราบ) ไปจนถึงข้อผิดพลาดที่ชัดเจน ตัวอย่างคืออัลกอริทึมตัวเลขสุ่ม RANDU ซึ่งใช้ในเมนเฟรมมานานหลายทศวรรษ มันเป็นข้อบกพร่องที่ร้ายแรง แต่ก็ไม่มีใครสังเกตเห็นความไม่เพียงพอเป็นเวลานาน
ในหลาย ๆ ด้าน การศึกษาวิจัยที่ใช้การคัดเลือกแบบสุ่ม การจำลองมอนติคาร์โล หรือวิธีการอื่นๆ บนพื้นฐานของ RNG มีความน่าเชื่อถือน้อยกว่าผลจาก GNPG ที่มีคุณภาพต่ำมาก แม้กระทั่งทุกวันนี้ บางครั้งก็จำเป็นต้องมีความระมัดระวัง ดังที่เห็นได้จากคำเตือนในสารานุกรมวิทยาศาสตร์สถิตินานาชาติ (2010)
กรณีศึกษาที่ประสบความสำเร็จ
ในภาพประกอบ ลองพิจารณาภาษาการเขียนโปรแกรม Java ที่ใช้กันอย่างแพร่หลาย ณ ปี 2017 Java ยังคงใช้ตัวสร้างเชิงเส้นสอดคล้อง (LCG) สำหรับ PRNG
ประวัติศาสตร์
PRNG แรกเพื่อหลีกเลี่ยงปัญหาร้ายแรงและยังคงวิ่งค่อนข้างเร็วคือ Mersenne Twister (ที่กล่าวถึงด้านล่าง) ซึ่งตีพิมพ์ในปี 1998 ตั้งแต่นั้นมา PRNG คุณภาพสูงอื่นๆ ก็ได้รับการพัฒนา
แต่ประวัติของตัวเลขสุ่มหลอกไม่ได้จบเพียงแค่นั้น ในช่วงครึ่งหลังของศตวรรษที่ 20 คลาสอัลกอริธึมมาตรฐานที่ใช้สำหรับ PRNG รวมถึงเครื่องกำเนิดเชิงเส้นที่สอดคล้องกัน ทราบว่าคุณภาพของ LCG ไม่เพียงพอ แต่ไม่มีวิธีการที่ดีกว่านี้ Press et al (2007) อธิบายผลลัพธ์ดังนี้: "หากเอกสารทางวิทยาศาสตร์ทั้งหมดที่สงสัยผลลัพธ์เนื่องจาก [LCGs และที่เกี่ยวข้อง] หายไปจากชั้นวางห้องสมุด จะมีช่องว่างขนาดเท่ากำปั้นของคุณบนชั้นวางทุกชั้น"
ความสำเร็จหลักในการสร้างเครื่องกำเนิดแบบสุ่มเทียมคือการแนะนำวิธีการตามการเกิดซ้ำเชิงเส้นในฟิลด์สององค์ประกอบ ออสซิลเลเตอร์ดังกล่าวเชื่อมต่อกับรีจิสเตอร์การเปลี่ยนแปลงการป้อนกลับเชิงเส้น พวกเขาทำหน้าที่เป็นพื้นฐานสำหรับการประดิษฐ์เซ็นเซอร์ตัวเลขสุ่มหลอก
โดยเฉพาะอย่างยิ่งการประดิษฐ์ 1997 โดย Mersen Twister หลีกเลี่ยงปัญหามากมายกับเครื่องกำเนิดไฟฟ้ารุ่นก่อน ๆ Mersenne Twister มีระยะเวลา 219937-1 รอบ (≈4.3 × 106001) ได้รับการพิสูจน์แล้วว่ามีการกระจายอย่างสม่ำเสมอใน (สูงสุด) 623 มิติ (สำหรับค่า 32 บิต) และในช่วงเวลาของการแนะนำนั้นเร็วกว่าเครื่องกำเนิดเสียงทางสถิติอื่นๆ ที่สร้างลำดับตัวเลขสุ่มหลอก
ในปี 2546 George Marsaglia ได้แนะนำเครื่องกำเนิด xorshift โดยอิงจากการทำซ้ำเชิงเส้น เครื่องกำเนิดไฟฟ้าเหล่านี้เป็นอย่างมากรวดเร็วและ - รวมกับการดำเนินการที่ไม่เป็นเชิงเส้น - พวกเขาผ่านการทดสอบทางสถิติที่เข้มงวด
ในปี 2549 ตระกูลเครื่องกำเนิดไฟฟ้า WELL ได้รับการพัฒนา เครื่องกำเนิด WELL ในแง่หนึ่งปรับปรุงคุณภาพของ Twister Mersenne ซึ่งมีพื้นที่ของรัฐที่ใหญ่เกินไปและการฟื้นตัวช้ามากจากพวกเขา สร้างตัวเลขสุ่มหลอกด้วยศูนย์จำนวนมาก
การเข้ารหัส
PRNG เหมาะสำหรับแอปพลิเคชันการเข้ารหัสเรียกว่า PRNG ที่ปลอดภัยในการเข้ารหัส (CSPRNG) ข้อกำหนดสำหรับ CSPRNG คือผู้โจมตีที่ไม่ทราบว่าเมล็ดพันธุ์มีข้อได้เปรียบเพียงเล็กน้อยในการแยกแยะลำดับเอาต์พุตของเครื่องกำเนิดไฟฟ้าจากลำดับแบบสุ่ม กล่าวอีกนัยหนึ่ง แม้ว่า PRNG จะต้องผ่านการทดสอบทางสถิติบางอย่างเท่านั้น CSPRNG ต้องผ่านการทดสอบทางสถิติทั้งหมดที่จำกัดเวลาพหุนามในขนาดเมล็ดพันธุ์
แม้ว่าการพิสูจน์คุณสมบัตินี้จะอยู่นอกเหนือระดับทฤษฎีความซับซ้อนในการคำนวณในปัจจุบัน แต่สามารถให้หลักฐานที่ชัดเจนได้โดยการลด CSPRNG ให้เป็นปัญหาที่ถือว่ายาก เช่น การแยกตัวประกอบจำนวนเต็ม โดยทั่วไป อาจต้องใช้เวลาหลายปีในการตรวจสอบก่อนที่อัลกอริทึมจะได้รับการรับรองเป็น CSPRNG
มันแสดงให้เห็นแล้วว่ามีแนวโน้มว่า NSA จะใส่ประตูหลังที่ไม่สมมาตรเข้าไปในเครื่องกำเนิดตัวเลขสุ่มหลอกที่ได้รับการรับรอง Dual_EC_DRBG
อัลกอริทึมสุ่มหลอกตัวเลข
อัลกอริธึม PRNG ส่วนใหญ่สร้างลำดับที่กระจายเท่าๆ กันโดยการทดสอบหลายๆ ครั้ง นี่เป็นคำถามเปิด มันเป็นหนึ่งในศูนย์กลางในทฤษฎีและการปฏิบัติของการเข้ารหัส: มีวิธีแยกแยะผลลัพธ์ของ PRNG คุณภาพสูงจากลำดับแบบสุ่มอย่างแท้จริงหรือไม่? ในการตั้งค่านี้ ตัวแก้ไขรู้ว่ามีการใช้อัลกอริธึม PRNG ที่รู้จัก (แต่ไม่ใช่สถานะที่เริ่มต้น) หรือใช้อัลกอริธึมแบบสุ่มอย่างแท้จริง เขาต้องแยกแยะระหว่างพวกเขา
ความปลอดภัยของอัลกอริธึมการเข้ารหัสและโปรโตคอลส่วนใหญ่ที่ใช้ PRNG นั้นตั้งอยู่บนสมมติฐานที่ว่าเป็นไปไม่ได้ที่จะแยกแยะระหว่างการใช้ PRNG ที่เหมาะสมกับการใช้ลำดับแบบสุ่มอย่างแท้จริง ตัวอย่างที่ง่ายที่สุดของการพึ่งพานี้คือการเข้ารหัสสตรีม ซึ่งส่วนใหญ่มักจะทำงานโดยละเว้นหรือส่งข้อความธรรมดาที่มีเอาต์พุต PRNG ทำให้เกิดข้อความเข้ารหัส การออกแบบ PRNG ที่เหมาะสมในการเข้ารหัสนั้นยากมาก เนื่องจากต้องเป็นไปตามเกณฑ์เพิ่มเติม ขนาดของช่วงเวลาเป็นปัจจัยสำคัญในความเหมาะสมในการเข้ารหัสของ PRNG แต่ไม่ใช่เพียงอย่างเดียว
PRNG คอมพิวเตอร์ยุคแรกๆ ที่เสนอโดย John von Neumann ในปี 1946 เรียกว่าวิธี Mean Squares อัลกอริทึมมีดังนี้: นำตัวเลขใดๆ ยกกำลังสอง ลบหลักตรงกลางของจำนวนผลลัพธ์เป็น "ตัวเลขสุ่ม" จากนั้นใช้ตัวเลขนี้เป็นตัวเลขเริ่มต้นสำหรับการวนซ้ำครั้งต่อไป ตัวอย่างเช่น การยกกำลังสองตัวเลข 1111 ให้1234321 ซึ่งเขียนได้เป็น 01234321 ตัวเลข 8 หลักคือกำลังสองของตัวเลข 4 หลัก ซึ่งจะทำให้ 2343 เป็นตัวเลข "สุ่ม" ผลลัพธ์ของการทำซ้ำขั้นตอนนี้คือ 4896 เป็นต้น วอน นอยมันน์ ใช้ตัวเลข 10 หลัก แต่กระบวนการก็เหมือนเดิม
ข้อเสียของ "จตุรัสกลาง"
ปัญหาของวิธี "กำลังสองเฉลี่ย" คือ ลำดับทั้งหมดทำซ้ำได้รวดเร็วมาก เช่น 0000 ฟอน นอยมันน์รู้เรื่องนี้ แต่เขาพบแนวทางที่เพียงพอสำหรับจุดประสงค์ของเขา และกังวลว่า "การแก้ไข" ทางคณิตศาสตร์จะซ่อนข้อผิดพลาดแทนที่จะลบออก
ฟอน นอยมันน์ พบว่าฮาร์ดแวร์สุ่มและตัวสร้างตัวเลขสุ่มหลอกไม่เหมาะสม: หากไม่ได้บันทึกเอาต์พุตที่สร้างขึ้น จะไม่สามารถตรวจสอบข้อผิดพลาดในภายหลังได้ หากพวกเขาต้องจดผลลัพธ์ของพวกเขา พวกเขาจะทำให้หน่วยความจำที่มีอยู่จำกัดของคอมพิวเตอร์หมดลง และทำให้คอมพิวเตอร์สามารถอ่านและเขียนตัวเลขได้ ถ้าเขียนตัวเลขบนการ์ด พวกเขาจะใช้เวลาในการเขียนและอ่านนานกว่ามาก บนคอมพิวเตอร์ ENIAC เขาใช้วิธี "สี่เหลี่ยมตรงกลาง" และดำเนินการรับตัวเลขสุ่มหลอกได้เร็วกว่าการอ่านตัวเลขจากบัตรเจาะหลายร้อยเท่า
จัตุรัสกลางถูกแทนที่ด้วยเครื่องกำเนิดไฟฟ้าที่ซับซ้อนมากขึ้น
วิธีนวัตกรรม
นวัตกรรมล่าสุดคือการรวมกำลังสองเฉลี่ยเข้ากับลำดับ Weil วิธีนี้ช่วยให้มั่นใจได้ถึงผลิตภัณฑ์คุณภาพสูงภายในระยะเวลานาน ช่วยให้ได้สูตรตัวเลขสุ่มหลอกที่ดีที่สุด
