Điểm:1

Độ phức tạp của khai thác/ký Hash

lá cờ bd

Trong khi đọc về khai thác tiền điện tử, tôi thấy rằng nó yêu cầu một số bit đầu của đầu ra hàm băm phải bằng 0. Điều này dẫn đến khả năng chống tạo ảnh trước của hàm băm, do đó được thực hiện với tìm kiếm toàn diện.

Câu hỏi của tôi, giả sử tôi có một hàm băm lý tưởng cung cấp đầu ra 128 bit và tôi muốn 4 bit đầu tiên là 0. Số thời gian dự kiến ​​tôi phải chạy nó (với các thông báo được chọn ngẫu nhiên) để tôi nhận được kết quả mong muốn là bao nhiêu?

Cụ thể hơn, tôi đang tìm kiếm một loại chức năng, sẽ mang lại sự phức tạp, để thiết lập $m$ bit của hàm băm lý tưởng trả về $n$ bit làm đầu ra.

kelalaka avatar
lá cờ in
Điều này có trả lời câu hỏi của bạn không? [SHA-512 - Tìm thông báo băm bắt đầu bằng ít nhất mười hai số không khó đến mức nào?](https://crypto.stackexchange.com/questions/89690/sha-512-how-difficult-is-it-to -tìm-a-băm-tiêu hóa-bắt đầu-với-ít nhất-mười hai)
hola avatar
lá cờ bd
@kelalaka cảm ơn vì đã liên kết. Cái đó mang tính thực nghiệm hơn, nhưng tôi muốn một số tính toán lý thuyết
kelalaka avatar
lá cờ in
Chúng tôi đã thua khi mô hình của chúng tôi là ngẫu nhiên thống nhất. Ngoài ra, câu trả lời đã là lý thuyết. Nếu bạn đang tìm kiếm giá trị mong đợi, điều đó thật dễ dàng; Đó là Thử nghiệm Bernoulli và giá trị kỳ vọng là $p$ và kết quả là 16/1. Giá trị kỳ vọng cho số lượng thử nghiệm độc lập để đạt được thành công đầu tiên là $1/p = 16$
kelalaka avatar
lá cờ in
Cũng xin lưu ý rằng, khi chúng tôi nói đến độ phức tạp, thì nó phải phụ thuộc vào đầu vào chứ không chỉ là định lượng như hàm băm mật mã dự kiến ​​sẽ có $\mathcal{O}(2^n)$ bảo mật trước hình ảnh và SHA-256 có bảo mật hình ảnh trước 256 bit không $\mathcal{O}(2^{256})$ vì đó là hằng số!.
Điểm:3
lá cờ cn

Đối với một đầu vào ngẫu nhiên. Mỗi bit có xác suất $\frac{1}{2}$ bằng không. Sau đó, bởi vì chúng tôi giả sử tính độc lập (hàm băm lý tưởng ngụ ý giả định này). Đối với mỗi đầu vào, xác suất để có $4$ số không trong các bit hàng đầu là $\frac{1}{2^4}=\frac{1}{16}$.

Sau đó $k$ tính toán, bởi vì chúng tôi coi mỗi đầu ra là độc lập (vẫn bởi vì đó là một hàm băm lý tưởng). Xác suất đợi chính xác $i$ các bước là một đầu ra tốt là $\frac{1}{16}\left(15/16\right)^{i-1}$. (vì bạn có đầu ra sai cho $(i-1)$ băm, và sau đó là một hàm băm).

Và kỳ vọng về thời gian tính toán là $\sum^{\infty}_{i=1} i\frac{1}{16}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=j}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=0}\left(15/16\right)^{j+i-1 }$

$$=\frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\sum^{\infty}_{i= 0}\left(15/16\right)^{i} $$ $$= \frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\frac{1}{1/16}$ $ $$=\sum^{\infty}_{j=0} \left(15/16\right)^{j} =16$$.

Sau đó, trung bình bạn phải tính toán $16$ băm để tìm một cái tốt.

Bạn có thể dễ dàng khái quát hóa bằng chứng này bằng cách thay thế $16$ qua $2^m$, và bạn sẽ suy ra rằng trung bình bạn cần tính $2^m$ băm.

Lưu ý rằng bởi vì chúng ta chọn trước các tọa độ mà chúng ta muốn có các số 0, nên tổng đầu ra của hàm băm không thành vấn đề nếu chúng ta nhìn vào số lượng giá trị băm mà chúng ta nên tính toán (nhưng nó có thể làm được nếu chúng ta xem xét thời gian tính toán của $H$).

hola avatar
lá cờ bd
Hừm. Vì vậy, bạn cần các thử nghiệm ngẫu nhiên $2^m$ để mong đợi đầu ra hàm băm trong đó các vị trí $m$ được cố định.
Ievgeni avatar
lá cờ cn
Có, nhưng đó là mức trung bình.

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