Sometimes Academics Change the World: The Genius of Ralph C. Merkle

Introduction

In a world where companies spend billions on research, it can often be forgotten that it is the work of individuals that often make the fundamental breakthroughs that transform our lives. The spending of massive budgets is no guarantee of success, and often it is the environment that is created and the drive and determination to succeed that proves the best investment creating important break-throughs. Along with this at the core is to know what the problem it is that you are trying to solve, and what other methods are around that can solve it in some way... the essence of a PhD.

Okay. It's 1978, and you're a 26 year-old PhD student, and you've been pouring over your supervisor's classic paper on key exchange (Martin Hellman). In your supervisor's paper he proposes that there may be the possibility of a trap-door function, where we could create two keys, one which encrypts and the other which decrypts. After going back to his work on his undergraduate degree, Ralph rushes in, and tells his distinguished supervisor that he's found the method that his supervisor had proposed. The world would soon find out the discovery with the classic paper of:

• Merkle, Ralph; Hellman, Martin (1978). "Hiding information and signatures in trapdoor knapsacks". Information Theory, IEEE Transactions on 24 (5): 525–530.

For Ralph it was the invention of public key encryption, and which now provides the core of the security on the Internet. His actual method has since been broken, but he showed the possibilities of how two keys could be created: one to lock and the other to open. For him the task was to create a public key were it was extremely difficult to derive the associated private key.

A supervisor and a thesis like no other

Ralph's thesis was successfully defended in 1979 [Here], and his acknowledgement, always a telling source for a PhD examiner on the environment around a PhD, hints towards the hot-house of ideas at Stanford University and at the University of California, Berkley at the time for cryptography:

What an honour it must have been to be in such a creative and stimulating environment with the assistances of Steve Pohlig, and from the great Whitfield Diffie, and then to have a supervisor of Martin Hellman. With that talent around you are either going to bloom or wither, there's very little in-between.

Don't you just love the statement of "... and who encouraged me when it counted most" and which hints towards Ralph struggling through his new methods, and for Martin to be there to guide and support, and most of all not get in his way, but the mentor and provide constructive feedback.

Ralph C. Merkle was born in 1952, and gained an M.S degree in 1997, and his Ph.D, entitled "Secrecy, authentication and public key systems" at Stanford University in 1979. Many people think that the ideas created in the PhD are incubated within the PhD studies, but for Ralph his first thoughts were part of an undergraduate assignment to devised a scheme for communication over an insecure channel.

He has since moved onto other areas, but his recognition for discovering a method for public key encryption has been recognised with an ACM award in 1996 for the Invention of Public Key Cryptography, and in 2000 received the RSA award for the invention. Many awards have followed, including being inducted in the National Inventors Hall of Fame in 2011.

For Ralph his method lasted four years, before the great Adi Shamir showed that it could be easily cracked:

• Shamir, Adi. "A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem." Advances in Cryptology. Springer US, 1983.

You must smile in the amount of effort that must have gone into PhD thesis before the days of word processors, and where someone had to actually type out all the characters (and check) for this:

Disinterested Professors

Many people think that undergraduate degrees are unlikely to create ideas that are ground breaking, but it is often not the case. Ralph, in 1974, pitched the idea of public key to his Professor in a coursework definition, and defined a method of key exchange (known as Merkle's Puzzles). It was rejected by professors, and was finally resurrected when Ralph heard of the work of Martin Hellman and Whitfield Diffie at Stanford. The text below says:

Project 2 looks more reasonable maybe because your description of Project 1 is muddled terribly

Ralph then submitted his idea as a paper to the Communications of the ACM, but was rejected, as his paper did not have a formal literature review or references to other work. For Ralph he reasoned that there couldn't have been references as there was no other work like this around. The paper was accepted three years later, but this time it has references to other work.

Ralph's idea was that Bob gives Alice a number of puzzles to solve, and Alice picks one of them and solves it. Alice then return back the answer with another puzzle. The answers to both puzzles is then used as a secret between Bob and Alice, and thus the key they use to send secret messages. Eve, who is listening, can solve the puzzles, and he has to solve both Bob and Alice's puzzles, and if the number of puzzles is large and the time taken to crack them is large, Eve will take much longer to discover the shared secret [Example].

His Public Key Method

The knapsack problem defines a problem where we have a number of weights and then must pack our knapsack with the minimum number of weights that will make it a given weight. In general the problem is:

• Given a set of numbers A and a number b.
• Find a subset of A which sums to b (or gets nearest to it).

So imagine you have a set of weights of 1, 4, 6, 8 and 15, and we want to get a weight of 28, we could thus use 1, 4, 8 and 15 (1+4+8+15=28).

So our code would become 11011 (represented by '1', '4', no '6', '8' and '15').

Then if our plain text is 10011, with a knapsack of 1, 4, 6, 8, 15, we have a cipher text of 1+4+8+15 which gives us 28.

A plain text of 00001 will give us a cipher text of 15.

With public key cryptography we have two knapsack problems. One of which is easy to solve (private key), and the other difficult (public key).

Creating a public and a private key

We can now create a super-increasing sequence with our weights where the current value is greater than the sum of the preceding ones, such as {1, 2, 4, 9, 20, 38}. Super-increasing sequences make it easy to solve the knapsack problem, where we take the total weight, and compare it with the largest weight, if it is greater than the weight, it is in it, otherwise it is not.

For example with weights of {1,2,4,9,20,38} with a value of 54, we get:

        
Check 54 for 38? Yes (smaller than 54). [1] We now have a balance of 16.
Check 16 for 20? No. [0].
Check 16 for 9? Yes. [1]. We now have a balance of 5.
Check 5 for 4? Yes. [1]. We now have a balance of 1.
Check 1 for 2? No. [0].
Check 1 for 1? Yes [1].

Our result is 101101.

If we have a non-super-increasing knapsack such as {1,3,4,6,10,12,41}, and have to make 54, it is much more difficult. So a non-super-increasing knapsack can be the public key, and the super-increasing one is the private key.

Making the Public Key

We first start with our super-increasing sequence, such as {1,2,4,10,20,40} and take the values and multiply by a number n, and take a modulus (m) of a value which is greater than the total (m - such as 120). For n we make sure that there are no common factors with any of the numbers. Let's select an n value of 53, so we get:

1×53 mod(120) = 53
2×53 mod(120) = 106
4×53 mod(120) = 92
10×53 mod(120) = 50
20×53 mod(120) = 100
40×53 mod(120) = 80

So the public key is: ({53,106,92,50,100,80},53,120) and the private key is {1, 2, 4, 10, 20,40}. The public key will be difficult to factor while the private key will be easy. Let's try to send a message that is in binary code:

111010 101101 111001

We have six weights so we split into three groups of six weights:

111010 = 53 + 106 + 92 + 100 = 351
101101 = 53+ 92 + 50 + 80 = 275
111001 = 53 + 106 + 92 + 80 = 331

Our cipher text is thus 351 275 331.

The two numbers known by the receiver is thus 120 (m - modulus) and 53 (n multiplier).

We need n-1, which is a multiplicative inverse of n mod m, i.e. n(n?1) = 1 mod m. For this we find the inverse of n:

n-1 = 53-1 mod 120
(53 x _n) mod 120 = 1 

So we try values of n-1 in (53 x n-1 mod 120) in order to get a result of 1:

n-1 	Result
1    	53
2   	106
3   	39
...
75  	15
76 	68
77 	1

So the inverse is 77. [Calculate]

The coded message is 351 275 331 and is now easy to calculate the plain text:

351×77 mod(120) = 27 = 111010 (1+2+4+20)
275×77 mod(120) = 55 = 101101
331×77 mod(120) = 47 = 111001

The decoded message is thus:

111010 101101 110001

which is the same as our original message:

111010 101101 111001

The decoding was so easy, the only thing we had was to find the inverse which is not too difficult.

Try this example here.

On this Wiki page [Here], the private key is {2, 7, 11, 21, 42, 89, 180, 354}, n=792, m=881, with data of "01100001" which gives a public key of {295, 592, 301, 14, 28, 353, 120, 236} and gives a cipher of "1129". Try example here.

Merkle Trees

Let's say we have two banks who do billions of transactions every day, and they want to check that all the transactions, or a batch of transactions, have been received correctly? One way is to use a Merkle tree (or a hash tree), and which is a method that was patented by Ralph Merkle [here] in 1979, where each non-leaf node is the hash of its children. Then, to check all the transactions, we would compute the hashes and calculate a root hash, and exchange that.

So let's say we have Bob The Bank, and Alice Online, and they exchange transactions. If they want to check their transactions at the end of the day, they can each compute the hash tree, by hashing non-leaf nodes with the hash of the children:

?Bob The Bank will then send the root hash to Alice Online, and she can then check that she computes the same value. If they agree, they have the same set of transactions. But let's say that Alice Online just wants to search for one of the branches of the tree. We can do this in Merkle trees by only increasing computing power by log(N) - where N is the number of nodes in the tree (where a hash list would vary with the number of nodes). In this way we could check to see if transactions 3 and 4 are in the tree.

Here is a simple demo of the Merkle tree method:

Merkle trees are used in so many applications, including with P2P networks, but also with Bitcoin transactions, Git distributions, and in the BitTorrent protocol. You will also find it in NoSQL systems including with Apache Cassandra. Another new application is in Quantum Computing robust cryptography methods.

Standing on the shoulders of giants

Listen as Ralph outlines "a life less boring" about cracking crypto with quantum computers:

https://www.verisign.com/en_US/innovation/verisign-labs/speakers-series/quantum-computers/index.xhtml?inc=www.verisigninc.com

For him, quantum computers will happen ... and how long will it be before they arrive? Can we build-in quantum robustness in crypto? 

Conclusions

Doing a PhD can be a long and difficult route, as you struggle with many concepts, but the feeling of discovering something new will never leave those who have been through the process. For Ralph it was one of the most fundamental discoveries ever, and the core principles around public key have went on to change the world in ways that could never have been envisaged: PKI. For him, his method was cracked after a few years, but the RSA method has stood the test of time, and still comes out fighting.

I love Ralph's thesis, and just wonder what it would have been like to be his examiner. In fact, I love my role as an external examiner, as it is one of the few times in my job that I can intensely engage on a 1-to-1 basis with someone, and encapsulate three years of study into three hours. PhD students should never walk out of an examination thinking ... "That was easy", but should always feel that they have engaged with someone who knows their work inside-out.

The point of a PhD examination is thus to probe every single idea, and how it all fits together, and check every single detail. Few times in your life to you have to face such as rigorous examination of your work, and it is something that few PhD graduates ever forget, especially in passing on this type of approach to their students.

It might surprise you, but the acknowledge can often tell you have the environment has been around the PhD study, and you can often pinpoint who really helped, and who didn't! I have quite a few PhD examinations coming up in the next few months, and I can't wait for them. It is probably one of the worst paid jobs in the world, where a thesis will often take over 50 hours to read (as you have lots of checking to do on each paper). If the supervisors have done their job, it is an easier task, if they haven't you're fixing typos, correcting bad grammar, and holes in the argument. So, again, you can tell the input of the supervisors in a thesis. My advice to any PhD student, ... don't use...

This is a very large number

as the statement is unscientific from many angles, and shows that the work has not been read properly by the supervision team.

For Ralph, I bow my head in respect for his intellect and drive.