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] RSA - Tìm khóa bí mật d

    RSA - Tìm khóa bí mật d

    Khóa bí mật (d) là nghịch đảo modulo của (e) theo (\varphi(n)):

    d≡e−1(modφ(n))⟺e⋅d≡1(modφ(n))d \equiv e^{-1} \pmod{\varphi(n)} \quad\Longleftrightarrow\quad e \cdot d \equiv 1 \pmod{\varphi(n)}d≡e−1(modφ(n))⟺e⋅d≡1(modφ(n))

    Cho (e) và (\varphi(n)) (đảm bảo (\gcd(e, \varphi) = 1)), hãy tìm (d) nhỏ nhất dương thỏa mãn.

    Ví dụ

    Input:

    7 20

    Output:

    3

    Vì (7 \times 3 = 21 \equiv 1 \pmod{20}).

    Gợi ý: dùng thuật toán Euclid mở rộng hoặc pow(e, -1, phi).

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

      Một dòng gồm hai số nguyên (e) và (\varphi).

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

      (1 < e < \varphi \le 10^{18}), (\gcd(e, \varphi) = 1)

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

      In ra (d) nhỏ nhất dương sao cho (e \cdot d \equiv 1 \pmod{\varphi}).

    Ví dụ:

    Đầu vào:

    7 20

    Đầu ra:

    3

    Giải thích:

    7*3=21=1 mod 20 nên d=3

    Đang tải editor...