Điểm:2

Chúng ta có thể kết hợp hai trình tạo ngẫu nhiên thực sự để có được một trình tạo mới không?

lá cờ co

Ai cũng biết rằng một bộ tạo ngẫu nhiên thực sự khai thác tính ngẫu nhiên xảy ra trong một số hiện tượng vật lý. Ngoài ra, đầu ra của một bộ tạo ngẫu nhiên thực sự có thể bị sai lệch hoặc tương quan. Do đó, kỹ thuật de-skewing là bắt buộc.

Câu hỏi của tôi là nếu chúng ta có hai bộ tạo bit ngẫu nhiên thực sự có đầu ra không vượt qua bộ thử nghiệm của NIST, liệu chúng ta có thể kết hợp các đầu ra này để có được bộ tạo bit ngẫu nhiên vượt qua bộ thử nghiệm ngẫu nhiên thống kê không?

Maarten Bodewes avatar
lá cờ in
Chỉ đơn giản là ghép nối hoặc thậm chí các bit XOR-ing từ PRNG có thể rất có khả năng hiển thị sai lệch, vì vậy tôi nghĩ câu trả lời là *không* đơn giản. Hoặc có thể là "kết hợp" không được mô tả. Tôi đoán nó sẽ phải chứa các kỹ thuật giảm độ lệch tương tự như phải xử lý một TRNG. Trên thực tế, tôi nghĩ bạn có thể chứng minh đây là trường hợp đơn giản bằng cách tách một luồng TRNG thành hai luồng bằng cách lấy từng bit khác.
Paul Uszak avatar
lá cờ cn
Nhiều thông tin khác về điều này [tại đây](https://cs.stackexchange.com/q/57648/31167)...
Điểm:3
lá cờ cn

Điều này thực sự được thực hiện khá thường xuyên trong mạch điện. Hãy xem xét một TRNG kỹ thuật số chung chung dựa trên bộ tạo dao động vòng: -

hoa hồng

Trên đây là một ví dụ thậm chí còn cực đoan hơn ví dụ của bạn, trong đó nhiều (có lẽ 32) bộ tạo dao động vòng riêng lẻ được sử dụng. Tất cả chúng đều giống hệt nhau, tất cả đều thất bại một cách ngoạn mục trước bất kỳ thử nghiệm ngẫu nhiên nào nhưng lại tự tạo ra entropy. Nếu cần 32 bộ tạo dao động vòng để tạo ra 1 bit/tick của entropy, bạn có thể tưởng tượng rằng mỗi bộ tạo ra ít hơn nhiều. Độ lệch của chúng cũng phải rất cao (là đặc điểm của các bộ dao động như vậy). Việc kết hợp chúng giúp cải thiện đáng kể tỷ lệ entropy và do đó làm giảm độ lệch đầu ra.

Một ví dụ khác là việc tạo ra $m \times n$ ma trận trích xuất ngẫu nhiên được sử dụng trong TRNG. Từ ID Quantique, Tài liệu kỹ thuật về Randomness Extractor, Phiên bản 1.0, tháng 9 năm 2012:-

Lý tưởng nhất là r nguồn riêng lẻ được sử dụng trong quy trình được mô tả để tạo ma trận m nên được từ các nguồn khác nhau.

Giai thoại này minh họa cho khái niệm này.Về mặt toán học, mô hình thích hợp là Bổ đề chồng chất (Mitsuru Matsui, Phương pháp phá mã tuyến tính cho mật mã DES) :-

$n$ độc lập, các biến nhị phân ngẫu nhiên, $X_1, X_2, \ldots X_n$,

$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$

Sắp xếp lại, để nếu $ \epsilon_{1,2, \ldots, n} $ đại diện cho sự thiên vị của $ X_1 \oplus \ldots \oplus X_n = 0 $, chúng ta có được độ lệch cuối cùng của $n$ kết hợp các nguồn độc lập như: -

$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$

Nói tóm lại, khi bạn kết hợp ngày càng nhiều RNG độc lập, độ lệch đầu ra tổng thể có xu hướng tiệm cận về không. Vì vậy, tạo ra một cái mới, tốt hơn.

kodlu avatar
lá cờ sa
Bổ đề 4 còn được gọi là bổ đề chồng chất của Matsui.
Điểm:2
lá cờ in

Đúng. Chúng ta có thể kết hợp hai PRNG và tạo ra một PRNG tốt hơn. Hình thức đơn giản nhất sẽ là XOR hai giá trị. Nếu ít nhất một trong số chúng là ngẫu nhiên, thì đầu ra cũng vậy. Điều này không khắc phục được mọi thứ, nhưng nó có các đặc tính tốt có thể chứng minh được. Về cơ bản, nó ít nhất cũng tốt như vậy (Giả sử ngay từ đầu chúng không tương quan với nhau).

Tuy nhiên, nếu chúng tôi có các nguồn rất sai lệch với một số entropy thực, chúng tôi có thể muốn áp dụng hàm băm mật mã. Điều này tốt ngay cả với một nguồn RNG duy nhất.

Các trình tạo ngẫu nhiên an toàn thường thu thập entropy từ nhiều nguồn yếu và trộn chúng bằng mật mã (Về cơ bản là hàm băm). Sau đó, nhóm entropy này là mầm mống cho PRNG bảo mật bằng mật mã. Giả sử chúng ta lo lắng về những đối thủ có khả năng tính toán không giới hạn. Trong trường hợp đó, chúng tôi cố gắng ước tính lượng entropy thực tế mà chúng tôi đã thu thập và chỉ xuất ra một lượng bit ngẫu nhiên nhỏ hơn cho đến khi chúng tôi thu được nhiều entropy hơn.

Điểm:1
lá cờ cn
Leo

Nếu một số điều kiện là đúng, thì có thể kết hợp hai TRNG thành một và thu được đầu ra tốt hơn từ chúng.

Tôi sẽ gọi hai bộ tạo ban đầu là TRNG-1 và TRNG-2 và sự kết hợp của chúng là TRNG-3.

  1. Nếu TRNG-1 đang tạo $k$ bit đầu ra mỗi giây và TRNG-2 đang tạo $l$ bit đầu ra mỗi giây, sự kết hợp của chúng (TRNG-3) cần tạo ra ít hơn $k+l$ bit đầu ra mỗi giây. Tốc độ đầu ra thực tế cần được xác định cẩn thận bằng cách xem xét entropy ước tính của cả hai máy phát và mức độ tương quan giữa chúng.
  2. TRNG-1 và TRNG-2 không cần phải tương quan hoàn toàn. Miễn là có một phương sai nhỏ, độc lập giữa chúng, thì có thể tạo ra đầu ra tốt hơn bằng cách kết hợp hơn là sử dụng riêng một trong số chúng.

Có nhiều cách để kết hợp TRNG-1 và TRNG-2. Dưới đây là một số ví dụ.

  1. Hàm băm mật mã
  2. Các chức năng của miếng bọt biển như Keccak hoặc miếng bọt biển Gimli
  3. Phép nhân với ma trận được điền ngẫu nhiên
  4. Ngay cả các phương pháp đơn giản như băm Pearson.

Nếu các TRNG tự nó tốt và không có mối tương quan có ý nghĩa, thì bạn có thể thoát khỏi một XOR đơn giản. Tuy nhiên, các phương pháp trên không quá phức tạp hoặc tốn kém, vì vậy tôi khuyên bạn nên giữ an toàn và thực hiện một trong số chúng.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.