Số ngẫu nhiên thực sự theo tỷ lệ - Chip bộ nhớ quá tải tạo ra các số thực sự ngẫu nhiên để mã hóa

Trong nhiều năm, những con số thực sự ngẫu nhiên ở quy mô đã khó nắm bắt. Vì vậy, tôi đọc nghiên cứu gần đây này https://www.newscientist.com/article/2303984-overloaded-memory-chips-generate-truly-random-numbers-for-encryption/ và https://cacm.acm.org/news/257835-overloaded-memory-chips-generate-truly-random-numbers-for-encryption với những âm mưu, dự đoán và phấn khích tuyệt vời.

Câu hỏi đầu tiên của tôi: Những khó khăn liên quan đến việc tạo số ngẫu nhiên thực sự là gì? Chi phí, thực tế như tiêu thụ điện năng?

Câu hỏi thứ hai: Cái gì và ai có thể là người phân xử về tính ngẫu nhiên thực sự? tức là ai quyết định con số cụ thể này thực sự được tạo ngẫu nhiên?

1. Khó khăn chính là tìm một nguồn entropy tốt. Đó là thước đo của "sự ngẫu nhiên". Vâng, nếu chúng ta có một giá trị $hạt giống$ như vậy mà $H(hạt giống)=n$, chúng tôi không thể tạo ra một chuỗi $x, |x|\geq|hạt|$ với entropy lớn hơn, tức là $\forall x : x=f(seed)\land|x|\geq|seed|\implies H(x)\leq H(seed)$, ở đâu $f$ là một số thuật toán xác định (PRNG). Entropy được định nghĩa như sau: $$ H(X)=-\sum_{x\ \in\ \text{Dom}(X)}\text{Pr}(x)\cdot\text{log}_2\text{Pr}(x) $$ ở đâu $X$ là một biến ngẫu nhiên. <removed>
   Nói cách khác, trong trường hợp tốt nhất, chúng ta nhận được một chuỗi dài hơn với cùng mức độ "ngẫu nhiên" trong đó như trong chuỗi ngắn nhất. Không có cách nào để tạo ra một có khả năng không giới hạn chuỗi ngẫu nhiên thực sự bằng cách sử dụng một số thuật toán từ một chuỗi hữu hạn mà không có bất kỳ nguồn entropy bổ sung nào.
   CẬP NHẬT: nó không hoàn toàn chính xác để sử dụng công thức cho trình tự. Nhưng ý nghĩa của đoạn này vẫn còn nguyên giá trị: bạn không thể tạo ra "sự ngẫu nhiên" từ con số không.

2. Chà, đó là một câu hỏi hay, bởi vì chúng ta có thể nói, rằng liệu một chuỗi nào đó có ngẫu nhiên hay không với một xác suất nhất định. Cách duy nhất là sử dụng các bài kiểm tra thống kê. Một chuỗi ngẫu nhiên lý tưởng (hoặc thực sự) được định nghĩa như sau: $$ X_\to=\{\zeta_1, \zeta_2, ..., \zeta_n,...\} $$ ở đâu $\zeta_i, i\in\{1,2,...\}$ được phân phối đều trên một số tập hợp $X$ biến ngẫu nhiên và trong mỗi tập hợp con $\{\zeta_{i_1},...,\zeta_{i_k}\}$ tất cả các biến là độc lập. Có một chuỗi tùy ý, điều duy nhất chúng ta có thể làm là kiểm tra các thuộc tính thống kê của nó và nói rằng với xác suất cao (hoặc thấp), các yêu cầu này phù hợp với các biến này <redacted to make it more clear>.
   <removed>
   Trong tất cả các bài báo tôi đã đọc về các trình tạo ngẫu nhiên thực sự đều được kiểm tra theo thống kê.Thật không may, tôi không thể đọc bài báo mà bạn đã đề cập trong câu hỏi, nhưng tôi nghĩ rằng sẽ có loại nghiên cứu tương tự.

Chà, tôi cho rằng có thể có một phương pháp tiềm năng để chứng minh, rằng một trình tạo nào đó tạo ra một chuỗi có entropy tối đa có thể, nhưng tôi vẫn chưa thấy nó. Nhưng có lẽ không thể có phương pháp như vậy. Nếu có một, tôi muốn đọc về nó :)

CẬP NHẬT: entropy tối đa không cần thiết cho tính ngẫu nhiên thực sự. Đây là một số trích dẫn của @Paul Uszak:

Một trình tự như vậy [thực sự ngẫu nhiên] chỉ cần một lượng phức tạp Kolmogorov tăng dần một cách đơn điệu. Xu hướng/tương quan là không liên quan.

TRNG không được kiểm tra tính ngẫu nhiên thực sự. sự thậtâ của họ xuất phát từ sự hiểu biết về các quá trình vật lý không xác định tạo ra độ phức tạp Kolmogorov đầu ra.

CẬP NHẬT: tóm lại: TRNG sử dụng một số sự kiện vật lý không thể đoán trước để tạo ra một chuỗi, PRNG sử dụng thuật toán máy tính.

Những khó khăn liên quan đến việc tạo ra các số ngẫu nhiên thực sự là gì?

Không có khó khăn hữu hình nào với việc tạo ra vô số số ngẫu nhiên thực sự. Các đã có daemon tuyên bố sẽ tạo megabit/s entropy thực sự mà không cần bất kỳ phần cứng bên ngoài nào. Mặc dù vậy, tôi không chắc ý nghĩa thực tế của at scaleâ là gì. Đạp xe một khóa AES mỗi phút là tốc độ Kolmogorov <3 bit/s. Với sự tôn trọng, đó là trò chơi trẻ em ngay cả đối với những người tự làm. Nhìn vào những bức ảnh tiệc đêm trên điện thoại thông minh của bạn và tự hỏi tất cả những tiếng ồn hình ảnh đó là gì. Nếu bạn có ~3000 Euro, bạn có thể mua một TRNG 240 Mbps sử dụng công nghệ tách chùm. Nếu cuộc sống của bạn phụ thuộc vào nó, $2600 có quá nhiều không? Và các Yeolde /dev/ngẫu nhiên sẽ làm> 30 kB/giờ chỉ cần kiểm tra email. Nhân đôi số tiền đó nếu bạn đang nghiên cứu về PornHub.

Lý do vô hình có khả năng nhất mà tôi không được đi vào được phản ánh trong những điều sau đây; Các vận động viên đang được khuyên nên sử dụng điện thoại có ổ ghi ở Bắc Kinh.

Cái gì và ai có thể là trọng tài về tính ngẫu nhiên thực sự?

Chỉ có bạn.

Có một dòng dây đeo trang web rất nổi tiếng nói rằng An toàn entropy? Entropy của bạn.â Khái niệm về tính không thể phân biệt trong tính toán có nghĩa là đầu ra của Mersenne Twister trông khá giống với đầu ra của /dev/ngẫu nhiên. Đây là lấy đi từ đây.

Trình tạo số ngẫu nhiên phần cứng trên chip của Intel trông có vẻ ngẫu nhiên nhưng không ai trong cộng đồng *nix tin tưởng nó. Và vì vậy họ không nên đưa ra NOBUS đã được xác nhận công khai2 chính sách. Và thật không may cho bạn/chúng tôi, không thể thiết kế ngược một khuôn silicon nhiều lớp với hàng tỷ bóng bán dẫn.

Phần này trong câu trả lời của tôi có thể tiếp tục với hàng nghìn lần di chuột, vì vậy tôi sẽ kết thúc bằng việc cố gắng thuyết phục bạn tự xây dựng một nguồn entropy với một chút điốt (£2,08 + VAT/20).

2 Nhận một chiếc mũ thiếc. Loại gà tây Giáng sinh thật dày. Mục NOBUS đã bị xóa khỏi Wikipedia. Rút ra kết luận của riêng bạn. Vì vậy, tôi hướng dẫn bạn đến WAPO mạo từ với người đứng đầu CIA/NSA (cùng một người).