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] ElGamal – Đồng cấu nhân

    Đồng cấu nhân của ElGamal

    Mã ElGamal với khóa công khai y=gx mod py=g^{x} \bmod py=gxmodp: bản mã của mmm là (c1,c2)=(gk,  m yk)(c_1,c_2)=(g^{k},\; m\,y^{k})(c1​,c2​)=(gk,myk). Nhân từng thành phần hai bản mã:

    (c1ac1b,  c2ac2b)=(gka+kb,  mamb yka+kb)(c_{1a}c_{1b},\; c_{2a}c_{2b}) = (g^{k_a+k_b},\; m_a m_b\, y^{k_a+k_b})(c1a​c1b​,c2a​c2b​)=(gka​+kb​,ma​mb​yka​+kb​)

    là bản mã của tích mambm_a m_bma​mb​. Giải mã: m=c2⋅(c1x)−1 mod pm = c_2 \cdot (c_1^{x})^{-1} \bmod pm=c2​⋅(c1x​)−1modp.

    Cho khóa bí mật xxx và hai bản mã, hãy tính bản mã tích và giải mã ra mamb mod pm_a m_b \bmod pma​mb​modp.

    Ví dụ

    ma=5,mb=7m_a=5, m_b=7ma​=5,mb​=7 cho ra tích 353535.

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

      Dòng 1: p g x. Dòng 2: c1a c2a. Dòng 3: c1b c2b.

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

      ppp nguyên tố, xxx là khóa bí mật, mọi thành phần trong [0,p)[0,p)[0,p).

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

      Dòng 1: bản mã tích c1 c2. Dòng 2: bản rõ tích mamb mod pm_a m_b \bmod pma​mb​modp.

    Ví dụ:

    Đầu vào:

    1019 2 17
10 854
200 767

    Đầu ra:

    981 820
35

    Giải thích:

    Nhân từng thành phần rồi giải mã cho tích $5 \times 7 = 35 \bmod 1019$.

    Đang tải editor...