Ralph Merkle

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

Ralph Merkle

The paper had barely been published when Hellman received a letter from a graduate student at the University of California, Berkeley.

The student had written a paper of his own, his letter explained. However: “The people with whom I try and discuss it either fail completely to understand what’s going on, or regard any attempt at solution as impossible,” he wrote, his frustration dripping from the page. Concluding: “The possibility arises of doing joint work, and I would be interested in this possibility.”

Signed: Ralph C. Merkle.

Although about seven or eight years younger than Diffie and Hellman, Merkle’s story was not so different from theirs. He’d always been good with numbers, consistently topped every math class, and he’d taken a keen interest in computers since starting university.

He was introduced to the field of cryptography during a class on computer security in his last term as an undergrad. But as the lecturer went over the Caesar cipher and other forms of symmetric encryption, he had immediately realized that the required in-person key exchange made the approach very limited. Merkle believed that in a world where more and more communication would go digital, a better solution was desperately needed.

Rather than traversing the country in a quest for answers, however, Merkle had limited his search for a solution to his own creative mind. And he eventually came up with a scheme that could, at least to an extent, do the trick.

This is how it would work.

First, Alice would create a great many cryptographic puzzles, perhaps millions or even more. The solution to each puzzle would consist of a unique number and an equally unique secret key. Alice herself would already know the solution to each puzzle; she’d know which numbers are matched with which secret keys. But each individual puzzle could also be solved by anyone else, with a little bit of computing power.

Alice would then send all the puzzles to Bob. Bob would in turn randomly pick one puzzle, and solve it with a bit of computing power to find the unique number and the corresponding secret key. He would then send the number (but not the corresponding secret key) back to Alice.

Based on the unique number returned by Bob, Alice would immediately know which secret key Bob found along with it. This secret key would then be the encryption key they’d share. Like any other symmetric encryption key, it would be used to encrypt and decrypt messages between them.

An eavesdropper, meanwhile, could have seen all the puzzles that Alice sent to Bob, and he could also have seen which unique number Bob sent back to Alice, but he still wouldn’t know the corresponding secret key.

To figure that out, the eavesdropper would actually have to randomly start solving all the puzzles (brute force) to try and find that one unique number that Bob sent back, which would then also reveal the secret key Alice and Bob settled on. This would be a computationally expensive process, however. Depending on the amount of puzzles that were initially created (and the difficulty to solve each puzzle), it could require a lot of processing power and take a long time.

Alice and Bob would therefore have an asymmetric advantage against the eavesdropper. They hardly needed to perform any computations at all to agree on a secret key, while the eavesdropper would have to perform many computations before he’d be able to listen in to their conversation.

This solution did, however, require that Alice and Bob share quite a bit of data in the form of puzzles. And the security of this solution would scale linearly with the total number of puzzles. To make the scheme ten times harder to crack, they would have to share ten times as many puzzles; to make the scheme a hundred times harder to crack, they’d have to share a hundred times as many puzzles, and so on. In practice, regular users’ data resource limitations suggest that a well-funded attacker with a supercomputer could in many cases decrypt messages within a matter of days.

Nonetheless, Merkle had conceived a solution that allowed two people to communicate fairly privately without the need to meet in person beforehand. Even if not perfect, he believed that this key-exchange technique was certainly novel, and potentially useful.

But Merkle hadn’t been able to convince anyone else. His idea received little praise at Berkeley, while his paper was rejected by Communications of the ACM, the prestigious journal of the Association for Computing Machinery (ACM). Sending secret keys over an insecure network was considered unacceptable by reviewers. Besides, they had pointed out, no prior literature had established key-exchange as an important problem in the first place.

Unable to convey its potential to anyone around him, the disappointed student was about to give up on his idea altogether—until he got his hands on a preprint of Diffie and Hellman’s paper. Merkle was quick to recognize that the duo was trying to solve a similar problem. It represented a form of vindication that he desperately needed, and he decided to reach out.

Unlike Merkle’s Berkely professor and the journal reviewers, Diffie and Hellman admired the ingenuity of the proposal. Whereas Diffie’s idea revolved around key pairs, Merkle’s approach cleverly allowed Alice and Bob to settle on a shared key in such a way that only they could (easily) calculate what this key is. Although Diffie and Hellman ultimately concluded that the scheme was not robust enough for what they were trying to achieve, the puzzle scheme did invite them to look at the problem from a new angle.

Hellman decided to take Merkle on as a summer intern, where he helped the Berkeley student redraft his paper into a version that would eventually be accepted by the ACM journal. Moreover, having proved himself to be a creative and clever thinker, Merkle was also looped into further conversations about public key cryptography.

Now, three minds were thinking about the problem.

ราล์ฟ เมอร์เคิล

แทบจะยังไม่ทันตีพิมพ์บทความ เฮลแมนก็ได้รับจดหมายจากนักศึกษาปริญญาโทที่มหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์

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

ลงชื่อ: ราล์ฟ ซี. เมอร์เคิล

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

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

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

นี่คือวิธีการ

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

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

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

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

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

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

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

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

แต่เมอร์เคิลไม่สามารถโน้มน้าวใจใครได้ ความคิดของเขาได้รับคำชมเพียงเล็กน้อยที่เบิร์กลีย์ ในขณะที่บทความของเขาถูกปฏิเสธโดย Communications of the ACM วารสารอันทรงเกียรติของสมาคมเครื่องจักรกลคำนวณ (ACM) ผู้ตรวจทานถือว่าการส่งกุญแจลับผ่านเครือข่ายที่ไม่ปลอดภัยนั้นยอมรับไม่ได้ นอกจากนี้ พวกเขายังชี้ให้เห็นว่าไม่มีวรรณกรรมก่อนหน้านี้ที่กำหนดให้การแลกเปลี่ยนกุญแจเป็นปัญหาสำคัญตั้งแต่แรก

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

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

เฮลแมนตัดสินใจรับเมอร์เคิลเป็นนักศึกษาฝึกงานช่วงฤดูร้อน โดยเขาช่วยนักศึกษาเบิร์กลีย์ปรับแก้บทความให้เป็นฉบับที่ในที่สุดก็ได้รับการตีพิมพ์ในวารสาร ACM นอกจากนี้ หลังจากพิสูจน์ตัวเองแล้วว่าเป็นนักคิดที่สร้างสรรค์และฉลาด เมอร์เคิลจึงถูกดึงเข้าร่วมการสนทนาเพิ่มเติมเกี่ยวกับการเข้ารหัสลับแบบกุญแจสาธารณะด้วย

ตอนนี้มีสามสมองที่คิดเกี่ยวกับปัญหานี้แล้ว