Câu hỏi Làm thế nào là giả ngẫu nhiên và số ngẫu nhiên thực sự khác nhau và tại sao nó quan trọng?


Tôi chưa bao giờ nhận được điều này. Chỉ cần nói rằng bạn viết một chương trình nhỏ bằng bất kỳ ngôn ngữ nào ở tất cả các cuộn một số con xúc xắc (chỉ cần sử dụng con xúc xắc làm ví dụ). Sau 600.000 cuộn, mỗi số sẽ được cuộn khoảng 100.000 lần, đó là những gì tôi mong đợi.

Tại sao có các trang web dành riêng cho 'ngẫu nhiên thực sự'? Chắc chắn, với sự quan sát ở trên, cơ hội nhận được bất kỳ số nào gần như chính xác là 1 bao nhiêu số mà nó có thể chọn.

Tôi đã thử nó Python: Đây là kết quả của 60 triệu cuộn. Biến thể cao nhất giống như 0,15. Không phải là ngẫu nhiên như nó sẽ nhận được?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

651


gốc


Hãy xem bài viết wikipedia trên số ngẫu nhiên được tạo bằng phần cứng Cũng thấy điều này - stats.stackexchange.com/questions/32794/… - steadyfish
Những gì bạn có nghĩa là "cuộn một số con xúc xắc"? Liệu nó có một cánh tay robot và máy ảnh kèm theo? - starblue
trong khi tôi đồng ý với ý chính của giọng nói của bạn, rằng chúng ta thường lo lắng về điều này quá nhiều, nhưng nó đã bị khai thác trong đời thực: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
Xem điều này bài viết về một trò chơi poker trực tuyến thiếu sự ngẫu nhiên thực sự vì sao nó quan trọng. - Varaquilex
Nếu bạn chỉ cần giữ một bộ đếm 0-5 và cuộn một con xúc xắc cho phù hợp, 666 tỷ lần, bạn sẽ nhận được một phân phối như nhau là tốt. - jcora


Các câu trả lời:


Hãy chơi một số poker máy tính, chỉ có bạn, tôi và một máy chủ cả hai chúng tôi tin tưởng. Máy chủ sử dụng trình tạo số giả ngẫu nhiên được khởi tạo với hạt giống 32 bit ngay trước khi chúng ta phát. Vì vậy, có khoảng bốn tỷ sàn có thể.

Tôi nhận được năm lá bài trong tay - dường như chúng tôi không chơi Texas Hold 'Em. Giả sử các thẻ được xử lý một cho tôi, một cho bạn, một cho tôi, một cho bạn, và như vậy. Vì vậy, tôi có thẻ thứ nhất, thứ ba, thứ năm, thứ bảy và thứ chín trên boong tàu.

Trước đó tôi chạy trình tạo số giả ngẫu nhiên bốn tỷ lần, một lần với mỗi hạt giống, và ghi lại thẻ đầu tiên được tạo ra cho mỗi cơ sở dữ liệu. Giả sử thẻ đầu tiên của tôi là nữ hoàng của spades. Điều đó chỉ cho thấy một là thẻ đầu tiên trong một trong mỗi 52 của những sàn có thể, vì vậy chúng tôi đã cắt giảm sàn có thể từ bốn tỷ đến khoảng 80 triệu hoặc hơn.

Giả sử lá bài thứ hai của tôi là ba trái tim. Bây giờ tôi chạy 80 triệu RNG của tôi nhiều lần hơn bằng cách sử dụng 80 triệu hạt giống sản xuất nữ hoàng của spades là số đầu tiên. Điều này đưa tôi một vài giây. Tôi viết xuống tất cả các tầng tạo ra ba trái tim làm lá bài thứ ba - lá bài thứ hai trong tay tôi. Đó là một lần nữa chỉ khoảng 2% của bộ bài, vì vậy bây giờ chúng tôi đang xuống đến 2 triệu sàn.

Giả sử lá bài thứ ba trong tay tôi là 7 câu lạc bộ. Tôi có một cơ sở dữ liệu 2 triệu hạt giống để giải quyết hai lá bài của tôi; Tôi chạy RNG của tôi thêm 2 triệu lần nữa để tìm 2% trong số những bộ bài đó tạo ra 7 câu lạc bộ như lá bài thứ ba, và chúng tôi chỉ còn 40 nghìn sàn.

Bạn thấy cách này đi. Tôi chạy RNG 40000 lần nữa để tìm tất cả các hạt sản xuất thẻ thứ tư, và chúng tôi giảm xuống 800 bộ, và sau đó chạy 800 lần để có được 20 hạt giống sản xuất thẻ thứ năm, và bây giờ tôi chỉ tạo ra hai mươi bộ bài và tôi biết rằng bạn có một trong hai mươi bàn tay có thể. Hơn nữa, tôi có một ý tưởng rất tốt về những gì tôi sẽ vẽ tiếp theo.

Bây giờ bạn có thấy lý do tại sao sự ngẫu nhiên thực sự là quan trọng? Cách bạn mô tả nó, bạn nghĩ rằng phân phối là quan trọng, nhưng phân phối không phải là những gì tạo ra một quá trình ngẫu nhiên. Không thể đoán trước là những gì làm cho một quá trình ngẫu nhiên.

CẬP NHẬT

Dựa trên các ý kiến ​​(bây giờ đã bị xóa do tính chất không mang tính xây dựng của họ), ít nhất 0,3% số người đã đọc điều này bị nhầm lẫn với quan điểm của tôi. Khi mọi người tranh luận chống lại các điểm tôi đã không thực hiện, hoặc tệ hơn, tranh luận cho điểm mà tôi đã làm làm cho trên giả định rằng tôi đã không làm cho họ, sau đó tôi biết rằng tôi cần phải giải thích rõ ràng hơn và cẩn thận.

Dường như có sự nhầm lẫn đặc biệt xung quanh từ phân phối vì vậy tôi muốn cẩn thận sử dụng tập quán.

Các câu hỏi trong tầm tay là:

  • Số pseudorandom và số ngẫu nhiên thực sự khác nhau như thế nào?
  • Tại sao sự khác biệt lại quan trọng?
  • Những khác biệt có liên quan gì đến việc phân phối đầu ra của PRNG không?

Hãy bắt đầu bằng cách xem xét hoàn hảo cách để tạo ra một cỗ bài ngẫu nhiên để chơi bài xì phé. Sau đó, chúng ta sẽ thấy các kỹ thuật khác để tạo ra các deck khác nhau như thế nào, và nếu có thể tận dụng lợi thế của sự khác biệt đó.

Hãy bắt đầu bằng cách giả sử rằng chúng ta có một hộp ma thuật có nhãn TRNG. Như đầu vào của nó, chúng tôi cung cấp cho nó một số nguyên n lớn hơn hoặc bằng một, và như đầu ra của nó nó cho chúng ta một số thực sự ngẫu nhiên giữa một và n, bao gồm. Đầu ra của hộp là hoàn toàn không thể đoán trước (khi được đưa ra một số khác không phải một) và bất kỳ số nào giữa một và n có khả năng là một số khác; đó là để nói rằng phân phối Là đồng phục. (Có những kiểm tra thống kê tiên tiến khác về tính ngẫu nhiên mà chúng ta có thể thực hiện; Tôi bỏ qua điểm này vì nó không phải là một giả thiết đối với lý luận của tôi. TRNG hoàn toàn ngẫu nhiên về mặt thống kê bằng giả thiết.)

Chúng tôi bắt đầu với một cỗ bài chưa được xáo trộn. Chúng tôi yêu cầu hộp cho một số từ một đến 52 - nghĩa là, TRNG(52). Dù số nào nó trả lại, chúng tôi đếm số thẻ đó từ tầng được sắp xếp của chúng tôi và xóa thẻ đó. Nó trở thành lá bài đầu tiên trên sàn xáo trộn. Sau đó, chúng tôi yêu cầu TRNG(51) và làm tương tự để chọn thẻ thứ hai, v.v.

Một cách khác để xem xét nó là: có 52! = 52 x 51 x 50 ... x 2 x 1 sàn có thể, khoảng 2226. Chúng tôi đã chọn một trong số họ một cách ngẫu nhiên.

Bây giờ chúng ta xử lý các thẻ. Khi tôi nhìn vào thẻ của mình, tôi có không có ý tưởng gì bạn có thẻ gì (Ngoài thực tế rõ ràng là bạn không có bất kỳ thẻ nào tôi có.) Chúng có thể là bất kỳ thẻ nào, với xác suất bằng nhau.

Vì vậy, hãy để tôi đảm bảo rằng tôi giải thích rõ ràng điều này. Chúng ta có phân bố đồng đều của mỗi đầu ra riêng lẻ của TRNG(n); mỗi người chọn một số từ 1 đến n với xác suất 1 / n. Ngoài ra, kết quả của quá trình này là chúng tôi đã chọn một trong 52! sàn có thể với xác suất 1/52 !, do đó phân phối trên bộ sàn có thể Là cũng thế đồng phục.

Được rồi.

Bây giờ chúng ta hãy giả sử rằng chúng ta có một hộp ma thuật ít hơn, có nhãn PRNG. Trước khi bạn có thể sử dụng nó, nó phải là gieo hạt với số không dấu 32 bit.

QUA MỘT BÊN: Tại sao lại là 32? Nó không thể được hạt giống với một số 64 hoặc 256 hoặc 10000 bit? Chắc chắn rồi. Nhưng (1) trong thực tế, hầu hết các giá trị PRNG đều được gieo với số 32 bit và (2) nếu bạn có 10000 bit ngẫu nhiên để tạo hạt giống thì tại sao bạn lại sử dụng PRNG? Bạn đã có một nguồn 10000 bit ngẫu nhiên!

Dù sao, quay trở lại cách PRNG hoạt động: sau khi nó được gieo hạt, bạn có thể sử dụng nó giống như cách bạn sử dụng TRNG. Tức là, bạn chuyển nó một số n và nó cho bạn trở lại một số từ 1 đến n. Hơn thế nữa, sự phân bố của đầu ra đó ít nhiều đồng đều. Đó là, khi chúng tôi hỏi PRNG đối với một số từ 1 đến 6, chúng tôi nhận được 1, 2, 3, 4, 5 hoặc 6 mỗi lần khoảng một phần sáu thời gian, bất kể hạt giống là gì.

Tôi muốn nhấn mạnh điểm này nhiều lần bởi vì nó có vẻ là một điều gây nhầm lẫn cho một số người bình luận. Việc phân phối PRNG là thống nhất trong ít nhất hai cách. Đầu tiên, giả sử chúng tôi chọn bất kỳ hạt giống cụ thể nào. Chúng tôi hy vọng rằng chuỗi PRNG(6), PRNG(6), PRNG(6)... một triệu lần sẽ tạo ra sự phân bố đồng đều các số từ 1 đến 6. Và thứ hai, nếu chúng ta chọn một triệu hạt giống khác nhau và được gọi là PRNG(6)  Một lần đối với mỗi hạt giống, một lần nữa chúng tôi mong đợi sự phân bố đồng đều các số từ 1 đến 6. Tính đồng nhất của PRNG đối với một trong các hoạt động này không liên quan đến vụ tấn công mà tôi mô tả.

Quá trình này được cho là giả ngẫu nhiên bởi vì hành vi của hộp thực sự là hoàn toàn xác định; nó chọn từ một trong 232 hành vi có thể dựa trên hạt giống. Đó là, một khi nó được gieo hạt, PRNG(6), PRNG(6), PRNG(6), ...  tạo ra một trình tự các số có phân bố đồng đều, nhưng chuỗi đó là hoàn toàn được xác định bởi hạt giống. Đối với một chuỗi các cuộc gọi nhất định, giả sử, PRNG (52), PRNG (51) ... và cứ thế, chỉ có 232 các chuỗi có thể. Hạt giống về cơ bản chọn cái mà chúng ta nhận được.

Để tạo ra một boong máy chủ bây giờ tạo ra một hạt giống. (Làm thế nào? Chúng ta sẽ trở lại điểm đó.) Rồi họ gọi PRNG(52), PRNG(51) và như vậy để tạo ra boong tàu, tương tự như trước đây.

Hệ thống này dễ bị tấn công mà tôi mô tả. Để tấn công máy chủ, trước tiên chúng tôi sẽ sao chép bản sao của hộp của chúng tôi bằng 0 và yêu cầu PRNG(52) và viết xuống. Sau đó, chúng tôi lại giống với 1, yêu cầu PRNG(52)và viết xuống, tất cả lên đến 232-1.

Bây giờ, các máy chủ poker đang sử dụng PRNG để tạo ra boong tàu đã tạo ra một hạt giống bằng cách nào đó. Nó không quan trọng làm thế nào họ làm như vậy. Họ có thể gọi TRNG(2^32) để có được một hạt giống thật sự ngẫu nhiên. Hoặc họ có thể lấy thời gian hiện tại như một hạt giống, mà hầu như không ngẫu nhiên chút nào; Tôi biết thời gian đó nhiều như bạn làm. Điểm của cuộc tấn công của tôi là nó không quan trọng, bởi vì tôi có cơ sở dữ liệu của tôi. Khi tôi nhìn thấy lá bài đầu tiên, tôi có thể loại bỏ 98% số hạt giống có thể. Khi tôi nhìn thấy lá bài thứ hai của mình, tôi có thể loại bỏ thêm 98%, và cứ thế, cho đến khi cuối cùng tôi có thể nhận được một số hạt giống có thể, và biết với khả năng cao trong tay bạn.

Bây giờ, một lần nữa, tôi muốn nhấn mạnh rằng giả định ở đây là nếu chúng ta gọi PRNG(6) một triệu lần chúng ta sẽ nhận được mỗi số khoảng một phần sáu thời gian. Phân phối đó là (nhiều hơn hoặc ít hơn) đồng phụcnếu tính đồng nhất của phân phối đó là tất cả những gì bạn quan tâm, đó là tốt. Điểm của câu hỏi là có những thứ khác phân phối PRNG(6) mà chúng tôi quan tâm? và câu trả lời là Vâng. Chúng tôi quan tâm NULL cũng.

Một cách khác để xem xét vấn đề là mặc dù phân phối một triệu cuộc gọi đến PRNG(6) có thể ổn, vì PRNG chỉ chọn từ 232 hành vi có thể, nó không thể tạo ra mọi tầng có thể.  Nó chỉ có thể tạo ra 232 của 2226 sàn có thể; một phần nhỏ. Vì vậy, phân phối trên bộ tất cả các sàn rất tệ. Nhưng một lần nữa, đòn tấn công cơ bản ở đây dựa trên việc chúng ta có thể thành công dự đoán hành vi trong quá khứ và tương lai của PRNG từ một mẫu nhỏ đầu ra của nó.

Hãy để tôi nói điều này một lần ba hoặc bốn lần để chắc chắn rằng điều này chìm vào. Có ba bản phân phối ở đây. Đầu tiên, việc phân phối quá trình tạo ra hạt giống 32 bit ngẫu nhiên. Điều đó có thể hoàn toàn ngẫu nhiên, không thể đoán trước và thống nhất và cuộc tấn công vẫn sẽ hoạt động. Thứ hai, phân phối một triệu cuộc gọi đến PRNG(6). Điều đó có thể hoàn toàn đồng nhất và cuộc tấn công vẫn sẽ hoạt động. Thứ ba, sự phân bố các bộ bài được chọn bởi quá trình giả ngẫu nhiên mà tôi đã mô tả. Sự phân bố đó cực kỳ kém; chỉ một phần nhỏ của các sàn có thể IRL có thể được chọn. Cuộc tấn công phụ thuộc vào dự đoán được về hành vi của PRNG dựa trên kiến ​​thức từng phần về đầu ra của nó.

ASIDE: Cuộc tấn công này yêu cầu kẻ tấn công biết hoặc có thể đoán được thuật toán chính xác được sử dụng bởi PRNG là gì. Cho dù đó là thực tế hay không là một câu hỏi mở. Tuy nhiên, khi thiết kế một hệ thống an ninh, bạn phải thiết kế nó để bảo vệ chống lại các cuộc tấn công ngay cả khi kẻ tấn công biết tất cả các thuật toán trong chương trình. Nói cách khác: phần của hệ thống bảo mật phải giữ bí mật để hệ thống được bảo mật được gọi là "khóa". Nếu hệ thống của bạn phụ thuộc vào tính bảo mật của nó đối với các thuật toán bạn sử dụng làm bí mật thì khóa của bạn chứa các thuật toán đó. Đó là một vô cùng vị trí yếu để được!

Tiếp tục đi.

Bây giờ hãy giả sử rằng chúng ta có một hộp ma thuật thứ ba có nhãn CPRNG. Đây là một phiên bản mã hóa sức mạnh của PRNG. Phải mất một hạt giống 256 bit chứ không phải là một hạt giống 32 bit. Nó chia sẻ với PRNG tài sản mà hạt giống chọn từ một trong 2256 hành vi có thể. Và giống như các máy khác của chúng tôi, nó có tài sản mà một số lượng lớn các cuộc gọi đến CPRNG(n) tạo ra sự phân bố đồng đều các kết quả giữa 1 và n: mỗi kết quả xảy ra 1 / n thời gian. Chúng ta có thể chạy cuộc tấn công của chúng ta chống lại nó không?

Cuộc tấn công ban đầu của chúng tôi yêu cầu chúng tôi lưu trữ 232 ánh xạ từ hạt đến PRNG(52). Nhưng 2256 là một con số lớn hơn nhiều; nó hoàn toàn không thể chạy được CPRNG(52)nhiều thời gian và lưu trữ kết quả.

Nhưng giả sử có một số khác cách để lấy giá trị của CPRNG(52) và từ đó suy ra một thực tế về hạt giống? Chúng tôi đã khá ngu ngốc cho đến nay, chỉ brute-buộc tất cả các kết hợp có thể. Chúng ta có thể nhìn vào bên trong hộp ma thuật, tìm ra cách nó hoạt động, và suy ra sự thật về hạt giống dựa trên đầu ra?

Không. Các chi tiết quá phức tạp để giải thích, nhưng CPRNG được thiết kế khéo léo để không thể suy ra được bất kì thực tế hữu ích về hạt giống từ đầu ra đầu tiên của CPRNG(52) hoặc từ bất kì tập hợp con của đầu ra, không có vấn đề lớn như thế nào.

OK, vậy bây giờ hãy giả sử máy chủ đang sử dụng CPRNG để tạo boong. Nó cần một hạt giống 256 bit. Làm thế nào để nó chọn hạt giống? Nếu nó chọn bất kỳ giá trị nào mà kẻ tấn công có thể dự đoán rồi đột nhiên cuộc tấn công trở nên khả thi trở lại. Nếu chúng ta có thể xác định được 2256 hạt giống có thể, chỉ có bốn tỷ trong số đó có khả năng được máy chủ chọn, sau đó Chúng tôi đang trở lại trong kinh doanh. Chúng ta có thể gắn kết tấn công này một lần nữa, chỉ chú ý đến số lượng nhỏ các hạt giống có thể được tạo ra.

Do đó máy chủ nên làm việc để đảm bảo rằng số 256 bit là phân bố đồng đều - nghĩa là, mỗi hạt giống có thể được chọn với xác suất 1/2256. Về cơ bản máy chủ nên gọi TRNG(2^256)-1 để tạo ra hạt giống cho CPRNG.

Điều gì sẽ xảy ra nếu tôi có thể hack máy chủ và đồng hành với nó để xem hạt giống nào đã được chọn? Trong trường hợp đó, kẻ tấn công biết quá khứ và tương lai hoàn chỉnh của CPRNG. Tác giả của máy chủ cần phải bảo vệ chống lại cuộc tấn công này! (Tất nhiên nếu tôi có thể gắn kết thành công cuộc tấn công này thì tôi có lẽ cũng chỉ cần chuyển tiền vào tài khoản ngân hàng của tôi một cách trực tiếp, vì vậy có lẽ điều đó không thú vị. Điểm là: hạt giống phải là một bí mật khó đoán, và số 256 bit thực sự ngẫu nhiên là khá khó đoán.)

Quay trở lại điểm trước đó của tôi về vấn đề phòng thủ: hạt giống 256 bit là Chìa khóa cho hệ thống bảo mật này. Ý tưởng về CPRNG là hệ thống được bảo mật miễn là khóa được bảo mật; ngay cả khi mọi thông tin khác về thuật toán được biết, miễn là bạn có thể giữ bí mật khóa, thẻ của đối phương không thể đoán trước được.

OK, vì vậy hạt giống nên được phân phối bí mật và thống nhất bởi vì nếu không, chúng ta có thể gắn kết một cuộc tấn công. Chúng ta có giả thiết rằng sự phân bố đầu ra của CPRNG(n) là thống nhất. Điều gì về việc phân phối trên tập hợp của tất cả các sàn có thể?

Bạn có thể nói: có 2256 chuỗi đầu ra có thể có bởi CPRNG, nhưng chỉ có 2226 sàn có thể. Do đó, có nhiều trình tự có thể hơn các bộ bài, vì vậy chúng tôi ổn; mọi tầng IRL có thể bây giờ (với xác suất cao) có thể có trong hệ thống này. Và đó là một đối số tốt, ngoại trừ ...

2226 chỉ là một xấp xỉtrong số 52 !. Chia nó ra. 2256/ 52! không thể là một con số nguyên vẹn bởi vì một điều, 52! là chia hết cho 3 nhưng không có sức mạnh của hai là! Vì đây không phải là một con số hoàn toàn, chúng tôi có tình huống mà tất cả các sàn đều là khả thi, nhưng một số sàn có nhiều khả năng hơn những người khác.

Nếu điều đó không rõ ràng, hãy xem xét tình hình với số lượng nhỏ hơn. Giả sử chúng ta có ba thẻ, A, B và C. Giả sử chúng ta sử dụng một PRNG với một hạt giống 8 bit, vì vậy có 256 hạt giống có thể. Có 256 đầu ra có thể có của PRNG(3) tùy thuộc vào hạt giống; không có cách nào để có một phần ba trong số họ là A, một phần ba trong số họ là B và một phần ba trong số họ là C vì 256 không chia hết cho 3. Có một chút thiên vị đối với một trong số họ.

Tương tự, 52 không chia đều thành 2256, do đó, phải có một số thiên vị đối với một số thẻ như thẻ đầu tiên được lựa chọn và một thiên vị xa những người khác.

Trong hệ thống ban đầu của chúng tôi với một hạt giống 32 bit có một sự thiên vị lớn và phần lớn các sàn có thể không bao giờ được sản xuất. Trong hệ thống này tất cả các sàn có thể được sản xuất, nhưng sự phân bố của sàn vẫn còn thiếu sót. Một số sàn là rất nhẹ nhiều khả năng hơn những người khác.

Bây giờ câu hỏi là: chúng ta có một cuộc tấn công dựa trên lỗ hổng này không? và câu trả lời là trong thực tế, có thể không. CPRNG được thiết kế sao cho nếu hạt giống thực sự là ngẫu nhiên sau đó không thể tính toán được sự khác biệt giữa CPRNG và TRNG.

OK, vậy hãy tổng kết lại.

Số pseudorandom và số ngẫu nhiên thực sự khác nhau như thế nào?

Chúng khác nhau về mức độ dự đoán mà chúng thể hiện.

  • Số ngẫu nhiên thực sự không thể đoán trước được.
  • Tất cả các số giả ngẫu nhiên có thể dự đoán được nếu hạt giống có thể được xác định hoặc đoán.

Tại sao sự khác biệt lại quan trọng?

Bởi vì có những ứng dụng mà sự an toàn của hệ thống dựa vào NULL.

  • Nếu TRNG được sử dụng để chọn mỗi thẻ thì hệ thống không thể thực hiện được.
  • Nếu CPRNG được sử dụng để chọn mỗi thẻ thì hệ thống sẽ an toàn nếu hạt giống không thể dự đoán được và chưa biết.
  • Nếu một PRNG bình thường với một không gian hạt nhỏ được sử dụng thì hệ thống không an toàn cho dù hạt giống là không thể đoán trước hay không biết; một không gian hạt nhỏ đủ nhạy cảm với các cuộc tấn công bạo lực của loại tôi đã mô tả.

Sự khác biệt có liên quan gì đến việc phân phối đầu ra của PRNG không?

Tính đồng nhất của phân phối hoặc thiếu cho cuộc gọi riêng lẻ đến RNG(n) không liên quan đến các cuộc tấn công mà tôi đã mô tả.

Như chúng ta đã thấy, cả hai PRNG và CPRNG tạo ra sự phân biệt kém về khả năng chọn bất kỳ boong cá nhân nào của tất cả các sàn có thể. Các PRNG là tồi tệ hơn đáng kể, nhưng cả hai đều có vấn đề.

Một câu hỏi nữa:

Nếu TRNG tốt hơn nhiều so với CPRNG, điều này sẽ tốt hơn nhiều so với PRNG, tại sao có ai sử dụng CPRNG hoặc PRNG?

Hai lý do.

Đầu tiên: chi phí. TRNG là đắt. Tạo ra những con số thật sự ngẫu nhiên là khó khăn. CPRNG cung cấp kết quả tốt cho nhiều cuộc gọi tùy ý chỉ với một gọi TRNG cho hạt giống. Mặt trái dĩ nhiên là bạn phải giữ bí mật hạt giống đó.

Thứ hai: đôi khi chúng tôi muốn khả năng dự đoán và tất cả những gì chúng tôi quan tâm là phân phối tốt. Nếu bạn đang tạo dữ liệu "ngẫu nhiên" làm đầu vào chương trình cho một bộ thử nghiệm và nó sẽ hiển thị một lỗi, thì sẽ tốt hơn nếu chạy bộ kiểm thử lại tạo ra lỗi đó một lần nữa!

Tôi hy vọng điều đó rõ ràng hơn nhiều.

Cuối cùng, nếu bạn thích điều này thì bạn có thể thích đọc thêm về chủ đề ngẫu nhiên và hoán vị:


1371



Ok, nam và nữ. Đó là đủ bình luận cho bây giờ. Nếu bạn muốn thảo luận thêm về vấn đề này, hãy lấy cho mình một phòng chat, kthnxbye! - Ivo Flipse♦
@Eric Nhưng hạt giống không được thiết lập lại trước mỗi bản vẽ boong mới, phải không? Vì vậy, trong khi bạn chính xác rằng chỉ có tương đối ít quỹ đạo chúng tôi lấy mẫu từ, bạn không biết chính xác vị trí của quỹ đạo tại thời điểm này và quỹ đạo giao nhau. - A.S.
Có người thực sự đã làm một việc như thế này - EJoshuaS
Một điều trị tốt (nhưng dày đặc) liên quan đến TAOCP vol 2 của Knuth, phần 3.5 “Chuỗi ngẫu nhiên là gì?” (P. 149), bắt đầu với định nghĩa chiếu sáng của chuỗi phân phối, phân phối k và phân phối equ. Chuỗi giả ngẫu nhiên được thảo luận trong 3.5.F (tr. 170). Xem thêm tiêu chí của giả ngẫu nhiên từ -lý thuyết phức tạp và BSI của Đức. - ShreevatsaR


Như Eric Lippert nói, nó không chỉ phân phối. Có nhiều cách khác để đo lường sự ngẫu nhiên.

Một trong số các trình tạo số ngẫu nhiên ban đầu có một chuỗi trong bit ít quan trọng nhất - nó được xen kẽ 0 và 1. Do đó, LSB có thể dự đoán 100%. Nhưng bạn cần phải lo lắng nhiều hơn thế. Mỗi bit phải không thể đoán trước được.

Đây là một cách hay để suy nghĩ về vấn đề này. Giả sử bạn đang tạo ra 64 bit ngẫu nhiên. Đối với mỗi kết quả, lấy 32 bit đầu tiên (A), và 32 bit cuối cùng (B), và tạo một chỉ mục thành một mảng x [A, B]. Bây giờ, hãy thực hiện phép thử một triệu lần và cho mỗi kết quả, tăng mảng tại số đó, tức là X [A, B] ++;

Bây giờ vẽ một biểu đồ 2D, nơi số lượng càng lớn, điểm ảnh sáng hơn tại vị trí đó.

Nếu nó thực sự là ngẫu nhiên, màu sắc phải là một màu xám đồng nhất. Nhưng bạn có thể lấy mẫu. Lấy ví dụ biểu đồ này về "ngẫu nhiên" trong số thứ tự TCP của hệ thống Windows NT:

Windows NT 

hoặc thậm chí cái này từ Windows 98:

Windows 98 

Và đây là sự ngẫu nhiên của việc triển khai bộ định tuyến Cisco (IOS). Cisco ISO

Những sơ đồ này là lịch sự của Giấy Michał Zalewski. Trong trường hợp cụ thể này, nếu người ta có thể dự đoán số thứ tự TCP sẽ là gì của một hệ thống, người ta có thể mạo danh hệ thống đó khi tạo kết nối tới một hệ thống khác - điều này sẽ cho phép cướp kết nối, chặn truyền thông, v.v. Và thậm chí nếu chúng ta không thể dự đoán con số tiếp theo 100% thời gian, nếu chúng ta có thể tạo ra một kết nối mới được tạo ra dưới sự kiểm soát của chúng tôi, chúng ta có thể tăng cơ hội thành công. Và khi máy tính có thể tạo ra 100.000 kết nối trong một vài giây, tỷ lệ cược của một cuộc tấn công thành công xuất phát từ thiên văn đến khả năng hoặc thậm chí có khả năng.


155



Điều này thật rực rỡ, nó làm tôi rơi nước mắt. Nên có một ứng dụng tạo ra các ứng dụng này cho mọi hệ điều hành (mobile / desktop / server) và nền tảng (JVM / Javascript / etc). - HDave
Hàm Windows rand () khá tốt! Nó tạo ra một đám mây không có bất kỳ mô hình rõ ràng nào. Xem triển khai của tôi để thử nó (và các thuật toán khác) ra: github.com/Zalastax/visualize_random - Zalastax


Mặc dù số giả ngẫu nhiên do máy tính tạo ra có thể chấp nhận được trong phần lớn trường hợp sử dụng mà người dùng máy tính gặp phải, có các trường hợp yêu cầu hoàn toàn số ngẫu nhiên không thể đoán trước.

Trong các ứng dụng bảo mật nhạy cảm như mã hóa, một trình tạo số giả ngẫu nhiên (PRNG) có thể tạo ra các giá trị, mặc dù có vẻ ngẫu nhiên trong thực tế, nhưng thực tế có thể dự đoán được bởi kẻ tấn công. Ai đó đang cố gắng để crack một hệ thống mã hóa có thể đoán được các khóa mã hóa nếu một PRNG được sử dụng và kẻ tấn công có thông tin về trạng thái của PRNG. Do đó, đối với các ứng dụng như vậy, một bộ tạo số ngẫu nhiên trong đó tạo ra các giá trị thực sự không cần thiết là cần thiết. Lưu ý rằng một số PRNG được thiết kế để bảo mật về mặt mã hóa và có thể sử dụng cho các ứng dụng nhạy cảm bảo mật như vậy.

Thông tin thêm về các cuộc tấn công RNG có thể được tìm thấy trong bài viết trên Wikipedia này.


91



Các PRNG mã hóa tồn tại và được sử dụng rộng rãi. Chúng có thể từ một hạt giống có kích cỡ khiêm tốn tạo ra một luồng ngẫu nhiên không giới hạn thực tế. Tính toán không thể phân biệt luồng như vậy từ các số ngẫu nhiên thực, do đó không có thông tin bổ sung nào có thể thu được từ bất kỳ phần nào của luồng đó và cho bất kỳ mục đích thực tế nào, các con số này tốt bằng số ngẫu nhiên thực. - aaaaaaaaaaaa
Tôi nghĩ cách dễ nhất để giải thích điều này là các thuật toán tạo số ngẫu nhiên phải được lập trình. Điều đó có nghĩa là có tập hợp các hướng dẫn đang được theo dõi. Nếu có một tập hợp các hướng dẫn, nó không thể ngẫu nhiên. - Keltari
@Keltari Bạn đang thiếu phần tử entropy ... Hầu hết các RNG (ít nhất là mật mã) thu thập dữ liệu đầu vào từ các nguồn bên ngoài (ví dụ di chuyển chuột) và sử dụng nó như một phần của điều kiện bắt đầu - A đến Bđược lập trình nhưng trạng thái ban đầu của A (nên) là không thể tránh khỏi. Linux /dev/random sẽ giữ một xấp xỉ bao nhiêu entropy có sẵn và ngừng đưa ra con số nếu nó rơi quá thấp. - Basic
Trong tò mò - tại sao đèn nham thạch được coi là "thật sự ngẫu nhiên"? Tôi hiểu nó thể hiện hành vi khá khó lường, nhưng ai đó có đủ hiểu biết về động lực học chất lỏng và cách các chất lỏng tương tác trong môi trường hấp dẫn của Trái đất chắc chắn có thể tạo ra kết quả "có thể đoán trước" được không? Chắc chắn, đèn dung nham là không thể đoán trước, nhưng đối với tôi, chúng không ngẫu nhiên chút nào, nhưng có thể đoán trước được. - theGreenCabbage
@ theGreenCabbage: Tôi nghi ngờ rằng đèn dung nham là hỗn loạn. Với một mô hình máy tính đủ tốt và đủ số chính xác, bạn có thể (về nguyên tắc) dự đoán hành vi trong một thời gian. Nhưng, bởi vì hệ thống là hỗn loạn, hai bóng nham thạch với sự thay đổi nhỏ nhất trong điều kiện ban đầu sẽ nhanh chóng phân tán trong hành vi. (Và nhận xét này bỏ qua những người thu hút hỗn loạn.) - dmm


Tôi đã thử nó bằng Python: Đây là kết quả của 60 triệu cuộn. Biến thể cao nhất giống như 0,15. Không phải là ngẫu nhiên như nó sẽ nhận được?

Trên thực tế, đó là nên "tốt" nó xấu... Tất cả câu trả lời hiện có đều tập trung vào dự đoán được đưa ra một chuỗi nhỏ các giá trị ban đầu. Tôi muốn đưa ra một vấn đề khác:

của bạn phân phối có độ lệch chuẩn nhỏ hơn nhiều so với cuộn ngẫu nhiên nên

Sự ngẫu nhiên thực sự không đến cái đó gần trung bình "gần như chính xác 1 bao nhiêu số mà nó có thể chọn" mà bạn đang sử dụng làm chỉ dẫn về chất lượng.

Nếu bạn nhìn vào câu hỏi về Stack Exchange này về phân phối xác suất cho nhiều cuộn xúc xắc, bạn sẽ thấy một công thức cho độ lệch chuẩn của N cuộn xúc xắc (giả sử kết quả thực sự ngẫu nhiên):

 sqrt(N * 35.0 / 12.0).

Sử dụng công thức đó, độ lệch chuẩn cho:

  • 1 triệu cuộn là 1708
  • 60 triệu cuộn là 13229

Nếu chúng ta xem kết quả của bạn:

  • 1 triệu cuộn: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) là 804
  • 60 triệu cuộn: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) là 3827

Bạn không thể mong đợi độ lệch chuẩn của một mẫu hữu hạn để khớp chính xác với công thức, nhưng nó sẽ đến khá gần. Tuy nhiên, tại 1 triệu cuộn bạn đã ít hơn một nửa stddev thích hợp, và bởi 60 triệu bạn dưới một phần ba - nó trở nên tồi tệ hơn, và đó không phải là trùng hợp ngẫu nhiên ....

Pseudo-RNG có xu hướng di chuyển qua một chuỗi các số riêng biệt, bắt đầu với hạt giống và không xem lại số gốc trong một khoảng thời gian cụ thể. Ví dụ: triển khai thư viện C cũ rand() chức năng thường có một khoảng thời gian 2 ^ 32 và chúng sẽ truy cập mọi số từ 0 đến 2 ^ 32-1 chính xác một lần trước khi lặp lại hạt giống. Vì vậy, nếu bạn mô phỏng 2 ^ 32 xúc xắc cuộn trước mô-đun (%) kết quả sẽ bao gồm mỗi số từ 0 đến 2 ^ 32, số đếm cho mỗi kết quả 1-6 sẽ là 715827883 hoặc 715827882 (2 ^ 32 không phải là bội số của 6) và độ lệch chuẩn do đó chỉ nhỏ hơn 0. công thức trên, độ lệch chuẩn chính xác cho 2 ^ 32 cuộn là 111924. Dù sao, vì số lượng các cuộn giả ngẫu nhiên của bạn làm tăng bạn hội tụ về 0 độ lệch chuẩn. Vấn đề có thể được dự kiến ​​là đáng kể khi số lượng cuộn là một phần đáng kể của giai đoạn, nhưng một số RNG giả có thể biểu hiện các vấn đề tồi tệ hơn - hoặc các vấn đề ngay cả với ít mẫu hơn các mẫu khác.

Vì vậy, ngay cả khi bạn không quan tâm đến các lỗ hổng mật mã, trong một số ứng dụng bạn có thể quan tâm đến việc phân phối không có quá nhiều kết quả giả tạo. Một số loại mô phỏng cụ thể là cố gắng tìm ra hậu quả của không đồng đều các kết quả tự nhiên xảy ra với các mẫu lớn các kết quả ngẫu nhiên riêng lẻ, nhưng chúng không được biểu diễn trong một số kết quả của pRNG. Nếu bạn đang cố gắng mô phỏng cách một dân số khổng lồ phản ứng với một số sự kiện, vấn đề này có thể hoàn toàn thay đổi kết quả của bạn dẫn đến kết luận không chính xác cực kỳ.


Để đưa ra một ví dụ cụ thể: Nói một nhà toán học nói với một lập trình viên poker rằng sau 60 triệu cuộn mô phỏng - được sử dụng để nhấp nháy hàng trăm "đèn" nhỏ xung quanh màn hình, nếu đã có 10,013,229 hoặc hơn sáu, mà nhà toán học dự kiến ​​sẽ 1 stddev đi từ trung bình, cần có một khoản thanh toán nhỏ. Theo Quy tắc 68–95–99,7 (Wikipedia) điều này sẽ xảy ra 16% của thời gian (~ 68% nằm trong độ lệch chuẩn / chỉ một nửa bên ngoài là ở trên). Với trình tạo số ngẫu nhiên của bạn, điều này là từ khoảng 3,5 độ lệch chuẩn trên mức trung bình: Dưới 0,025% cơ hội - hầu như không có khách hàng nào nhận được lợi ích này. Xem bảng Độ lệch cao hơn trên trang vừa được đề cập, cụ thể:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

75



Bạn đang so sánh táo và cam ở đây. Hai độ lệch chuẩn hoàn toàn không có gì để làm với nhau. - Jbeuh


Tôi vừa viết trình tạo số ngẫu nhiên này để tạo ra các cuộn xúc xắc

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Bạn sử dụng nó như thế này

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

v.v. Bạn có vui lòng sử dụng trình tạo này cho một chương trình chạy một trò chơi xúc xắc không? Hãy nhớ rằng, phân phối của nó là chính xác những gì bạn mong đợi từ một máy phát điện "thật sự ngẫu nhiên"!

Các trình tạo số giả ngẫu nhiên thực chất giống nhau - chúng tạo ra các con số có thể dự đoán được với sự phân bố chính xác. Chúng tệ vì cùng một lý do mà bộ tạo số ngẫu nhiên đơn giản ở trên là xấu - chúng không thích hợp cho các tình huống mà bạn cần tính không tiên đoán chính xác, không chỉ phân phối chính xác.


50



"Trình tạo số giả ngẫu nhiên ... tạo ra các con số có thể dự đoán được với phân phối chính xác" - Chỉ vì nó là một PRNG không đảm bảo rằng nó có phân phối hoàn hảo (trên thực tế, các số thương mại không lớn, chính xác lý do được nêu trong các câu trả lời này). Mặc dù chúng có thể dự đoán được đủ thông tin (bản ngã được sử dụng, bắt đầu từ hạt giống, giá trị đầu ra, w / e), chúng vẫn có phương sai. - Brian S
Bên cạnh đó, tôi biết, nhưng get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on chỉ là quá thanh lịch không đề cập đến :) - Janus Troelsen
@BrianS Trên thực tế, một PRNG mà các kiểm tra phân phối không thành công theo thời gian sẽ có thể dự đoán được theo định nghĩa. Vì vậy, trên một số N lớn, nếu bạn nhận được thậm chí một chút cách từ N / 2 đứng đầu trong đồng xu N lật, bạn có thể bắt đầu cá cược trên đầu, và bạn có thể giành chiến thắng nhiều hơn bạn bị mất. Tương tự như vậy, nếu bạn có một phân phối hoàn hảo của đầu v đuôi, nhưng người đứng đầu luôn luôn đi theo cặp, sau đó bạn lại có một công thức để chiến thắng. Thử nghiệm phân phối là cách bạn biết PRNG là tốt. - Jon Kiparsky
Bạn quên nonlocal next :-). - Kos
Ví dụ tốt hơn: Pi được cho là bình thường, có nghĩa là bất kỳ chuỗi các chữ số của bất kỳ độ dài nhất định trong bất kỳ cơ sở xuất hiện không thường xuyên hơn bất kỳ chuỗi khác của chiều dài đó trong cơ sở đó. Một thuật toán, khi được yêu cầu n bit ngẫu nhiên, tiếp theo n bit của pi và trả về chúng ("hạt giống" là bit bạn bắt đầu), nên trong thời gian dài tạo ra một phân phối hoàn toàn đồng đều. Nhưng bạn vẫn không muốn nó cho máy phát điện của bạn - người biết bó cuối cùng của bit mà bạn tạo ra có thể tìm thấy lần đầu tiên chuỗi đó xảy ra, giả sử hạt giống của bạn ở đó, và có thể là chính xác. - cpast


Việc tạo số ngẫu nhiên mà máy tính của bạn có thể thực hiện phù hợp với hầu hết các nhu cầu và bạn không thể gặp một thời điểm mà bạn cần một số thực sự ngẫu nhiên.

Đúng thế hệ số ngẫu nhiên có mục đích của nó mặc dù. Trong bảo mật máy tính, cờ bạc, lấy mẫu thống kê lớn, v.v.

Nếu bạn quan tâm đến các ứng dụng của các số ngẫu nhiên, hãy kiểm tra Bài viết trên Wikipedia.


26



Vấn đề lớn là khi bạn cần số ngẫu nhiên mà kẻ tấn công không thể dự đoán vì lý do bảo mật. - David Schwartz
Bạn chắc chắn là địa ngục có khả năng đi qua một thời gian mà bạn cần một số thực sự ngẫu nhiên. Đủ để mở một trang web bắt đầu bằng https://... - Jan Hudec
@ JanHudec: Vâng, trong sử dụng hàng ngày, bạn sẽ cần số ngẫu nhiên an toàn vào thời điểm bạn mở bất kỳ chương trình nào, trước khi bạn nhập vào thanh địa chỉ: hãy xem địa chỉ bố trí không gian địa chỉ. Đó là lý do những thứ như thế này xảy ra. - Reid
@JanHudec Tôi đã nói cụ thể theo nghĩa là bạn sẽ cần sử dụng trình tạo số ngẫu nhiên trực tuyến. Số ngẫu nhiên thực được sử dụng thường xuyên, nhưng rất ít người thực sự cần tạo ra chúng. - Alex McKenzie
Máy đánh bạc cũng sử dụng PRNG chứ không phải TRNG. Các máy phát điện chạy tất cả thời gian và một số được chọn vào thời điểm chính xác mà các nút quay được đẩy. Tổng số PRNG và số lần bấm nút ngẫu nhiên thực sự thành TRNG. - Roger Dahl


Các số ngẫu nhiên được tạo ra bởi các hàm điển hình trong hầu hết các ngôn ngữ lập trình không phải là số ngẫu nhiên hoàn toàn. Chúng là số ngẫu nhiên giả. Vì chúng không hoàn toàn là số ngẫu nhiên, chúng có thể được đoán với đủ thông tin về các số được tạo trước đó. Đây sẽ là thiên tai vì an ninh trong mã hóa.

Ví dụ về chức năng tạo số ngẫu nhiên sau được sử dụng trong glibc không tạo ra số ngẫu nhiên hoàn toàn. Số ngẫu nhiên giả được tạo ra bởi điều này có thể được đoán. Nó là một sai lầm cho các vấn đề an ninh. Có một lịch sử của việc này trở nên tai hại. Điều này không nên được sử dụng trong mật mã.

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

Loại trình tạo số ngẫu nhiên giả này sẽ không bao giờ được sử dụng ở những nơi nhạy cảm về bảo mật mặc dù có ý nghĩa thống kê đến nay.

Một trong những cuộc tấn công nổi tiếng trên giả ngẫu nhiên chính là tấn công vào 802.11b WEP. WEP có khóa dài 104 bit, được nối với bộ đếm 24 bit (bộ đếm) để tạo khóa 128 bit, lần lượt được áp dụng cho Thuật toán RC4 để tạo khóa ngẫu nhiên giả.

( RC4( IV + Key ) ) XOR (message)

Các khóa liên quan chặt chẽ với nhau. Ở đây, chỉ có IV tăng 1 trong mỗi bước và tất cả những người khác vẫn giữ nguyên. Vì đây không phải là hoàn toàn ngẫu nhiên, nó là thảm họa và dễ dàng bị phá vỡ. Chìa khóa có thể được phục hồi bằng cách phân tích khoảng 40000 khung hình, đó là vấn đề của phút. Nếu WEP sử dụng hoàn toàn ngẫu nhiên 24-bit IV, thì nó có thể an toàn cho đến khoảng 2 ^ 24 (gần 16,8 triệu) khung.

Vì vậy, một trong những nên đi với máy phát điện số ngẫu nhiên tinh khiết trong các vấn đề nhạy cảm an ninh khi có thể.


26



Tôi đổ lỗi cho các công cụ WEP trên một giao thức được thiết kế tồi tệ bằng cách sử dụng một mật mã yếu. Với mật mã dòng hiện đại, bạn có thể sử dụng bộ đếm như IV. - CodesInChaos
Vấn đề chính với WEP là lặp lại khóa trong 2 ^ 24 (gần 16 triệu) khung. Nó thậm chí còn tồi tệ hơn với các phím liên quan mà làm cho nó có thể crack mã trong khoảng 40000 khung hình. Điểm chính ở đây là chìa khóa không phải là ngẫu nhiên. Nó có liên quan chặt chẽ, do đó dễ bị nứt. - Prabhu
Pseudo-randomness là xấu trong mật mã chỉ khi tạo khóa mã hóa. Nó hoàn toàn tốt đẹp hơn thế. Thật vậy, RC4 là ít hơn một máy phát điện số giả ngẫu nhiên hạt giống với việc mở rộng 128-bit của khóa XORed vào plaintext của tin nhắn. - Matt


Sự khác biệt là số giả tạo được tạo ra có thể dự đoán được (lặp lại) sau một thời gian không có số ngẫu nhiên thực sự. Độ dài cần thiết để lặp lại phụ thuộc vào chiều dài của hạt giống được sử dụng cho thế hệ của nó.

Đây là một video khá hay về chủ đề đó: http://www.youtube.com/watch?v=itaMNuWLzJo 


12



Dự đoán! = Lặp lại. Mersenne Twister là một ví dụ điển hình về điều đó. Trên hầu hết việc thực hiện sau 624 Int32 bạn có thể dự đoán tất cả các số tiếp theo, nhưng trình tự Mersenne Twister dài hơn nhiều (2 ^ 19937 - 1). - HoLyVieR
Tôi không hiểu tại sao câu trả lời này không được đẩy lên ngăn xếp, vì điều này dường như với tôi rằng đây là câu trả lời chính xác và ngắn gọn cho câu hỏi, ít nhất một phần. Các số ngẫu nhiên giả có thể dễ dàng dự đoán sau một số lần rút, số lượng các phép vẽ khác nhau với thuật toán giả ngẫu nhiên "chất lượng". Chọn một thuật toán "tốt" đang xem xét các khía cạnh: 1. mỗi giá trị được vẽ theo tần suất bằng nhau (phân phối), 2. phải mất một thời gian dài để khởi động lại chuỗi lúc bắt đầu và bắt đầu vẽ lại các số tương tự trong cùng một thứ tự. - mins
"các số ngẫu nhiên thực sự không phải là [có thể dự đoán được]". Đối với ngày hôm nay điều này là đúng sự thật. Bây giờ nếu chúng ta tin vào thuyết Big Bang, và chúng ta có nhiều quyền lực để tính toán trạng thái vũ trụ bất cứ lúc nào sau BB, dựa trên vật lý thì ... chúng ta có thể dự đoán tương lai, bao gồm thực tế là Tôi đang viết nhận xét rất chính xác này. Đúng? - mins
Tuy nhiên, đó là giả thiết, tuy nhiên, xét đến mức độ entropy rộng lớn liên quan đến các hành động thực tế của các vật thể thực, sức mạnh tính toán cần thiết sẽ cực kỳ lớn. Hãy nghĩ về các lục địa được bao phủ trong máy tính. Ngoài ra, do sự phụ thuộc vào trạng thái trước đó, trạng thái của mọi cơ thể trong vũ trụ tại mọi thời điểm sẽ cần phải được lưu trữ, theo định nghĩa sẽ đòi hỏi nhiều không gian hơn là có sẵn trong vũ trụ, hoàn toàn đầy bộ nhớ - TheEnvironmentalist
@TheEnvironmentalist - Ah! "Lục địa được bao phủ trong máy tính" ... không phải là điều "Hướng dẫn của Hitchhiker đến thiên hà"? ;-) - ysap


Giả sử rằng một số ngẫu nhiên giả có thể được đoán bởi bất kỳ ai trước khi nó được tạo ra.

Đối với các ứng dụng tầm thường, giả ngẫu nhiên là tốt, giống như ví dụ của bạn, bạn sẽ nhận được khoảng phần trăm chính xác (khoảng 1/6 của tổng số kết quả) với một số biến thể nhỏ (Bạn sẽ thấy nếu bạn cuộn 600 con xúc xắc) lần);

Tuy nhiên, khi nói đến những thứ như bảo mật máy tính; Sự ngẫu nhiên thực sự là bắt buộc.

Ví dụ, thuật toán RSA bắt đầu với máy tính chọn hai số ngẫu nhiên (P và Q) và sau đó thực hiện một số bước để những số đó tạo ra các số đặc biệt được gọi là khóa công cộng và khóa riêng của bạn. (Phần quan trọng của khóa riêng là nó là riêng tư, và không ai khác biết điều đó!)

Nếu kẻ tấn công có thể biết hai con số 'ngẫu nhiên' mà máy tính của bạn sẽ chọn, họ có thể thực hiện các bước tương tự để tính khóa riêng của bạn (cái mà không ai khác biết phải biết!)

Với khóa riêng của bạn, kẻ tấn công có thể làm những việc như a) Nói chuyện với ngân hàng của bạn giả vờ là bạn, b) Lắng nghe lưu lượng truy cập internet 'an toàn' của bạn và có thể giải mã nó, c) Giả mạo giữa bạn và các bên khác trên internet.

Đó là nơi ngẫu nhiên thực sự (nghĩa là không thể đoán được / tính toán) là bắt buộc.


10





Số ngẫu nhiên đầu tiên mà tôi từng sử dụng có đặc tính tuyệt vời của bất kỳ hai số ngẫu nhiên liên tiếp nào, số thứ hai lớn hơn với xác suất là 0,6. Không 0,5. Và thứ ba lớn hơn giây thứ hai với xác suất 0.6, v.v. Bạn có thể tưởng tượng cách nó chơi tàn phá với một mô phỏng.

Một số người sẽ không tin tôi điều này thậm chí có thể với những con số ngẫu nhiên được phân phối đều, nhưng rõ ràng là có thể nếu bạn nhìn vào dãy số (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) trong đó số thứ hai của hai số lớn hơn với xác suất 0.6.

Mặt khác, để mô phỏng nó có thể là quan trọng để có thể tái tạo các số ngẫu nhiên. Giả sử bạn thực hiện mô phỏng lưu lượng truy cập và muốn tìm hiểu cách một số hành động bạn có thể thực hiện có thể cải thiện lưu lượng truy cập. Trong trường hợp đó, bạn muốn có thể tạo lại chính xác dữ liệu lưu lượng truy cập giống nhau (như những người đang cố gắng nhập thị trấn) với các hành động khác nhau mà bạn đã cố gắng cải thiện lưu lượng truy cập.


10