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] Trao đổi khóa Diffie-Hellman trên đường cong Elliptic (ECDH)

    Trong giao thức trao đổi khóa Diffie-Hellman trên đường cong elliptic (ECDH), hai bên Alice và Bob thống nhất trước tham số miền công khai: đường cong E:y2≡x3+ax+b(modp)E: y^2\equiv x^3+ax+b\pmod pE:y2≡x3+ax+b(modp) và điểm cơ sở (generator) G=(Gx,Gy)G=(G_x,G_y)G=(Gx​,Gy​).

    Alice chọn khóa bí mật dAd_AdA​, tính khóa công khai A=dA⋅GA=d_A\cdot GA=dA​⋅G và gửi cho Bob. Bob chọn khóa bí mật dBd_BdB​, tính khóa công khai B=dB⋅GB=d_B\cdot GB=dB​⋅G và gửi cho Alice. Khóa bí mật chung (dùng chung) là điểm: S=dA⋅B=dB⋅A=(dAdB)⋅GS=d_A\cdot B=d_B\cdot A=(d_A d_B)\cdot GS=dA​⋅B=dB​⋅A=(dA​dB​)⋅G Quy ước giá trị dùng làm khóa dùng chung cuối cùng là hoành độ xxx của điểm SSS (giả thiết đề bài luôn đảm bảo S≠OS\neq OS=O).

    Cho TTT bộ dữ liệu, mỗi bộ gồm tham số miền và hai khóa bí mật dA,dBd_A,d_BdA​,dB​ (có thể rất lớn), hãy tính hoành độ xxx của SSS cho mỗi bộ. Phép nhân vô hướng cần cài đặt bằng thuật toán Double-and-Add.

    Ví dụ: p=97,a=2,b=3,G=(0,10),dA=7,dB=11⇒xS=49p=97,a=2,b=3,G=(0,10),d_A=7,d_B=11 \Rightarrow x_S=49p=97,a=2,b=3,G=(0,10),dA​=7,dB​=11⇒xS​=49.

    • Định dạng đầu vào:
      • Dòng 1: số nguyên TTT (1≤T≤1001\le T\le 1001≤T≤100).
      • TTT dòng tiếp theo, mỗi dòng 7 số nguyên: "p a b Gx Gy dA dBp\ a\ b\ G_x\ G_y\ d_A\ d_Bp a b Gx​ Gy​ dA​ dB​" (1≤dA,dB≤10181\le d_A,d_B\le 10^{18}1≤dA​,dB​≤1018).
    • Định dạng đầu ra:

      TTT dòng, mỗi dòng in một số nguyên là hoành độ xxx của khóa bí mật chung SSS.

    Ví dụ:

    Đầu vào:

    1
97 2 3 0 10 25 3

    Đầu ra:

    30

    Đầu vào:

    1
97 2 3 0 10 7 11

    Đầu ra:

    49

    Đang tải editor...