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] Mã hóa đồng cấu cộng – Gộp bản mã lũy thừa

    Đồng cấu cộng với mã hóa lũy thừa

    Xét lược đồ mã hóa "trong số mũ": E(m)=gm mod pE(m) = g^{m} \bmod pE(m)=gmmodp. Lược đồ này đồng cấu cộng vì:

    E(m1)⋅E(m2)=gm1gm2=gm1+m2 mod p=E(m1+m2)E(m_1)\cdot E(m_2) = g^{m_1} g^{m_2} = g^{m_1 + m_2} \bmod p = E(m_1 + m_2)E(m1​)⋅E(m2​)=gm1​gm2​=gm1​+m2​modp=E(m1​+m2​)

    Cho nnn bản mã ci=gmic_i = g^{m_i}ci​=gmi​, hãy tính bản mã gộp C=∏ci mod pC = \prod c_i \bmod pC=∏ci​modp và phục hồi tổng m=∑mim = \sum m_im=∑mi​ bằng logarit rời rạc (tìm kiếm).

    Ví dụ

    p=101,g=2p=101, g=2p=101,g=2, các bản mã E(3)=8,E(5)=32E(3)=8, E(5)=32E(3)=8,E(5)=32 cho C=8⋅32=256≡54C = 8\cdot32 = 256 \equiv 54C=8⋅32=256≡54, và m=8m = 8m=8.

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

      Dòng 1: p g n. Dòng 2: n bản mã cic_ici​.

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

      ppp nguyên tố nhỏ (≤5000\le 5000≤5000), ggg là căn nguyên thủy, ∑mi<p\sum m_i < p∑mi​<p.

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

      Dòng 1: bản mã gộp CCC. Dòng 2: tổng m=∑mim = \sum m_im=∑mi​.

    Ví dụ:

    Đầu vào:

    101 2 2
8 32

    Đầu ra:

    54
8

    Giải thích:

    $8 \cdot 32 = 256 \equiv 54 \pmod{101}$; và $2^8 = 256 \equiv 54$, nên tổng số mũ $m=3+5=8$.

    Đang tải editor...