Public-key cryptography: Difference between revisions

Revision as of 21:09, 28 November 2024

Latest revision as of 06:31, 27 August 2025

(44 intermediate revisions by 33 users not shown)

Line 7:

1) Alice signs a message with her private key.

2) Using Alice's public key, Bob can verify that Alice sent the message and that the message has not been modified.]]

[[File:Public key shared secret.svg|thumb|250px|right| In the [[Diffie–Hellman key exchange]] scheme, each party generates a public/private key pair and distributes the public key of the pair. After obtaining an authentic (n.b., this is critical) copy of each other's public keys, Alice and Bob can compute a shared secret offline. The shared secret can be used, for instance, as the key for a [[symmetric cipher]], which will be, in essentially all cases, much faster.]]

[[File:Public key encryption.svg|thumb|250px|right|In an asymmetric key encryption scheme, anyone can encrypt messages using a public key, but only the holder of the paired private key can decrypt such a message. The security of the system depends on the secrecy of the private key, which must not become known to any other.]]

'''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'''.{{Ref RFC|4949|notes=no}}<ref>{{Cite journal |last1=Bernstein |first1=Daniel J. |last2=Lange |first2=Tanja |date=2017-09-14 |title=Post-quantum cryptography |url=http://www.nature.com/articles/nature23461 |journal=Nature |language=en |volume=549 |issue=7671 |pages=188–194 |doi=10.1038/nature23461 |pmid=28905891 |bibcode=2017Natur.549..188B |s2cid=4446249 |issn=0028-0836}}</ref> Key pairs are generated with [[cryptographic]] [[algorithms]] based on [[mathematical]] problems termed [[one-way function]]s. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.<ref>{{Cite book|url=https://books.google.com/books?id=Dam9zrViJjEC|title=Cryptography and Network Security: Principles and Practice|last=Stallings|first=William|date=3 May 1990|publisher=Prentice Hall|isbn=9780138690175|page=165|language=en}}</ref> There are many kinds of public-key cryptosystems, with different security goals, including [[digital signature]], [[Diffie–Hellman key exchange]], [[Key encapsulation mechanism|public-key key encapsulation]], and public-key encryption.

There are many kinds of public-key cryptosystems, with different security goals, including [[digital signature]], [[Diffie-Hellman key exchange]], [[Key encapsulation mechanism|public-key key encapsulation]], and public-key encryption.

Public key algorithms are fundamental security primitives in modern [[cryptosystem]]s, including applications and protocols that offer assurance of the confidentiality and authenticity of electronic communications and data storage. They underpin numerous Internet standards, such as [[Transport Layer Security|Transport Layer Security (TLS)]], [[SSH]], [[S/MIME]], and [[Pretty Good Privacy|PGP]]. Compared to [[symmetric cryptography]], public-key cryptography can be too slow for many purposes,<ref>

Line 28 ⟶ 27:

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

Line 93 ⟶ 92:

|title=Handbook of Financial Cryptography and Security

|year=2010

|isbn=1420059815978-1420059816

|publisher=Chapman &amp; Hall/CRC

|chapter=Chapter 13: Anonymous Communication

|author-last1=Danezis

Line 104 ⟶ 103:

|author-first3=Paul

|author-link3=Paul Syverson

|pages=341-390341–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.

Line 121 ⟶ 120:

|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

Line 132 ⟶ 131:

|url=https://dspace.mit.edu/handle/1721.1/149471

|chapter=11: Limitations of End-to-End Encryption

|hdl=1721.1/149471

|hdl-access=free

|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

Line 158 ⟶ 159:

|conference=[[USENIX]]

|year=2001

|pages=65-7865–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.

Line 179 ⟶ 180:

== Applications ==

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. Most digital services such as financial services, email, and messaging applications utilized daily are secured using public key encryption. <ref>{{Cite web |date=2025-06-05 |title=Post-Quantum Cryptography: A New Security Paradigm for the Post-Quantum Era |url=https://www.pentasecurity.com/blog/security-issue-post-quantum-cryptography/ |access-date=2025-07-10 |website=Penta Security Inc. |language=en-US}}</ref>

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

Line 198 ⟶ 199:

All public key schemes are in theory susceptible to a "[[brute-force attack|brute-force key search attack]]".<ref>{{cite book|last1=Paar|first1=Christof|first2=Jan|last2=Pelzl|first3=Bart|last3=Preneel|url=http://www.crypto-textbook.com|title=Understanding Cryptography: A Textbook for Students and Practitioners|publisher=Springer|year=2010|isbn=978-3-642-04100-6}}</ref> 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 (algorithm)|RSA]] and [[ElGamal encryption]] have known attacks that are much faster than the brute-force approach.{{cn|date=June 2024}} None of these are sufficiently improved to be actually practical, however.

Major weaknesses have been found for several formerly promising asymmetric key algorithms. The [[Merkle–Hellman knapsack cryptosystem|"knapsack packing" algorithm]] was found to be insecure after the development of a new attack.<ref>{{Cite journalbook|last1=Shamir|first1=Adi|datetitle=November23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) |titlechapter=A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem |urldate=https://ieeexplore.ieee.org/document/4568386|journal=23rd Annual Symposium onNovember Foundations of Computer Science1982 (SFCS 1982)|pages=145–152|doi=10.1109/SFCS.1982.5}}</ref> As with all cryptographic functions, public-key implementations may be vulnerable to [[side-channel attack]]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 ===

Line 223 ⟶ 224:

|website=UpGuard

|access-date=June 26, 2020

}}{{sps|{{subst:DATE}}|date=January 2024}}</ref><ref name="martin-GF">

{{cite web

|author=martin

Line 233 ⟶ 234:

|archive-url=https://web.archive.org/web/20160819165216/https://en.greatfire.org/blog/2013/jan/china-github-and-man-middle

|archive-date=19 August 2016

}}{{sps|{{subst:DATE}}|date=January 2024}}</ref><ref name="percy-GF">

{{cite web

|url=https://en.greatfire.org/blog/2014/sep/authorities-launch-man-middle-attack-google

Line 241 ⟶ 242:

|website=GreatFire

|access-date=June 26, 2020

}}{{sps|{{subst:DATE}}|date=January 2024}}</ref>

=== Public key infrastructure ===

Line 270 ⟶ 271:

=== Anticipation ===

In his 1874 book ''The Principles of Science'', [[William Stanley Jevons]] wrote:<ref name=TPS_1>{{cite book| title=The Principles of Science: A Treatise on Logic and Scientific Method| author=Jevons, W.S.| url=https://archive.org/details/principlesofscie00jevorich/principlesofscie00jevorich/page/n166/mode/1up?view=theater| publisher=[[Macmillan & Co.]]| page=141| date=1874| access-date=18 January 2024}}</ref><blockquote>

Can the reader say what two numbers multiplied together will produce the number [[William Stanley Jevons#Jevons's number|8616460799]]?<ref name=JN_1>{{cite web| title=Jevons' Number| author=Weisstein, E.W.| url=https://mathworld.wolfram.com/JevonsNumber.html| publisher=[[MathWorld]]| date=2024| access-date=18 January 2024}}</ref> I think it unlikely that anyone but myself will ever know.<ref name=TPS_1/></blockquote>

Here he described the relationship of [[one-way function]]s 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."<ref>{{cite journal |doi=10.1080/0161-119691884933 |year=1996 |last=Golob |first=Solomon W. |journal=Cryptologia |volume=20 |issue=3 |page=243|title=On Factoring Jevons' Number |s2cid=205488749 }}</ref>

=== Classified discovery ===

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.<ref>{{cite web| last=Ellis| first=James H.| title=The Possibility of Secure Non-secret Digital Encryption| date=January 1970|url=https://cryptocellar.org/cesg/possnse.pdf| publisher=CryptoCellar| access-date=18 January 2024}}</ref><ref>{{cite news |last=Sawer |first=Patrick |title=The unsung genius who secured Britain's computer defences and paved the way for safe online shopping |journal=The Telegraph |date=11 March 2016 |url=https://www.newindianexpress.com/world/2016/mar/12/the-anonymous-researcher-who-held-the-key-to-cyber-security-910751.html}}</ref>

In 1973, his colleague [[Clifford Cocks]] implemented what has become known as the [[RSA (cryptosystem)|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]].<ref name="zdnet"/> 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:

<blockquote>

Line 283 ⟶ 284:

—[[Ralph Benjamin]]<ref name="zdnet">{{cite web |url=https://www.zdnet.com/article/gchq-pioneers-on-birth-of-public-key-crypto/ |title=GCHQ pioneers on birth of public key crypto |first=Tom |last=Espiner |date=26 October 2010 |website=[[ZDNet]]}}</ref>

</blockquote>

These discoveries were not publicly acknowledged for 27 years, until the research was declassified by the British government in 1997.<ref name=singh>{{cite book |last=Singh |first=Simon |author-link=Simon Singh |title=The Code Book |publisher=Doubleday |year=1999 |pages=[https://archive.org/details/codebookevolutio00sing/page/279 279]–292|title-link=The Code Book }}</ref>

=== Public discovery ===

Line 309 ⟶ 310:

}}</ref> RSA uses [[modular exponentiation|exponentiation modulo]] a product of two very large [[prime]]s, to encrypt and decrypt, performing both public key encryption and public key digital signatures. Its security is connected to the extreme difficulty of [[integer factorization|factoring large integers]], a problem for which there is no known efficient general technique. A description of the algorithm was published in the [[List of Martin Gardner Mathematical Games columns|Mathematical Games]] column in the August 1977 issue of [[Scientific American]].<ref>{{cite journal |url=http://www.msri.org/people/members/sara/articles/rsa.pdf |journal=SIAM News |volume=36 |issue=5 |date=June 2003 |title=Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders |first=Sara |last=Robinson }}</ref>

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed, including the [[Rabin cryptosystemsignature]], [[ElGamal encryption]], [[Digital Signature Algorithm|DSA]] and [[Elliptic-curve cryptography|ECC]].

== Examples ==