Real Virtuality: The Birth of Public-Key Encryption
By 1975, hardware developments enabled cost reductions that brought cryptographic devices to remote cash dispensers and computer terminals, standardizing cryptographic systems in a way that required innovation. Because existing hardware enabled two strangers to communicate across a network, cryptographic systems needed to enable those strangers to communicate securely and easily. At the time, symmetric key encryption established a shared secret between parties using a courier or an expensive private channel. This expensive, inefficient key distribution system did not empower two physical strangers to email one another. With the emergence of email, not only did key distribution need to simplify, but the authentication of electronic mail needed to equal that of physical mail. Signatures authenticated physical mail, and digital signatures could do the same for email. The desire to implement secure, authentic, and easy communication between strangers incited a dialogue between mathematicians across the United States. Ralph Merkle was the first to propose the concept of a public-key cryptosystem in which all information sent over a channel is public, but an eavesdropper must expend an exponentially larger amount of work than the secure communicators to read a message, making it statistically infeasible for the eavesdropper to decrypt. Merkle continued to work with Whitfield Diffie and Martin Hellman to establish the the Diffie-Hellman (D-H) key exchange in 1976, a non-authenticated key agreement protocol. Although the D-H key exchange was non-authenticated, it established the foundation for many authenticated protocols including RSA. Ron Rivest (an editor on Merkle’s original paper), Adi Shamir, and Leonard Adleman published a method for public-key cryptosystems and obtaining digital signatures 1977. Merkle, Diffie, Hellman, and the RSA team took each other’s courses and read each other’s papers, developing a dialogue in their work that optimized the work of their counterparts. Their dialogue was not only a form of collaboration, but it was communication that led to cryptosystems mimicking real systems. Because public-key encryption made email feel like physical mail or talking on the phone, except faster and easier, public-key cryptosystems became the most sustainable method of key exchange.
Merkle secured communications over insecure channels by hiding a cryptographic key in a series of puzzles that were easy for the intended receivers to solve, but difficult for an eavesdropper to solve. Diffie and Hellman recognized that Merkle’s puzzles, though too inefficient to practically implement, attempted to generate a one-way function: a function that is easy to compute in one direction but incredibly difficult to invert. The pair wanted to simplify the process of Merkle’s puzzles while maintaining its intention. After extensive research, Diffie and Hellman developed a key exchange system that utilized exponentiation in a finite field, thereby practicing modular arithmetic. In modular arithmetic, the set of congruence classes relatively prime to the modulus number p form the multiplicative group of integers modulo p. In D-H key exchange, p is prime and g is a primitive root modulo p that is a part of the multiplicative group of integers. Prior to encryption, the two parties, Alice and Bob, publicly agree on a modulo p and a base g for exponentiation. Then, Alice and Bob privately choose secret exponents, a and b respectively, that they share with no one (not even each other). Alice creates message A where A = ga mod p, and Bob creates a message B where B= gb mod p. Alice then sends A to Bob, and Bob sends Bto Alice publicly over the network. Once Alice receives B, she exponentiates it with B as the base and a as the exponent. When Bob receives A, he exponentiates it with Aas the base and b as the exponent. Through that exponentiation, Alice and Bob both generate the same shared secret KwhereK=Abmod p=(ga)b mod p =(gb)a mod p =Ba mod p. Alice and Bob are now able to use K to encrypt and decrypt messages with the Advanced Encryption Standard or other modes of symmetric key encryption. The Diffie-Hellman Key Exchange is a method for establishing a shared secret that participating parties can use to encrypt or decrypt messages; it is not a method of encryption.
Because the Diffie-Hellman Key Exchange does not encrypt messages, it cannot authenticate messages, thereby solving only one of the major problems that rose with the emergence of email in the late 1970s. At the time, Diffie and Hellman thought the problems of key exchange and digital signatures would be addressed separately, but the RSA team responded by packaging the solutions together within a public-key cryptosystem. RSA encryption goes beyond key exchange to encrypt and authenticate private messages using the exchanged keys. RSA consists of two phases: key generation and key encryption/decryption. Key generation, similar to the Diffie-Hellman Key Exchange, generates public and private key pairs Kpub, Kprivusing one-way functions. However, instead of generating the keys in modular p, key generation takes place in modular (n), the Euler totient of n, where n=pq and pand q are very large prime numbers (at least 2512 bits each). Using Euler’s phi function, which determines the number of positive integers relatively prime to n, we find (n) where (n)=(p) (q) =(p-1)(q-1)because every integer less than a prime number is relatively prime to that number. Next, Alice chooses some Kpub=e where eis an element of the set 1, 2,…,(n)-1 such that e and (n) are relatively prime. Because e and (n)are relatively prime, the greatest common denominator between e and (n) is 1. Therefore, the inverse of e exists, and the Extended Euclidean Algorithm can find its inverse, d where d = Kprivsuch thated = 1 mod (n). Notice that Kpub is a function of n and e while Kprivis a function solely of d. Although n and e are public, they are related to d only through pand q, and it is statistically infeasible to calculate pand q from n.
Once the public and private keys have been generated, Alice and Bob can encrypt and decrypt messages that they send to one another. The RSA encryption and decryption functions are very simple exponentiation functions. If Alice wants to encrypt a message to send to Bob, she uses Bob’s public key Kpubbob=ebob(which can be held in a key directory just like a phonebook) and generates a ciphertext yusing the function y=E(x) =xe mod n where xis the plaintext. To decrypt a message Bob uses his private key Kpriv = d and exponentiates y by d, that is, x= D(y) =yd mod n = (xe)d mod n = x1 mod n = x. To attack RSA encryptions, an eavesdropper must know (n) to find d, and (n) depends on pand q which are infeasible to compute from only the public information n and e.
The RSA encryption and decryption algorithm treats cryptographic systems like real-world systems. Because the RSA team was addressing problems that rose with electronic mail, they designed a cryptosystem that felt like a physical mail system: retrieving keys from a phonebook like one would an address, making “opening” and “sealing” mail simple, and including signatures for authentication. If the electronic mail system were to replace the physical mail system, then signatures were necessary for business transactions. An electronic signature is messenger-dependent as well as signer-dependent, therefore the electronic system uses the real-world system as its foundation, and then builds on it to improve the legitimacy and efficiency of transactions. If Alice wants to sign a message that she is sending to Bob, she first decrypts the plaintext message x (every plaintext can be thought of as some other message’s ciphertext) using her private key S = DA(x). Then, she encrypts the decrypted message using Bob’s public key to send to Bob EB(S). When Bob receives a signed message from Alice, he first decrypts the signature to obtain S=DB(x). After Bob validates the message is from Alice, he extracts the message with the encryption method of the sender x = EA(S), where EAis available in the public directory (phonebook).
Because the dialogue between leading mathematicians during the late 1970s was philosophical and considerate of real-world systems, the developments made in the virtual world were sustainable. Merkle, Diffie, Hellman, and the RSA team recognized the inability of the symmetric key cryptosystem to efficiently establish a shared secret as a failure: they did not dress up the failure as result of innovation or a necessary byproduct of secure online communications. Instead, they observed and mimicked the long-established, customer-approved paper mail system, and optimized processes where they could. Public-key cryptosystems exemplify not only abstract mathematical thinking, but abstract mathematical thinking as a product of observing and analyzing the effectiveness of existing practices in the real world.