Tôi đang xem qua chữ ký một lần của Lamport Diffie.
Như một lưu ý phụ; công việc này là một nỗ lực ban đầu mà đỉnh điểm là cái được gọi là "Phương thức chữ ký dựa trên trạng thái băm"; thiết kế hiện đại bao gồm XMSS và LMS, và gần với những gì trong bài báo Merkle một cách đáng ngạc nhiên. Bạn có thể thấy liên kết Wiki dễ tiếp cận hơn...
Trong mọi trường hợp, để giải quyết câu hỏi của bạn:
- Làm cách nào để các tin nhắn dài (lớn hơn 100 bit) có thể được ánh xạ thành các tin nhắn ngắn (100 bit) bằng chức năng một chiều và chỉ tin nhắn ngắn được ký?
Nghe có vẻ không quá đơn giản:
Chúng tôi lấy thông điệp dài để ký
Chúng tôi sử dụng nó làm đầu vào cho 'hàm một chiều' (thuật ngữ hiện đại: hàm băm), tạo ra đầu ra có kích thước cố định (trong ví dụ này là 100 bit)
Chúng tôi lấy đầu ra 100 bit đó và áp dụng thuật toán chữ ký cho nó.
Điều này không dành riêng cho chữ ký dựa trên hàm băm; về cơ bản, tất cả các thuật toán chữ ký (ít nhất, bất kỳ thuật toán nào tôi đã nghe nói đến) đều sử dụng một biến thể của thuật toán này làm bước đầu tiên. Sự khác biệt duy nhất là 100 bit sẽ không được coi là đủ dài; chúng tôi thường nhấn mạnh vào các kết quả băm dài hơn nhiều (vì khả năng của kẻ tấn công đã tăng lên rất nhiều kể từ năm 1979, do đó chúng tôi cần làm cho hệ thống của mình mạnh hơn).
Câu hỏi rõ ràng là "tại sao điều này lại an toàn"? Chà, nếu chúng ta giả sử rằng kẻ tấn công không thể tìm thấy một thông báo khác mà hàm một chiều ánh xạ tới cùng 100 bit và kẻ tấn công không thể tạo chữ ký cho tập hợp 100 bit khác mà thông báo của kẻ tấn công ánh xạ tới, thì điều đó là an toàn .
Trên thực tế, trong thực tế, chúng tôi lo lắng về các cuộc tấn công xung đột, trong đó kẻ tấn công có quyền kiểm soát thông báo hợp lệ đang được ký (nhưng anh ta vẫn cần tạo ra một chữ ký giả mạo, nghĩa là chữ ký hợp lệ cho một thông báo chưa được ký); Merkle cân nhắc điều đó, tuy nhiên, bây giờ hãy để mọi thứ đơn giản.
- "tin nhắn có thể được mã hóa bằng một khóa ngẫu nhiên mới được tạo..." Ai đó có thể giải thích điều này cho tôi không?
Chà, phần này có thể được bỏ qua - đây là một phần của bài báo mà tiền điện tử hiện đại không tuân theo.
Merkle cố gắng xác định 'chức năng mã hóa được chứng nhận' và sử dụng các giả định cụ thể để làm như vậy, bao gồm cả đầu vào ngẫu nhiên; thông báo được ký không phải là ngẫu nhiên, và do đó anh ta chèn một chức năng mã hóa (với một khóa ngẫu nhiên) để làm cho nó phù hợp với các giả định của anh ta.
Trong tiền điện tử hiện đại, chúng tôi không làm điều này - chúng tôi thường sử dụng hàm băm có sẵn (chẳng hạn như SHA-2 hoặc SHAKE) và sử dụng hàm đó - chúng đã được thiết kế (và phân tích mã hóa) để đáp ứng các giả định khác nhau về mật mã hàm băm; do đó chúng tôi (với tư cách là nhà thiết kế chữ ký) không phải lo lắng về điều đó.
Công bằng mà nói với Merkle, đây có thể là lần đầu tiên bất kỳ ai cố gắng tìm ra 'hàm băm chống va chạm' sẽ trông như thế nào và anh ấy đã có một nỗ lực khá tốt - đó không phải là hướng mà các nhà mật mã học sau này đã thực hiện.
- "Phương pháp được mô tả cho đến nay có một lỗi là B có thể thay đổi m bằng cách thay đổi các bit từ 1 thành 0..." Ai đó có thể giải thích cách khắc phục sự cố này không.
Chà, chúng ta hãy xem xét trường hợp đơn giản nhất; ký một bit duy nhất. Trong "phương pháp được mô tả cho đến nay", để tạo khóa riêng, chúng tôi sẽ chọn một giá trị ngẫu nhiên $x$và áp dụng một chức năng ngẫu nhiên $F$ với nó, tạo ra giá trị chung $F(x)$. Sau đó, để ký bit '1', chúng tôi sẽ tạo dưới dạng chữ ký $x$ (mà người xác minh sẽ có thể xác thực rằng $F$ ánh xạ tới khóa chung). Tuy nhiên, để ký bit '0', chúng tôi sẽ không tiết lộ bất cứ điều gì. Rõ ràng là ai đó nhìn thấy chữ ký hợp lệ là '1' có thể chuyển đổi nó thành chữ ký '0' (hoặc, đối với vấn đề đó, tạo chữ ký '0' mà không nhìn thấy gì).
Trong sơ đồ Lamport, để ký một bit, chúng tôi tạo hai giá trị ngẫu nhiên $x$ và $x'$và xuất bản dưới dạng khóa công khai các giá trị $F(x)$ và $F(x')$. Để ký số 0, chúng tôi sản xuất $x$; để ký một 1, chúng tôi sản xuất $x'$; ai đó có chữ ký là 1 không thể tạo chữ ký bằng 0 (vì họ phải tạo $x$và họ không biết điều đó).
Bây giờ, điều này hoạt động, tuy nhiên nó khá tốn kém (cuối cùng, bạn cần một khóa chung có số đầu ra băm gấp đôi số bit mà hàm băm của bạn tạo ra - ví dụ: nếu hàm băm của bạn tạo ra 100 bit, thì khóa này có một khóa chung bao gồm của 200 giá trị băm). Bài báo tiếp tục chỉ ra các cách để giảm nó, như đã đề cập trong phần 4 và 5 của bài báo (đó là những gì được sử dụng trong thực tế).