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] Giải mã RSA: tìm khóa bí mật và khôi phục bản rõ

    Cho hai số nguyên tố p,qp, qp,q, số mũ công khai eee và bản mã ccc của một hệ RSA. Đặt n=pqn = pqn=pq, ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)ϕ(n)=(p−1)(q−1) (giả thiết gcd⁡(e,ϕ(n))=1\gcd(e, \phi(n)) = 1gcd(e,ϕ(n))=1). Hãy:

    1. Tìm khóa bí mật ddd là nghịch đảo modulo của eee theo ϕ(n)\phi(n)ϕ(n) (tức 1≤d<ϕ(n)1 \le d < \phi(n)1≤d<ϕ(n), e⋅d≡1(modϕ(n))e \cdot d \equiv 1 \pmod{\phi(n)}e⋅d≡1(modϕ(n))), sử dụng thuật toán Euclid mở rộng.
    2. Giải mã để khôi phục bản rõ m=cd mod nm = c^d \bmod nm=cdmodn.

    In ra giá trị mmm.

    Ví dụ kinh điển: p=61,q=53,e=17,c=2790⇒n=3233,ϕ(n)=3120,d=2753p=61, q=53, e=17, c=2790 \Rightarrow n=3233, \phi(n)=3120, d=2753p=61,q=53,e=17,c=2790⇒n=3233,ϕ(n)=3120,d=2753, và m=27902753 mod 3233=65m = 2790^{2753} \bmod 3233 = 65m=27902753mod3233=65.

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

      Một dòng chứa 4 số nguyên p q e cp\ q\ e\ cp q e c cách nhau bởi dấu cách (p,qp, qp,q nguyên tố, 1≤e<ϕ(n)1 \le e < \phi(n)1≤e<ϕ(n), gcd⁡(e,ϕ(n))=1\gcd(e,\phi(n))=1gcd(e,ϕ(n))=1, 0≤c<n=pq0 \le c < n = pq0≤c<n=pq).

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

      Một dòng chứa số nguyên mmm là bản rõ đã giải mã.

    Ví dụ:

    Đầu vào:

    61 53 17 2790

    Đầu ra:

    65

    Đầu vào:

    17 11 7 186

    Đầu ra:

    186

    Đang tải editor...