History of Cryptography - Modern Cryptography - Public Key

Public Key

The second development, in 1976, was perhaps even more important, for it fundamentally changed the way cryptosystems might work. This was the publication of the paper New Directions in Cryptography by Whitfield Diffie and Martin Hellman. It introduced a radically new method of distributing cryptographic keys, which went far toward solving one of the fundamental problems of cryptography, key distribution, and has become known as Diffie-Hellman key exchange. The article also stimulated the almost immediate public development of a new class of enciphering algorithms, the asymmetric key algorithms.

Prior to that time, all useful modern encryption algorithms had been symmetric key algorithms, in which the same cryptographic key is used with the underlying algorithm by both the sender and the recipient, who must both keep it secret. All of the electromechanical machines used in WWII were of this logical class, as were the Caesar and Atbash ciphers and essentially all cipher systems throughout history. The 'key' for a code is, of course, the codebook, which must likewise be distributed and kept secret, and so shares most of the same problems in practice.

Of necessity, the key in every such system had to be exchanged between the communicating parties in some secure way prior to any use of the system (the term usually used is 'via a secure channel') such as a trustworthy courier with a briefcase handcuffed to a wrist, or face-to-face contact, or a loyal carrier pigeon. This requirement is never trivial and very rapidly becomes unmanageable as the number of participants increases, or when secure channels aren't available for key exchange, or when, as is sensible cryptographic practice, keys are frequently changed. In particular, if messages are meant to be secure from other users, a separate key is required for each possible pair of users. A system of this kind is known as a secret key, or symmetric key cryptosystem. D-H key exchange (and succeeding improvements and variants) made operation of these systems much easier, and more secure, than had ever been possible before in all of history.

In contrast, asymmetric key encryption uses a pair of mathematically related keys, each of which decrypts the encryption performed using the other. Some, but not all, of these algorithms have the additional property that one of the paired keys cannot be deduced from the other by any known method other than trial and error. An algorithm of this kind is known as a public key or asymmetric key system. Using such an algorithm, only one key pair is needed per user. By designating one key of the pair as private (always secret), and the other as public (often widely available), no secure channel is needed for key exchange. So long as the private key stays secret, the public key can be widely known for a very long time without compromising security, making it safe to reuse the same key pair indefinitely.

For two users of an asymmetric key algorithm to communicate securely over an insecure channel, each user will need to know their own public and private keys as well as the other user's public key. Take this basic scenario: Alice and Bob each have a pair of keys they've been using for years with many other users. At the start of their message, they exchange public keys, unencrypted over an insecure line. Alice then encrypts a message using her private key, and then re-encrypts that result using Bob's public key. The double-encrypted message is then sent as digital data over a wire from Alice to Bob. Bob receives the bit stream and decrypts it using his own private key, and then decrypts that bit stream using Alice's public key. If the final result is recognizable as a message, Bob can be confident that the message actually came from someone who knows Alice's private key (presumably actually her if she's been careful with her private key), and that anyone eavesdropping on the channel will need Bob's private key in order to understand the message.

Asymmetric algorithms rely for their effectiveness on a class of problems in mathematics called one-way functions, which require relatively little computational power to execute, but vast amounts of power to reverse, if reversal is possible at all. A classic example of a one-way function is multiplication of very large prime numbers. It's fairly quick to multiply two large primes, but very difficult to find the factors of the product of two large primes. Because of the mathematics of one-way functions, most possible keys are bad choices as cryptographic keys; only a small fraction of the possible keys of a given length are suitable, and so asymmetric algorithms require very long keys to reach the same level of security provided by relatively shorter symmetric keys. The need to both generate the key pairs, and perform the encryption/decryption operations make asymmetric algorithms computationally expensive, compared to most symmetric algorithms. Since symmetric algorithms can often use any sequence of (random, or at least unpredictable) bits as a key, a disposable session key can be quickly generated for short-term use. Consequently, it is common practice to use a long asymmetric key to exchange a disposable, much shorter (but just as strong) symmetric key. The slower asymmetric algorithm securely sends a symmetric session key, and the faster symmetric algorithm takes over for the remainder of the message.

Asymmetric key cryptography, Diffie-Hellman key exchange, and the best known of the public key / private key algorithms (i.e., what is usually called the RSA algorithm), all seem to have been independently developed at a UK intelligence agency before the public announcement by Diffie and Hellman in 1976. GCHQ has released documents claiming they had developed public key cryptography before the publication of Diffie and Hellman's paper. Various classified papers were written at GCHQ during the 1960s and 1970s which eventually led to schemes essentially identical to RSA encryption and to Diffie-Hellman key exchange in 1973 and 1974. Some of these have now been published, and the inventors (James H. Ellis, Clifford Cocks, and Malcolm Williamson) have made public (some of) their work.

Read more about this topic:  History Of Cryptography, Modern Cryptography

Other articles related to "public key, key, keys, public keys":

Lamport Signature - Security Parameters
... In Lamport signatures, each bit of the public key and signature is based on short messages requiring only a single invocation to a hash function ... For each private key yi,j and its corresponding zi,j public key pair, the private key length must be selected so performing a preimage attack on the length of the input is not faster than performing a ... For example, in a degenerate case, if each private key yi,j element was only 16 bits in length, it is trivial to exhaustively search all 216 possible private key ...
TLS-PSK
... Transport layer security pre-shared key ciphersuites (TLS-PSK) is a set of cryptographic protocols that provide secure communication based on pre-shared keys ... These pre-shared keys are symmetric keys shared in advance among the communicating parties ... set of ciphersuites uses only symmetric key operations for authentication ...
Security Of Automated Teller Machines - Security
... As for terminal security, it is of a great importance in cases where cipher keys reside in terminals ... In the absence of physical security, an abuser may be probe for a key or substitute its value ... Moreover, the use of public key cryptosystem (PKC) where public keys in the Electronic funds transfer are made recourse to prove to be insecure in the absence of ...
Merkle Signature Scheme - Signature Verification
... The receiver knows the public key, the message, and the signature ... of, the receiver computes by hashing the public key of the one-time signature ... If equals the public key of the merkle signature scheme, the signature is valid ...
Data Validation And Certification Server - Services Provided By DVCS - Validation of Public Key Certificates
... The Validation of Public Key Certificates service is used to verify and assert the validity (according to ) of one or more public key certificates at the specified time ... When verifying a public key certificate, the DVCS verifies that the certificate included in the request is a valid certificate and determines its revocation status at a specified time ...

Famous quotes containing the words key and/or public:

    As soon as you are in a social setting, you better take away the key to the lock of your heart and pocket it; those who leave the key in the lock are fools.
    Johann Wolfgang Von Goethe (1749–1832)

    Here also was made the novelty ‘Chestnut Bell’ which enjoyed unusual popularity during the gay nineties when every dandy jauntily wore one of the tiny bells on the lapel of his coat, and rang it whenever a story-teller offered a ‘chestnut.’
    —Administration for the State of Con, U.S. public relief program (1935-1943)