ปัญหาของดิฟฟีเฮลแมน

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

ปัญหาของดิฟฟีเฮลแมน (อังกฤษ: Diffie–Hellman problem) เป็นปัญหาเชิงคณิตศาสตร์ที่ออกแบบโดยวิทฟิลด์ ดิฟฟี และมาร์ติน เฮลแมน ว่าด้วยวิทยาการเข้ารหัสลับแบบสมมาตร แรงจูงใจสำหรับปัญหานี้มาจากว่า การเข้ารหัสลับในหลายรูปแบบจะใช้ฟังก์ชันทางเดียว ซึ่งเป็นกระบวนการทางคณิตศาสตร์ที่สามารถประมวลผลได้อย่างรวดเร็วแค่ในทิศทางเดียว กล่าวคือระบบเหล่านี้จะสามารถเข้ารหัสข้อมูลอิเล็กทรอนิกส์ได้ง่าย แต่การถอดรหัสนั้นจะเป็นไปได้ยาก ปัญหาดังกล่าวมีดังต่อไปนี้

กำหนดให้ เป็นเซตของสมการพีชคณิต แล้วให้ และ แล้วถ้ารู้ค่าของ กับ จงหาค่าของ

ยกตัวอย่างเช่น ในการสลับกุญแจดิฟฟีเฮลแมน หากผู้ส่งมีกุญแจส่วนตัว ผู้รับมีกุญแจส่วนตัว และทั้งคู่มีกุญแจสาธารณะ กับ นักดักฟังจะสามารถเข้าถึงค่าของ กับ ได้เท่านั้น ผู้ส่งและผู้รับสามารถหาค่าของ ได้ง่าย แต่นักดักฟังจะหาค่าได้ยากเนื่องจากในความเป็นจริงจะต้องใช้เวลานานมากในการหาค่า และ จากค่า และ

ความซับซ้อนในการคำนวณ[แก้]

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

แหล่งข้อมูลอื่น[แก้]

  • B. den Boer, Diffie–Hellman is as strong as discrete log for certain primes in Advances in Cryptology – CRYPTO 88, Lecture Notes in Computer Science 403, Springer, p. 530, 1988.
  • U. M. Maurer and S. Wolf, Diffie–Hellman oracle in Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 268–282, 1996.
  • D. Boneh and R. J. Lipton, Algorithms for black-box fields and their application to cryptotography in Advances in Cryptology – CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 283–297, 1996.
  • A. Muzereau, N. P. Smart and F. Vercauteran, The equivalence between the DHP and DLP for ellipti curves used in practical applications, LMS J. Comput. Math., 7, pp. 50–72, 2004. See [www.lms.ac.uk].
  • Biham, Eli; Boneh, Dan; Reingold, Omer (1999). "Breaking generalized Diffie–Hellman modulo a composite is no easier than factoring". Information Processing Letters. 70 (2): 83–87. CiteSeerX 10.1.1.39.110. doi:10.1016/S0020-0190(99)00047-2.