Score:1

แคร็กรหัสลับ n และ m ด้วยมือด้วยการแลกเปลี่ยนกุญแจ Diffie-Hellman

ธง us

ปัญหา: คุณเห็นว่า Michael และ Nikita ตกลงเรื่องรหัสลับโดยใช้การแลกเปลี่ยนรหัส Diffie-Hellman ไมเคิลและนิกิต้าเลือก $p = 97$ และ $g = 5$. Nikita เลือกหมายเลขสุ่ม n และบอก Michael ว่า $g^n \equiv 3\pmod{97}$และไมเคิลเลือกหมายเลขสุ่ม $m$ และบอก Nikita นั่น $g^m â¡ 7 \pmod{97}$. กำลังดุร้ายถอดรหัสรหัสของพวกเขา: What is the รหัสลับที่ Nikita และ Michael เห็นด้วย? คืออะไร $n$? อะไร เป็น $m$?

นี่คือวิธีการกำหนดการแลกเปลี่ยน Diffie-Hellman ในตำราเรียน:

  1. Michael และ Nikita ร่วมกันเลือกจำนวนเต็ม 200 หลัก p ที่น่าจะเป็นไปได้ เป็นจำนวนเฉพาะและเลือกหมายเลข $g$ กับ $1 < g < p$.
  2. Nikita แอบเลือกจำนวนเต็ม $n$.
  3. ไมเคิลแอบเลือกจำนวนเต็ม $m$.
  4. Nikita คำนวณ $g^n \pmod{p}$ บนคอมพิวเตอร์พกพาของเธอและบอก Michael หมายเลขผลลัพธ์ทางโทรศัพท์
  5. ไมเคิลบอกนิกิตา $g^m \pmod{p}$.
  6. รหัสลับที่ใช้ร่วมกันคือ $s\equiv g^{nm}\pmod{p}$ ซึ่งทั้ง Nikita และ Michael สามารถคำนวณได้

ความคิด / ความพยายามของฉัน:
ความพยายาม 1. ฉันพยายามค้นหา $n$ ผ่านการแก้สมการโมดูลาร์ $5^n\equiv 3\pmod{97}.$ จากนั้นเราก็มี $n\equiv \log_53\pmod{97},$ ซึ่งไม่ใช่จำนวนเต็มจึงไม่สมเหตุสมผล
ความพยายามที่ 2 ฉันพยายามค้นหารหัสโดยใช้ $g^n$ และ $ก^ม.$ อย่างไรก็ตาม ฉันไม่เห็นหนทางที่จะไปถึง $g^{nm}$ เนื่องจาก $g^ng^m = g^{n+m},$ และเราไม่สามารถคำนวณได้ $(g^n)^m$ หรือ $(g^m)^n$ โดยไม่รู้ตัว $m$ หรือ $n,$ ซึ่งจากความพยายาม 1 ฉันไม่พบจำนวนเต็มสำหรับ

ขอขอบคุณสำหรับความช่วยเหลือ! ขอขอบคุณ

DannyNiu avatar
vu flag
ความพยายามที่ 1 มาถูกทางแล้ว ควรสังเกตว่า ลอการิทึมเป็นแบบไม่ต่อเนื่อง ดังนั้นฟังก์ชันบันทึกจำนวนจริงจึงใช้ไม่ได้ที่นี่ มันควรเป็นจำนวนเต็ม และอย่างที่คุณพูด มิฉะนั้นก็ไม่สมเหตุสมผล
BoostMatch avatar
us flag
คุณจะแก้ไขได้อย่างไรหากเป็นบันทึกที่ไม่ต่อเนื่อง
DannyNiu avatar
vu flag
การบังคับอย่างโหดเหี้ยม (พยายามทีละคน) นั้นดีสำหรับจำนวนน้อยในการออกกำลังกายของคุณ แฮ็กเกอร์จะใช้เทคนิคทางคณิตศาสตร์ เช่น Pollard-rho หรือ General Number Field Sieve (GNFS)
BoostMatch avatar
us flag
@DannyNiu โอ้เพราะฉะนั้น "กำลังดุร้าย" ในการออกกำลังกาย!
kelalaka avatar
in flag
ด้วยโปรแกรมขนาดเล็กขณะสร้าง [ตารางดัชนี](https://crypto.stackexchange.com/a/76241/18298) ค้นหาค่าที่คุณต้องการ

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา