Một số giả ngẫu nhiên là một số đặc biệt được tạo bởi một trình tạo đặc biệt. Trình tạo bit ngẫu nhiên xác định (PRNG), còn được gọi là Trình tạo bit ngẫu nhiên xác định (DRBG), là một thuật toán để tạo ra một chuỗi số có các đặc tính gần đúng với các đặc điểm của chuỗi số ngẫu nhiên. Chuỗi PRNG được tạo không thực sự ngẫu nhiên, vì nó hoàn toàn được xác định bởi một giá trị gốc được gọi là hạt giống PRNG, có thể bao gồm các giá trị thực sự ngẫu nhiên. Mặc dù các trình tự gần với ngẫu nhiên hơn có thể được tạo bằng cách sử dụng trình tạo số ngẫu nhiên phần cứng, nhưng trình tạo số giả ngẫu nhiên rất quan trọng trong thực tế đối với tốc độ tạo số và khả năng tái tạo của chúng.
Đơn
PRNG là trọng tâm của các ứng dụng như mô phỏng (ví dụ: cho Monte Carlo), trò chơi điện tử (ví dụ: tạo thủ tục) và mật mã. Các ứng dụng mật mã yêu cầu đầu radữ liệu không thể dự đoán được từ thông tin trước đó. Các thuật toán phức tạp hơn được yêu cầu không kế thừa tính tuyến tính của các PRNG đơn giản.
Điều khoản và Điều kiện
Các đặc tính thống kê tốt là yêu cầu chính để có được PRNG. Nói chung, cần phân tích toán học cẩn thận để đảm bảo rằng RNG tạo ra các con số đủ gần với ngẫu nhiên để phù hợp với mục đích sử dụng.
John von Neumann cảnh báo không nên hiểu sai PRNG như một trình tạo ngẫu nhiên thực sự và nói đùa rằng "Bất kỳ ai coi phương pháp số học để tạo ra các số ngẫu nhiên chắc chắn đang ở trong tình trạng tội lỗi."
Sử dụng
PRNG có thể được khởi chạy từ trạng thái ban đầu tùy ý. Nó sẽ luôn tạo ra cùng một chuỗi khi được khởi tạo với trạng thái này. Khoảng thời gian PRNG được định nghĩa như sau: tối đa trên tất cả các trạng thái ban đầu của độ dài của tiền tố trình tự không lặp lại. Khoảng thời gian được giới hạn bởi số lượng trạng thái, thường được đo bằng bit. Vì độ dài chu kỳ có khả năng tăng gấp đôi khi mỗi bit "trạng thái" được thêm vào, nên dễ dàng tạo PRNG với các khoảng thời gian đủ lớn cho nhiều ứng dụng thực tế.
Nếu trạng thái bên trong của PRNG chứa n bit, chu kỳ của nó có thể không quá 2n kết quả, nó ngắn hơn nhiều. Đối với một số PRNG, thời lượng có thể được tính toán mà không bỏ qua toàn bộ khoảng thời gian. Thanh ghi dịch chuyển phản hồi tuyến tính (LFSR) thườngđược chọn để có khoảng thời gian bằng 2n - 1.
Bộ tạo đồng dư tuyến tính có các chu kỳ có thể được tính toán bằng cách sử dụng bao thanh toán. Mặc dù PPP sẽ lặp lại kết quả của nó sau khi chúng đạt đến cuối kỳ, nhưng một kết quả lặp lại không có nghĩa là đã đạt đến cuối kỳ, vì trạng thái bên trong của nó có thể lớn hơn sản lượng; điều này đặc biệt rõ ràng đối với các PRNG có đầu ra bit đơn.
Các lỗi có thể xảy ra
Các lỗi được tìm thấy bởi các PRNG bị lỗi bao gồm từ lỗi tinh vi (và không xác định) đến lỗi rõ ràng. Một ví dụ là thuật toán số ngẫu nhiên RANDU, đã được sử dụng trên máy tính lớn trong nhiều thập kỷ. Đó là một thiếu sót nghiêm trọng, nhưng sự thiếu sót của nó đã không được chú ý trong một thời gian dài.
Trong nhiều lĩnh vực, các nghiên cứu sử dụng lựa chọn ngẫu nhiên, mô phỏng Monte Carlo, hoặc các phương pháp khác dựa trên RNG kém tin cậy hơn nhiều vì có thể là kết quả của GNPG chất lượng kém. Thậm chí ngày nay, đôi khi cần phải thận trọng, bằng chứng là cảnh báo trong Bách khoa toàn thư về Khoa học Thống kê Quốc tế (2010).
Nghiên cứu điển hình thành công
Để minh họa, hãy xem xét ngôn ngữ lập trình Java được sử dụng rộng rãi. Tính đến năm 2017, Java vẫn dựa vào Trình tạo thông số tuyến tính (LCG) cho PRNG của nó.
Lịch sử
PRNG đầu tiên để tránh các vấn đề nghiêm trọng và vẫn chạy khá nhanh,là Mersenne Twister (thảo luận bên dưới), được xuất bản vào năm 1998. Kể từ đó, các PRNG chất lượng cao khác đã được phát triển.
Nhưng lịch sử của các số giả ngẫu nhiên không kết thúc ở đó. Trong nửa sau của thế kỷ 20, loại thuật toán tiêu chuẩn được sử dụng cho PRNG bao gồm các bộ tạo đồng dư tuyến tính. Chất lượng của LCG được biết là không phù hợp, nhưng các phương pháp tốt hơn không có sẵn. Press và cộng sự (2007) đã mô tả kết quả như sau: "Nếu tất cả các bài báo khoa học có kết quả bị nghi ngờ vì [LCG và liên quan] biến mất khỏi các kệ thư viện, sẽ có một khoảng trống to bằng nắm tay của bạn trên mỗi kệ."
Thành tựu chính trong việc tạo ra trình tạo giả ngẫu nhiên là giới thiệu các phương pháp dựa trên hồi quy tuyến tính trong trường hai phần tử; các bộ dao động như vậy được kết hợp với các thanh ghi dịch chuyển phản hồi tuyến tính. Chúng là cơ sở cho việc phát minh ra cảm biến số giả ngẫu nhiên.
Đặc biệt, phát minh năm 1997 của Mersen Twister đã tránh được nhiều vấn đề với các máy phát điện trước đó. Mersenne Twister có chu kỳ 219937−1 lần lặp (≈4,3 × 106001). Nó đã được chứng minh là được phân phối đồng đều trong (tối đa) 623 chiều (đối với các giá trị 32 bit) và tại thời điểm giới thiệu nó nhanh hơn các trình tạo âm thanh thống kê khác tạo ra chuỗi số giả ngẫu nhiên.
Năm 2003, George Marsaglia đã giới thiệu một dòng máy phát xorshift cũng dựa trên sự lặp lại tuyến tính. Những máy phát điện này cực kỳnhanh chóng và - kết hợp với hoạt động phi tuyến tính - chúng vượt qua các bài kiểm tra thống kê nghiêm ngặt.
Năm 2006, dòng máy phát điện WELL được phát triển. Trình tạo WELL theo một nghĩa nào đó cải thiện chất lượng của Twister Mersenne, có không gian trạng thái quá lớn và khả năng khôi phục rất chậm từ chúng, tạo ra các số giả ngẫu nhiên với rất nhiều số không.
Mật mã
PRNG thích hợp cho các ứng dụng mật mã được gọi là PRNG bảo mật bằng mật mã (CSPRNG). Yêu cầu đối với CSPRNG là kẻ tấn công không biết hạt giống chỉ có một lợi thế nhỏ trong việc phân biệt trình tự đầu ra của trình tạo với trình tự ngẫu nhiên. Nói cách khác, trong khi PRNG chỉ được yêu cầu để vượt qua một số bài kiểm tra thống kê nhất định, thì một CSPRNG phải vượt qua tất cả các bài kiểm tra thống kê được giới hạn trong thời gian đa thức ở kích thước hạt giống.
Mặc dù bằng chứng về tính chất này vượt quá mức hiện tại của lý thuyết độ phức tạp tính toán, nhưng bằng chứng mạnh mẽ có thể được cung cấp bằng cách giảm CSPRNG thành một vấn đề được coi là khó, như thừa số nguyên. Nói chung, có thể cần nhiều năm đánh giá trước khi một thuật toán có thể được chứng nhận là CSPRNG.
Người ta đã chỉ ra rằng có khả năng NSA đã chèn một cửa sau không đối xứng vào trình tạo số giả ngẫu nhiên Dual_EC_DRBG được chứng nhận bởi NIST.
Thuật toán giả ngẫu nhiênsố
Hầu hết các thuật toán PRNG tạo ra các chuỗi được phân phối đồng đều bởi bất kỳ thử nghiệm nào. Đây là một câu hỏi mở. Nó là một trong những trọng tâm trong lý thuyết và thực hành về mật mã: có cách nào để phân biệt đầu ra của một PRNG chất lượng cao với một chuỗi thực sự ngẫu nhiên không? Trong cài đặt này, trình phân giải biết rằng một thuật toán PRNG đã biết đã được sử dụng (nhưng không phải trạng thái mà nó được khởi tạo) hoặc một thuật toán thực sự ngẫu nhiên đã được sử dụng. Anh ấy phải phân biệt giữa chúng.
Tính bảo mật của hầu hết các thuật toán và giao thức mật mã sử dụng PRNG dựa trên giả định rằng không thể phân biệt giữa việc sử dụng một PRNG phù hợp và việc sử dụng một chuỗi thực sự ngẫu nhiên. Các ví dụ đơn giản nhất của sự phụ thuộc này là mật mã dòng, thường hoạt động bằng cách bỏ qua hoặc gửi thông điệp bản rõ với đầu ra PRNG, tạo ra bản mã. Việc thiết kế các PRNG thích hợp về mặt mật mã là vô cùng khó khăn vì chúng phải đáp ứng các tiêu chí bổ sung. Quy mô của chu kỳ là một yếu tố quan trọng trong tính phù hợp với mật mã của một PRNG, nhưng không phải là yếu tố duy nhất.
Một máy tính ban đầu PRNG do John von Neumann đề xuất vào năm 1946 được gọi là phương pháp bình phương trung bình. Thuật toán như sau: lấy một số bất kỳ, bình phương nó, loại bỏ các chữ số ở giữa của số kết quả làm "số ngẫu nhiên", sau đó sử dụng số này làm số bắt đầu cho lần lặp tiếp theo. Ví dụ: bình phương số 1111 cho1234321, có thể viết là 01234321, số có 8 chữ số là bình phương của số có 4 chữ số. Điều này cho 2343 là một số "ngẫu nhiên". Kết quả của việc lặp lại quy trình này là 4896, v.v. Von Neumann đã sử dụng các số có 10 chữ số, nhưng quy trình vẫn diễn ra như cũ.
Nhược điểm của "ô vuông giữa"
Vấn đề với phương pháp "bình phương trung bình" là tất cả các chuỗi cuối cùng lặp lại, một số rất nhanh, ví dụ: 0000. Von Neumann biết về điều này, nhưng ông đã tìm thấy một cách tiếp cận phù hợp với mục đích của mình và lo lắng rằng "sửa chữa" toán học sẽ chỉ ẩn các lỗi thay vì xóa chúng.
Von Neumann phát hiện phần cứng tạo số ngẫu nhiên và giả ngẫu nhiên không phù hợp: nếu chúng không ghi lại kết quả được tạo, chúng sẽ không thể được kiểm tra lỗi sau này. Nếu họ ghi lại kết quả của mình, họ sẽ làm cạn kiệt bộ nhớ khả dụng hạn chế của máy tính và do đó khả năng đọc và ghi số của máy tính. Nếu các con số được viết trên thẻ, chúng sẽ mất nhiều thời gian hơn để viết và đọc. Trên máy tính ENIAC mà anh ấy đã sử dụng, phương pháp "ô vuông giữa" và thực hiện quá trình lấy các số giả ngẫu nhiên nhanh hơn vài trăm lần so với việc đọc các số từ thẻ đục lỗ.
Hình vuông có nghĩa đã được thay thế bằng các máy phát điện phức tạp hơn.
Phương pháp cải tiến
Một cải tiến gần đây là kết hợp bình phương trung bình với dãy Weil. Phương pháp này đảm bảo sản phẩm chất lượng cao trongthời kỳ dài. Nó giúp có được các công thức số giả ngẫu nhiên tốt nhất.
