Asymmetric key cryptography: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Howard C. Berkowitz
(Cleanup of more specific material removed from cryptography; needs expansion)
 
m (Text replacement - "{{subpages}}" to "{{PropDel}}<br><br>{{subpages}}")
(14 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{subpages}}
{{PropDel}}<br><br>{{subpages}}
{{main|Cryptography}}
{{main|Cryptography}}
In contrast with symmetric encryption, '''asymmetric''' encryption, a user has their computer produce two different keys, related mathematically so that data encrypted with one can only be decrypted with the other. One key is the '''public key''' and can be published. The other is the private key and is kept secret, never leaving the user's computer.  
{{TOC|right}}
 
In symmetric encryption, there is only one key per message and it is used for both encryption and decryption; both users must have it. In '''asymmetric''' encryption, there are two different keys, one for encryption and one for decryption. A user has their computer produce two different keys, related mathematically so that data encrypted with one can only be decrypted with the other. One key is the '''public key''' and can be published. The other is the '''private key''' and is kept secret, never leaving the user's computer. "Public" need not mean that it be available to anyone who requests it; it is used relative to only authorized users in an organization. Many military cryptosystems use asymmetric encryption, but the average person would not be able to obtain the public key for a high-security network such as [[JWICS]].  


The method was first published in a 1976 paper by  Whitfield Diffie and Martin Hellman. <ref>{{citation
The method was first published in a 1976 paper by  Whitfield Diffie and Martin Hellman. <ref>{{citation
Line 9: Line 11:
  | volume = 5
  | volume = 5
  | pages = 109-112
  | pages = 109-112
  | date = June 8, 1976}}</ref>.  A '''public key cryptography''' system is constructed so that calculation of the private key is computationally infeasible from knowledge of the public key, even though they are necessarily related. Instead, both keys are generated secretly, as an interrelated pair<ref>Ralph Merkle was working on similar ideas at the time, and Hellman has suggested that the term used should be Diffie-Hellman-Merkle asymmetric key cryptography.</ref>. The  historian David Kahn described public-key cryptography as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance".<ref>David Kahn, "Cryptology Goes Public", 58 ''Foreign Affairs'' 141, 151 (fall 1979), p. 153.</ref>
  | date = June 8, 1976}}</ref>.  '''Public key cryptography''' is constructed so that calculation of the private key is computationally infeasible from knowledge of the public key, even though they are necessarily related. Instead, both keys are generated secretly, as an interrelated pair<ref>Ralph Merkle was working on similar ideas at the time, and Hellman has suggested that the term used should be Diffie-Hellman-Merkle asymmetric key cryptography.</ref>. The  historian David Kahn described public-key cryptography as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance".<ref>David Kahn, "Cryptology Goes Public", 58 ''Foreign Affairs'' 141, 151 (fall 1979), p. 153.</ref>
 
The encryption alone does not make a complete system. [[Public key infrastructure]] is necessary, which consists of a set of services for generating the key pair and securely sending the public key to a repository, for users to obtain public keys, determine that they are valid, let the issuer revoke one when necessary, etc.


There were some cryptanalytic vulnerabilities, however, until Diffie and Hellman showed that public-key cryptography was possible by presenting the [[Diffie-Hellman]] key exchange protocol.<ref name=dh2>{{citation
There were some cryptanalytic vulnerabilities, however, until Diffie and Hellman showed that public-key cryptography was possible by presenting the [[Diffie-Hellman]] key exchange protocol.<ref name=dh2>{{citation
Line 18: Line 22:
  | url = http://www.cs.jhu.edu/~rubin/courses/sp03/papers/diffie.hellman.pdf  
  | url = http://www.cs.jhu.edu/~rubin/courses/sp03/papers/diffie.hellman.pdf  
  | date = Nov. 1976
  | date = Nov. 1976
  | pages = 644-654}}</ref> In 1978, Ronald Rivest, Adi Shamir, and Len Adleman invented [[RSA]], another public-key system<ref name=RSA>{{citation
  | pages = 644-654}}</ref> In 1978, Ronald Rivest, Adi Shamir, and Len Adleman invented the [[RSA algorithm]], another public-key system<ref name=RSA>{{citation
  | first1 = Ronald L. | last1 = Rivest | first2 = Adi |last2= Shamir | first3 = Len | last3 = Adleman   
  | first1 = Ronald L. | last1 = Rivest | first2 = Adi |last2= Shamir | first3 = Len | last3 = Adleman   
  | url = http://theory.lcs.mit.edu/~rivest/rsapaper.pdf  
  | url = http://theory.lcs.mit.edu/~rivest/rsapaper.pdf  
Line 34: Line 38:


Unlike symmetric encryption which assumes both sender and receiver already know the private key, public-key exchange allows you to securely issue a key to anyone so that person can then send you encrypted information.  Only the intended recipient can read the ciphertext, by applying a private decryption key. A separate key pair is needed for each direction of transmission.
Unlike symmetric encryption which assumes both sender and receiver already know the private key, public-key exchange allows you to securely issue a key to anyone so that person can then send you encrypted information.  Only the intended recipient can read the ciphertext, by applying a private decryption key. A separate key pair is needed for each direction of transmission.
== Mathematical basis ==
Public-key algorithms are most often based on the [[Computational complexity theory|computational complexity]] of "hard" problems, often from [[number theory]].  The hardness of RSA is related to the [[integer factorization]] problem, while Diffie-Hellman and DSA are related to the [[discrete logarithm]] problem.  More recently, [[elliptic curve cryptography]] has developed in which security is based on number theoretic problems involving elliptic curves. Methods have also been proposed based on the [[subset sum]] problem (though those have been broken) and the algebra of [[braid groups]].
Because of the complexity of the underlying problems, most public-key algorithms involve operations such as [[modular arithmetic|modular]] multiplication and exponentiation, which are much more computationally expensive than the techniques used in most block ciphers, especially with typical key sizes. As a result, public-key cryptosystems are commonly "hybrid" systems, in which a fast symmetric-key encryption algorithm is used for the message itself, while the relevant symmetric key is sent with the message, but encrypted using a public-key algorithm.  Similarly, hybrid signature schemes are often used, in which a cryptographic hash function is computed, and only the resulting hash is digitally signed.<ref name=HAC>{{citation
| first1 = AJ | last1 = Menezes | first2 = PC | last2= van Oorschot | first3= SA | last3 = Vanstone 
| url=http://www.cacr.math.uwaterloo.ca/hac/
| title = Handbook of Applied Cryptography
| date = Fifth Edition, 2001
| ISBN=0-8493-8523-7}}</ref>


==Generating session keys==
==Generating session keys==
Public-key encryption is slower than conventional symmetric encryption. The primary usage of public-key encryption is in hybrid systems where a symmetric algorithm does the bulk data encryption while the public key algorithm provides other services. For example, in [[PGP]] email encryption the sender generates a random key for the symmetric bulk encryption and uses public key techniques to securely deliver it to the receiver. In the [[Diffie-Hellmann]] key agreement protocol, used in [[IPsec]] and other systems, public key techniques provide authentication.  
Public-key encryption is slower than conventional symmetric encryption. The primary usage of public-key encryption is in [[hybrid cryptosystem]]s where a symmetric algorithm does the bulk data encryption while the public key algorithm provides other services. For example, in [[PGP]] email encryption the sender generates a random key for the symmetric bulk encryption and uses public key techniques to securely deliver it to the receiver. In the [[Diffie-Hellman]] key agreement protocol, used in [[IPsec]] and other systems, public key techniques provide authentication.  


An advantage of asymmetric over symmetric cryptosystems is that all symmetric system keys must be kept secret, and the logistics of [[key management]] become complex.  Asymmetric systems allow public keys to be distributed freely.
An advantage of asymmetric over symmetric cryptosystems is that all symmetric system keys must be kept secret, and the logistics of [[key management]] become complex.  Asymmetric systems allow public keys to be distributed freely.
==Digital signatures==
==Digital signatures==
In addition to encryption, public-key cryptography can be used to implement [[digital signature]] schemes.  A digital signature is somewhat like an ordinary [[signature]]; they have the characteristic that they are easy for a user to produce, but difficult for anyone else to forge. Digital signatures can also be permanently tied to the content of the message being signed; they cannot be 'moved' from one document to another, for any attempt will be detectable. In digital signature schemes, there are two algorithms: one for ''signing'', in which a secret key is used to process the message (or a hash of the message or both), and one for ''verification,'' in which the matching public key is used with the message to check the validity of the signature.  [[RSA]] and [[Digital Signature Algorithm|DSA]] are two of the most popular digital signature schemes.  Digital signatures are central to the operation of [[public key infrastructure]]s and to many network security schemes ([[Transport Layer Security|SSL/TLS]], many [[VPN]]s, etc).<ref name="schneierbook">{{citation  
In addition to encryption, public-key cryptography can be used to implement [[digital signature]] schemes.  A digital signature is somewhat like an ordinary [[signature]]; they have the characteristic that they are easy for a user to produce, but difficult for anyone else to forge. Digital signatures can also be permanently tied to the content of the message being signed; they cannot be 'moved' from one document to another, for any attempt will be detectable. In digital signature schemes, there are two algorithms: one for ''signing'', in which a secret key is used to process the message (or a hash of the message or both), and one for ''verification,'' in which the matching public key is used with the message to check the validity of the signature.  [[RSA algorithm|RSA]] and [[Digital Signature Algorithm|DSA]] are two of the most popular digital signature schemes.  Digital signatures are central to the operation of [[public key infrastructure]]s and to many network security schemes ([[Transport Layer Security|SSL/TLS]], many [[VPN]]s, etc).<ref name="schneierbook">{{citation  
  | first = Bruce | last = Schneier
  | first = Bruce | last = Schneier
  | title = Applied Cryptography
  | title = Applied Cryptography
Line 52: Line 68:
  | date = April 2002  
  | date = April 2002  
  | url = http://www.ietf.org/rfc/rfc3278.txt}}</ref>
  | url = http://www.ietf.org/rfc/rfc3278.txt}}</ref>
Public-key algorithms are most often based on the [[Computational complexity theory|computational complexity]] of "hard" problems, often from [[number theory]].  The hardness of RSA is related to the [[integer factorization]] problem, while Diffie-Hellman and DSA are related to the [[discrete logarithm]] problem.  More recently, [[elliptic curve cryptography]] has developed in which security is based on number theoretic problems involving elliptic curve]s.  Because of the complexity of the underlying problems, most public-key algorithms involve operations such as [[modular arithmetic|modular]] multiplication and exponentiation, which are much more computationally expensive than the techniques used in most block ciphers, especially with typical key sizes. As a result, public-key cryptosystems are commonly "hybrid" systems, in which a fast symmetric-key encryption algorithm is used for the message itself, while the relevant symmetric key is sent with the message, but encrypted using a public-key algorithm.  Similarly, hybrid signature schemes are often used, in which a cryptographic hash function is computed, and only the resulting hash is digitally signed.<ref name=HAC>{{citation
| first1 = AJ | last1 = Menezes | first2 = PC | last2= van Oorschot | first3= SA | last3 = Vanstone 
| url=http://www.cacr.math.uwaterloo.ca/hac/
| title = Handbook of Applied Cryptography
| date = Fifth Edition, 2001
| ISBN=0-8493-8523-7}}</ref>


==References==
==References==
{{reflist}}
{{reflist}}

Revision as of 05:48, 8 April 2024

This article may be deleted soon.
To oppose or discuss a nomination, please go to CZ:Proposed for deletion and follow the instructions.

For the monthly nomination lists, see
Category:Articles for deletion.


This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.
For more information, see: Cryptography.

In symmetric encryption, there is only one key per message and it is used for both encryption and decryption; both users must have it. In asymmetric encryption, there are two different keys, one for encryption and one for decryption. A user has their computer produce two different keys, related mathematically so that data encrypted with one can only be decrypted with the other. One key is the public key and can be published. The other is the private key and is kept secret, never leaving the user's computer. "Public" need not mean that it be available to anyone who requests it; it is used relative to only authorized users in an organization. Many military cryptosystems use asymmetric encryption, but the average person would not be able to obtain the public key for a high-security network such as JWICS.

The method was first published in a 1976 paper by Whitfield Diffie and Martin Hellman. [1]. Public key cryptography is constructed so that calculation of the private key is computationally infeasible from knowledge of the public key, even though they are necessarily related. Instead, both keys are generated secretly, as an interrelated pair[2]. The historian David Kahn described public-key cryptography as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance".[3]

The encryption alone does not make a complete system. Public key infrastructure is necessary, which consists of a set of services for generating the key pair and securely sending the public key to a repository, for users to obtain public keys, determine that they are valid, let the issuer revoke one when necessary, etc.

There were some cryptanalytic vulnerabilities, however, until Diffie and Hellman showed that public-key cryptography was possible by presenting the Diffie-Hellman key exchange protocol.[4] In 1978, Ronald Rivest, Adi Shamir, and Len Adleman invented the RSA algorithm, another public-key system[5] It had been released as an MIT "Technical Memo" in April 1977, and published in Martin Gardner's Scientific American "Mathematical Recreations" column. In 1997, it finally became publicly known that asymmetric cryptography had been invented by James H. Ellis at GCHQ, a British intelligence organization, in the early 1970s, and that both the Diffie-Hellman and RSA algorithms had been previously developed (by Malcolm J. Williamson and Clifford Cocks, respectively)[6].

Unlike symmetric encryption which assumes both sender and receiver already know the private key, public-key exchange allows you to securely issue a key to anyone so that person can then send you encrypted information. Only the intended recipient can read the ciphertext, by applying a private decryption key. A separate key pair is needed for each direction of transmission.

Mathematical basis

Public-key algorithms are most often based on the computational complexity of "hard" problems, often from number theory. The hardness of RSA is related to the integer factorization problem, while Diffie-Hellman and DSA are related to the discrete logarithm problem. More recently, elliptic curve cryptography has developed in which security is based on number theoretic problems involving elliptic curves. Methods have also been proposed based on the subset sum problem (though those have been broken) and the algebra of braid groups.

Because of the complexity of the underlying problems, most public-key algorithms involve operations such as modular multiplication and exponentiation, which are much more computationally expensive than the techniques used in most block ciphers, especially with typical key sizes. As a result, public-key cryptosystems are commonly "hybrid" systems, in which a fast symmetric-key encryption algorithm is used for the message itself, while the relevant symmetric key is sent with the message, but encrypted using a public-key algorithm. Similarly, hybrid signature schemes are often used, in which a cryptographic hash function is computed, and only the resulting hash is digitally signed.[7]

Generating session keys

Public-key encryption is slower than conventional symmetric encryption. The primary usage of public-key encryption is in hybrid cryptosystems where a symmetric algorithm does the bulk data encryption while the public key algorithm provides other services. For example, in PGP email encryption the sender generates a random key for the symmetric bulk encryption and uses public key techniques to securely deliver it to the receiver. In the Diffie-Hellman key agreement protocol, used in IPsec and other systems, public key techniques provide authentication.

An advantage of asymmetric over symmetric cryptosystems is that all symmetric system keys must be kept secret, and the logistics of key management become complex. Asymmetric systems allow public keys to be distributed freely.

Digital signatures

In addition to encryption, public-key cryptography can be used to implement digital signature schemes. A digital signature is somewhat like an ordinary signature; they have the characteristic that they are easy for a user to produce, but difficult for anyone else to forge. Digital signatures can also be permanently tied to the content of the message being signed; they cannot be 'moved' from one document to another, for any attempt will be detectable. In digital signature schemes, there are two algorithms: one for signing, in which a secret key is used to process the message (or a hash of the message or both), and one for verification, in which the matching public key is used with the message to check the validity of the signature. RSA and DSA are two of the most popular digital signature schemes. Digital signatures are central to the operation of public key infrastructures and to many network security schemes (SSL/TLS, many VPNs, etc).[8] Diffie-Hellman and RSA, in addition to being the first publicly known examples of high quality public-key cryptosystems, have been among the most widely used. Others include the Cramer-Shoup cryptosystem, ElGamal encryption, and various elliptic curve techniques.[9]

References

  1. Diffie, Whitfield (June 8, 1976), "Multi-user cryptographic techniques", AFIPS Proceedings 4 5: 109-112
  2. Ralph Merkle was working on similar ideas at the time, and Hellman has suggested that the term used should be Diffie-Hellman-Merkle asymmetric key cryptography.
  3. David Kahn, "Cryptology Goes Public", 58 Foreign Affairs 141, 151 (fall 1979), p. 153.
  4. Diffie, Whitfield & Martin Hellman (Nov. 1976), "New Directions in Cryptography", IEEE Transactions on Information Theory IT-22: 644-654
  5. Rivest, Ronald L.; Adi Shamir & Len Adleman (1978), "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21 (2): pp.120-126
  6. Cocks, Clifford (20 November 1973), "A Note on 'Non-Secret Encryption", CESG Research Report
  7. Menezes, AJ; PC van Oorschot & SA Vanstone (Fifth Edition, 2001), Handbook of Applied Cryptography, ISBN 0-8493-8523-7
  8. Schneier, Bruce (2nd edition, 1996,), Applied Cryptography, John Wiley & Sons, ISBN 0-471-11709-9
  9. S. Blake-Wilson, D. Brown, P. Lambert (April 2002), Use of Elliptic Curve Cryptography (ECC) Algorithms in Cryptographic Message Syntax (CMS)., RFC 3278