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] Galois LFSR: sinh chuỗi bit

    Galois LFSR

    Khác với Fibonacci LFSR (XOR các tap rồi đưa vào cuối), Galois LFSR dịch thanh ghi và XOR bit vừa xuất ra vào các vị trí có tap. Mô hình dùng ở đây:

    Trạng thái s0…sn−1s_0 \dots s_{n-1}s0​…sn−1​, s0s_0s0​ là bit xuất ra. Mỗi bước:

    1. out = s[0].
    2. Dịch trái thành s1…sn−1 outs_1 \dots s_{n-1}\, outs1​…sn−1​out (đưa out vào cuối).
    3. Nếu out == 1: với mỗi iii có ci+1=1c_{i+1}=1ci+1​=1, đảo bit ở vị trí iii (XOR 1).

    Sinh kkk bit keystream.

    Ví dụ

    n=3n=3n=3, taps 1 0 11\,0\,1101, trạng thái 0 0 10\,0\,1001, k=8k=8k=8 → một chuỗi xác định.

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

      Dòng 1: nnn. Dòng 2: taps c1…cnc_1 \dots c_nc1​…cn​. Dòng 3: trạng thái đầu. Dòng 4: kkk.

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

      1≤n≤161 \le n \le 161≤n≤16, 1≤k≤1000001 \le k \le 1000001≤k≤100000.

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

      Một dòng kkk bit keystream.

    Ví dụ:

    Đầu vào:

    3
1 0 1
0 0 1
8

    Đầu ra:

    00111111

    Giải thích:

    Galois LFSR: xuất s0=1 rồi dịch và XOR taps vào trạng thái.

    Đang tải editor...