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] Định danh Schnorr (chứng minh không tiết lộ)

    Giao thức định danh Schnorr

    Người chứng minh biết khóa bí mật xxx với khóa công khai y=gx mod py=g^{x} \bmod py=gxmodp (nhóm bậc qqq). Bằng chứng gồm:

    • Cam kết: r=gk mod pr = g^{k} \bmod pr=gkmodp
    • Thử thách: eee
    • Đáp: s=(k+e⋅x) mod qs = (k + e\cdot x) \bmod qs=(k+e⋅x)modq

    Người xác minh kiểm tra:

    gs=?r⋅ye(modp)g^{s} \stackrel{?}{=} r \cdot y^{e} \pmod pgs=?r⋅ye(modp)

    Đúng vì gk+ex=gk(gx)e=r yeg^{k+ex} = g^{k}(g^{x})^{e} = r\,y^{e}gk+ex=gk(gx)e=rye. Đây là chứng minh không tiết lộ tri thức (ZK).

    Ví dụ

    Bộ (r,e,s)(r,e,s)(r,e,s) hợp lệ thì in VALID.

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

      Một dòng: p q g y r e s.

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

      p=2q+1p=2q+1p=2q+1 nguyên tố an toàn, ggg bậc qqq, 0≤e,s<q0 \le e,s < q0≤e,s<q.

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

      VALID nếu gs≡r yeg^{s} \equiv r\,y^{e}gs≡rye, ngược lại INVALID.

    Ví dụ:

    Đầu vào:

    23 11 2 9 16 3 8

    Đầu ra:

    VALID

    Giải thích:

    Với $x=5,k=4,e=3$: $s=(4+15)\bmod 11=8$; kiểm tra $g^{8} \equiv r\,y^{3} \pmod{23}$ đúng nên `VALID`.

    Đang tải editor...