Điểm:1

Bẻ khóa bí mật, n và m bằng tay với vũ lực trao đổi khóa Diffie-Hellman

lá cờ us

Vấn đề: Bạn thấy Michael và Nikita đồng ý về một khóa bí mật bằng cách sử dụng trao đổi khóa Diffie-Hellman. Michael và Nikita chọn $p = 97$$g = 5$. Nikita chọn một số n ngẫu nhiên và nói với Michael rằng $g^n \equiv 3\pmod{97}$, và Michael chọn một số ngẫu nhiên $m$ và nói với Nikita điều đó $g^m â¡ 7 \pmod{97}$. Brute force bẻ khóa mã của họ: Cái gì là chìa khóa bí mật mà Nikita và Michael đồng ý? Là gì $n$? Gì Là $m$?

Đây là cách trao đổi Diffie-Hellman được định nghĩa trong sách giáo khoa:

  1. Michael và Nikita cùng nhau chọn một số nguyên p có 200 chữ số có khả năng là số nguyên tố và chọn một số $g$ với $1 < g < p$.
  2. Nikita bí mật chọn một số nguyên $n$.
  3. Michael bí mật chọn một số nguyên $m$.
  4. Nikita tính toán $g^n \pmod{p}$ trên máy tính cầm tay của cô ấy và nói Michael số kết quả qua điện thoại.
  5. Michael nói với Nikita $g^m \pmod{p}$.
  6. Khóa bí mật được chia sẻ sau đó là $s\equiv g^{nm}\pmod{p}$ mà cả Nikita và Michael đều có thể tính toán.

Suy nghĩ/nỗ lực của tôi:
Nỗ lực 1. Tôi đã cố gắng tìm $n$ thông qua việc giải phương trình mô đun $5^n\equiv 3\pmod{97}.$ Sau đó chúng tôi có $n\equiv \log_53\pmod{97},$ đó không phải là một số nguyên và do đó không có ý nghĩa.
Nỗ lực 2. Tôi đã cố gắng tìm chìa khóa bằng cách sử dụng $g^n$$g^m.$ Tuy nhiên, tôi không thấy một cách nào để tiếp cận $g^{nm}$ từ $g^ng^m = g^{n+m},$ và chúng ta không thể tính toán $(g^n)^m$ hoặc $(g^m)^n$ không biết $m$ hoặc $n,$ mà từ Lần thử 1, tôi không thể tìm thấy số nguyên.

Sẽ đánh giá cao sự giúp đỡ! Cảm ơn bạn

DannyNiu avatar
lá cờ vu
Nỗ lực 1 đang đi đúng hướng. Cần lưu ý rằng, logarit là rời rạc nên hàm logarit số thực không áp dụng ở đây. Nó phải là một số nguyên và như bạn đã nói, nếu không thì nó không có ý nghĩa gì.
BoostMatch avatar
lá cờ us
Làm thế nào bạn có thể giải quyết nó nếu đó là một bản ghi rời rạc?
DannyNiu avatar
lá cờ vu
Brutal-force (thử từng cái một) rất tốt cho những con số nhỏ như vậy trong bài tập của bạn. Tin tặc sẽ sử dụng các kỹ thuật toán học như Pollard-rho hoặc sàng trường số chung (GNFS).
BoostMatch avatar
lá cờ us
@DannyNiu Ồ, do đó mới có "vũ phu" trong bài tập!
kelalaka avatar
lá cờ in
Với một chương trình nhỏ trong khi xây dựng [bảng chỉ mục](https://crypto.stackexchange.com/a/76241/18298), hãy tìm giá trị mong muốn của bạn.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.