Điểm:3

Sự khác biệt giữa ngẫu nhiên không thống nhất và ngẫu nhiên thống nhất

lá cờ bt

Tôi đang đọc về Hàm dẫn xuất chính (KDF) và trong một phần của Sách mật mã trong thế giới thực của David Wong, một phép so sánh đang được thực hiện với trình tạo số giả ngẫu nhiên (PRNG). Và một trong những điểm khác biệt được cho là KDF lấy đầu vào có độ dài tùy ý ngẫu nhiên không đồng nhất, trong khi PRNG lấy khóa k-bit ngẫu nhiên đồng nhất. Mặc dù cả hai đều có đầu ra độ dài tùy ý ngẫu nhiên thống nhất.

Về cơ bản, người ta nói rằng Sự khác biệt chính là KDF không mong đợi một bí mật ngẫu nhiên hoàn toàn thống nhất làm đầu vào (miễn là nó có đủ entropy).

Chính xác thì ngẫu nhiên không đồng nhất và ngẫu nhiên đồng nhất có nghĩa là gì trong ngữ cảnh này? Ngoài ra, entropy có nghĩa là gì trong bối cảnh này?

Có vẻ như việc hiểu rõ hơn về các thuật ngữ này sẽ giúp đánh giá đúng hơn sự khác biệt giữa KDF và PRNG

Ievgeni avatar
lá cờ cn
Bạn có thể thêm trích dẫn và/hoặc liên kết để có thêm ngữ cảnh không?
Điểm:5
lá cờ ng

thống nhất ngẫu nhiên có nghĩa là tất cả các giá trị có thể đều có khả năng như nhau.Trong đó "tất cả các giá trị có thể" sẽ là những giá trị trong một số tập hợp, khi không được xác định theo cách khác, là tập hợp các chuỗi bit có kích thước của biến được xem xét.

Một ví dụ về đầu vào không đồng nhất cho KDF là khi KDF được cung cấp kết quả của quá trình trao đổi khóa Diffie–Hellman trong $\mathbb Z_p^*$ với $g$ một máy phát điện của cả nhóm đó. Đầu vào của KDF có thể là giá trị của $g^{a\,b}\bmod p$ được biểu thị dưới dạng một chuỗi phụ (ví dụ: big-endian) có kích thước cố định (của $p$, được làm tròn lên bội số của 8 bit), với $a$$b$ bí mật phù du ngẫu nhiên. Một số chuỗi phụ hợp lệ ở đầu vào của KDF không bao giờ có thể xảy ra trong quá trình sử dụng thực tế đó: các chuỗi phụ đầu vào không đại diện cho một số nguyên trong $[1,p-1]$, bao gồm các chuỗi phụ all-0x00 và all-0xFF. Và trong số những cái có thể đạt được, dư lượng bậc hai (đạt được khi một trong hai $a$ hoặc $b$ chẵn) có khả năng cao gấp ba lần so với dư lượng không bậc hai (đạt được khi $a$$b$ là số lẻ).

Một ví dụ khác về đầu vào không đồng nhất là cụm mật khẩu, là đầu vào chung cho một số KDF (chẳng hạn như Argon2 hiện đại hoặc PBKDF2 lỗi thời).


Shannon entropy (tính bằng bit) của một quá trình tạo ra một biến $X$ có thể mất $n$ giá trị các giá trị khác biệt với xác suất $p_i$ với $0\le i<n$, do đó với do đó $1=\displaystyle\sum_{0\le i<n}p_i$$0\le p_i\le1$, được định nghĩa là số lượng $$H(X)=\sum_{0\le i<n\text{ và }p_i\ne0}p_i\log_2(1/p_i)$$

Một entropy hữu ích khác là entropy tối thiểu, định nghĩa là $$H_\text{min}(X)=\log_2(1/\max_{0\le i<n}{p_i})$$

Nó luôn giữ $H_\text{min}(X)\le H(X)$.

Một quá trình tạo ra một $b$-bit chuỗi bit $X$$b$-bit entropy (đối với một trong hai định nghĩa) khi và chỉ khi nó tạo ra các chuỗi bit ngẫu nhiên đồng nhất. Khi ngẫu nhiên không đồng nhất, entropy của nó nhỏ hơn $b$-bit, xuống tới $0$ khi nó luôn tạo ra cùng một chuỗi bit.

Một cách không chính thức, có đủ entropy ở đầu vào của một KDF nếu đầu ra của KDF đó về cơ bản là ngẫu nhiên thống nhất (đối với định nghĩa ít nhiều nghiêm ngặt về điều đó). Điều đó có thể xảy ra khi đầu vào của KDF không ngẫu nhiên đồng nhất, nhưng chỉ khi đầu vào đó có (min-)entropy ít nhất là chiều rộng đầu ra của KDF là $b$ bit (hoặc ít nhất $b$ như vậy mà $2^b$ bất chấp sự liệt kê của đối thủ). Và đó hoàn toàn không phải là điều kiện đủ.

dade avatar
lá cờ bt
về cơ bản nếu tất cả các giá trị có thể - không có khả năng như nhau - do bất kỳ hạn chế nào - thì bạn có tính ngẫu nhiên không đồng nhất không?
fgrieu avatar
lá cờ ng
@dade: vậy đó. Ngoại trừ chúng tôi nói "ngẫu nhiên không đồng nhất" hoặc "ngẫu nhiên không đồng nhất".
dade avatar
lá cờ bt
Sau đó, một câu hỏi liên quan ... làm thế nào một "ngẫu nhiên không đồng đều" có "đủ entropy"?
Paul Uszak avatar
lá cờ cn
@dade Đừng suy nghĩ quá nhiều về điều này - nó đơn giản thôi. Hãy tưởng tượng rằng bạn muốn có 128 âstuffâ, đủ để mã hóa. Nếu nó có tốc độ 8 (phân phối đồng đều theo byte), thì bạn chỉ cần 16 lần. Nhưng bạn có thể nhận được 128 trong số âitâ với tỷ lệ 5,3 (phân phối kỳ lạ) nếu bạn thực hiện 25 lần.
Điểm:4
lá cờ cn

Chính xác thì ngẫu nhiên không đồng nhất và ngẫu nhiên đồng nhất có nghĩa là gì trong ngữ cảnh này? Ngoài ra, entropy có nghĩa là gì trong bối cảnh này?

Đây là tính ngẫu nhiên với phân phối không đồng đều được minh họa dưới dạng hàm khối lượng xác suất (PMF): -

pmf

Bạn có thể thấy rằng cho đến nay số không vẫn phổ biến. Nếu tính ngẫu nhiên đồng nhất, tất cả các giá trị sẽ thẳng hàng với đường màu xanh ở p = 0,0039, tức là $\frac{1}{256}$. Vì trong mật mã, chúng tôi quan tâm đến min. Sự hỗn loạn $\big(H_{\infty} = -\log_2 (p_{max}) \big)$, phân phối trên (nếu I.I.D) có $H_{\infty} \khoảng 5,3$ bit/byte.

Nếu PMF là ngẫu nhiên thống nhất, chúng ta sẽ có $H_{\infty} = 8$ bit/byte. Đây là entropy cực đại đặc trưng cho sự phân bố đồng đều.

Vì vậy, tính ngẫu nhiên không đồng nhất đi vào KDF (có thể là mật khẩu như '123456') và tính ngẫu nhiên đồng nhất xuất hiện.

fgrieu avatar
lá cờ ng
"tính ngẫu nhiên không đồng nhất đi vào KDF và tính ngẫu nhiên đồng nhất xuất hiện" _if_ có đủ entropy trong đầu vào.
Paul Uszak avatar
lá cờ cn
@fgrieu À, hạt dẻ cũ của bạn - sự khác biệt giữa độ phức tạp Kolmogorov, entropy mật mã và entropy thông tin. Chúng ta thực sự nên giải quyết chuyện này vào một ngày nào đó...

Đă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.