Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Merkle: xác thực đường dẫn (authentication path)

    Người xác minh chữ ký Merkle/XMSS phải kiểm tra đường dẫn xác thực: từ một lá và các nút anh-em (siblings) dọc đường lên, tái tạo gốc và so với gốc công khai.

    Với chỉ số lá idx, ở mỗi mức xét bit tương ứng của idx: bit 000 ⇒ nút hiện tại là con trái, bit 111 ⇒ con phải. Hàm gộp:

    h(traˊi,phải)=(traˊi⋅1000003+phải) mod M.h(\text{trái},\text{phải}) = (\text{trái}\cdot 1000003 + \text{phải}) \bmod M.h(traˊi,phải)=(traˊi⋅1000003+phải)modM.

    In VALID nếu gốc tái tạo khớp root, ngược lại INVALID.

    • Định dạng đầu vào:

      Dòng 1: h idx M. Dòng 2: giá trị lá. Dòng 3: gốc công khai root. Dòng 4: h giá trị anh-em (từ dưới lên).

    • Ràng buộc đầu vào:

      1≤h≤321 \le h \le 321≤h≤32; 0≤idx<2h0 \le idx < 2^h0≤idx<2h; 2≤M≤109+72 \le M \le 10^9+72≤M≤109+7.

    • Định dạng đầu ra:

      Một dòng: VALID hoặc INVALID.

    Ví dụ:

    Đầu vào:

    1 0 1000000007
1
1000005
2

    Đầu ra:

    VALID

    Giải thích:

    idx=0 ⇒ lá là con trái: (1·1000003+2)=1000005 = root ⇒ VALID.

    Đang tải editor...