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] Mã hoá NTRU thu nhỏ (toy NTRU)

    NTRU là một trong những sơ đồ mật mã dựa trên lưới (lattice-based) sớm nhất được đề xuất để chống lại máy tính lượng tử, hoạt động trên vành đa thức Rq=Zq[x]/(xn−1)R_q = \mathbb{Z}_q[x]/(x^n - 1)Rq​=Zq​[x]/(xn−1).

    Cho bộ tham số n,q,pn, q, pn,q,p, đa thức khoá công khai h=(h0,…,hn−1)h = (h_0, \dots, h_{n-1})h=(h0​,…,hn−1​), đa thức ngẫu nhiên r=(r0,…,rn−1)r = (r_0, \dots, r_{n-1})r=(r0​,…,rn−1​) và đa thức thông điệp m=(m0,…,mn−1)m = (m_0, \dots, m_{n-1})m=(m0​,…,mn−1​) (các hệ số của r,mr, mr,m thường nhỏ, ví dụ ∈{−1,0,1}\in \{-1, 0, 1\}∈{−1,0,1}). Bản mã được tính theo công thức mã hoá NTRU thu gọn:

    c=(p⋅r⋅h+m) mod qc = (p \cdot r \cdot h + m) \bmod qc=(p⋅r⋅h+m)modq

    trong đó phép nhân đa thức là tích chập vòng (cyclic convolution) theo modulo xn−1x^n - 1xn−1: hệ số bậc kkk của tích a⋅ba \cdot ba⋅b là ∑(i+j) mod n=kaibj\sum_{(i+j) \bmod n = k} a_i b_j∑(i+j)modn=k​ai​bj​. Kết quả mỗi hệ số của ccc được đưa về đại diện không âm trong khoảng [0,q−1][0, q-1][0,q−1].

    Cho n,q,p,h,r,mn, q, p, h, r, mn,q,p,h,r,m, hãy tính đa thức bản mã ccc.

    Ví dụ

    Input:

    4 32 3
5 1 0 2
1 0 -1 0
1 0 0 -1

    Output:

    16 29 17 2
    • Định dạng đầu vào:

      Dòng 1: ba số nguyên n,q,pn, q, pn,q,p (1≤n≤2001 \le n \le 2001≤n≤200, 2≤q2 \le q2≤q). Dòng 2: nnn số nguyên — các hệ số h0,…,hn−1h_0, \dots, h_{n-1}h0​,…,hn−1​. Dòng 3: nnn số nguyên — các hệ số r0,…,rn−1r_0, \dots, r_{n-1}r0​,…,rn−1​ (có thể âm). Dòng 4: nnn số nguyên — các hệ số m0,…,mn−1m_0, \dots, m_{n-1}m0​,…,mn−1​ (có thể âm).

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

      In ra nnn số nguyên c0,…,cn−1c_0, \dots, c_{n-1}c0​,…,cn−1​ trên một dòng, cách nhau bởi dấu cách, mỗi số nằm trong [0,q−1][0, q-1][0,q−1].

    Ví dụ:

    Đầu vào:

    1 16 3
7
1
1

    Đầu ra:

    6

    Đầu vào:

    4 32 3
5 1 0 2
1 0 -1 0
1 0 0 -1

    Đầu ra:

    16 29 17 2

    Đang tải editor...