Public-key cryptography

Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of : public keys which may be disseminated widely, and private keys which are known only to the owner. The generation of such keys depends on based on problems to produce . Effective security only requires keeping the private key private; the public key can be openly distributed without compromising security.[1]

In such a system, any person can encrypt a message using the receiver’s public key, but that encrypted message can only be decrypted with the receiver’s private key.

Robust is also possible. A sender can combine a message with a private key to create a short digital signature on the message. Anyone with the corresponding public key can combine a message, a putative digital signature on it, and the known public key to verify whether the signature was valid, i.e. made by the owner of the corresponding private key.[2][3]

Public key algorithms are fundamental security ingredients in modern , applications and protocols assuring the confidentiality, authenticity and of electronic communications and data storage. They underpin various Internet standards, such as , , , and . Some public key algorithms provide and secrecy (e.g., ), some provide digital signatures (e.g., ), and some provide both (e.g., ).

Contents

Description

Before the mid-1970s, all cipher systems were using , in which the same 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 – a . This requirement is never trivial and very rapidly becomes unmanageable as the number of participants increases, or when secure channels aren’t available for key exchange, 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 private key needs to be kept secure by its owner.

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

  • Public key encryption, in which a message is encrypted with a recipient’s public key. The message cannot be decrypted by anyone who does not possess the matching private key, who is thus presumed to be the owner of that key and the person associated with the public key. This is used in an attempt to ensure confidentiality.
  • 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 likely to be the person associated with the public key. This also ensures that the message has not been tampered with, as a signature is mathematically bound to the message it originally was made with, and verification will fail for practically any other message, no matter how similar to the original message.

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 a malicious third party. There are several possible approaches, including:

A (PKI), in which one or more third parties – known as – certify ownership of key pairs. relies upon this.

A “web of trust” which decentralizes authentication by using individual endorsements of the link between user and public key. uses this approach, as well as lookup in the (DNS). The system for digitally signing emails also uses this approach.

Applications

The most obvious application of a public key encryption system is in encrypting communication to provide confidentiality – a message that a sender encrypts using the recipient’s public key 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.

system 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, , non-repudiation protocols, etc.

Because asymmetric key algorithms are nearly always much more computationally intensive than symmetric ones, in many cases it is common to exchange a key using a , then transmit data using that key and a symmetric key algorithm. , , and the /TLS family of schemes use this procedure, and are thus called .

Weaknesses

As with all security-related systems, it is important to identify potential weaknesses.

Algorithms

All public key schemes are in theory susceptible to a “”.[4] Such attacks are however impractical if the amount of computation needed to succeed – termed the “work factor” by – 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 have much lower work factors, making resistance to a brute-force attack irrelevant. Some special and specific algorithms have been developed to aid in attacking some public key encryption algorithms – both and have known attacks that are much faster than the brute-force approach.[5]

Major weaknesses have been found for several formerly promising asymmetric key algorithms. The was found to be insecure after the development of a new attack. [] Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys (a “”). A great deal of active research is currently underway to both discover, and to protect against, new attack algorithms.

Alteration of public keys

Another potential security vulnerability in using asymmetric keys is the possibility of a , 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 also be intercepted, decrypted, and re-encrypted by the attacker using the correct public keys for different communication segments, in all instances, so as to avoid suspicion.

This attack may seem to be difficult to implement in practice, but it is not impossible when using insecure media (e.g., public networks, such as the or wireless forms of communications) – for example, a malicious staff member at an Internet Service Provider (ISP) might find it quite easy to carry out.

Public key infrastructure

One approach to prevent such attacks involves the use of a (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 in turn has potential weaknesses.

For example, the certificate authority issuing the certificate must be trusted to have properly checked the identity of the key-holder, must ensure the correctness of the public key when it issues a certificate, must be secure from computer piracy, and must have made arrangements with all participants to check all their certificates before protected communications can begin. , 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 any single 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 alternate scenario rarely discussed , an attacker who penetrated an authority’s servers and obtained 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 and its predecessor , 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 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. 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 “” is possible, making any subordinate certificate wholly insecure.

Examples

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

  • protocol
  • DSS (Digital Signature Standard), which incorporates the
  • Various techniques
  • Various password-authenticated key agreement techniques
  • encryption algorithm ()
  • authenticated key agreement protocol

Examples of asymmetric key algorithms not widely adopted include:

  • cryptosystem

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

Examples of protocols using asymmetric key algorithms include:

  • , an implementation of
  • , a secure protocol
  • standardized by and its predecessor
  • Bitcoin

History

During the early , 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 kept absolutely secret, could then be used to exchange encrypted messages. A number of significant practical difficulties arise with this approach to .

Anticipation

In his 1874 book The Principles of Science, [6] wrote:
Can the reader say what two numbers multiplied together will produce the number ?[7] I think it unlikely that anyone but myself will ever know.[8]

Here he described the relationship of to cryptography, and went on to discuss specifically the problem used to create a . In July 1996, mathematician 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.”[9]

Classified discovery

In 1970, , a British cryptographer at the UK (GCHQ), conceived of the possibility of “non-secret encryption”, (now called public key cryptography), but could see no way to implement it.[10] In 1973, his colleague implemented what has become known as the , giving a practical method of “non-secret encryption”, and in 1974, another GCHQ mathematician and cryptographer, , developed what is now known as . The scheme was also passed to the USA’s .[11] With a military focus and low computing power, the power of public key cryptography was unrealised in both organisations:

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 designing an open internet architecture for , its adaptation and adoption for the … did public key cryptography realise its full potential.

—[11]

Their discovery was not publicly acknowledged for 27 years, until the research was declassified by the British government in 1997.[12]

Public discovery

In 1976, an asymmetric key cryptosystem was published by and who, influenced by ‘s work on public key distribution, disclosed a method of public key agreement. This method of key exchange, which uses , came to be known as .[13] 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 , and was invented in 1974 and published in 1978.

In 1977, a generalization of Cocks’ scheme was independently invented by , and , all then at . The latter authors published their work in 1978, and the algorithm came to be known as , from their initials.[14] RSA uses exponentiation modulo a product of two very large , to encrypt and decrypt, performing both public key encryption and public key digital signature. Its security is connected to the extreme difficulty of , a problem for which there is no known efficient general technique.

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed in the field of public key cryptography, including the , , – and .

See Also on BitcoinWiki

Notes

References

Hirsch, Frederick J.. }

|"SSL/TLS Strong Encryption: An Introduction" |"SSL/TLS Strong Encryption: An Introduction"

}}. }

|[ Apache HTTP Server] |Apache HTTP Server

}}. http://httpd.apache.org/docs/2.2/ssl/ssl_intro.html#cryptographictech. Retrieved 17 April 2013.. The first two sections contain a very good introduction to public-key cryptography.

External links

  • ↑
  • ↑
  • ↑
  • ↑
  • ↑ Mavroeidis, Vasileios, and Kamer Vishi, “The Impact of Quantum Computing on Present Cryptography”, International Journal of Advanced Computer Science and Applications, 31 March 2018
  • ↑ Jevons, William Stanley, The Principles of Science: A Treatise on Logic and Scientific Method p. 141, Macmillan & Co., London, 1874, 2nd ed. 1877, 3rd ed. 1879. Reprinted with a foreword by , Dover Publications, New York, NY, 1958.
  • ↑ This came to be known as “Jevons’s number”. The only nontrivial factor pair is 89681 × 96079.
  • ↑ Principles of Science, Macmillan & Co., 1874, p. 141.
  • ↑ }}}}}}}}}}}}}}}}}}} |Surname2= |Surname3= |Surname4= |Surname5= |Surname6= |Surname7= |Surname8= |Surname9= |Given1=Solomon W. |Given2= |Given3= |Given4= |Given5= |Given6= |Given7= |Given8= |Given9= |Authorlink1= |Authorlink2= |Authorlink3= |Authorlink4= |Authorlink5= |Authorlink6= |Authorlink7= |Authorlink8= |Authorlink9= |Coauthors= |Other= |Year=1996 |YearNote= |Date=1996 |Title=On Factoring Jevons’ Number |TransTitle= |IncludedWorkTitle= |TitleType= |language= |URL=https://semanticscholar.org/paper/0b3e9a0c0e8bf84413f49d3a4585c207f58da70e |IncludedWorkURL= |AccessDate= |OriginalURL=https://semanticscholar.org/paper/0b3e9a0c0e8bf84413f49d3a4585c207f58da70e |ArchiveURL= |ArchiveDate= |DeadURL= |format= |Periodical=Cryptologia |Issue=3 |TitleNote= |At=243 |Edition= |Series= |Volume=20 |Publisher= |Place= |PublicationPlace= |PublicationDate= |EditorSurname1= |EditorSurname2= |EditorSurname3= |EditorSurname4= |EditorGiven1= |EditorGiven2= |EditorGiven3= |EditorGiven4= |Editorlink1= |Editorlink2= |Editorlink3= |Editorlink4= |ARXIV= |ASIN= |ASIN-TLD= |BIBCODE= |DOI=10.1080/0161-119691884933 |DoiBroken= |ISBN= |ISSN= |JFM= |JSTOR= |LCCN= |MR= |OCLC= |OL= |OSTI= |PMC= |PMID= |RFC= |SSRN= |ZBL= |ID= |laysummary= |laydate= |laysource= |quote= |Ref= |amp= |AuthorMask= |AuthorSep=; |NameSep=, |PS=. |Sep=. |template doc demo= |Trunc=8 }}
  • ↑ }}}}}}}}}}}}}}}}}}} |Surname2= |Surname3= |Surname4= |Surname5= |Surname6= |Surname7= |Surname8= |Surname9= |Given1=Patrick |Given2= |Given3= |Given4= |Given5= |Given6= |Given7= |Given8= |Given9= |Authorlink1= |Authorlink2= |Authorlink3= |Authorlink4= |Authorlink5= |Authorlink6= |Authorlink7= |Authorlink8= |Authorlink9= |Coauthors= |Year=2016 |YearNote= |Date=11 March 2016 |Title=The unsung genius who secured Britain’s computer defences and paved the way for safe online shopping |TransTitle= |IncludedWorkTitle= |language= |URL=https://www.telegraph.co.uk/history/12191473/The-unsung-genius-who-secured-Britains-computer-defences-and-paved-the-way-for-safe-online-shopping.html |IncludedWorkURL= |AccessDate= |OriginalURL=https://www.telegraph.co.uk/history/12191473/The-unsung-genius-who-secured-Britains-computer-defences-and-paved-the-way-for-safe-online-shopping.html |ArchiveURL= |ArchiveDate= |DeadURL= |format= |Periodical=The Telegraph |Issue= |TitleNote= |At= |Edition= |Series= |Volume= |Publisher= |Place= |PublicationPlace= |PublicationDate= |ARXIV= |ASIN= |ASIN-TLD= |BIBCODE= |DOI= |DoiBroken= |ISBN= |ISSN= |JFM= |JSTOR= |LCCN= |MR= |OCLC= |OL= |OSTI= |PMC= |PMID= |RFC= |SSRN= |ZBL= |ID= |laysummary= |laydate= |laysource= |quote= |Ref= |amp= |AuthorMask= |AuthorSep=; |NameSep=, |PS=. |Sep=. |template doc demo= |Trunc=8 }}
  • ↑ 11.011.1 Tom Espiner (26 October 2010). } |“GCHQ pioneers on birth of public key crypto” |”GCHQ pioneers on birth of public key crypto” }}. http://www.zdnet.com/article/gchq-pioneers-on-birth-of-public-key-crypto/.
  • ↑
  • ↑ }}}}}}}}}}}}}}}}}}} |Surname2=Hellman |Surname3= |Surname4= |Surname5= |Surname6= |Surname7= |Surname8= |Surname9= |Given1=Whitfield |Given2=Martin E. |Given3= |Given4= |Given5= |Given6= |Given7= |Given8= |Given9= |Authorlink1=Whitfield Diffie |Authorlink2=Martin Hellman |Authorlink3= |Authorlink4= |Authorlink5= |Authorlink6= |Authorlink7= |Authorlink8= |Authorlink9= |Coauthors= |Other= |Year=1976 |YearNote= |Date=November 1976 |Title=New Directions in Cryptography |TransTitle= |IncludedWorkTitle= |TitleType= |language= |URL=https://web.archive.org/web/20141129035850/https://ee.stanford.edu/%7Ehellman/publications/24.pdf |IncludedWorkURL= |AccessDate= |OriginalURL=//ee.stanford.edu/%7Ehellman/publications/24.pdf |ArchiveURL=https://web.archive.org/web/20141129035850/https://ee.stanford.edu/%7Ehellman/publications/24.pdf |ArchiveDate=2014-11-29 |DeadURL= |format= |Periodical= |Issue=6 |TitleNote= |At=644–654 |Edition= |Series= |Volume=22 |Publisher= |Place= |PublicationPlace= |PublicationDate= |EditorSurname1= |EditorSurname2= |EditorSurname3= |EditorSurname4= |EditorGiven1= |EditorGiven2= |EditorGiven3= |EditorGiven4= |Editorlink1= |Editorlink2= |Editorlink3= |Editorlink4= |ARXIV= |ASIN= |ASIN-TLD= |BIBCODE= |DOI=10.1109/TIT.1976.1055638 |DoiBroken= |ISBN= |ISSN= |JFM= |JSTOR= |LCCN= |MR= |OCLC= |OL= |OSTI= |PMC= |PMID= |RFC= |SSRN= |ZBL= |ID= |laysummary= |laydate= |laysource= |quote= |Ref= |amp= |AuthorMask= |AuthorSep=; |NameSep=, |PS=. |Sep=. |template doc demo= |Trunc=8 }}
  • ↑ }}}}}}}}}}}}}}}}}}} |Surname2=Shamir |Surname3=Adleman |Surname4= |Surname5= |Surname6= |Surname7= |Surname8= |Surname9= |Given1=R. |Given2=A. |Given3=L. |Given4= |Given5= |Given6= |Given7= |Given8= |Given9= |Authorlink1= |Authorlink2= |Authorlink3= |Authorlink4= |Authorlink5= |Authorlink6= |Authorlink7= |Authorlink8= |Authorlink9= |Coauthors= |Other= |Year=1978 |YearNote= |Date=February 1978 |Title=A Method for Obtaining Digital Signatures and Public-Key Cryptosystems |TransTitle= |IncludedWorkTitle= |TitleType= |language= |URL=http://people.csail.mit.edu/rivest/Rsapaper.pdf |IncludedWorkURL= |AccessDate= |OriginalURL=http://people.csail.mit.edu/rivest/Rsapaper.pdf |ArchiveURL= |ArchiveDate= |DeadURL= |format= |Periodical= |Issue=2 |TitleNote= |At=120–126 |Edition= |Series= |Volume=21 |Publisher= |Place= |PublicationPlace= |PublicationDate= |EditorSurname1= |EditorSurname2= |EditorSurname3= |EditorSurname4= |EditorGiven1= |EditorGiven2= |EditorGiven3= |EditorGiven4= |Editorlink1= |Editorlink2= |Editorlink3= |Editorlink4= |ARXIV= |ASIN= |ASIN-TLD= |BIBCODE= |DOI=10.1145/359340.359342 |DoiBroken= |ISBN= |ISSN= |JFM= |JSTOR= |LCCN= |MR= |OCLC= |OL= |OSTI= |PMC= |PMID= |RFC= |SSRN= |ZBL= |ID= |laysummary= |laydate= |laysource= |quote= |Ref= |amp= |AuthorMask= |AuthorSep=; |NameSep=, |PS=. |Sep=. |template doc demo= |Trunc=8 }}