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. Key pairs are generated with
cryptographic
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
algorithms
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
based on
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
problems termed
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, s ...
s. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.
In a public-key encryption system, anyone with a public key can
encrypt
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can deci ...
a message, yielding a ciphertext, but only those who know the corresponding private key can decrypt the ciphertext to obtain the original message.
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
Metadata is "data that provides information about other data", but not the content of the data, such as the text of a message or the image itself. There are many distinct types of metadata, including:
* Descriptive metadata – the descriptive ...
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.
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 which 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
The Secure Shell Protocol (SSH) is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
SSH applications are based on ...
,
S/MIME S/MIME (Secure/Multipurpose Internet Mail Extensions) is a standard for public key encryption and signing of MIME data. S/MIME is on an IETF standards track and defined in a number of documents, most importantly . It was originally developed by R ...
and
PGP
PGP or Pgp may refer to:
Science and technology
* P-glycoprotein, a type of protein
* Pelvic girdle pain, a pregnancy discomfort
* Personal Genome Project, to sequence genomes and medical records
* Pretty Good Privacy, a computer program for the ...
. Some public key algorithms provide
key distribution and secrecy (e.g.,
Diffie–Hellman key exchange), some provide
digital signatures (e.g.,
Digital Signature Algorithm
The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant ...
), 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. Today's cryptosystems (such as
TLS,
Secure Shell
The Secure Shell Protocol (SSH) is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
SSH applications are based on ...
) 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
Before the mid-1970s, all cipher systems used
symmetric key algorithm
Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between t ...
s, in which the same
cryptographic key
A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the 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
In cryptography, a secure channel is a means of data transmission that is resistant to overhearing and tampering. A confidential channel is a means of data transmission that is resistant to overhearing, or eavesdropping (e.g., reading the conten ...
. 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
Confidentiality involves a set of rules or a promise usually executed through confidentiality agreements that limits the access or places restrictions on certain types of information.
Legal confidentiality
By law, lawyers are often required ...
of a message.
* ''
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. 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
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 ce ...
" which decentralizes authentication by using individual endorsements of links between a user and the public key belonging to that user.
PGP
PGP or Pgp may refer to:
Science and technology
* P-glycoprotein, a type of protein
* Pelvic girdle pain, a pregnancy discomfort
* Personal Genome Project, to sequence genomes and medical records
* Pretty Good Privacy, a computer program for the ...
uses this approach, in addition to lookup in the
domain name system
The Domain Name System (DNS) is a hierarchical and distributed naming system for computers, services, and other resources in the Internet or other Internet Protocol (IP) networks. It associates various information with domain names assigned t ...
(DNS). The
DKIM
DomainKeys Identified Mail (DKIM) is an email authentication method designed to detect forged sender addresses in email (email spoofing), a technique often used in phishing and email spam.
DKIM allows the receiver to check that an email claimed ...
system for digitally signing emails also uses this approach.
Applications
The most obvious application of a public key encryption system is for encrypting communication to provide
confidentiality
Confidentiality involves a set of rules or a promise usually executed through confidentiality agreements that limits the access or places restrictions on certain types of information.
Legal confidentiality
By law, lawyers are often required ...
– 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
Authentication (from ''authentikos'', "real, genuine", from αὐθέντης ''authentes'', "author") is the act of proving an assertion, such as the identity of a computer system user. In contrast with identification, the act of indicati ...
.
Non-repudiation Non-repudiation refers to a situation where a statement's author cannot successfully dispute its authorship or the validity of an associated contract. The term is often seen in a legal setting when the authenticity of a signature is being challenged ...
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
Digital currency (digital money, electronic money or electronic currency) is any currency, money, or money-like asset that is primarily managed, stored or exchanged on digital computer systems, especially over the internet. Types of digital cu ...
,
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.
An important property is that an eavesdropper or m ...
,
time-stamping services and non-repudiation protocols.
Hybrid cryptosystems
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
Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between th ...
to transmit data using the now-shared ''symmetric key'' for a symmetric key encryption algorithm.
PGP
PGP or Pgp may refer to:
Science and technology
* P-glycoprotein, a type of protein
* Pelvic girdle pain, a pregnancy discomfort
* Personal Genome Project, to sequence genomes and medical records
* Pretty Good Privacy, a computer program for the ...
,
SSH
The Secure Shell Protocol (SSH) is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
SSH applications are based on ...
, 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
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 which 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.
Algorithms
All public key schemes are in theory susceptible to a "
brute-force key search attack". However, such an attack is impractical if the amount of computation needed to succeed – termed the "work factor" by
Claude Shannon
Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory".
As a 21-year-o ...
– 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
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 1985. ElGamal encryption is used in t ...
have known attacks that are much faster than the brute-force approach. 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. As with all cryptographic functions, public-key implementations may be vulnerable to
side-channel attack
In computer security, a side-channel attack is any attack based on extra information that can be gathered because of the fundamental way a computer protocol or algorithm is implemented, rather than flaws in the design of the protocol or algori ...
s 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
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't be prevented or monitored by the sender.
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
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
, 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
An Internet service provider (ISP) is an organization that provides services for accessing, using, or participating in the Internet. ISPs can be organized in various forms, such as commercial, community-owned, non-profit, or otherwise private ...
(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.
Public key infrastructure
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 browser
A web browser is application software for accessing websites. When a user requests a web page from a particular website, the browser retrieves its files from a web server and then displays the page on the user's screen. Browsers are used on ...
s, 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. In an alternative scenario rarely discussed, 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.
Despite its theoretical and potential problems, this approach is widely used. Examples include
TLS and its predecessor
SSL, which are commonly used to provide security for web browser transactions (for example, to securely send credit card details to an online store).
Aside from the resistance to attack of a particular key pair, the security of the certification
hierarchy
A hierarchy (from Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy is an important ...
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
In cryptography and computer security, a man-in-the-middle, monster-in-the-middle, machine-in-the-middle, monkey-in-the-middle, meddler-in-the-middle, manipulator-in-the-middle (MITM), person-in-the-middle (PITM) or adversary-in-the-middle (AiTM) ...
" is possible, making any subordinate certificate wholly insecure.
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
The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a variant ...
*
ElGamal
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 1985. ElGamal encryption is used in th ...
*
Elliptic-curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide eq ...
**
Elliptic Curve Digital Signature Algorithm
In cryptography, the Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant of the Digital Signature Algorithm (DSA) which uses elliptic-curve cryptography.
Key and signature-size
As with elliptic-curve cryptography in general, the b ...
(ECDSA)
**
Elliptic-curve Diffie–Hellman Elliptic-curve Diffie–Hellman (ECDH) is a key agreement protocol that allows two parties, each having an elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be directly used as ...
(ECDH)
**
Ed25519
In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.
It is designed to be faster than existing digital signature scheme ...
and
Ed448
In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.
It is designed to be faster than existing digital signature scheme ...
(
EdDSA)
**
X25519
X, or x, is the twenty-fourth and third-to-last letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''"ex"'' (pronounced ), ...
and
X448 (ECDH/EdDH)
*Various
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.
An important property is that an eavesdropper or m ...
techniques
*
Paillier cryptosystem
The Paillier cryptosystem, invented by and named after 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. The ...
*
RSA encryption algorithm (
PKCS#1)
*
Cramer–Shoup cryptosystem
*
YAK authenticated key agreement protocol
Examples of asymmetric key algorithms not yet widely adopted include:
*
NTRUEncrypt cryptosystem
*
Kyber
Kyber is a key encapsulation method (KEM) designed to be resistant to cryptanalysis, cryptanalytic attacks with future powerful quantum computing, quantum computers. It is used to establish a shared secret between two communicating parties without ...
*
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. The algorithm has never gained much acceptance in ...
Examples of notable – yet insecure – asymmetric key algorithms include:
*
Merkle–Hellman knapsack cryptosystem The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems. It was published by Ralph Merkle and Martin Hellman in 1978. A polynomial time attack was published by Adi Shamir in 1984. As a result, the cryptosyste ...
Examples of protocols using asymmetric key algorithms include:
*
S/MIME S/MIME (Secure/Multipurpose Internet Mail Extensions) is a standard for public key encryption and signing of MIME data. S/MIME is on an IETF standards track and defined in a number of documents, most importantly . It was originally developed by R ...
*
GPG, an implementation of
OpenPGP
Pretty Good Privacy (PGP) is an encryption program that provides cryptographic privacy and authentication for data communication. PGP is used for signing, encrypting, and decrypting texts, e-mails, files, directories, and whole disk partiti ...
, and an Internet Standard
*
EMV
EMV is a payment method based on a technical standard for smart payment cards and for payment terminals and automated teller machines which can accept them. EMV stands for " Europay, Mastercard, and Visa", the three companies that created th ...
, EMV Certificate Authority
*
IPsec
In computing, Internet Protocol Security (IPsec) is a secure network protocol suite that authenticates and encrypts packets of data to provide secure encrypted communication between two computers over an Internet Protocol network. It is used in ...
*
PGP
PGP or Pgp may refer to:
Science and technology
* P-glycoprotein, a type of protein
* Pelvic girdle pain, a pregnancy discomfort
* Personal Genome Project, to sequence genomes and medical records
* Pretty Good Privacy, a computer program for the ...
*
ZRTP
ZRTP (composed of Z and Real-time Transport Protocol) is a cryptographic key-agreement protocol to negotiate the keys for encryption between two end points in a Voice over IP (VoIP) phone telephony call based on the Real-time Transport Protocol. ...
, a secure
VoIP
Voice over Internet Protocol (VoIP), also called IP telephony, is a method and group of technologies for the delivery of voice communications and multimedia sessions over Internet Protocol (IP) networks, such as the Internet. The terms Internet t ...
protocol
*
Transport Layer Security
Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securi ...
standardized by
IETF
The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
and its predecessor
Secure Socket Layer
Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securi ...
*
SILC
*
SSH
The Secure Shell Protocol (SSH) is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
SSH applications are based on ...
*
Bitcoin
Bitcoin ( abbreviation: BTC; sign: ₿) is a decentralized digital currency that can be transferred on the peer-to-peer bitcoin network. Bitcoin transactions are verified by network nodes through cryptography and recorded in a public distr ...
*
Off-the-Record Messaging
History
During the early
history of cryptography
Cryptography, the use of codes and ciphers to protect secrets, began thousands of years ago. Until recent decades, it has been the story of what might be called classical cryptography — that is, of methods of encryption that use pen and paper, ...
, 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
In his 1874 book ''The Principles of Science'',
William Stanley Jevons
William Stanley Jevons (; 1 September 183513 August 1882) was an English economist and logician.
Irving Fisher described Jevons's book ''A General Mathematical Theory of Political Economy'' (1862) as the start of the mathematical method in ec ...
wrote:
Can the reader say what two numbers multiplied together will produce the number 8616460799? I think it unlikely that anyone but myself will ever know.
Here he described the relationship of
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, s ...
s to cryptography, and went on to discuss specifically the
factorization
In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
problem used to create a
trapdoor function
In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trap ...
. 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."
Classified discovery
In 1970,
James H. Ellis, a British cryptographer at the UK
Government Communications Headquarters
Government Communications Headquarters, commonly known as GCHQ, is an intelligence and security organisation responsible for providing signals intelligence (SIGINT) and information assurance (IA) to the government and armed forces of the Un ...
(GCHQ), conceived of the possibility of "non-secret encryption", (now called public key cryptography), but could see no way to implement it. In 1973, his colleague
Clifford Cocks
Clifford Christopher Cocks (born 28 December 1950) is a British mathematician and cryptographer.
In 1973, while working at the United Kingdom Government Communications Headquarters (GCHQ), he invented a public-key cryptography algorithm equiv ...
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
The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
.
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
The European Organization for Nuclear Research, known as CERN (; ; ), is an intergovernmental organization that operates the largest particle physics laboratory in the world. Established in 1954, it is based in a northwestern suburb of Gene ...
, its adaptation and adoption for the Arpanet
The Advanced Research Projects Agency Network (ARPANET) was the first wide-area packet-switched network with distributed control and one of the first networks to implement the TCP/IP protocol suite. Both technologies became the technical fou ...
... did public key cryptography realise its full potential.
—Ralph Benjamin
Ralph Benjamin (17 November 1922 – 7 May 2019) was a British scientist and electrical engineer.
Biography
Benjamin was born in Darmstadt, Germany. He attended boarding school in Switzerland from 1937, and was sent to England in 1939 as ...
These discoveries were not publicly acknowledged for 27 years, until the research was declassified by the British government in 1997.
Public discovery
In 1976, an asymmetric key cryptosystem was published by
Whitfield Diffie
Bailey Whitfield 'Whit' Diffie (born June 5, 1944), ForMemRS, is an American cryptographer and mathematician and one of the pioneers of public-key cryptography along with Martin Hellman and Ralph Merkle. Diffie and Hellman's 1976 paper ''New Dir ...
and
Martin Hellman
Martin Edward Hellman (born October 2, 1945) is an American cryptologist and mathematician, best known for his involvement with public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle. Hellman is a longtime contributor to ...
who, influenced by
Ralph Merkle
Ralph C. Merkle (born February 2, 1952) is a computer scientist and mathematician. He is one of the inventors of public-key cryptography, the inventor of cryptographic hashing, and more recently a researcher and speaker on cryonics.
Contribution ...
'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 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.
In 1977, a generalization of Cocks' scheme was independently invented by
Ron Rivest
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial In ...
,
Adi Shamir
Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identifi ...
and
Leonard Adleman
Leonard Adleman (born December 31, 1945) is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award, often called the Nobel prize of Computer science. He is also kno ...
, all then at
MIT
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...
. The latter authors published their work in 1978 in
Martin Gardner
Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of Lew ...
's
Scientific American
''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...
column, and the algorithm came to be known as
RSA, from their initials.
RSA uses
exponentiation modulo a product of two very large
primes
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, 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 (though prime factorization may be obtained through brute-force attacks; this grows much more difficult the larger the prime factors are). A description of the algorithm was published in the
Mathematical Games
A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games ne ...
column in the August 1977 issue of
Scientific American
''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...
.
Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed, including the
Rabin cryptosystem
The Rabin cryptosystem is a family of public-key encryption schemes
based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.
The Rabin trapdoor function has the advantage that invert ...
,
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 1985. ElGamal encryption is used in t ...
,
DSA - and
elliptic curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide ...
.
See also
*
Books on cryptography
Books on cryptography have been published sporadically and with highly variable quality for a long time. This is despite the tempting, though superficial, paradox that secrecy is of the essence in sending confidential messages — see Kerckhoffs ...
*
GNU Privacy Guard
GNU Privacy Guard (GnuPG or GPG) is a free-software replacement for Symantec's PGP cryptographic software suite. The software is compliant with RFC 4880, the IETF standards-track specification of OpenPGP. Modern versions of PGP are interoperable ...
*
Identity-based encryption ID-based encryption, or identity-based encryption (IBE), is an important primitive of ID-based cryptography. As such it is a type of public-key encryption in which the public key of a user is some unique information about the identity of the user ( ...
(IBE)
*
Key escrow
*
Key-agreement protocol In cryptography, a key-agreement protocol is a protocol whereby two or more parties can agree on a key in such a way that both influence the outcome. If properly done, this precludes undesired third parties from forcing a key choice on the agreeing ...
*
PGP word list The PGP Word List ("Pretty Good Privacy word list", also called a biometric word list for reasons explained below) is a list of words for conveying data bytes in a clear unambiguous way via a voice channel. They are analogous in purpose to the NATO ...
*
Post-quantum cryptography
In cryptography, post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack ...
*
Pretty Good Privacy
Pretty Good Privacy (PGP) is an encryption program that provides cryptographic privacy and authentication for data communication. PGP is used for signing, encrypting, and decrypting texts, e-mails, files, directories, and whole disk partition ...
*
Pseudonym
A pseudonym (; ) or alias () is a fictitious name that a person or group assumes for a particular purpose, which differs from their original or true name (orthonym). This also differs from a new name that entirely or legally replaces an individua ...
*
Public key fingerprint
In public-key cryptography, a public key fingerprint is a short sequence of bytes used to identify a longer public key. Fingerprints are created by applying a cryptographic hash function to a public key. Since fingerprints are shorter than the k ...
*
Public key infrastructure (PKI)
*
Quantum computing
*
Quantum cryptography
Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution ...
*
Secure Shell
The Secure Shell Protocol (SSH) is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
SSH applications are based on ...
(SSH)
*
Symmetric-key algorithm
*
Threshold cryptosystem A threshold cryptosystem, the basis for the field of threshold cryptography, is a cryptosystem that protects information by encrypting it and distributing it among a cluster of fault-tolerant computers. The message is encrypted using a public key, ...
*
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 ce ...
Notes
References
*. The first two sections contain a very good introduction to public-key cryptography.
*
*
*
IEEE 1363: Standard Specifications for Public-Key Cryptography* Christof Paar, Jan Pelzl
"Introduction to Public-Key Cryptography" Chapter 6 of "Understanding Cryptography, A Textbook for Students and Practitioners". (companion web site contains online cryptography course that covers public-key cryptography), Springer, 2009.
*
External links
Oral history interview with Martin Hellman Charles Babbage Institute
The IT History Society (ITHS) is an organization that supports the history and scholarship of information technology by encouraging, fostering, and facilitating archival and historical research. Formerly known as the Charles Babbage Foundation, ...
, University of Minnesota. Leading cryptography scholar
Martin Hellman
Martin Edward Hellman (born October 2, 1945) is an American cryptologist and mathematician, best known for his involvement with public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle. Hellman is a longtime contributor to ...
discusses the circumstances and fundamental insights of his invention of public key cryptography with collaborators
Whitfield Diffie
Bailey Whitfield 'Whit' Diffie (born June 5, 1944), ForMemRS, is an American cryptographer and mathematician and one of the pioneers of public-key cryptography along with Martin Hellman and Ralph Merkle. Diffie and Hellman's 1976 paper ''New Dir ...
and
Ralph Merkle
Ralph C. Merkle (born February 2, 1952) is a computer scientist and mathematician. He is one of the inventors of public-key cryptography, the inventor of cryptographic hashing, and more recently a researcher and speaker on cryonics.
Contribution ...
at Stanford University in the mid-1970s.
An account of how GCHQ kept their invention of PKE secret until 1997
{{Authority control
Anonymity networks
Cryptographic software
Cryptographic protocols
Cryptography
Banking technology
Public key infrastructure
Network architecture