Editing Public-key cryptography (section)

== Description ==
Before the mid-1970s, all cipher systems used [[symmetric key algorithm]]s, 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 cryptosystem, the public keys can be disseminated widely and openly, and only the corresponding private keys need be kept secret.

The two best-known types of public key cryptography are [[digital signature]] and public-key encryption:

* 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.<ref name="hac-digsig">
{{cite book
 |author1-last=Menezes |author1-first=Alfred J. |author1-link=Alfred Menezes
 |author2-last=van Oorschot |author2-first=Paul C. |author2-link=Paul van Oorschot
 |author3-last=Vanstone |author3-first=Scott A. |author3-link=Scott Vanstone
 |title=Handbook of Applied Cryptography
 |publisher=CRC Press
 |date=October 1996
 |isbn=0-8493-8523-7
 |chapter=Chapter 8: Public-key encryption
 |url=https://cacr.uwaterloo.ca/hac/about/chap11.pdf
 |pages=425–488
 |access-date=2022-10-08
}}</ref><ref name="djb-forgery">
{{cite book
 |first=Daniel J. |last=Bernstein |author-link=Daniel J. Bernstein
 |chapter=Protecting communications against forgery
 |title=Algorithmic Number Theory
 |publisher=MSRI Publications
 |volume=44
 |date=1 May 2008
 |url=https://cr.yp.to/antiforgery/forgery-20080501.pdf
 |access-date=2022-10-08
 |at=§5: Public-key signatures, pp. 543–545
}}</ref><ref name="bellare-goldwasser2008digsigs">{{cite book
|title=Lecture Notes on Cryptography
|first1=Mihir
|last1=Bellare
|author-link1=Mihir Bellare
|first2=Shafi
|last2=Goldwasser
|author-link2=Shafi Goldwasser
|date=July 2008
|url=https://cseweb.ucsd.edu/~mihir/papers/gb.pdf#page=168
|chapter=Chapter 10: Digital signatures
|page=168
|access-date=2023-06-11
|archive-date=2022-04-20
|archive-url=https://web.archive.org/web/20220420003617/https://cseweb.ucsd.edu/~mihir/papers/gb.pdf#page=168
|url-status=live
}}</ref><p>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.</p>
* 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.<ref name="hac-pke">
{{cite book
 |author1-last=Menezes |author1-first=Alfred J. |author1-link=Alfred Menezes
 |author2-last=van Oorschot |author2-first=Paul C. |author2-link=Paul van Oorschot
 |author3-last=Vanstone |author3-first=Scott A. |author3-link=Scott Vanstone
 |title=Handbook of Applied Cryptography
 |publisher=CRC Press
 |date=October 1996
 |isbn=0-8493-8523-7
 |chapter=8: Public-key encryption
 |url=https://cacr.uwaterloo.ca/hac/about/chap8.pdf
 |pages=283–319
 |access-date=2022-10-08
}}</ref><p>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.</p><p>Only the journalist who knows the corresponding private key can decrypt the ciphertexts to obtain the sources' messages&mdash;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.<ref name="dds2009anoncomm">{{cite book
|editor-last=Rosenberg
|editor-first=Burton
|title=Handbook of Financial Cryptography and Security
|year=2010
|isbn=978-1420059816
|publisher=Chapman & Hall/CRC
|chapter=Chapter 13: Anonymous Communication
|author-last1=Danezis
|author-first1=George
|author-link1=George Danezis
|author-last2=Diaz
|author-first2=Claudia
|author-last3=Syverson
|author-first3=Paul
|author-link3=Paul Syverson
|pages=341–390
|url=https://www.freehaven.net/anonbib/cache/systems-anon-communication.pdf
|quote=Since PGP, beyond compressing the messages, does not make any further attempts to hide their size, it is trivial to follow a message in the network just by observing its length.
}}</ref><ref name="rackoff-simon1993cryptotrafficanalysis">{{cite conference
|author-last1=Rackoff
|author-first1=Charles
|author-link1=Charles Rackoff
|author-last2=Simon
|author-first2=Daniel R.
|title=Cryptographic defense against traffic analysis
|year=1993
|book-title=Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing
|conference=STOC '93: ACM [[Symposium on the Theory of Computing]]
|publisher=[[Association for Computing Machinery]]
|pages=672–681
|doi=10.1145/167088.167260
|doi-access=free
|quote=Now, certain types of information cannot reasonably be assumed to be concealed.  For instance, an upper bound on the total volume of a party’s sent or received communication (of any sort) is obtainable by anyone with the resources to examine all possible physical communication channels available to that party. 
}}</ref><ref name="karger1977nondiscretionaryaccesscontrol">{{cite thesis
|last=Karger
|first=Paul A.
|title=Non-Discretionary Access Control for Decentralized Computing Systems
|publisher=[[Laboratory for Computer Science]], [[Massachusetts Institute of Technology]]
|degree=S.M.
|number=MIT-LCS-TR-179
|date=May 1977
|url=https://dspace.mit.edu/handle/1721.1/149471
|chapter=11: Limitations of End-to-End Encryption
|hdl=1721.1/149471
|quote=The scenario just described would seem to be secure, because all data is encrypted before being passed to the communications processors.  However, certain control information must be passed in cleartext from the host to the communications processor to allow the network to function. This control information consists of the destination address for the packet, the length of the packet, and the time between successive packet transmissions.
}}</ref><ref name="chaum1981untraceableemail">{{cite journal
|author-last=Chaum
|author-first=David L.
|author-link=David Chaum
|title=Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms
|editor-last=Rivest
|editor-first=R.
|editor-link=Ron Rivest
|journal=[[Communications of the ACM]]
|date=February 1981
|volume=24
|number=2
|publisher=[[Association for Computing Machinery]]
|quote=Recently, some new solutions to the “key distribution problem” (the problem of providing each communicant with a secret key) have been suggested, under the name of public key cryptography.  Another cryptographic problem, the “traffic analysis problem” (the problem of keeping confidential who converses with whom, and when they converse), will become increasingly important with the growth of electronic mail.
}}</ref>  Public-key encryption on its own also does not tell the recipient anything about who sent a message{{r
|hac-pke
|page=283
|quote=The main objective of public-key encryption is to provide privacy or confidentiality.  Since A’s encryption transformation is public knowledge, public-key encryption alone does not provide data origin authentication (Definition 9.76) or data integrity (Definition 9.75).  Such assurances must be provided through use of additional techniques (see §9.6), including message authentication codes and digital signatures.
}}<ref "davis2001defectivesignencrypt">{{cite conference
|last=Davis
|first=Don
|title=Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML
|book-title=Proceedings of the 2001 USENIX Annual Technical Conference
|conference=[[USENIX]]
|year=2001
|pages=65–78
|url=https://www.usenix.org/legacy/events/usenix01/full_papers/davis/davis_html/
|quote=Why is naïve Sign & Encrypt insecure?  Most simply, S&E is vulnerable to “surreptitious forwarding:” Alice signs & encrypts for Bob's eyes, but Bob re-encrypts Alice's signed message for Charlie to see.  In the end, Charlie believes Alice wrote to him directly, and can't detect Bob's subterfuge.
}}</ref><ref "an2001authencpubkey">{{cite tech report
|last=An
|first=Jee Hea
|title=Authenticated Encryption in the Public-Key Setting: Security Notions and Analyses
|publisher=IACR Cryptology ePrint Archive
|number=2001/079
|date=2001-09-12
|url=https://eprint.iacr.org/2001/079
|access-date=2024-11-24
}}</ref>&mdash;it just conceals the content of the message.</p>

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. [[Transport Layer Security|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. [[Pretty Good Privacy|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.