Cryptographic system with public and private keys
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.
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 a signature that passes verification with the public key on one message will not pass verification with the public key on other messages.
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
" 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, there are various potential weaknesses in public-key cryptography. 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.
[
citation needed
]
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.
[13]
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.
[
citation needed
]
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.
[14]
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.
[
citation needed
]
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.
[15]
[16]
[17]
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.
Unencrypted metadata
[
edit
]
Most of the available public-key encryption software does not conceal
metadata
in the message header, which might include the identities of the sender and recipient, the sending date, subject field, and the software they use etc. Rather, only the body of the message is concealed and can only be decrypted with the private key of the intended recipient. This means that a third party could construct quite a detailed model of participants in a communication network, along with the subjects being discussed, even if the message body itself is hidden.
However, there has been a recent demonstration of messaging with encrypted headers, which obscures the identities of the sender and recipient, and significantly reduces the available metadata to a third party.
[18]
The concept is based around an open repository containing separately encrypted metadata blocks and encrypted messages. Only the intended recipient is able to decrypt the metadata block, and having done so they can identify and download their messages and decrypt them. Such a messaging system is at present in an experimental phase and not yet deployed. Scaling this method would reveal to the third party only the inbox server being used by the recipient and the timestamp of sending and receiving. The server could be shared by thousands of users, making social network modelling much more challenging.
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
wrote:
[19]
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.
[19]
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."
[21]
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.
[22]
[23]
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
.
[24]
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
[24]
These discoveries were not publicly acknowledged for 27 years, until the research was declassified by the British government in 1997.
[25]
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
.
[26]
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.
[27]
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.
[28]
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
.
[29]
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
.
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:
See also
[
edit
]
Notes
[
edit
]
- ^
R. Shirey (August 2007).
Internet Security Glossary, Version 2
. Network Working Group.
doi
:
10.17487/RFC4949
.
RFC
4949
.
Informational.
- ^
Bernstein, Daniel J.; Lange, Tanja (14 September 2017).
"Post-quantum cryptography"
.
Nature
.
549
(7671): 188?194.
Bibcode
:
2017Natur.549..188B
.
doi
:
10.1038/nature23461
.
ISSN
0028-0836
.
PMID
28905891
.
S2CID
4446249
.
- ^
Stallings, William (3 May 1990).
Cryptography and Network Security: Principles and Practice
. Prentice Hall. p. 165.
ISBN
9780138690175
.
- ^
Menezes, Alfred J.
;
van Oorschot, Paul C.
;
Vanstone, Scott A.
(October 1996). "8: Public-key encryption".
Handbook of Applied Cryptography
(PDF)
. CRC Press. pp. 283?319.
ISBN
0-8493-8523-7
. Retrieved
8 October
2022
.
- ^
Menezes, Alfred J.
;
van Oorschot, Paul C.
;
Vanstone, Scott A.
(October 1996). "8: Public-key encryption".
Handbook of Applied Cryptography
(PDF)
. CRC Press. pp. 425?488.
ISBN
0-8493-8523-7
. Retrieved
8 October
2022
.
- ^
Bernstein, Daniel J.
(1 May 2008). "Protecting communications against forgery".
Algorithmic Number Theory
(PDF)
. Vol. 44. MSRI Publications. §5: Public-key signatures, pp. 543?545
. Retrieved
8 October
2022
.
- ^
Alvarez, Rafael; Caballero-Gil, Candido; Santonja, Juan; Zamora, Antonio (27 June 2017).
"Algorithms for Lightweight Key Exchange"
.
Sensors
.
17
(7): 1517.
doi
:
10.3390/s17071517
.
ISSN
1424-8220
.
PMC
5551094
.
PMID
28654006
.
- ^
"Asymmetric encryption"
.
IONOS Digitalguide
. Retrieved
2 June
2022
.
- ^
Mihir, Bellare; Goldwasser, Shafi.
"Chapter 10: Digital signatures"
(PDF)
.
Lecture Notes on Cryptography
.
- ^
Escribano Pablos, Jose Ignacio; Gonzalez Vasco, Maria Isabel (April 2023).
"Secure post-quantum group key exchange: Implementing a solution based on Kyber"
.
IET Communications
.
17
(6): 758?773.
doi
:
10.1049/cmu2.12561
.
hdl
:
10016/37141
.
ISSN
1751-8628
.
S2CID
255650398
.
- ^
Stohrer, Christian; Lugrin, Thomas (2023), Mulder, Valentin; Mermoud, Alain; Lenders, Vincent; Tellenbach, Bernhard (eds.), "Asymmetric Encryption",
Trends in Data Protection and Encryption Technologies
, Cham: Springer Nature Switzerland, pp. 11?14,
doi
:
10.1007/978-3-031-33386-6_3
,
ISBN
978-3-031-33386-6
- ^
Paar, Christof; Pelzl, Jan; Preneel, Bart (2010).
Understanding Cryptography: A Textbook for Students and Practitioners
. Springer.
ISBN
978-3-642-04100-6
.
- ^
Shamir, Adi (November 1982).
"A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem"
.
23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)
: 145?152.
doi
:
10.1109/SFCS.1982.5
.
- ^
Tunggal, Abi (20 February 2020).
"What Is a Man-in-the-Middle Attack and How Can It Be Prevented ? What is the difference between a man-in-the-middle attack and sniffing?"
.
UpGuard
. Retrieved
26 June
2020
.
[
self-published source?
]
- ^
Tunggal, Abi (20 February 2020).
"What Is a Man-in-the-Middle Attack and How Can It Be Prevented - Where do man-in-the-middle attacks happen?"
.
UpGuard
. Retrieved
26 June
2020
.
[
self-published source?
]
- ^
martin (30 January 2013).
"China, GitHub and the man-in-the-middle"
.
GreatFire
. Archived from
the original
on 19 August 2016
. Retrieved
27 June
2015
.
[
self-published source?
]
- ^
percy (4 September 2014).
"Authorities launch man-in-the-middle attack on Google"
.
GreatFire
. Retrieved
26 June
2020
.
[
self-published source?
]
- ^
Bjorgvinsdottir, Hanna; Bentley, Phil (24 June 2021). "Warp2: A Method of Email and Messaging with Encrypted Addressing and Headers".
arXiv
:
1411.6409
[
cs.CR
].
- ^
a
b
Jevons, W.S. (1874).
The Principles of Science: A Treatise on Logic and Scientific Method
.
Macmillan & Co.
p. 141
. Retrieved
18 January
2024
.
- ^
Weisstein, E.W. (2024).
"Jevons' Number"
.
MathWorld
. Retrieved
18 January
2024
.
- ^
Golob, Solomon W. (1996). "On Factoring Jevons' Number".
Cryptologia
.
20
(3): 243.
doi
:
10.1080/0161-119691884933
.
S2CID
205488749
.
- ^
Ellis, James H. (January 1970).
"The Possibility of Secure Non-secret Digital Encryption"
(PDF)
. CryptoCellar
. Retrieved
18 January
2024
.
- ^
Sawer, Patrick (11 March 2016).
"The unsung genius who secured Britain's computer defences and paved the way for safe online shopping"
.
The Telegraph
.
- ^
a
b
Espiner, Tom (26 October 2010).
"GCHQ pioneers on birth of public key crypto"
.
www.zdnet.com
.
- ^
Singh, Simon
(1999).
The Code Book
. Doubleday. pp.
279
?292.
- ^
Diffie, Whitfield
;
Hellman, Martin E.
(November 1976).
"New Directions in Cryptography"
(PDF)
.
IEEE Transactions on Information Theory
.
22
(6): 644?654.
CiteSeerX
10.1.1.37.9720
.
doi
:
10.1109/TIT.1976.1055638
.
Archived
(PDF)
from the original on 29 November 2014.
- ^
"Asymmetric encryption"
.
IONOS Digitalguide
. Retrieved
9 June
2022
.
- ^
Rivest, R.; Shamir, A.; Adleman, L. (February 1978).
"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"
(PDF)
.
Communications of the ACM
.
21
(2): 120?126.
CiteSeerX
10.1.1.607.2677
.
doi
:
10.1145/359340.359342
.
S2CID
2873616
. Archived from
the original
(PDF)
on 17 December 2008
. Retrieved
15 November
2019
.
- ^
Robinson, Sara (June 2003).
"Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders"
(PDF)
.
SIAM News
.
36
(5).
References
[
edit
]
- Hirsch, Frederick J.
"SSL/TLS Strong Encryption: An Introduction"
.
Apache HTTP Server
. Retrieved
17 April
2013
.
. The first two sections contain a very good introduction to public-key cryptography.
- Ferguson, Niels
;
Schneier, Bruce
(2003).
Practical Cryptography
.
Wiley
.
ISBN
0-471-22357-3
.
- Katz, Jon
; Lindell, Y. (2007).
Introduction to Modern Cryptography
.
CRC Press
.
ISBN
978-1-58488-551-1
.
- Menezes, A. J.
; van Oorschot, P. C.;
Vanstone, Scott A.
(1997).
Handbook of Applied Cryptography
. Taylor & Francis.
ISBN
0-8493-8523-7
.
- 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.
- Salomaa, Arto (1996).
Public-Key Cryptography
(2 ed.). Berlin:
Springer
. 275.
doi
:
10.1007/978-3-662-03269-5
.
ISBN
978-3-662-03269-5
.
S2CID
24751345
.
External links
[
edit
]