Các lượt nộp

Danh sách bài

Báo lỗi

solution

Đề bài: [An toàn thông tin] Khôi phục trạng thái đầu LFSR từ keystream

Khôi phục trạng thái LFSR

Biết cấu hình taps của một LFSR Fibonacci bậc $n$ và quan sát $k$ bit keystream. Hãy tìm trạng thái đầu $s_0 \dots s_{n-1}$ sinh ra đúng $k$ bit đó.

Duyệt tất cả $2^n$ trạng thái, in trạng thái đầu tiên khớp keystream (coi $s_0$ là bit thấp nhất của số nguyên, tăng dần từ 0). Nếu không có, in -1.

Ví dụ

taps $1\,0\,1$ , keystream 0011101 → trạng thái 0 0 1.

Định dạng đầu vào:
Dòng 1: $n$ . Dòng 2: taps. Dòng 3: $k$ . Dòng 4: $k$ bit keystream.
Ràng buộc đầu vào:
$1 \le n \le 18$ , $1 \le k \le 100000$ .
Định dạng đầu ra:
Trạng thái đầu ( $n$ bit cách nhau bởi dấu cách) hoặc -1.

Ví dụ:

Đầu vào:

3
1 0 1
7
0 0 1 1 1 0 1

Đầu ra:

0 0 1

Giải thích:

Trạng thái 001 sinh ra 0011101 nên đáp án là 0 0 1.

Đang tải editor...