Bài tập | NEU OJ

Chữ ký Lamport là sơ đồ chữ ký một lần dựa hoàn toàn trên hàm băm, được xem là an toàn hậu lượng tử vì không dựa trên các bài toán số học (phân tích số nguyên, logarit rời rạc) mà máy tính lượng tử có thể giải nhanh bằng thuật toán Shor.

Với thông điệp có $n$ bit, khoá bí mật gồm $n$ cặp chuỗi ngẫu nhiên $(sk_{i,0}, sk_{i,1})$ , $i = 1, \dots, n$ . Khoá công khai tương ứng là $(pk_{i,0}, pk_{i,1})$ với $pk_{i,b} = \text{SHA256}(sk_{i,b})$ (băm chuỗi $sk_{i,b}$ mã hoá UTF-8, kết quả biểu diễn dạng hex thường — 64 ký tự).

Cho khoá bí mật, hãy sinh khoá công khai tương ứng.

Ví dụ

Input:

2
abc def
hello world

Output:

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad cb8379ac2098aa165029e3938a51da0bcecfc008fd6795f401178647f96c5b34
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 486ea46224d1bb4fb680f34f7c9ad96a8f24ec88be73ea8e5a6c65260e9cb8a7

(Dòng 1 là băm SHA256 của abc và def; dòng 2 là băm của hello và world.)

Định dạng đầu vào:
Dòng đầu tiên chứa số nguyên $n$ ( $n \ge 0$ ) — số cặp khoá bí mật. $n$ dòng tiếp theo, mỗi dòng chứa hai chuỗi $sk_{i,0}$ và $sk_{i,1}$ (không chứa khoảng trắng), cách nhau bởi một dấu cách.
Định dạng đầu ra:
In ra $n$ dòng, dòng thứ $i$ gồm hai chuỗi hex (viết thường, 64 ký tự mỗi chuỗi) là $pk_{i,0}$ và $pk_{i,1}$ , cách nhau bởi một dấu cách.

solution

Đề bài: [An toàn thông tin] Sinh khoá công khai Lamport