DUST ATTACK

Public-key cryptography

Public-key cryptography
Public-key cryptography
Public-key cryptography
Public-key cryptography

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key.[1][2] Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.[3]

In a public-key encryption system, anyone with a public key can encrypt a message, yielding a ciphertext, but only those who know the corresponding private key can decrypt the ciphertext to obtain the original message.[4]

For example, a journalist can publish the public key of an encryption key pair on a web site so that sources can send secret messages to the news organization in ciphertext. Only the journalist who knows the corresponding private key can decrypt the ciphertexts to obtain the sources’ messages—an eavesdropper reading email on its way to the journalist cannot decrypt the ciphertexts. However, public-key encryption does not conceal metadata like what computer a source used to send a message, when they sent it, or how long it is. Public-key encryption on its own also does not tell the recipient anything about who sent a message—it just conceals the content of a message in a ciphertext that can only be decrypted with the private key.

In a digital signature system, a sender can use a private key together with a message to create a signature. Anyone with the corresponding public key can verify whether the signature matches the message, but a forger who does not know the private key cannot find any message/signature pair that will pass verification with the public key.[5][6]

For example, a software publisher can create a signature key pair and include the public key in software installed on computers. Later, the publisher can distribute an update to the software signed using the private key, and any computer receiving an update can confirm it is genuine by verifying the signature using the public key. As long as the software publisher keeps the private key secret, even if a forger can distribute malicious updates to computers, they cannot convince the computers that any malicious updates are genuine.

Public key algorithms are fundamental security primitives in modern cryptosystems, including applications and protocols that offer assurance of the confidentiality, authenticity and non-repudiability of electronic communications and data storage. They underpin numerous Internet standards, such as Transport Layer Security (TLS), SSH, S/MIME and PGP. Some public key algorithms provide key distribution and secrecy (e.g., Diffie–Hellman key exchange), some provide digital signatures (e.g., Digital Signature Algorithm), and some provide both (e.g., RSA). Compared to symmetric encryption, asymmetric encryption is rather slower than good symmetric encryption, too slow for many purposes.[7] Today’s cryptosystems (such as TLS, Secure Shell) use both symmetric encryption and asymmetric encryption, often by using asymmetric encryption to securely exchange a secret key, which is then used for symmetric encryption.

Description[edit]

Before the mid-1970s, all cipher systems used 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. 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 – for instance, via a secure channel. This requirement is never trivial and very rapidly becomes unmanageable as the number of participants increases, or when secure channels are not available, 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.

By contrast, in a public key system, the public keys can be disseminated widely and openly, and only the corresponding private keys need be kept secret by its owner.

Two of the best-known uses of public key cryptography are:

  • Public key encryption, in which a message is encrypted with the intended recipient’s public key. For properly chosen and used algorithms, messages cannot in practice be decrypted by anyone who does not possess the matching private key, who is thus presumed to be the owner of that key and so the person associated with the public key. This can be used to ensure confidentiality of a message.[8]
  • Digital signatures, in which a message is signed with the sender’s private key and can be verified by anyone who has access to the sender’s public key.[9] This verification proves that the sender had access to the private key, and therefore is very likely to be the person associated with the public key. It also proves that the signature was prepared for that exact message, since verification will fail for any other message one could devise without using the private key.

One important issue is confidence/proof that a particular public key is authentic, i.e. that it is correct and belongs to the person or entity claimed, and has not been tampered with or replaced by some (perhaps malicious) third party. There are several possible approaches, including:

A public key infrastructure (PKI), in which one or more third parties – known as certificate authorities – certify ownership of key pairs. TLS relies upon this. This implies that the PKI system (software, hardware, and management) is trust-able by all involved.

A “web of trust” that decentralizes authentication by using individual endorsements of links between a user and the public key belonging to that user. PGP uses this approach, in addition to lookup in the domain name system (DNS). The DKIM system for digitally signing emails also uses this approach.

Applications[edit]

The most obvious application of a public key encryption system is for encrypting communication to provide confidentiality – a message that a sender encrypts using the recipient’s public key, which can be decrypted only by the recipient’s paired private key.

Another application in public key cryptography is the digital signature. Digital signature schemes can be used for sender authentication.

Non-repudiation systems use digital signatures to ensure that one party cannot successfully dispute its authorship of a document or communication.

Further applications built on this foundation include: digital cash, password-authenticated key agreement, time-stamping services and non-repudiation protocols.

Hybrid cryptosystems[edit]

Because asymmetric key algorithms are nearly always much more computationally intensive than symmetric ones, it is common to use a public/private asymmetric key-exchange algorithm to encrypt and exchange a symmetric key, which is then used by symmetric-key cryptography to transmit data using the now-shared symmetric key for a symmetric key encryption algorithm. PGP, SSH, and the SSL/TLS family of schemes use this procedure; they are thus called hybrid cryptosystems. The initial asymmetric cryptography-based key exchange to share a server-generated symmetric key from the server to client has the advantage of not requiring that a symmetric key be pre-shared manually, such as on printed paper or discs transported by a courier, while providing the higher data throughput of symmetric key cryptography over asymmetric key cryptography for the remainder of the shared connection.

Weaknesses[edit]

As with all security-related systems, it is important to identify potential weaknesses. Aside from poor choice of an asymmetric key algorithm (there are few that are widely regarded as satisfactory) or too short a key length, the chief security risk is that the private key of a pair becomes known. All security of messages, authentication, etc., will then be lost.

Additionally, with the advent of quantum computing, many asymmetric key algorithms are considered vulnerable to attacks, and new quantum-resistant schemes are being developed to overcome the problem.[10][11]

Algorithms[edit]

All public key schemes are in theory susceptible to a “brute-force key search attack“.[12] However, such an attack is impractical if the amount of computation needed to succeed – termed the “work factor” by Claude Shannon – is out of reach of all potential attackers. In many cases, the work factor can be increased by simply choosing a longer key. But other algorithms may inherently have much lower work factors, making resistance to a brute-force attack (e.g., from longer keys) irrelevant. Some special and specific algorithms have been developed to aid in attacking some public key encryption algorithms; both RSA and ElGamal encryption have known attacks that are much faster than the brute-force approach.[13] None of these are sufficiently improved to be actually practical, however.

Major weaknesses have been found for several formerly promising asymmetric key algorithms. The “knapsack packing” algorithm was found to be insecure after the development of a new attack.[14] As with all cryptographic functions, public-key implementations may be vulnerable to side-channel attacks that exploit information leakage to simplify the search for a secret key. These are often independent of the algorithm being used. Research is underway to both discover, and to protect against, new attacks.

Alteration of public keys[edit]

Another potential security vulnerability in using asymmetric keys is the possibility of a “man-in-the-middle” attack, in which the communication of public keys is intercepted by a third party (the “man in the middle”) and then modified to provide different public keys instead. Encrypted messages and responses must, in all instances, be intercepted, decrypted, and re-encrypted by the attacker using the correct public keys for the different communication segments so as to avoid suspicion.

A communication is said to be insecure where data is transmitted in a manner that allows for interception (also called “sniffing“). These terms refer to reading the sender’s private data in its entirety. A communication is particularly unsafe when interceptions can not be prevented or monitored by the sender.[15]

A man-in-the-middle attack can be difficult to implement due to the complexities of modern security protocols. However, the task becomes simpler when a sender is using insecure media such as public networks, the Internet, or wireless communication. In these cases an attacker can compromise the communications infrastructure rather than the data itself. A hypothetical malicious staff member at an Internet Service Provider (ISP) might find a man-in-the-middle attack relatively straightforward. Capturing the public key would only require searching for the key as it gets sent through the ISP’s communications hardware; in properly implemented asymmetric key schemes, this is not a significant risk.

In some advanced man-in-the-middle attacks, one side of the communication will see the original data while the other will receive a malicious variant. Asymmetric man-in-the-middle attacks can prevent users from realizing their connection is compromised. This remains so even when one user’s data is known to be compromised because the data appears fine to the other user. This can lead to confusing disagreements between users such as “it must be on your end!” when neither user is at fault. Hence, man-in-the-middle attacks are only fully preventable when the communications infrastructure is physically controlled by one or both parties; such as via a wired route inside the sender’s own building. In summation, public keys are easier to alter when the communications hardware used by a sender is controlled by an attacker.[16][17][18]

Public key infrastructure[edit]

One approach to prevent such attacks involves the use of a public key infrastructure (PKI); a set of roles, policies, and procedures needed to create, manage, distribute, use, store and revoke digital certificates and manage public-key encryption. However, this has potential weaknesses.

For example, the certificate authority issuing the certificate must be trusted by all participating parties to have properly checked the identity of the key-holder, to have ensured the correctness of the public key when it issues a certificate, to be secure from computer piracy, and to have made arrangements with all participants to check all their certificates before protected communications can begin. Web browsers, for instance, are supplied with a long list of “self-signed identity certificates” from PKI providers – these are used to check the bona fides of the certificate authority and then, in a second step, the certificates of potential communicators. An attacker who could subvert one of those certificate authorities 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. An attacker who penetrates an authority’s servers and obtains its store of certificates and keys (public and private) would be able to spoof, masquerade, decrypt, and forge transactions without limit, assuming that they were able to place themselves in the communication stream.

Despite its theoretical and potential problems, Public key infrastructure is widely used. Examples include TLS and its predecessor SSL, which are commonly used to provide security for web browser transactions (for example, most websites utilize TLS for HTTPS).

Aside from the resistance to attack of a particular key pair, the security of the certification hierarchy 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” is possible, making any subordinate certificate wholly insecure.

Examples[edit]

Examples of well-regarded asymmetric key techniques for varied purposes include:

Examples of asymmetric key algorithms not yet widely adopted include:

Examples of notable – yet insecure – asymmetric key algorithms include:

Examples of protocols using asymmetric key algorithms include:

History[edit]

During the early history of cryptography, two parties would rely upon a key that they would exchange by means of a secure, but non-cryptographic, method such as a face-to-face meeting, or a trusted courier. This key, which both parties must then keep absolutely secret, could then be used to exchange encrypted messages. A number of significant practical difficulties arise with this approach to distributing keys.

Anticipation[edit]

In his 1874 book The Principles of Science, William Stanley Jevons[19] wrote:

Can the reader say what two numbers multiplied together will produce the number 8616460799?[20] I think it unlikely that anyone but myself will ever know.[21]

Here he described the relationship of one-way functions to cryptography, and went on to discuss specifically the factorization problem used to create a trapdoor function. In July 1996, mathematician Solomon W. Golomb said: “Jevons anticipated a key feature of the RSA Algorithm for public key cryptography, although he certainly did not invent the concept of public key cryptography.”[22]

Classified discovery[edit]

In 1970, James H. Ellis, a British cryptographer at the UK Government Communications Headquarters (GCHQ), conceived of the possibility of “non-secret encryption”, (now called public key cryptography), but could see no way to implement it.[23][24] In 1973, his colleague Clifford Cocks implemented what has become known as the RSA encryption algorithm, giving a practical method of “non-secret encryption”, and in 1974 another GCHQ mathematician and cryptographer, Malcolm J. Williamson, developed what is now known as Diffie–Hellman key exchange. The scheme was also passed to the US’s National Security Agency.[25] Both organisations had a military focus and only limited computing power was available in any case; the potential of public key cryptography remained unrealised by either organization:

I judged it most important for military use … if you can share your key rapidly and electronically, you have a major advantage over your opponent. Only at the end of the evolution from Berners-Lee designing an open internet architecture for CERN, its adaptation and adoption for the Arpanet … did public key cryptography realise its full potential.

—Ralph Benjamin[25]

These discoveries were not publicly acknowledged for 27 years, until the research was declassified by the British government in 1997.[26]

Public discovery[edit]

In 1976, an asymmetric key cryptosystem was published by Whitfield Diffie and Martin Hellman who, influenced by Ralph Merkle‘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.[27] This was the first published practical method for establishing a shared secret-key over an authenticated (but not confidential) 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 only published in 1978. This makes asymmetric encryption a rather new field in cryptography although cryptography itself dates back more than 2,000 years.[28]

In 1977, a generalization of Cocks’s scheme was independently invented by Ron Rivest, Adi Shamir and Leonard Adleman, all then at MIT. The latter authors published their work in 1978 in Martin Gardner‘s Scientific American column, and the algorithm came to be known as RSA, from their initials.[29] RSA uses exponentiation modulo a product of two very large primes, to encrypt and decrypt, performing both public key encryption and public key digital signatures. Its security is connected to the extreme difficulty of factoring large integers, a problem for which there is no known efficient general technique. A description of the algorithm was published in the Mathematical Games column in the August 1977 issue of Scientific American.[30]

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed, including the Rabin cryptosystem, ElGamal encryption, DSA and ECC.

When a transaction is initiated by a user to send, say bitcoins, to another person, the transaction has to be broadcast to the network where distributed nodes confirm the validity of the transaction before finalizing it and recording it on the blockchain.

Before the transaction is broadcast, it is digitally signed using the private key. The signature proves ownership of the private key, although it does not divulge the details of the private key to anyone. Since a public key is fashioned from the private key, the user’s public key is used to prove that the digital signature came from his private key. Once the transaction has been verified as valid, the funds are sent to the recipient’s public address.

The public address is a hashed version of the public key. Because the public key is made up of an extremely long string of numbers, it is compressed and shortened to form the public address. In effect, the private key generates the public key, which, in turn, generates the public address.

When two people enter into an agreement where one sends the other tokens or coins, they reveal their public addresses to each other. The public address is like a bank account number. The sender needs the number to be able to send the funds to the recipient who will then be able to spend or withdraw it with his private key. The recipient can also verify the sender’s batch of coins using the sender’s public address that will be displayed on his or her screen.

Special Considerations

Although the public key and address are worked out from the private key, the reverse case is nearly impossible.

The cryptocurrency network stays secure by using complicated mathematical functions to ensure that a private key is not able to be worked out from the public key, especially since the public key and its hash version are seen by everyone on the network.

Since it’s impossible to regenerate the private key from public key or address, if a user loses his private key, any bitcoin or altcoin located at his public address will be inaccessible forever. On the other hand, a user who loses his public key can have it recreated with the private key.

Public-key cryptography is a cryptographic approach which involves the use of asymmetric key algorithms instead of or in addition to symmetric key algorithms. Unlike symmetric key algorithms, it does not require a secure initial exchange of one or more secret keys to both sender and receiver. The asymmetric key algorithms are used to create a mathematically related key pair: a secret private key and a published public key. Use of these keys allows protection of the authenticity of a message by creating a digital signature of a message using the private key, which can be verified using the public key. It also allows protection of the confidentiality and integrity of a message, by public key encryption, encrypting the message using the public key, which can only be decrypted using the private key.

Public key cryptography is a fundamental and widely used technology around the world. It is the approach which is employed by many cryptographic algorithms and cryptosystems. It underpins such Internet standards as Transport Layer Security (TLS) (successor to SSL), PGP, and GPG.

How it works

The distinguishing technique used in public key cryptography is the use of asymmetric key algorithms, where the key used to encrypt 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 only be decrypted with the corresponding private key. The keys are related mathematically, but the private key cannot feasibly (ie. in actual or projected practice) be derived from the public key. The discovery of algorithms that could produce public/private key pairs revolutionized the practice of cryptography beginning in the middle 1970s.

In contrast, symmetric-key algorithms, variations of which have 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, and the SSL/TLS family of schemes do this, for instance, and are thus called hybrid cryptosystems.

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—presumably, this will be the owner of that key and the person associated with the public key used. This is used for confidentiality.
  • Digital signatures: 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, see also message digest.

An analogy to public-key encryption is that of a locked mailbox 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. 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 (PKI), in which one or more third parties, known as certificate authorities, certify ownership of key pairs. Another approach, used by PGP, is the “web of trust” method to ensure authenticity of key pairs.

History

During the early history of cryptography, two parties would agree 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. 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[1] described the relationship of one-way functions to cryptography and went on to discuss specifically the factorization problem used to create the trapdoor function in the RSA system. In July 1996, one observer[2] 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,[3] 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) 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 and Martin Hellman, who, influenced by Ralph Merkle’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, Clifford Cocks, and Malcolm Williamson at the Government Communications Headquarters (GCHQ) in the UK in 1973[4]. 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”.

A generalisation of Cocks’ scheme was independently invented in 1977 by Rivest, Shamir and Adleman, all then at MIT. 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 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, a problem for which there is no known efficient (i.e., practicably fast) general technique. In 1979 Michael O. Rabin published a related cryptosystem 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 (invented by Taher ElGamal) relies on the (similar, and related) difficulty of the discrete logarithm problem, as does the closely related DSA developed at the US National Security Agency (NSA) and published by NIST as a proposed standard. The introduction of elliptic curve cryptography by Neal Koblitz and Victor Miller independently and simultaneously in the mid-1980s has yielded new public-key algorithms based on the discrete logarithm problem. Although mathematically more complex, elliptic curves provide smaller key sizes 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 the product of two large primes or computing discrete logarithms. 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.

In contrast to the one-time pad, no public-key encryption scheme has been shown to be secure against eavesdroppers with unlimited computational power. Proofs of security for asymmetric key cryptography therefore hold only with respect to computationally-limited adversaries, and can give guarantees (relative to particular mathematical assumptions) of the form “the scheme cannot be broken using a desktop computer in 1000 years”, or “this algorithm is secure if no improved method of (for instance, integer factoring) is found”.

The most obvious application of a public key encryption system is confidentiality; a message which 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 schemes. Digital signature schemes can be used for sender authentication and non-repudiation. 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 only be computed 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 only needs to know 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) the algorithm does not resemble any encryption scheme.

To achieve authentication, and confidentiality, the sender could first sign the message using his private key, then encrypt the message and 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, multi-party key agreement, time stamping service, non-repudiation protocols, etc.

Practical considerations

A postal analogy

An analogy which can be used to understand the advantages of an asymmetric system is to imagine two people, Alice and Bob, 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 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 read 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 is typically used during key exchange.

Actual algorithms—two linked keys

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 which 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.

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 can be proven to be secure against any adversary, no matter how much computing power is available. Unfortunately, there is no public-key scheme with this property, since all public-key schemes are susceptible to 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 have known attacks which 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 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 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). 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 or wireless communications). A malicious staff member at Alice or Bob’s ISP might find it quite easy to carry out.

One approach to prevent such attacks is the use of a certificate authority, a trusted third party 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 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 browsers, 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, 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 cryptosystems for reasons of efficiency; in such a cryptosystem, a shared secret key (“session key”) 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; these allow the validity of the association to be formally verified by reference to a trusted third party, either in the form of a hierarchical certificate authority (e.g., X.509), a local trust model (e.g., SPKI), or a web of trust scheme (e.g., that originally built into PGP and GPG 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 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 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 which 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 which 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 which 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 essentially 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 obviously 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 both authority to revoke and to 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.

Spreading the revocation

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) to 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 that 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, ideally, 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 which 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 which 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. 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.

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 attacksTemplate:Citation needed, among other things.

Examples

Examples of well-regarded asymmetric key techniques for varied purposes include:

Examples of asymmetric key algorithms not widely adopted include:

Examples of notable yet insecure asymmetric key algorithms include:

Examples of protocols using asymmetric key algorithms include:

  • GPG, an implementation of OpenPGP
  • Internet Key Exchange
  • PGP
  • ZRTP, a secure VoIP protocol
  • Secure Socket Layer, now implemented as an IETF standard TLS
  • SILC
  • SSH

See also

Template:Portal

Notes

  1. ↑ Jevons, William Stanley, The Principles of Science: A Treatise on Logic and Scientific Method p. 141, Macmillan & Co., London, 1874, 2nd ed. 1877, 3rd ed. 1879. Reprinted with a foreword by Ernst Nagel, Dover Publications, New York, NY, 1958.
  2. ↑ Template:Cite journal
  3. ↑ The 1890s date for the publication of Jevons’ book in this quotation is incorrect.
  4. ↑ http://www.gchq.gov.uk/history/pke.html

References

External links

Cryptography navboxBlock ciphersAES – Blowfish – DES – Serpent – Twofish

Template:Link FA

af:Publiekesleutelkriptografie ar:تشفير باستخدام المفتاح المعلن bn:পাবলিক কী ক্রিপ্টোগ্রাফি ca:Criptografia de clau pública cs:Asymetrická kryptografie de:Asymmetrisches Kryptosystem el:Κρυπτογράφηση Δημόσιου Κλειδιού es:Criptografía asimétrica eu:Kriptografia asimetriko fa:رمزنگاری کلید عمومی fr:Cryptographie asymétrique ko:공개 키 암호 방식 it:Crittografia asimmetrica he:מפתח ציבורי ka:ასიმეტრიული კრიპტოსისტემა lt:Viešojo rakto kriptografija hu:Nyílt kulcsú titkosítás nl:Asymmetrische cryptografie ja:公開鍵暗号 no:Asymmetrisk kryptering nn:Asymmetrisk kryptering pl:Kryptografia klucza publicznego pt:Criptografia de chave pública ro:Criptografie asimetrică ru:Криптосистема с открытым ключом sr:Асиметрична криптографија sv:Asymmetrisk kryptering th:การเข้ารหัสลับแบบกุญแจอสมมาตร tr:Açık anahtarlı şifreleme uk:Асиметричні алгоритми шифрування ur:عوامی کنجی تخطیط صفر vi:Mật mã hóa khóa công khai zh:公开密钥加密