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] Giao thức OTP chuỗi băm một chiều (S/KEY)

    Giao thức S/KEY dùng xích băm một chiều để xác thực nhiều lượt đăng nhập mà không cần truyền lại mật khẩu gốc qua mạng. Xuất phát từ một seed (chuỗi ASCII), ta định nghĩa x0=x_0 = x0​= seed (mã hoá UTF-8 thành byte) và

    xi=SHA-256(xi−1),i=1,…,nx_i = \text{SHA-256}(x_{i-1}), \quad i=1,\ldots,nxi​=SHA-256(xi−1​),i=1,…,n

    (băm trên chuỗi byte thô, giống bài "Xích băm Lamport"). Máy chủ lưu thanh ghi xác thực ban đầu R=xnR = x_nR=xn​ (dạng hex).

    Người dùng thực hiện lần lượt mmm lượt đăng nhập, đánh số k=1,2,…,mk=1,2,\ldots,mk=1,2,…,m. Ở lượt thứ kkk, người dùng gửi lên máy chủ một giá trị yky_kyk​ (chuỗi hex, cho trước ở input — có thể đúng hoặc sai). Máy chủ xác thực bằng cách kiểm tra

    SHA-256(yk)=?R\text{SHA-256}(y_k) \stackrel{?}{=} RSHA-256(yk​)=?R

    (so sánh trên bytes: giải mã yky_kyk​ từ hex thành byte trước khi băm). Nếu khớp: in OK, đồng thời cập nhật R←ykR \leftarrow y_kR←yk​ (chuẩn hoá về chữ thường) để dùng làm chốt so sánh cho lượt xác thực kế tiếp. Nếu không khớp: in FAIL, và RRR giữ nguyên không đổi (không cập nhật).

    Lưu ý: về bản chất mỗi yky_kyk​ hợp lệ chính là giá trị xxx ở bước liền trước chốt hiện tại trong xích băm (ví dụ lượt đăng nhập đầu tiên hợp lệ phải gửi y1=xn−1y_1 = x_{n-1}y1​=xn−1​), nhưng bạn chỉ cần lập trình đúng quy tắc kiểm tra và cập nhật RRR ở trên, không cần biết trước thứ tự sử dụng của xích.

    Cho seed, nnn và mmm giá trị y1,…,ymy_1,\ldots,y_my1​,…,ym​ theo đúng thứ tự, hãy in ra kết quả (OK/FAIL) của từng lượt đăng nhập.

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

      Gồm 3+m3+m3+m dòng:

      • Dòng 1: seed — chuỗi ASCII không chứa khoảng trắng, độ dài từ 1 đến 200 ký tự.
      • Dòng 2: số nguyên nnn (1≤n≤20001 \le n \le 20001≤n≤2000).
      • Dòng 3: số nguyên mmm (0≤m≤10000 \le m \le 10000≤m≤1000).
      • mmm dòng tiếp theo, mỗi dòng là một chuỗi hex yky_kyk​ (độ dài chẵn, có thể không phải 64 ký tự, chữ hoa hoặc thường).
    • Định dạng đầu ra:

      mmm dòng, mỗi dòng là OK hoặc FAIL cho lượt đăng nhập tương ứng theo đúng thứ tự. Nếu m=0m=0m=0 thì không in gì.

    Ví dụ:

    Đầu vào:

    s28seed
3
4
a1cc219803a808ee54fa4c77b6a327a5f2ac4be41680b0b2ca39534961ada057
6f353e0228f6a7e798ce585a0820077098ccb4efb82adc9463205c264aa121ca
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
73323873656564

    Đầu ra:

    OK
OK
FAIL
OK

    Đầu vào:

    anything
5
0

    Đầu ra:

    Đang tải editor...