Tác giả: David Wong
Nguồn: https://cryptologie.net/posts/hash-based-signatures-part-iv-xmss-and-sphincs/
Bài báo gốc được xuất bản vào tháng 12 năm 2015.
Bài viết này là chương cuối cùng sê-ri sê-ri bài đăng trên blog về các lược đồ chữ ký dựa trên hàm băm. Bạn có thể tìm thấy bài viết đầu tiên trong sê-ri này ( bản dịch tiếng Trung ) tại đây.
Giờ thì đến phần thú vị nhất — phương thức ký tên thực tế.
PQCrypto đã công bố một đề xuất sơ bộ hơn một tháng trước. Trong đó thuật toán hậu lượng tử được đề xuất là " XMSS " và " SPHINCS ":
Bài viết này trước tiên sẽ giới thiệu XMSS, một lược đồ chữ ký có trạng thái; sau đó là SPHINCS, lược đồ chữ ký không trạng thái đầu tiên!
XMSS
“ Hệ thống chữ ký Merkle mở rộng (XMSS)” xuất hiện vào năm 2011 và sau đó trở thành bản dự thảo của IETF (Lực lượng nhiệm vụ kỹ thuật Internet) vào năm 2015 .
Cấu trúc chính của nó tương tự như Merkle trees, chỉ có một vài khác biệt nhỏ. Trong cây XMSS, nút con được XOR với một mặt nạ trước khi được băm thành nút cha của chúng. Mỗi nút có một mặt nạ duy nhất.
Điểm độc đáo thứ hai là các lá của cây XMSS không phải là hàm băm của các khóa công khai dùng một lần, mà là các giá trị gốc của một loại cây khác—được gọi là "cây L".
Cây L cũng áp dụng một mặt nạ cho các giá trị băm của nút; mặt nạ của cây L khác với mặt nạ của cây XMSS chính, nhưng nó phổ biến trên tất cả các cây L.
Các lá của cây L-tree lưu trữ một phần tử với khóa công khai WOTS+ (sơ đồ này được giải thích trong bài viết đầu tiên của sê-ri này ( bản dịch tiếng Trung )).
Nếu bạn cũng giống tôi và thắc mắc tại sao khóa công khai của WOTS+ cần được lưu trữ trên cây, đây là lời giải thích của Huelsing:
Mục đích của cấu trúc cây không phải là để lưu trữ khóa công khai WOTS, mà là để băm nó, và phương pháp này cho phép chúng ta chứng minh rằng một hàm băm có "khả năng chống tìm ảnh ngược thứ hai" là đủ (không cần hàm băm có khả năng chống va chạm).
Ngoài ra, khóa công khai chính bao gồm nút của cây XMSS và mặt nạ bit được sử dụng trong cây XMSS và cây L.
SPHINCS
“SPHINCS” là một phương pháp tiếp cận mới hơn, kết hợp nhiều tiến bộ trong lĩnh vực này, và hơn thế nữa! Nó mang đến cho chúng ta trạng thái phi quốc tịch mà tất cả chúng ta đều mong đợi.
Đúng vậy, điều này có nghĩa là bạn không cần phải lưu bất kỳ trạng thái nào nữa. Nhưng trước khi giải thích cách thức hoạt động của nó, hãy cùng xem cấu trúc của SPHINCS.
Đầu tiên, SPHINCS được tạo thành từ nhiều cây.
Hãy cùng xem xét cây đầu tiên:
- Mỗi nút là giá trị băm của kết quả phép XOR giữa chuỗi nút trước đó với mặt nạ bit của cấp độ tương ứng.
- Khóa công khai bao gồm giá trị băm gốc và mặt nạ bit.
- Các lá của cây chính là các khóa công khai đã được nén của cây L-tree WOTS+.
Hãy coi cây L-tree WOTS+ như cây L-tree XMSS mà chúng ta đã giải thích trước đó, ngoại trừ thiết kế mặt nạ bit của nó trông giống cây băm SPHINCS hơn (nghĩa là, mỗi cấp độ của cây có một mặt nạ riêng).
Mỗi lá chứa một chữ ký dùng một lần Winderitz, cho phép chúng ta ký vào một cây khác. Do đó, theo sơ đồ trên, lớp tiếp theo sẽ có 4 cây SPHINCS, mỗi cây chứa một khóa công khai WOTS+ trong các lá của nó.
Quá trình này tiếp tục đi xuống... Số lượng các chồng cây và số lượng lá trong mỗi cây hoàn toàn phụ thuộc vào các tham số ban đầu của bạn. Cuối cùng, khi bạn đạt đến lớp 0, chữ ký WOTS+ không còn ký các cây SPHINCS khác nữa, mà chỉ ký các cây HORS.
Cây HORS có cấu trúc giống hệt cây L, ngoại trừ việc chúng chứa chữ ký HORS ít lần thay vì chữ ký Winternitz một lần. Chúng tôi sử dụng chúng để ký các thông điệp của mình, điều này giúp cải thiện tính bảo mật của hệ thống vì miễn là chúng ta luôn sử dụng cùng một khóa HORS khi ký một thông điệp, sẽ không có sự cố nghiêm trọng nào xảy ra.
Sơ đồ sau, trích từ bài báo SPHINCS, đã trừu tượng hóa các cây L-tree WOTS+ (hiển thị chúng dưới dạng chữ ký của cây SPHINCS tiếp theo) và cho thấy đường dẫn duy nhất đến một thông điệp:
Khi ký thông điệp M, trước tiên chúng ta tạo một giá trị băm "ngẫu nhiên" và một số chỉ mục "ngẫu nhiên" cho M. Tôi dùng dấu ngoặc kép vì trong lược đồ chữ ký SPHINCS, mọi thứ đều được tính toán một cách xác định bằng cách sử dụng một hàm giả ngẫu nhiên. Tham số này cho biết cây HORS nào sẽ được sử dụng để ký giá trị băm ngẫu nhiên của M. Đó là lý do tại sao bạn không cần phải nhớ trạng thái: vì số chỉ mục được suy ra một cách xác định từ thông điệp. Việc ký cùng một thông điệp sẽ luôn sử dụng cùng một cây HORS; trong khi việc ký hai thông điệp khác nhau sẽ có xác suất cao sử dụng hai cây HORS khác nhau.
Sê-Ri này đã kết thúc!
Phần bổ sung: Đây là một hình minh họa khác từ bài báo " Cá heo vũ trang ", mà tôi cho rằng rất xuất sắc!
(qua)
