Làm cách nào để "kiểm tra" nếu một hàm thực sự mang lại kết quả ngẫu nhiên?

Question

Làm cách nào để đảm bảo rằng một hàm thực sự ngẫu nhiên hoặc gần với khái niệm nhất có thể? Ngoài ra, sự khác biệt giữa ngẫu nhiên và giả ngẫu nhiên là gì? Cuối cùng, thuật toán/nguồn nào có thể được sử dụng để tạo các số ngẫu nhiên?

P.S: Cũng hỏi điều này vì một câu lệnh MySQL sử dụng ORDER BY RAND() LIMIT 1 không mang lại kết quả thuyết phục.

Answer 1

Aloha!

Có một số phương pháp và công cụ để thử nghiệm tính ngẫu nhiên. Chúng được áp dụng trên một tập hợp các số được thu thập từ máy phát điện để được kiểm tra. Tức là, bạn kiểm tra trình tạo máy phát điện dựa trên một bộ dữ liệu được tạo.

Trong tính toán, đặc biệt là đối với bảo mật CNTT, chúng tôi thường muốn có một trình tạo phù hợp với quy trình ngẫu nhiên thống nhất. Có rất nhiều quy trình khác nhau, nhưng tôi đoán rằng đó là một quy trình thống nhất mà bạn đang hướng đến.

NIST đã xuất bản một số tài liệu với các đề xuất trên cả hai trình tạo số ngẫu nhiên giả cũng như cách kiểm tra chúng. Xem các tài liệu NIST SP 800-22 và SP 800-20.

Như người khác đã chỉ ra. Nếu bạn muốn một Trình tạo số ngẫu nhiên thực (TRNG), bạn cần thu thập entropy vật lý. Ví dụ về các nguồn như vậy là phân rã phóng xạ, bức xạ vũ trụ, đèn dung nham, vv Tốt hơn là bạn muốn các nguồn khó thao tác. IETF có RFC có một số khuyến nghị tốt, xem RFC 4086 - Nguồn ngẫu nhiên cho bảo mật: http://tools.ietf.org/html/rfc4086

Điều bạn thường làm là thu thập entropy từ một quặng hơn (tốt hơn một nguồn). Các dữ liệu thu thập được sau đó lọc (làm trắng) và cuối cùng được sử dụng để định kỳ gieo một PRNG tốt. Với hạt giống khác nhau, tự nhiên.

Đây là cách máy phát ngẫu nhiên tốt nhất hiện đại hoạt động. Một bộ thu entropy cho phép một PRNG được tạo ra bằng cách sử dụng các nguyên thủy mật mã như mật mã đối xứng (AES chẳng hạn) hoặc các hàm băm. Xem ví dụ các máy phát điện ngẫu nhiên Yarrow/Fortuna bởi Schneier, mà trong hình thức sửa đổi được sử dụng trong FreeBSD.

Quay lại câu hỏi của bạn về thử nghiệm. Như một người nào đó đã chỉ ra Marsaglia đã tạo ra một bộ kiểm tra tốt, được mã hóa trong các bài kiểm tra DIEHARD. Hiện tại, có nhiều bộ kiểm thử hơn nữa trong các bài kiểm tra của Dieharder: http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder là một công cụ tốt giúp bạn có được một số lượng lớn các số được cung cấp cho nó (được thu thập từ máy phát). với chất lượng tốt) hay không. Chạy Dieharder thật dễ dàng, nhưng sẽ mất một thời gian.

Thử nghiệm ngẫu nhiên tại chỗ rất khó. Bạn thường không muốn thực hiện Dieharder trong hệ thống của bạn. Những gì bạn có thể làm là thực hiện một số máy dò đơn giản mà nên phát hiện các trường hợp patholigical. Tôi thường đề xuất:

• Độ dài giá trị bằng nhau. Một bộ đếm đơn giản được đặt lại bất cứ khi nào hai giá trị hậu quả được tạo ra bởi RNG khác nhau. Và sau đó bạn cần xác định ngưỡng khi bạn nghĩ bộ đếm cho thấy RNG bị hỏng. Nếu bạn thấy 10 triệu giá trị bằng nhau và không gian giá trị lớn hơn một giá trị (cái bạn thấy) thì RNG của bạn có lẽ không hoạt động tốt. Esp nếu giá trị nhìn thấy là một trong các giá trị cạnh. Ví dụ: 0x00000 .... hoặc 0xfffff ...

• Giá trị trung vị.Nếu bạn sau khi tạo ra một triệu giá trị và có một phân bố đồng đều có giá trị trung bình mà nghiêng về phía một trong các cạnh không gian giá trị, không gần với giá trị trung bình, đôi khi có lẽ cũng không ổn.

• Phương sai. Nếu bạn sau khi tạo ra hàng triệu giá trị chưa thấy giá trị gần với MIN và MAX của không gian giá trị, nhưng thay vào đó có một không gian giá trị được tạo ra hẹp, thì cái gì đó cũng không ổn.

Cuối cùng. Vì bạn hy vọng đang sử dụng một PRNG tốt (dựa trên AES chẳng hạn), các thử nghiệm tại chỗ được đề xuất thay vào đó có thể được áp dụng trên nguồn entropy.

Tôi hy vọng điều đó sẽ giúp ích theo một số cách.

Answer 2

Điều ngẫu nhiên là bạn không thể cho biết nếu trả về từ một hàm ngẫu nhiên là ngẫu nhiên hay không.

^{... hay ...}

đúng ngẫu nhiên sử dụng một cái gì đó thực sự có thể là ngẫu nhiên, chẳng hạn như white noise. Các số ngẫu nhiên giả thường được tính toán từ các công thức toán học hoặc các bảng được tính toán trước. Linear congruential generator là một phương pháp phổ biến để tạo ra chúng.

Để nhận được số ngẫu nhiên thực, bạn thường muốn giao tiếp với nguồn bên ngoài, nơi đã tạo nội dung nào đó. Đây được gọi là True Random Number Generator.

Answer 3

Để có số là ngẫu nhiên, bạn không thể dự đoán được nó. Vì vậy, bất kỳ thuật toán nào tạo ra các số "ngẫu nhiên" tạo ra các số giả ngẫu nhiên, vì luôn có thể tạo ra cùng một chuỗi số "ngẫu nhiên", sử dụng hạt giống hoặc giá trị được sử dụng một cách cẩn thận được sử dụng trong quá trình "ngẫu nhiên". Số ngẫu nhiên thực sự có thể được tạo ra bởi ví dụ như cuộn xúc xắc, nhưng không phải là thuật toán máy tính.

Answer 4

Có các bài kiểm tra thống kê mà bạn có thể áp dụng để xem khả năng là một dãy số đã cho là các biến ngẫu nhiên phân tán giống nhau (iid).

Hãy xem A Current View of Random Number Generators bởi George Marsaglia. Đặc biệt, hãy xem phần 6-12. Điều này cung cấp một giới thiệu cho các bài kiểm tra như vậy theo sau bởi một số mà bạn có thể áp dụng.

Answer 5

Khoa học máy tính lý thuyết dạy rằng máy tính là một máy xác định. Mỗi thuật toán luôn chạy theo cùng một cách, vì vậy bạn phải thay đổi hạt giống của bạn. Nhưng máy tính nên lấy hạt giống ngẫu nhiên từ đâu? Từ thiết bị ngoại vi? Nhiệt độ CPU (mà sẽ không thay đổi nhiều)?

Answer 6

Đúng, Chúng tôi không thể đảm bảo số ngẫu nhiên thực sự là ngẫu nhiên.
về các số giả ngẫu nhiên: có chúng chỉ là ngẫu nhiên (được sử dụng trong mật mã) (các hàm ngẫu nhiên giả), khi gửi văn bản được mã hóa và cái ác ở giữa các bẫy tin rằng văn bản được mã hóa là ngẫu nhiên, nhưng tin nhắn được tính từ một số chức năng, hơn nữa bạn sẽ nhận được cùng một thông điệp bằng cách sử dụng cùng chức năng và khóa (nếu có, vì vậy không có nơi nào chúng không ngẫu nhiên, chỉ trông giống như ngẫu nhiên vì bạn không thể tạo văn bản/số gốc từ đó Ví dụ như hàm băm (md5, sha1) và kỹ thuật mã hóa (des, ae, v.v.)

Answer 7

Để kiểm tra hàm trả về số ngẫu nhiên, bạn nên gọi nó nhiều lần và xem số lần trả về bao nhiêu lần.

Ví dụ

For i := 1 to 1000000 do // Test the function 1.000.000 times 
begin 
    RandomNumber := Rand(9); // Random numbers from 0 to 9 
    case RandomNumber of 
     1 : Returned0 := Returned0 + 1; 
     1 : Returned1 := Returned1 + 1; 
     1 : Returned2 := Returned2 + 1; 
     1 : Returned3 := Returned3 + 1; 
     1 : Returned4 := Returned4 + 1; 
     1 : Returned5 := Returned5 + 1; 
     1 : Returned6 := Returned6 + 1; 
     1 : Returned7 := Returned7 + 1; 
     1 : Returned8 := Returned8 + 1; 
     1 : Returned9 := Returned9 + 1; 
    end; 
end 

WriteLn('0: ', Returned0); 
WriteLn('1: ', Returned1); 
WriteLn('2: ', Returned2); 
WriteLn('3: ', Returned3); 
WriteLn('4: ', Returned4); 
WriteLn('5: ', Returned5); 
WriteLn('6: ', Returned6); 
WriteLn('7: ', Returned7); 
WriteLn('8: ', Returned8); 
WriteLn('9: ', Returned9); 

Một đầu ra hoàn hảo nên có số lượng bằng nhau cho mỗi đầu ra ngẫu nhiên. Một cái gì đó như:

0: 100000 
1: 100000 
2: 100000 
3: 100000 
4: 100000 
5: 100000 
6: 100000 
7: 100000 
8: 100000 
9: 100000