As part of our ongoing celebration of the 20th Anniversary of Public Key Infrastructure (PKI), we’re looking back in a four-part series on the pioneers, processes and events that have shaped this ever-evolving technology.
In part one, we traced the early history of PKI and highlighted some of the challenges that led to important technological innovations. Today we look back at how managing symmetric keys in the 1970’s was proving problematic – and how key players forged new solutions for a growing need.
Public-Key Solves Half of the Key Distribution Problem
At MIT in the mid-1970s, Whitfield Diffie was exploring how to devise a crypto-system in which the encryption and decryption keys were different – and in which knowledge of one revealed nothing about the other. If such a scheme were to exist, it would be possible to broadly publish an encryption key while keeping the decryption key secret. This would overcome the difficulty of distributing confidential key material, from which the earlier “Needham- Schroeder” scheme suffered. Whitfield Diffie coined the counter-intuitive term “public-key cryptography” for this idea.
(In an historical footnote from 1970 at the UK Government Communications Headquarters, James Ellis had already identified the possibility of public-key cryptography – but the government at that time decided not to publish his discovery.)
Together with Martin Hellman at Stanford in 1976, Diffie proposed the idea that a one-way function would have the characteristics required for public-key-based key agreement. They came up with the idea of using the Discrete Logarithm Problem (DLP) as the basis of the one-way function.
The discrete logarithm problem, or DLP, is a pretty simple idea: while it is relatively easy to multiply a number by itself many times, it is relatively hard, given that number and the result, to figure out how many times it has been multiplied. The initial number is a parameter of the system, the result is the public key and the number of times the initial number was multiplied is the private key. And in order to make it practically impossible to discover someone’s private key, given both the input and the result, the key has to be large; Diffie and Hellman suggested 200 bits.
The Diffie-Hellman scheme solved the key-agreement problem in which two parties – using only unprotected exchanges – could agree on a key known only to them, which could then be used with a symmetric algorithm to encrypt their communications. But, Diffie also realized that if one could discover a one-way function containing a trapdoor
(a one-way function whose inverse can be calculated using specific, secret knowledge) then it could also be used for authenticating the identity of the other party.
Rivest, Shamir and Adleman
In 1978, Rivest, Shamir and Adleman discovered a function with the required property. They devised the first practical public-key scheme that included a trapdoor and showed how it could be used for both encryption and digital signature. Their scheme is based on the well-known difficulty of finding the factors of a large composite number. They recommended using a 664-bit number, which seemed to provide adequate security at the time. (Indeed, it was another thirty years before factoring numbers of this size became practical. Today, numbers with a size of 2048 bits are recommended.)
Even with the relatively small numbers specified by the three men, the RSA algorithm performed too slowly for interactive use on the rudimentary desktop computers of the time. Expensive custom silicon or digital signal processing chips were required to achieve acceptable performance. Today, silicon technology has advanced to the point where modern RSA implementations can be executed in constrained environments – including smart cards – with acceptable performance for many applications.
Certificates solve the other half of the problem
While public-key schemes eliminated the need to distribute confidential key material, they still required public keys generated by one party to be distributed to the parties with whom they wished to communicate in a trustworthy way. If an attacker could control the public key used by the sender, they could cause that sender to encrypt the message in such a way that it could be read by the attacker.
Loren Kohnfelder, also studying at MIT in 1978, showed how digital signatures could solve this problem. He coined the term “certificate” to describe how a user’s key could be bound to his or her identity by a naming authority using a digital signature. Any other user who had a trusted copy of the authority’s public key could verify that a public key genuinely belonged to the user named in the certificate. In the same thesis, he introduced the idea of the signed revocation list to restore the secure state in the event that a certificate had been miss-issued or compromised in some other way. The idea of public-key infrastructure had been born.
Next time: How PKI faced the challenges of government regulations and key escrow.