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] Xác minh chữ ký số RSA (giáo dục)

    Trong lược đồ chữ ký số RSA phiên bản giáo dục (không dùng padding), khóa công khai là cặp (n,e)(n, e)(n,e), khóa bí mật là ddd (với e⋅d≡1(modφ(n))e \cdot d \equiv 1 \pmod{\varphi(n)}e⋅d≡1(modφ(n))). Người ký tạo chữ ký cho giá trị băm thông điệp mmm (biểu diễn dưới dạng số nguyên, 0≤m<n0 \le m < n0≤m<n) bằng:

    s=md mod ns = m^d \bmod ns=mdmodn

    Người xác thực, chỉ biết khóa công khai (n,e)(n,e)(n,e), kiểm tra chữ ký sss có hợp lệ với thông điệp mmm hay không bằng cách kiểm tra:

    se mod n=?m mod ns^e \bmod n \stackrel{?}{=} m \bmod nsemodn=?mmodn

    Cho bốn số nguyên n,e,m,sn, e, m, sn,e,m,s (đều không âm, nnn có thể rất lớn, tới hàng trăm chữ số), hãy xác định chữ ký có hợp lệ hay không.

    Ví dụ: n=3233, e=17, m=65, s=588n=3233,\ e=17,\ m=65,\ s=588n=3233, e=17, m=65, s=588. Vì 58817 mod 3233=65588^{17} \bmod 3233 = 6558817mod3233=65 nên chữ ký hợp lệ, in ra VALID.

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

      Một dòng chứa 4 số nguyên không âm, cách nhau bởi khoảng trắng: n e m s.

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

      In VALID nếu se mod n=m mod ns^e \bmod n = m \bmod nsemodn=mmodn, ngược lại in INVALID.

    Ví dụ:

    Đầu vào:

    3233 17 65 588

    Đầu ra:

    VALID

    Đầu vào:

    3233 17 65 589

    Đầu ra:

    INVALID

    Đang tải editor...