Public-key cryptography

# Public-key cryptography

Discussion

Encyclopedia

Public-key cryptography refers to a cryptographic
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

system requiring two separate keys, one to lock or encrypt the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....

, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private. If the lock/encryption key is the one published then the system enables private communication from the public to the unlocking key's owner. If the unlock/decryption key is the one published then the system serves as a signature verifier of documents locked by the owner of the private key.

This cryptographic approach uses asymmetric key algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s, hence the more general name of "asymmetric key cryptography". Some of these algorithms have the public key/private key property; that is, neither key is derivable from knowledge of the other; not all asymmetric key algorithms do. Those with this property are particularly useful and have been widely deployed, and are the source of the commonly used name. The public key is used to transform a message into an unreadable form, decryptable only by using the (different but matching) private key. Participants in such a system must create a mathematically linked key pair (i.e., a public and a private key). By publishing the public key, the key producer empowers anyone who gets a copy of the public key to produce messages only he can read -- because only the key producer has a copy of the private key (required for decryption). When someone wants to send a secure message to the creator of those keys, the sender encrypts it (i.e., transforms it into an unreadable form) using the intended recipient's public key; to decrypt the message, the recipient uses the private key. No one else, including the sender, can do so.

Thus, unlike symmetric key algorithms, a public key algorithm does not require a secure
Secure channel
In cryptography, a secure channel is a way of transferring data that is resistant to interception and tampering.A confidential channel is a way of transferring data that is resistant to interception, but not necessarily resistant to tampering....

initial exchange
Key exchange
Key exchange is any method in cryptography by which cryptographic keys are exchanged between users, allowing use of a cryptographic algorithm....

of one, or more, secret keys between the sender and receiver. These algorithms work in such a way that, while it is easy for the intended recipient to generate the public and private keys and to decrypt the message using the private key, and while it is easy for the sender to encrypt the message using the public key, it is extremely difficult for anyone to figure out the private key based on their knowledge of the public key. They are based on mathematical relationships (the most notable ones being the integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

and discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

problems) that have no efficient solution.

The use of these algorithms also allows authenticity of a message to be checked by creating a digital signature
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

of a message using the private key, which can be verified using the public key.

Public key cryptography is a fundamental and widely used technology. It is an approach used by many cryptographic algorithms and cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...

s. It underpins such Internet standards as Transport Layer Security (TLS)
Transport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...

(successor to SSL), PGP
Pretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...

, and GPG
GNU Privacy Guard
GNU Privacy Guard is a GPL Licensed alternative to the PGP suite of cryptographic software. GnuPG is compliant with RFC 4880, which is the current IETF standards track specification of OpenPGP...

.

## How it works

The distinguishing technique used in public key cryptography is the use of asymmetric key algorithms, where the key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...

used to encrypt
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...

a message is not the same as the key used to decrypt it. Each user has a pair of cryptographic keys — a public encryption key and a private decryption key. The publicly available encrypting-key is widely distributed, while the private decrypting-key is known only to the recipient. Messages are encrypted with the recipient's public key and can be decrypted only with the corresponding private key. The keys are related mathematically, but parameters are chosen so that determining the private key from the public key is prohibitively expensive. The discovery of algorithms that could produce public/private key pairs revolutionized
History of cryptography
The history of cryptography begins thousands of years ago. Until recent decades, it has been the story of what might be called classic cryptography — that is, of methods of encryption that use pen and paper, or perhaps simple mechanical aids...

the practice of cryptography beginning in the mid-1970s.

In contrast, symmetric-key algorithm
Symmetric-key algorithm
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both encryption of plaintext and decryption of ciphertext. The encryption key is trivially related to the decryption key, in that they may be identical or there is...

s, variations of which having been used for thousands of years, use a single secret key — which must be shared and kept private by both sender and receiver — for both encryption and decryption. To use a symmetric encryption scheme, the sender and receiver must securely share a key in advance.

Because symmetric key algorithms are nearly always much less computationally intensive, it is common to exchange a key using a key-exchange algorithm and transmit data using that key and a symmetric key algorithm. PGP
Pretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...

, and the SSL
Transport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...

/TLS family of schemes do this, for instance, and are thus called hybrid cryptosystem
Hybrid cryptosystem
In cryptography, public-key cryptosystems are convenient in that they do not require the sender and receiver to share a common secret in order to communicate securely . However, they often rely on complicated mathematical computations and are thus generally much more inefficient than comparable...

s
.

## Description

The two main branches of public key cryptography are:
• Public key encryption: a message encrypted with a recipient's public key cannot be decrypted by anyone except a possessor of the matching private key — it is presumed that this will be the owner of that key and the person associated with the public key used. This is used for confidentiality
Confidentiality
Confidentiality is an ethical principle associated with several professions . In ethics, and in law and alternative forms of legal resolution such as mediation, some types of communication between a person and one of these professionals are "privileged" and may not be discussed or divulged to...

.
• Digital signature
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

s: a message signed with a sender's private key can be verified by anyone who has access to the sender's public key, thereby proving that the sender had access to the private key (and therefore is likely to be the person associated with the public key used), and the part of the message that has not been tampered with. On the question of authenticity
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...

An analogy to public-key encryption is that of a locked mailbox
Letter box
A letter box, letterbox, letter plate, letter hole, mail slot, or mailbox is a receptacle for receiving incoming mail at a private residence or business...

with a mail slot. The mail slot is exposed and accessible to the public; its location (the street address) is in essence the public key. Anyone knowing the street address can go to the door and drop a written message through the slot; however, only the person who possesses the key can open the mailbox and read the message.

An analogy for digital signatures is the sealing of an envelope with a personal wax seal
Seal (device)
A seal can be a figure impressed in wax, clay, or some other medium, or embossed on paper, with the purpose of authenticating a document ; but the term can also mean the device for making such impressions, being essentially a mould with the mirror image of the design carved in sunken- relief or...

. The message can be opened by anyone, but the presence of the seal authenticates the sender.

A central problem for use of public-key cryptography is confidence (ideally proof) that a public key is correct, belongs to the person or entity claimed (i.e., is 'authentic'), and has not been tampered with or replaced by a malicious third party. The usual approach to this problem is to use a public-key infrastructure
Public key infrastructure
Public Key Infrastructure is a set of hardware, software, people, policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates. In cryptography, a PKI is an arrangement that binds public keys with respective user identities by means of a certificate...

(PKI), in which one or more third parties, known as certificate authorities
Certificate authority
In cryptography, a certificate authority, or certification authority, is an entity that issues digital certificates. The digital certificate certifies the ownership of a public key by the named subject of the certificate...

, certify ownership of key pairs. PGP
Pretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...

, in addition to a certificate authority structure, has used a scheme generally called the "web of trust
Web of trust
In cryptography, a web of trust is a concept used in PGP, GnuPG, and other OpenPGP-compatible systems to establish the authenticity of the binding between a public key and its owner. Its decentralized trust model is an alternative to the centralized trust model of a public key infrastructure ,...

", which decentralizes such authentication of public keys by a central mechanism, substituting individual endorsements of the link between user and public key. No fully satisfactory solution to the public key authentication problem is known.

## History

During the early history of cryptography
History of cryptography
The history of cryptography begins thousands of years ago. Until recent decades, it has been the story of what might be called classic cryptography — that is, of methods of encryption that use pen and paper, or perhaps simple mechanical aids...

, two parties would rely upon a key using a secure, but non-cryptographic, method; for example, a face-to-face meeting or an exchange via a trusted courier. This key, which both parties kept absolutely secret, could then be used to exchange encrypted messages. A number of significant practical difficulties arise in this approach to distributing keys
Key distribution
In symmetric key cryptography, both parties must possess a secret key which they must exchange prior to using any encryption. Distribution of secret keys has been problematic until recently, because it involved face-to-face meeting, use of a trusted courier, or sending the key through an existing...

. Public-key cryptography addresses these drawbacks so that users can communicate securely over a public channel without having to agree upon a shared key beforehand.

In 1874, a book by William Stanley Jevons
William Stanley Jevons
William Stanley Jevons was a British economist and logician.Irving Fisher described his book The Theory of Political Economy as beginning the mathematical method in economics. It made the case that economics as a science concerned with quantities is necessarily mathematical...

described the relationship of one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...

s to cryptography and went on to discuss specifically the factorization
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...

problem used to create the trapdoor function
Trapdoor function
A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction without special information, called the "trapdoor"...

in the RSA system. In July 1996, one observer commented on the Jevons book in this way:

In his book The Principles of Science: A Treatise on Logic and Scientific Method, written and published in the 1890s, William S. Jevons observed that there are many situations where the 'direct' operation is relatively easy, but the 'inverse' operation is significantly more difficult. One example mentioned briefly is that enciphering (encryption) is easy while deciphering (decryption) is not. In the same section of Chapter 7: Introduction titled 'Induction an Inverse Operation', much more attention is devoted to the principle that multiplication of integers is easy, but finding the (prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

) factors of the product is much harder. Thus, Jevons anticipated a key feature of the RSA Algorithm for public key cryptography, though he certainly did not invent the concept of public key cryptography.

An asymmetric-key cryptosystem was published in 1976 by Whitfield Diffie
Whitfield Diffie
Bailey Whitfield 'Whit' Diffie is an American cryptographer and one of the pioneers of public-key cryptography.Diffie and Martin Hellman's paper New Directions in Cryptography was published in 1976...

and Martin Hellman
Martin Hellman
Martin Edward Hellman is an American cryptologist, and is best known for his invention of public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle...

, who, influenced by Ralph Merkle
Ralph Merkle
Ralph C. Merkle is a researcher in public key cryptography, and more recently a researcher and speaker on molecular nanotechnology and cryonics...

's work on public-key distribution, disclosed a method of public-key agreement. This method of key exchange, which uses exponentiation in a finite field, came to be known as Diffie–Hellman key exchange. This was the first published practical method for establishing a shared secret-key over an authenticated (but not private) communications channel without using a prior shared secret. Merkle's public-key-agreement technique became known as Merkle's Puzzles, and was invented in 1974 and published in 1978.

In 1997, it was publicly disclosed that asymmetric key algorithms were developed by James H. Ellis
James H. Ellis
James Henry Ellis was a British engineer and mathematician. In 1970, while working at the Government Communications Headquarters in Cheltenham he conceived of the possibility of "non-secret encryption", more commonly termed public-key cryptography.-Early life, education and career:Ellis was born...

, Clifford Cocks
Clifford Cocks
Clifford Christopher Cocks, CB, is a British mathematician and cryptographer at GCHQ.He invented the widely-used encryption algorithm now commonly known as RSA, about three years before it was independently developed by Rivest, Shamir, and Adleman at MIT...

, and Malcolm Williamson
Malcolm J. Williamson
Malcolm John Williamson is a British mathematician and cryptographer. In 1974 he discovered what is now known as Diffie-Hellman key exchange. He was then working at GCHQ and was therefore unable to publicize his research as his work was classified...

The Government Communications Headquarters is a British intelligence agency responsible for providing signals intelligence and information assurance to the UK government and armed forces...

(GCHQ) in the UK
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...

in 1973. The researchers independently developed Diffie–Hellman key exchange and a special case of RSA. The GCHQ cryptographers referred to the technique as "non-secret encryption". This work was named an IEEE Milestone in 2010.

A generalization of Cocks's scheme was independently invented in 1977 by Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...

, Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...

Leonard Max Adleman is an American theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. He is known for being a co-inventor of the RSA cryptosystem in 1977, and of DNA computing...

, all then at MIT
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...

. The latter authors published their work in 1978, and the algorithm appropriately came to be known as RSA. RSA uses exponentiation modulo a product of two large primes
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

to encrypt and decrypt, performing both public key encryption and public key digital signature, and its security is connected to the presumed difficulty of factoring large integers
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

, a problem for which there is no known efficient (i.e., practicably fast) general technique. In 1979 Michael O. Rabin
Michael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...

published a related cryptosystem
Rabin cryptosystem
The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer factorization, which is...

that is probably secure as long as factorization of the public key remains difficult; it remains an assumption that RSA also enjoys this security.

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed in the field of public-key cryptography. The ElGamal cryptosystem
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...

(invented by Taher ElGamal
Taher Elgamal
Dr. Taher Elgamal is an Egyptian cryptographer. Elgamal is sometimes written as El Gamal or ElGamal, but Elgamal is now preferred...

) relies on the (similar, and related) difficulty of the discrete logarithm problem, as does the closely related DSA
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...

developed at the US National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...

(NSA) and published by NIST as a proposed standard. The introduction of elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...

by Neal Koblitz
Neal Koblitz
Neal I. Koblitz is a Professor of Mathematics at the University of Washington in the Department of Mathematics. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyperelliptic curve cryptography and the...

and Victor Miller
Victor S. Miller
Victor Saul Miller is an American mathematician at the Center for Communications Research of the Institute for Defense Analyses in Princeton, New Jersey, US. He received his A.B. in mathematics from Columbia University in 1968, and his Ph.D. in mathematics from Harvard University in 1975...

independently and simultaneously in the mid-1980s has yielded new public-key algorithms based on the discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

problem. Although mathematically more complex, elliptic curves provide smaller key size
Key size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...

s and faster operations for equivalent estimated security.

## Security

Some encryption schemes can be proven secure on the basis of the presumed hardness of a mathematical problem like factoring
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

the product of two large primes or computing discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

s. Note that "secure" here has a precise mathematical meaning, and there are multiple different (meaningful) definitions of what it means for an encryption scheme to be secure. The "right" definition depends on the context in which the scheme will be deployed.

The most obvious application of a public key encryption system is confidentiality
Confidentiality
Confidentiality is an ethical principle associated with several professions . In ethics, and in law and alternative forms of legal resolution such as mediation, some types of communication between a person and one of these professionals are "privileged" and may not be discussed or divulged to...

; a message that a sender encrypts using the recipient's public key can be decrypted only by the recipient's paired private key (assuming, of course, that no flaw is discovered in the basic algorithm used).

Another type of application in public-key cryptography is that of digital signature
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

schemes. Digital signature schemes can be used for sender authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...

and non-repudiation
Non-repudiation
Non-repudiation refers to a state of affairs where the purported maker of a statement will not be able to successfully challenge the validity of the statement or contract. The term is often seen in a legal setting wherein the authenticity of a signature is being challenged...

. In such a scheme, a user who wants to send a message computes a digital signature of this message and then sends this digital signature together with the message to the intended receiver. Digital signature schemes have the property that signatures can be computed only with the knowledge of a private key. To verify that a message has been signed by a user and has not been modified the receiver needs to know only the corresponding public key. In some cases (e.g., RSA), there exist digital signature schemes with many similarities to encryption schemes. In other cases (e.g., DSA
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...

), the algorithm does not resemble any encryption scheme.

To achieve both authentication and confidentiality, the sender can first sign the message using his private key and then encrypt both the message and the signature using the recipient's public key.

These characteristics can be used to construct many other, sometimes surprising, cryptographic protocols and applications, like digital cash, password-authenticated key agreement
In cryptography, a password-authenticated key agreement method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.-Types:...

, multi-party key agreement, time-stamping service, non-repudiation protocols, etc.

### A postal analogy

An analogy that can be used to understand the advantages of an asymmetric system is to imagine two people, Alice and Bob
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...

, sending a secret message through the public mail. In this example, Alice wants to send a secret message to Bob, and expects a secret reply from Bob.

With a symmetric key system, Alice first puts the secret message in a box, and locks the box using a padlock
Padlocks are portable locks used to protect against theft, vandalism, sabotage, unauthorized use, and harm. They are designed to protect against some degree of forced and surreptitious entry.- History :...

to which she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he uses an identical copy of Alice's key (which he has somehow obtained previously, maybe by a face-to-face meeting) to open the box, and reads the message. Bob can then use the same padlock to send his secret reply.

In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and reads the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.

The critical advantage in an asymmetric key system is that Bob and Alice never need to send a copy of their keys to each other. This prevents a third party (perhaps, in the example, a corrupt postal worker) from copying a key while it is in transit, allowing said third party to spy on all future messages sent between Alice and Bob. So in the public key scenario, Alice and Bob need not trust the postal service as much. In addition, if Bob were careless and allowed someone else to copy his key, Alice's messages to Bob would be compromised, but Alice's messages to other people would remain secret, since the other people would be providing different padlocks for Alice to use.

In another kind of asymmetric key system, Bob and Alice have separate padlocks.
First, Alice puts the secret message in a box, and locks the box using a padlock to which only she has a key.
She then sends the box to Bob through regular mail.
When Bob receives the box, he adds his own padlock to the box, and sends it back to Alice.
When Alice receives the box with the two padlocks, she removes her padlock and sends it back to Bob.
When Bob receives the box with only his padlock on it, Bob can then unlock the box with his key and read the message from Alice. Note that, in this scheme, the order of Decryption is the same as the order of encryption; this is only possible if commutative ciphers are used. A commutative cipher is one in which the order of encryption and decryption is interchangeable, just as the order of multiplication is interchangeable; i.e., `A*B*C = A*C*B = C*B*A`. A simple `XOR` with the individual keys is such a commutative cipher. For example, let `E1` and `E2` be two encryption functions and let "`M`" be the message so if Alice encrypts it using `E1` and sends `E1(M)` to Bob. Bob then again encrypts the message as `E2(E1(M))` and sends it to Alice. Now Alice Decrypts `E2(E1(M))` using `E1`. She'll now get `E2(M)`, meaning when she sends this again to Bob, he will be able to decrypt the message using `E2` and get "`M`". Although none of the keys were ever exchanged, the message "`M`" may well be a key, e.g., Alice's Public key.
This three-pass protocol
Three-pass protocol
In cryptography, the three-pass protocol for sending messages is a framework which allows one party to securely send a message to a second party without the need to exchange or distribute encryption keys...

is typically used during key exchange
Key exchange
Key exchange is any method in cryptography by which cryptographic keys are exchanged between users, allowing use of a cryptographic algorithm....

.

Not all asymmetric key algorithms operate in precisely this fashion. The most common ones have the property that Alice and Bob each own two keys, one for encryption and one for decryption. In a secure asymmetric key encryption scheme, the private key should not be deducible from the public key. This is known as public-key encryption, since an encryption key can be published without compromising the security of messages encrypted with that key.

In the analogy above, Bob might publish instructions on how to make a lock ("public key"), but the lock is such that it is impossible (so far as is known) to deduce from these instructions how to make a key that will open that lock ("private key"). Those wishing to send messages to Bob use the public key to encrypt the message; Bob uses his private key to decrypt it.

Another example is that Alice and Bob both choose a key at random and contact each other to compare the depth of each notch on their keys. Having determined the difference a locked box is built with a special lock that has each pin inside divided into 2 pins, matching the numbers of their keys. Now the box will be able to be opened with either key and Alice and Bob can exchange messages inside securely.

### Weaknesses

Of course, there is a possibility that someone could "pick" Bob's or Alice's lock. Among symmetric key encryption algorithms, only the one-time pad
In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...

can be proven to be secure against any adversary, no matter how much computing power is available. However, there is no public-key scheme with this property, since all public-key schemes are susceptible to the brute-force key search attack. Such attacks are impractical if the amount of computation needed to succeed (termed 'work factor' by Claude Shannon) is out of reach of potential attackers. In many cases, the work factor can be increased by simply choosing a longer key. But other attacks may have much lower work factors, making resistance to brute-force attack irrelevant, and some are known for some public key encryption algorithms. Both RSA and ElGamal encryption
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...

have known attacks that are much faster than the brute-force approach. Such estimates have changed both with the decreasing cost of computer power, and new mathematical discoveries.

In practice, these insecurities can be generally avoided by choosing key sizes large enough that the best-known attack would take so long that it is not worth any adversary's time and money to break the code. For example, if an estimate of how long it takes to break an encryption scheme is one thousand years, and it were used to encrypt your credit card details, they would be safe enough, since the time needed to decrypt the details will be rather longer than the useful life of those details, which expire after a few years. Typically, the key size needed is much longer for public key algorithms than for symmetric key algorithms.

Aside from the resistance to attack of a particular keypair, the security of the certification hierarchy
Hierarchy
A hierarchy is an arrangement of items in which the items are represented as being "above," "below," or "at the same level as" one another...

must be considered when deploying public key systems. Some certificate authority (usually a purpose built program running on a server computer) vouches for the identities assigned to specific private keys by producing a digital certificate. Public key digital certificates are typically valid for several years at a time, so the associated private keys must be held securely over that time. When a private key used for certificate creation higher in the PKI server hierarchy is compromised or accidentally disclosed then a man-in-the-middle attack
Man-in-the-middle attack
In cryptography, the man-in-the-middle attack , bucket-brigade attack, or sometimes Janus attack, is a form of active eavesdropping in which the attacker makes independent connections with the victims and relays messages between them, making them believe that they are talking directly to each other...

is possible, making any subordinate certificate wholly insecure.

Major weaknesses have been found for several formerly promising asymmetric key algorithms. The 'knapsack packing' algorithm was found to be insecure when a new attack was found. Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys (see side channel attack
Side channel attack
In cryptography, a side channel attack is any attack based on information gained from the physical implementation of a cryptosystem, rather than brute force or theoretical weaknesses in the algorithms...

). Thus, mere use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new attacks.

Another potential security vulnerability in using asymmetric keys is the possibility of a man-in-the-middle attack, in which communication of public keys is intercepted by a third party and modified to provide different public keys instead. Encrypted messages and responses must also be intercepted, decrypted and re-encrypted by the attacker using the correct public keys for different communication segments in all instances to avoid suspicion. This attack may seem to be difficult to implement in practice, but it's not impossible when using insecure media (e.g., public networks such as the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...

or wireless communications). A malicious staff member at Alice or Bob's ISP might find it quite easy to carry out. In the earlier postal analogy, Alice would have to have a way to make sure that the lock on the returned packet really belongs to Bob before she removes her lock and sends the packet back. Otherwise, the lock could have been put on the packet by a corrupt postal worker pretending to be Bob to Alice.

One approach to prevent such attacks is the use of a certificate authority
Certificate authority
In cryptography, a certificate authority, or certification authority, is an entity that issues digital certificates. The digital certificate certifies the ownership of a public key by the named subject of the certificate...

, a trusted third party
Trusted third party
In cryptography, a trusted third party is an entity which facilitates interactions between two parties who both trust the third party; The Third Party reviews all critical transaction communications between the parties, based on the ease of creating fraudulent digital content. In TTP models, the...

responsible for verifying the identity of a user of the system and issuing a tamper resistant and non-spoofable digital certificate for participants. Such certificates are signed
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...

data blocks stating that this public key belongs to that person, company, or other entity. This approach also has weaknesses. For example, the certificate authority issuing the certificate must be trusted to have properly checked the identity of the key-holder, the correctness of the public key when it issues a certificate, and has made arrangements with all participants to check all certificates before protected communications can begin. Web browser
Web browser
A web browser is a software application for retrieving, presenting, and traversing information resources on the World Wide Web. An information resource is identified by a Uniform Resource Identifier and may be a web page, image, video, or other piece of content...

s, for instance, are supplied with many self-signed identity certificates from PKI providers; these are used to check certificate's bonafides (issued properly by the claimed central PKI server?) and then, in a second step, the certificate of a potential communicant. An attacker who could subvert the certificate authority into issuing a certificate for a bogus public key could then mount a man-in-the-middle attack as easily as if the certificate scheme were not used at all. Despite its problems, this approach is widely used; examples include SSL and its successor, TLS
Transport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...

, which are commonly used to provide security in web browsers, for example, to securely send credit card details to an online store.

### Computational cost

Public key algorithms known thus far are relatively computationally costly compared with most symmetric key algorithms of apparently equivalent security. The difference factor is the use of typically quite large keys. This has important implications for their practical use. Most are used in hybrid cryptosystem
Hybrid cryptosystem
In cryptography, public-key cryptosystems are convenient in that they do not require the sender and receiver to share a common secret in order to communicate securely . However, they often rely on complicated mathematical computations and are thus generally much more inefficient than comparable...

s for reasons of efficiency; in such a cryptosystem, a shared secret key ("session key
Session key
A session key is a single-use symmetric key used for encrypting all messages in one communication session. A closely related term is traffic encryption key or TEK, which refers to any key used to encrypt messages, as opposed to other uses, like encrypting other keys .Session keys can introduce...

") is generated by one party and this much briefer session key is then encrypted by each recipient's public key. Each recipient uses the corresponding private key to decrypt the session key. Once all parties have obtained the session key they can use a much faster symmetric algorithm to encrypt and decrypt messages. In many of these schemes, the session key is unique to each message exchange, being pseudo-randomly chosen for each message.

### Associating public keys with identities

The binding between a public key and its 'owner' must be correct, lest the algorithm function perfectly and yet be entirely insecure in practice. As with most cryptography, the protocols used to establish and verify this binding are critically important. Associating a public key with its owner is typically done by protocols implementing a public key infrastructure
Public key infrastructure
Public Key Infrastructure is a set of hardware, software, people, policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates. In cryptography, a PKI is an arrangement that binds public keys with respective user identities by means of a certificate...

; these allow the validity of the association to be formally verified by reference to a trusted third party
Trusted third party
In cryptography, a trusted third party is an entity which facilitates interactions between two parties who both trust the third party; The Third Party reviews all critical transaction communications between the parties, based on the ease of creating fraudulent digital content. In TTP models, the...

, in the form of either a hierarchical certificate authority
Certificate authority
In cryptography, a certificate authority, or certification authority, is an entity that issues digital certificates. The digital certificate certifies the ownership of a public key by the named subject of the certificate...

(e.g., X.509
X.509
In cryptography, X.509 is an ITU-T standard for a public key infrastructure and Privilege Management Infrastructure . X.509 specifies, amongst other things, standard formats for public key certificates, certificate revocation lists, attribute certificates, and a certification path validation...

), a local trust model (e.g., SPKI
Simple public key infrastructure
Simple public key infrastructure was born out of a joint effort to overcome the overcomplication and scalability problems of traditional X.509 public key infrastructure. It is specified in two Internet Engineering Task Force Request For Comments specifications—RFC 2692 and RFC 2693—from the IETF...

), or a web of trust
Web of trust
In cryptography, a web of trust is a concept used in PGP, GnuPG, and other OpenPGP-compatible systems to establish the authenticity of the binding between a public key and its owner. Its decentralized trust model is an alternative to the centralized trust model of a public key infrastructure ,...

scheme (e.g., that originally built into PGP
Pretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...

and GPG
GNU Privacy Guard
GNU Privacy Guard is a GPL Licensed alternative to the PGP suite of cryptographic software. GnuPG is compliant with RFC 4880, which is the current IETF standards track specification of OpenPGP...

and still to some extent usable with them). Whatever the cryptographic assurance of the protocols themselves, the association between a public key and its owner is ultimately a matter of subjective judgment on the part of the trusted third party, since the key is a mathematical entity while the owner, and the connection between owner and key, are not. For this reason, the formalism of a public key infrastructure must provide for explicit statements of the policy
Policy
A policy is typically described as a principle or rule to guide decisions and achieve rational outcome. The term is not normally used to denote what is actually done, this is normally referred to as either procedure or protocol...

followed when making this judgment. For example, the complex and never fully implemented X.509 standard allows a certificate authority to identify its policy by means of an object identifier
Object identifier
In computing, an object identifier or OID is an identifier used to name an object . Structurally, an OID consists of a node in a hierarchically-assigned namespace, formally defined using the ITU-T's ASN.1 standard. Successive numbers of the nodes, starting at the root of the tree, identify each...

, which functions as an index into a catalog of registered policies. Policies may exist for many different purposes, ranging from anonymity to military classification.

### Relation to real world events

A public key will be known to a large and, in practice, unknown set of users. All events requiring revocation or replacement of a public key can take a long time to take full effect with all who must be informed (i.e., all those users who possess that key). For this reason, systems that must react to events in real time (e.g., safety-critical systems or national security systems) should not use public-key encryption without taking great care. There are four issues of interest:

#### Privilege of key revocation

A malicious (or erroneous) revocation of some or all of the keys in the system is likely, or in the second case, certain, to cause a complete failure of the system. If public keys can be revoked individually, this is a possibility. However, there are design approaches that can reduce the practical chance of this occurring. For example, by means of certificates we can create what is called a "compound principal"; one such principal could be "Alice and Bob have Revoke Authority". Now only Alice and Bob (in concert) can revoke a key, and neither Alice nor Bob can revoke keys alone. However, revoking a key now requires both Alice and Bob to be available, and this creates a problem of reliability. In concrete terms, from a security point of view, there is now a single point of failure in the public key revocation system. A successful Denial of Service attack against either Alice or Bob (or both) will block a required revocation. In fact, any partition of authority between Alice and Bob will have this effect, regardless of how it comes about.

Because the principle allowing revocation authority for keys is very powerful, the mechanisms used to control it should involve both, as many participants as possible (to guard against malicious attacks of this type), while at the same time as few as possible (to ensure that a key can be revoked without dangerous delay). Public key certificates that include an expiry date are unsatisfactory in that the expiry date may not correspond with a real-world revocation need, but at least such certificates need not all be tracked down system-wide, nor must all users be in constant contact with the system at all times.

#### Distribution of a new key

After a key has been revoked, or when a new user is added to a system, a new key must be distributed in some predetermined manner.
Assume that Carol's key has been revoked (e.g., automatically by exceeding its use-before date, or less so, because of a compromise of Carol's matching private key). Until a new key has been distributed, Carol is effectively out of contact. No one will be able to send her messages without violating system protocols (i.e., without a valid public key, no one can encrypt messages to her), and messages from her cannot be signed for the same reason. Or, in other words, the "part of the system" controlled by Carol is in essence unavailable. Security requirements have been ranked higher than system availability in such designs.

One could leave the power to create (and certify) keys as well as revoke them in the hands of each user, and the original PGP design did so, but this raises problems of user understanding and operation. For security reasons, this approach has considerable difficulties; if nothing else, some users will be forgetful or inattentive or confused. On one hand, a message revoking a public key certificate should be spread as fast as possible while, on the other hand, (parts of) the system might be rendered inoperable before a new key can be installed. The time window can be reduced to zero by always issuing the new key together with the certificate that revokes the old one, but this requires co-location of authority to both revoke keys and generate new keys.

It is most likely a system-wide failure if the (possibly combined) principal that issues new keys fails by issuing keys improperly. It is an instance of a common mutual exclusion; a design can make the reliability of a system high, but only at the cost of system availability, and vice versa.

Notification of a key certificate revocation must be spread to all those who might potentially hold it, and as rapidly as possible.

There are two means of spreading information (e.g., a key revocation here) in a distributed system: either the information is pushed to users from a central point(s), or it is pulled from a central point(s) by end users.

Pushing the information is the simplest solution in that a message is sent to all participants. However, there is no way of knowing whether all participants will actually receive the message. And, if the number of participants is large and some of their physical or network distance great, the probability of complete success (which is, in ideal circumstances, required for system security) will be rather low. In a partly updated state, the system is particularly vulnerable to denial of service attacks as security has been breached, and a vulnerability window will continue to exist as long as some users have not 'gotten the word'. In other words, pushing certificate revocation messages is neither easy to secure nor very reliable.

The alternative to pushing is pulling. In the extreme, all certificates contain all the keys needed to verify that the public key of interest (i.e., the one belonging to the user to whom one wishes to send a message, or whose signature is to be checked) is still valid. In this case, at least some use of the system will be blocked if a user cannot reach the verification service (i.e., one of those systems that can establish the current validity of another user's key). Again, such a system design can be made as reliable as one wishes, at the cost of lowering security (the more servers to check for the possibility of a key revocation, the longer the window of vulnerability).

Another trade-off is to use a somewhat less reliable, but more secure, verification service but to include an expiry date for each of the verification sources. How long this timeout should be is a decision that embodies a trade-off between availability and security that will have to be decided in advance, at system design time.

#### Recovery from a leaked key

Assume that the principal authorized to revoke a key has decided that a certain key must be revoked. In most cases this happens after the fact; for instance, it becomes known that at some time in the past an event occurred that endangered a private key. Let us denote the time at which it is decided that the compromise occurred with T.

Such a compromise has two implications. Messages encrypted with the matching public key (now or in the past) can no longer be assumed to be secret. One solution to avoid this problem is to use a protocol that has perfect forward secrecy
Perfect forward secrecy
In an authenticated key-agreement protocol that uses public key cryptography, perfect forward secrecy is the property that ensures that a session key derived from a set of long-term public and private keys will not be compromised if one of the private keys is compromised in the future.Forward...

. Second, signatures made with the no longer trusted to be actually private key after time T, can no longer be assumed to be authentic without additional information about who, where, when, etc. of the events leading up to digital signature. These will not always be available, and so all such digital signatures will be less than credible. A solution to reduce the impact of leaking a private key of a signature scheme is to use timestamps
Trusted timestamping
Trusted timestamping is the process of securelykeeping track of the creation and modification time of a document. Securityhere means that no one — not even the owner of the document — should be able to change it once it has been recorded provided that the timestamper's integrity is never...

.

Loss of secrecy and/or authenticity, even for a single user, has system-wide security implications, and a strategy for recovery must thus be established. Such a strategy will determine who has authority and under what conditions to revoke a public key certificate, how to spread the revocation, but also, ideally, how to deal with all messages signed with the key since time T (which will rarely be known precisely). Messages sent to that user (which require the proper, now compromised, private key to decrypt) must be considered compromised as well, no matter when they were sent.

Such a recovery procedure can be quite complex, and while it is in progress the system will likely be vulnerable against Denial of Service attacks, among other things.

## Examples

Examples of well-regarded asymmetric key techniques for varied purposes include:
• Diffie–Hellman key exchange protocol
• DSS (Digital Signature Standard), which incorporates the Digital Signature Algorithm
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...

• ElGamal
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...

• Various elliptic curve
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...

techniques
In cryptography, a password-authenticated key agreement method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.-Types:...

techniques
• Paillier cryptosystem
Paillier cryptosystem
The Paillier cryptosystem, named after and invented by Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult...

• RSA encryption algorithm (PKCS#1
PKCS1
In cryptography, PKCS#1 is the first of a family of standards called Public-Key Cryptography Standards , published by RSA Laboratories. It provides the basic definitions of and recommendations for implementing the RSA algorithm for public-key cryptography...

)
• Cramer–Shoup cryptosystem

Examples of asymmetric key algorithms not widely adopted include:
• NTRUEncrypt
NTRUEncrypt
The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is a lattice-based alternative to RSA and ECC and is based on the shortest vector problem in a lattice...

cryptosystem
• McEliece cryptosystem
McEliece cryptosystem
In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process...

Examples of notable yet insecure asymmetric key algorithms include:
• Merkle–Hellman knapsack cryptosystem

Examples of protocols using asymmetric key algorithms include:
• GPG
GNU Privacy Guard
GNU Privacy Guard is a GPL Licensed alternative to the PGP suite of cryptographic software. GnuPG is compliant with RFC 4880, which is the current IETF standards track specification of OpenPGP...

, an implementation of OpenPGP
• Internet Key Exchange
Internet key exchange
Internet Key Exchange is the protocol used to set up a security association in the IPsec protocol suite. IKE builds upon the Oakley protocol and ISAKMP...

• PGP
Pretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...

• ZRTP
ZRTP
ZRTP is a cryptographic key-agreement protocol to negotiate the keys for encryption between two end points in a Voice over Internet Protocol phone telephony call based on the Real-time Transport Protocol. It uses Diffie-Hellman key exchange and the Secure Real-time Transport Protocol for...

, a secure VoIP protocol
• Secure Socket Layer, now codified as the IETF standard Transport Layer Security
Transport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...

(TLS)
• SILC
SILC (protocol)
SILC is a protocol that provides secure synchronous conferencing services over the Internet.- Components :...

• SSH
Secure Shell
Secure Shell is a network protocol for secure data communication, remote shell services or command execution and other secure network services between two networked computers that it connects via a secure channel over an insecure network: a server and a client...