ผลต่างระหว่างรุ่นของ "ตัวสร้างเลขสุ่มเทียม"

ตัวสร้างเลขสุ่มเทียม หรือที่รู้จักกันในนาม ตัวสร้างบิตสุ่มแบบกำหนดได้ (Deterministic random bit generator: DRBG) เป็นขั้นตอนวิธีสำหรับใช้ในการสร้างลำดับของตัวเลขที่มีความใกล้เคียงกับคุณสมบัติของการสุ่ม ถึงแม้ว่าลำดับตัวเลขที่ได้จากขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมนี้จะใกล้เคียงกับลำดับเลขสุ่มแท้จริงมากแค่ไหนแต่มันก็ไม่ได้เป็นลำดับตัวเลขแบบสุ่มที่แท้จริงเนื่องจากลำดับตัวเลขที่ได้ออกมาจากตัวสร้างเลขสุ่มเทียมทั้งหมดได้มาจากกลุ่มเล็กๆเล็ก ๆ ของค่าเริ่มต้นที่เรากำหนดให้เป็นตัวตั้งต้น (seed) ของตัวสร้างเลขสุ่มเทียม ถึงแม้ว่าเรามี[[ตัวสร้างเลขสุ่มจากฮาร์ดแวร์]]ที่สามารถนำมาสร้างลำดับสุ่มแท้ได้ แต่ลำดับสุ่มเสมือนที่ได้จากตัวสร้างเลขสุ่มเทียมเองก็มีความสำคัญในทางปฏิบัติหลายๆหลาย ๆ อย่าง ทั้งในด้านการจำลอง เช่น ระบบกายภาพที่ใช้[[วิธีมอนติคาร์โล]] ในด้าน[[การเข้ารหัส]] (cryptography) ในด้าน[[การก่อกำเนิดกระบวนคำสั่ง]] (procedural generation) ส่วนใหญ่เกี่ยวข้องกับ[[คอมพิวเตอร์กราฟิกส์]] (โปรแกรมประยุกต์และวิดีโอเกมขั้นออกแบบ) [[ขั้นตอนวิธีแบบสุ่ม|ขั้นตอนวิธีเชิงสุ่ม]]มากมายเองก็ได้อิทธิพลมาจากตัวสร้างเลขสุ่มเทียมเป็นส่วนหนึ่งในการแก้ปัญหา นอกจากการใช้งานแล้วการพิสูจน์ว่าตัวสร้างเลขสุ่มเทียมใช้งานได้จริงก็มีความสำคัญไม่แพ้กัน ซึ่งการพิสูจน์นี้ต้องอาศัยการวิเคราะห์ทางคณิตศาสตร์อย่างระมัดระวังในการทำให้แน่ใจได้ว่าตัวสร้างเลขสุ่มเทียมได้สร้างลำดับสุ่มเสมือนที่มีลักษณะสุ่มเพียงพอสำหรับการใช้งาน

ตัวสร้างเลขสุ่มเทียมที่อาศัยคอมพิวเตอร์ ยุคแรกๆแรก ๆ คิดค้นโดย [[จอห์น ฟอน นอยมันน์]] ในปี ค.ศ. 1946 รู้จักกันในนามของ [[วิธีมิดเดิลสแควร์]] (middle-square method) ขั้นตอนวิธีนี้ง่ายมาก รับตัวเลขอะไรเข้ามาเป็น ตัวตั้งต้น ก็นำตัวเลขนั้นมายกกำลัง 2 แล้วนำหลักตรงกลางออกจากผลลัพธ์ที่ได้ ก็จะได้ตัวเลขสุ่มขึ้นมาตามต้องการ ซึ่งสามารถนำตัวเลขนี้มาเป็น ตัวตั้งต้น ในการสร้างตัวเลขสุ่มอื่นๆอื่น ๆ ต่อไปได้เรื่อยๆเรื่อย ๆ

ตัวสร้างเลขสุ่มเทียม เริ่มต้นจากสถานะเริ่มต้นอะไรก็ได้โดยใช้สถานะ seed (สถานะเริ่มต้น) เป็นตัวเริ่มต้นของตัวสร้างเลขสุ่มเทียม ซึ่งทำให้เกิดการวนซ้ำของลำดับได้โดยความยาวสูงสุดของลำดับสุ่มเสมือนก่อนเกิดการซ้ำเกิดขึ้นถูกวัดจากขนาดของสถานะซึ่งวัดได้โดยความยาวของบิต ความยาวคาบของการวนซ้ำสูงสุดจะยาวเพิ่มเป็น 2 เท่าทุก 1บิตที่เพิ่มขึ้นจึงทำให้ง่ายที่จะสร้าง ตัวสร้างเลขสุ่มเทียม ที่มีคาบการวนซ้ำที่ยาวเพียงพอสำหรับหลายๆหลาย ๆ โปรแกรมในทางปฏิบัติ ถ้าสถานะของ ตัวสร้างเลขสุ่มเทียม มี n บิต คาบการวนซ้ำจะไม่ยาวเกินกว่า 2ⁿ เช่น เรจิสเตอร์เลื่อนป้อนกลับได้เชิงเส้น[[:en:Linear Feedback Shift Registers|Linear Feedback Shift Registers]] (LFSRs) โดยปกติจะถูกทำให้มีคาบการวนซ้ำที่มีความยาวแน่นอนคือ2ⁿ−1. ตัวสร้างสมภาคเชิงเส้น[[:en:Linear congruential generators|Linear congruential generators]] มีคาบการวนซ้ำซึ่งสามารถคำนวณได้จากการหาตัวประกอบ มิกซ์ Mixes (ไม่มีข้อบังคับ) มีคาบการวนซ้ำโดยเฉลี่ย 2^n/2 มิกซ์ Mixes (ซึ่งสามารถย้อนกลับได้) มีคาบการวนซ้ำโดยเฉลี่ย 2ⁿ ถึงแม้ว่า ตัวสร้างเลขสุ่มเทีย จะมีการซ้ำของผลลัพธ์หลังจากถึงคาบการวนซ้ำแต่การเจอตัวซ้ำไม่ได้หมายความว่ามันครบคาบการวนซ้ำเสมอไปเพราะคาบการวนซ้ำที่แท้จริงอาจจะยาวกว่านี้

จุดบกพร่องเหล่านี้มีตั้งแต่ไม่สามารถสังเกตเห็นได้จนกระทั่งสามารถเห็นได้อย่างชัดเจน ตัวอย่างหนึ่งก็คือ แรนดู [[:en:RANDU|RANDU]] ซึ่งเป็นขั้นตอนวิธีในการสร้างเลขสุ่มเทียมที่ใช้กันมากว่าทศวรรตบน คอมพิวเตอร์ [[:en:Mainframe_computer|mainframe]] ซึ่งไม่สมบูรณ์แบบอย่างมากๆมาก ๆ แต่เนื่องด้วยสมัยนั้นวิทยาการในการตรวจสอบที่มียังมีไม่เพียงพอ ทำให้ความไม่สมบุร์ณ์แบบดังกล่าวไม่ถูกตรวจพบเป็นระยะเวลายาวนาน อีกตัวอย่างหนึ่งของปัญหาก็คือ การวิจัยในหลายๆหลาย ๆ สาขาในช่วงเวลาดังกล่าวซึ่งอาศัย การเลือกแบบสุ่ม การจำลองแบบ วิธีมอนติคาโล [[:en:Monte_Carlo_method|Monte Carlo method]] หรือในทางอื่นๆอื่น ๆ ได้ผลการวิจัยที่มีความน่าเชื่อถือน้อยกว่าที่มันควรจะเป็น

ความมั่นคงและระเบียบวิธีการในการเข้ารหัสของขั้นตอนวิธีตัวสร้างเลขสุ่มเทียม มี่ใช้กันส่วนมากตั้งอยู่บนสมมุติฐานที่ว่าเป็นไปไม่ได้ที่จะแยกลำดับสุ่มเสมือนจากการใช้งานของตัวสร้างเลขสุ่มเทียมที่เหมาะสมออกจากลำดับสุ่มแท้จริงได้ ตัวอย่างหนึ่งที่เห็นได้ชัดคือ กระแสข้อมูลรหัส ([[:en:Stream_ciphers|stream ciphers]]) ซึงส่วนมากทำงานโดยใช้ตัวดำเนินการทางตรรกศาสตร์ [[:en:Exclusive or|exclusive or]] (XOR) ระหว่างข้อความปกติกับผลลัพธ์จากตัวสร้างเลขสุ่มเทียม ผลิต ข้อความรหัส ([[:en:Ciphertext|ciphertext]]) ออกมา การออกแบบ ตัวสร้างเลขสุ่มเทียม ที่สามารถเข้ารหัสได้อย่างเพียงพอต่อความต้องการในปัจจุบันนี้เป็นสิ่งที่ยากอย่างสุดสุดเพราะว่า ตัวสร้างเลขสุ่มเทียม ที่ออกแบบนี้นอกจากจะต้องสอดคล้องกฎเกณฑ์ข้อกำหนดพื้นฐานสำหรับตัวสร้างเลขสุ่มเทียมทั่วไปที่ไม่ได้ใช้เข้ารหัสแล้วยังต้องสอดคล้องกับกฎเกณฑ์ข้อกำหนดต่างๆต่าง ๆ เพิ่มเติมเพื่อเป็นเครื่องยืนยันว่าสามารถใช้เข้ารหัสได้อย่างเพียงพอ

ตัวสร้างเลขสุ่มเทียม ที่เหมาะสำหรับใช้งานในการเข้ารหัส ถูกเรียกว่า ตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส [[:en:Cryptographically_secure_pseudorandom_number_generator|cryptographically secure PRNG (CSPRNG)]] ขณะที่ ตัวสร้างเลขสุ่มเทียม ทั่วๆทั่ว ๆ ไป แค่ผ่านการทดสอบทางสถิติจำนวนหนึ่งก็พอ ส่วน ตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส ต้องผ่านการทดสอบทางสถิติทั้งหมดและต้องอยู่ภายในเวลาแบบ ฟังก์ชันพหุนาม กับขนาดของ ค่าเริ่มต้น (seed) ถึงแม้ว่าคุณสมบัติดังกล่าวจะไม่สามารถพิสูจน์ได้ในทางปฏิบัติก็ตาม เราก็ยังสามารถแสดงหลักฐานข้อพิสูจน์ที่แข็งแรงเพียงพอให้เห็นได้ว่าตัวสร้างเลขสุ่มเทียมที่สร้างขึ้นมีความมั่นคงเชิงรหัสหรือไม่ โดยลดรูปคุณสมบัติดังกล่าวไปสู่ปัญหาที่ยากๆยาก ๆ ทางคณิตศาสตร์ที่เป็นที่รู้ๆรู้ ๆ กันซึ่งเป็นหนึ่งในกลุ่มปัญหา [[:en:NP_(complexity)|NP]] เช่น การแยกตัวประกอบจำนวนเต็มที่มีหลายๆหลาย ๆ หลัก โดยปกติแล้วต้องใช้เวลาหลายปีในการตรวจสอบกว่าจะสามารถยืนยันได้ว่าขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมใดๆใด ๆ นั้นจะเป็น ตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัสหรือไม่

* การผสมผสานระหว่าง ขั้นตอนวิธีตัวสร้างเลขสุ่มเทียม ดั้งเดิมหลายๆหลาย ๆ ตัวโดยมีเป้าหมายในการกำจัดลำดับที่ดูเหมือนว่าไม่ได้ถูกสุ่มออกไป

* การออกแบบ ขั้นตอนวิธี ชนิดพิเศษที่ตั้งอยู่บนสมมุติฐานอย่างยากทางคณิตศาสตร์ เช่น Micali-Schnorr, ขั้นตอนวิธี[[Blum Blum Shub]] ซึ่งได้พิสูจน์ความมั่นคงของรหัสได้เป็นอย่างดีไว้แล้ว ขั้นตอนวิธี เหล่านี้จะใช้เวลาช้ากว่า ตัวสร้างเลขสุ่มเทียม แบบอื่นและใช้งานไม่ได้ในทางปฏิบัติด้านอื่นๆอื่น ๆ นอกจากใช้ในการเข้ารหัสเท่านั้น

* K2 ลำดับสุ่มเสมือนซึ่งไม่สามารถแยกจากลำดับสุ่มแท้จริงด้วยการทดสอบทางสถิติที่แน่ชัด การทดสอบโมโนบิต monobit test (จำนวนที่เท่ากันของเลขศูนย์และเลขหนึ่งในลำดับ), การทดสอบโปกโกอร์ poker test (ตัวอย่างพิเศษของ [[:en:Chi-square_test|chi-square test]]), การทดสอบการวิ่ง[[:en:Runs_test|runs test]] (นับจำนวนความถี่ของการวิ่งของความยาวที่ต่างๆต่าง ๆ กัน), การทดสอบการวิ่งระยะยาว longruns test (ตรวจสอบการวิ่ว่ามี ความยาวมากกว่า 34 or หรือใหญ่กว่า 20 000 bits ในลำดับหรือไม่ — both from BSI2 (AIS 20, v. 1, 1999) and FIPS (140-1, 1994), และ การทดสอบความผิดพลาดอันเนื่องมากจากความสัมพันธ์[[:en:Autocorrelation|autocorrelation]] test ใจความสำคัญของการทดสอบเหล่านี้คือลำดับย่อยใดๆใด ๆ ที่เลือกมาจะต้องไม่มีข้อมูลใดของตัวถัดไปของลำดับปรากฏอยู่

* K3 สำหรับในทางปฏิบัติเป็นไปไม่ได้ที่ผู้โจมตีใดๆใด ๆ จะคำนวณหรือเดาตัวเลขสุ่มได้จากลำดับย่อยใดๆใด ๆ ที่ได้มา ตัวก่อนหน้าหรือตัวถัดไปของลำดับ หรือจากสถานะใดๆใด ๆ ของ ตัวสร้างเลขสุ่มเทียม

* K4 สำหรับในทางปฏิบัติเป็นไปไม่ได้ที่ผู้โจมตีใดๆใด ๆ จะคำนวณหรือเดาตัวเลขสุ่มได้จาก สถานะภายในของตัวสร้างเลขสุ่มเทียม ตัวก่อนหน้าหรือตัวถัดไปของลำดับ หรือ สถานะก่อนหน้าใดๆใด ๆ ของ ตัวสร้างเลขสุ่มเทียม

=== โปรแกรมประยุกต์และการประยุกต์ใช้งานในด้านอื่นๆอื่น ๆ ===

* โปรแกรมสุ่มเลขบัตรประจำตัวประชาชน-สุ่มเลขบัตรประชาชนสำหรับใช้ในการสมัครสมาชิกเว็บต่างๆต่าง ๆ เพื่อความปลอดภัยของผู้สมัครสมาชิก