The Breakthrough

แปลโดย : Claude 3 Opus (Pro)

The Breakthrough

It was Hellman who finally made the pieces click.

Although his solution didn’t tick all the boxes he and Diffie were aiming for—there was no digital authentication—Hellman came up with a scheme that would let two parties communicate privately, without the need to share an encryption key in person beforehand. Similar to Merkle’s puzzle scheme, the idea behind the Diffie-Hellman key exchange (as this solution would come to be known) is that Alice and Bob can settle on a shared secret: essentially, a symmetric encryption key that only they know.

To generate this shared secret, Alice and Bob would use key pairs, the idea first suggested by Diffie. Their private keys would essentially just be very big random numbers—so big that not even the fastest supercomputers would be able to guess them in a million years. Each public key, then, could be derived from a private key through a one-way function. Calculating the public key from the private key would be easy, while calculating the private key from the public key would basically be impossible.

To produce the shared secret, then, both Alice and Bob would each multiply their own private key with the other person’s public key. This should give both of them the same result: the shared secret.

This works because, in both cases, the shared secret is essentially a combination of both private keys put through a one-way function once. When Alice multiplies her private key with Bob’s public key, the one-way function is already “embedded” in Bob’s public key, and the opposite is true when Bob multiplies his private key with Alice’s public key. Although Alice and Bob perform the math in a different “order,” the outcome has to be the same.

(As a simplified analogy, this is similar to how the outcomes of 2 x (3 x 5) and 3 x (2 x 5) are both 30. In this analogy, 2 is Alice’s private key, 3 is Bob’s private key, x 5 is the one-way function, and 30 is the shared secret.)

Meanwhile, no one else would be able to generate Alice and Bob’s shared secret. After all, if the two public keys are multiplied, the result is essentially a combination of both private keys, but put through a one-way function twice—one time too many. (Continuing the analogy, this would compare to (2 x 5) x (3 x 5), which would result in 150 instead of 30.)

Generating the shared secret, therefore, requires access to either Alice’s or Bob’s private key. As long as they’d keep these a secret, the two of them could enjoy mathematically guaranteed private communication.

Defying an entire body of knowledge, the Diffie-Hellman key exchange could realize something that was long thought impossible. With that, the technique had the potential to dramatically transform the entire field of cryptography, and the two unconventional cryptographers were well aware of this fact when they submitted their second paper, “New Directions in Cryptography,” to IEEE Transactions on Information Theory—a prestigious scientific journal published by a professional association for electrical engineering.

“We stand today on the brink of a revolution in cryptography,” Diffie and Hellmann announced in the paper, published in the journal’s November 1976 edition. Foreseeing that their breakthrough would mark the beginning of a major upheaval, they continued: “theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science.”

Indeed, it soon became evident that Diffie and Hellman had opened the floodgates. A new generation of cryptographers was about to introduce a cascade of innovation into the world of crypto.

การก้าวข้ามขีดจำกัด

เฮลแมนเป็นคนที่ทำให้ชิ้นส่วนต่างๆ ลงล็อกในที่สุด

แม้ว่าวิธีแก้ปัญหาของเขาจะไม่ตรงกับทุกข้อที่เขาและดิฟฟี่ตั้งเป้าไว้ - ไม่มีการรับรองความถูกต้องแบบดิจิทัล - แต่เฮลแมนก็คิดค้นรูปแบบที่จะช่วยให้สองฝ่ายสื่อสารกันเป็นส่วนตัวได้ โดยไม่จำเป็นต้องแบ่งปันกุญแจเข้ารหัสด้วยตนเองก่อน คล้ายกับรูปแบบปริศนาของเมอร์เคิล ความคิดเบื้องหลัง Diffie-Hellman key exchange (ชื่อที่วิธีแก้ปัญหานี้จะเป็นที่รู้จัก) คือ อลิซและบ๊อบสามารถตกลงใช้ความลับร่วมกัน: โดยพื้นฐานแล้วคือกุญแจเข้ารหัสแบบสมมาตรที่มีเพียงพวกเขาเท่านั้นที่รู้

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

เพื่อสร้างความลับร่วมกัน อลิซและบ๊อบแต่ละคนจะคูณกุญแจส่วนตัวของตนเองกับกุญแจสาธารณะของอีกฝ่าย ผลลัพธ์ที่ได้ควรเหมือนกันทั้งคู่: คือความลับร่วมกัน

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

(เป็นการเปรียบเทียบอย่างง่าย สิ่งนี้คล้ายกับว่าทำไมผลลัพธ์ของ 2 x (3 x 5) และ 3 x (2 x 5) จึงเท่ากับ 30 ทั้งคู่ ในการเปรียบเทียบนี้ 2 คือกุญแจส่วนตัวของอลิซ 3 คือกุญแจส่วนตัวของบ๊อบ x 5 คือฟังก์ชันทางเดียว และ 30 คือความลับร่วมกัน)

ในขณะเดียวกัน คนอื่นจะไม่สามารถสร้างความลับร่วมกันของอลิซและบ๊อบได้ ท้ายที่สุดแล้ว หากนำกุญแจสาธารณะทั้งสองมาคูณกัน ผลลัพธ์โดยพื้นฐานแล้วคือการรวมกุญแจส่วนตัวทั้งสอง แต่ผ่านฟังก์ชันทางเดียวสองครั้ง - มากเกินไปหนึ่งครั้ง (สานต่อการเปรียบเทียบ สิ่งนี้จะเทียบได้กับ (2 x 5) x (3 x 5) ซึ่งจะได้ผลลัพธ์เป็น 150 แทนที่จะเป็น 30)

ดังนั้น การสร้างความลับร่วมกันจำเป็นต้องเข้าถึงกุญแจส่วนตัวของอลิซหรือบ๊อบ ตราบใดที่พวกเขาเก็บสิ่งเหล่านี้เป็นความลับ ทั้งสองก็จะได้รับการสื่อสารส่วนตัวที่รับประกันทางคณิตศาสตร์

ท้าทายองค์ความรู้ทั้งหมด Diffie-Hellman key exchange สามารถทำในสิ่งที่เคยคิดว่าเป็นไปไม่ได้มานาน ด้วยเหตุนี้ เทคนิคนี้จึงมีศักยภาพที่จะเปลี่ยนแปลงทั้งสาขาวิทยาการรหัสลับอย่างมาก และนักวิทยาการรหัสลับที่ไม่เหมือนใครทั้งสองตระหนักถึงข้อเท็จจริงนี้เป็นอย่างดีเมื่อพวกเขาส่งบทความที่สองของตน "New Directions in Cryptography" ไปยัง IEEE Transactions on Information Theory - วารสารวิทยาศาสตร์ชั้นนำที่ตีพิมพ์โดยสมาคมวิชาชีพวิศวกรรมไฟฟ้า

"วันนี้เรายืนอยู่ที่ขอบของการปฏิวัติในวิทยาการรหัสลับ" ดิฟฟี่และเฮลแมนประกาศในบทความที่ตีพิมพ์ในฉบับเดือนพฤศจิกายน 1976 ของวารสาร คาดการณ์ว่าความก้าวหน้าของพวกเขาจะเป็นจุดเริ่มต้นของการเปลี่ยนแปลงครั้งใหญ่ พวกเขาเสริมว่า "พัฒนาการทางทฤษฎีในทฤษฎีสารสนเทศและวิทยาการคอมพิวเตอร์แสดงให้เห็นแนวโน้มของการให้ระบบเข้ารหัสที่พิสูจน์ได้ว่าปลอดภัย เปลี่ยนศิลปะโบราณนี้ให้เป็นวิทยาศาสตร์"

แท้จริงแล้ว ในไม่ช้าก็เห็นได้ชัดว่าดิฟฟี่และเฮลแมนได้เปิดประตูน้ำ นักวิทยาการรหัสลับรุ่นใหม่กำลังจะนำนวัตกรรมมากมายเข้าสู่โลกของการเข้ารหัส