Learning crypto: The Diffie-Hellman-Merkle Key Exchange


This is the first installment of a series intended to help you gain a clear understanding of some of the more understandable aspects of modern day, cryptography, known as Public Key Infrastructure ( PKI ).  While PKI is part and parcel of cryptocurrency technology, the implications are much farther reaching.  Trust me and read on, you want to know about this.

PKI enables both asymmetrical encryption and digital signatures, with digital signatures being one of the core technologies employed in cryptocurrency.  The digital signature itself is worthy of much study and we’ll be getting into bitcoin’s use of elliptic curve digital signatures in a future article. Independent of all that, remember,  part of my motivation is that there are some things that are simply too cool to keep secret!

In this article we are discussing the radical invention that broadly enabled asymmetric cryptography, wherein a Public/Private key pair is the distinguishing factor.  One part of the key pair can be shared freely and the other part must be kept an absolute secret.  Thus, the mathematically fascinating problem is to be able to exchange secret keys with a total stranger using a communications medium that can easily be monitored by anyone.  At first glance, it seems impossible.


New Directions in Cryptography

A mere 36 years ago, this problem was solved by Whitfield Diffie and Martin Hellman.  The perplexing problem and its elegant, brilliant and quite understandable solution is one of the trickiest things I have ever encountered.

A bit more history

The algorithm we are studying today was published in 1976 and was originally known as the Diffie-Helman Private Key Exchange.   RSA keys were invented, shortly thereafter, with  the D-H key being faster and cheaper due to the fact that it does not depend on large prime numbers, like RSA, but rather simply, on truly random numbers.

click here to read the full paper



In 2002, Martin Hellman wrote:

The system…has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called ‘Diffie–Hellman–Merkle key exchange’ if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle’s equal contribution to the invention of public key cryptography.

Extreme bitcoin technology buffs are quite familiar with Merkle roots and trees, hence we are in very good company here.  Even less technically minded adopters, still, are passingly familiar the name Merkle.

The following youtube does a remarkable job of discussing the problem and explaining the algorithm, which is trivial and mind-breaking all at the same time.  Watch this and think about it. Then watch it again until it becomes crystal clear in your mind.  You’ll really enjoy thinking about this amazing mathematics.  If you are a programmer, take careful notes and attempt the extra credit assignment below.

So, the root of the solution is the one way function, cheap and easy in one direction and nearly impossible in the other.

While this article is more about cryptography reaching the public domain than it is about cryptocurrency, we need to know our roots, recognize the legends that paved the way for Satoshi and walk before we try to run.

Extra Credit: Let’s do some programming and learning together.  Write the code.  Pick your favorite programming language and implement the DHM secret key exchange.   Feel free to post your code in the comments below, that should be quite interesting.  I’ll post my C language solution in a couple of weeks.

Extra Credit: watch this lecture given by Whitfield Diffie:


Other articles by rebphil that you might enjoy. 
Dark Wallet     Alpha Test Introduction    Dark Lobby   Alpha 4 update
Learning Crypto     DHM Key exchange     Eliptical Curve DSA     Greedy Mining
CannaCoin     IRC tipbot wallet     CannaStore
Tips for Phil:
BTC: 1JcNZ48vhNATfa96dXw8CVGhggSE2X795W
LTC: LVzr5taTj5Y4zG8MvpSGbQAT92YXrqdnpu