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ừ modulus nhỏ

    Hệ mật RSA an toàn khi modulus n=p×qn = p \times qn=p×q (tích của hai số nguyên tố lớn, phân biệt) khó bị phân tích thành thừa số. Tuy nhiên nếu p,qp, qp,q đủ nhỏ, kẻ tấn công có thể phân tích nnn bằng chia thử, từ đó tính φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1)φ(n)=(p−1)(q−1), suy ra số mũ bí mật ddd là nghịch đảo của số mũ công khai eee theo modulo φ(n)\varphi(n)φ(n), và giải mã bản mã ccc thành bản rõ m=cd mod nm = c^d \bmod nm=cdmodn.

    Cho nnn (là tích của hai số nguyên tố phân biệt), số mũ công khai eee và bản mã ccc, hãy tìm bản rõ mmm.

    Ví dụ: n=3233=61×53n = 3233 = 61 \times 53n=3233=61×53, φ(n)=3120\varphi(n) = 3120φ(n)=3120, e=17e = 17e=17 (với gcd⁡(17,3120)=1\gcd(17, 3120)=1gcd(17,3120)=1), d=2753d = 2753d=2753. Với c=2790c = 2790c=2790, bản rõ là m=27902753 mod 3233=65m = 2790^{2753} \bmod 3233 = 65m=27902753mod3233=65.

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

      Một dòng chứa ba số nguyên nnn, eee, ccc cách nhau bởi khoảng trắng (n≤1012n \le 10^{12}n≤1012 là tích của hai số nguyên tố phân biệt mỗi số ≤106\le 10^6≤106; 1≤e<φ(n)1 \le e < \varphi(n)1≤e<φ(n) với gcd⁡(e,φ(n))=1\gcd(e, \varphi(n)) = 1gcd(e,φ(n))=1; 0≤c<n0 \le c < n0≤c<n).

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

      In ra bản rõ mmm (0≤m<n0 \le m < n0≤m<n).

    Ví dụ:

    Đầu vào:

    77 7 71

    Đầu ra:

    15

    Đầu vào:

    6 1 5

    Đầu ra:

    5

    Đang tải editor...