Difference between revisions of "Public-key encryption"

From Conservapedia
Jump to: navigation, search
m (spelling, refs)
(ccorrect many errors)
Line 1: Line 1:
−
'''Public-key encryption''' is an [[encryption]] method in which both the message and the public key are public. There is a private key used known only to the individual. This differs from the traditional (so-called "private-key") encryption, in which the key is kept secret from the intended recipient. Public-key encryption is a form of ''[[symmetry|asymmetric]] encryption'', meaning that it is much easier to encrypt a message than to decrypt it, at least without knowing the encryption key; this is the reason that the key has to be made public.
+
'''Public-key encryption''' is an [[encryption]] method in which both the encryption key is public. There is a private key used known only to the individual. This differs from the traditional (so-called "private-key") encryption, in which the key is kept secret from the intended recipient. Public-key encryption is a form of ''[[symmetry|asymmetric]] encryption'', meaning that it is much easier to encrypt a message than to decrypt it, at least without knowing the decryption key.
  
−
Well-known public-key encryption algorithms include '''Diffie-Hellman''',
+
Well-known public-key encryption algorithms include '''Diffie-Hellman''' and '''RSA'''. In Diffie-Hellman, the hardness is based on the [[discrete logarithm]]; in RSA it is [[factoring]].
−
'''El-Gamal''', and '''RSA'''. These algorithms all work on the same basic
+
−
model, which is that of a [[cyclic group]] ''G'' distributing over an operation ''o'' which may or may not be [[commutative]]. In Diffie-Hellman and El-Gamal, the basic operation is the [[discrete logarithm]]; in RSA it is [[factoring]].
+
  
 
==Diffie-Hellman encryption==
 
==Diffie-Hellman encryption==
−
Diffie-Hellman encryption, also known as "Diffie-Hellman key exchange", relies on the fundamental [[hardness|difficulty]] of [[computing]] the discrete logarithm ''g<sup>a</sup>'' of a number ''x'' in the [[Group (mathematics)|group]] ''G''. It was invented by [[Whitfield Diffie]] and [[Lillian Hellman]] in 1976. The protocol proceeds in three steps:
+
Diffie-Hellman encryption, also known as "Diffie-Hellman key exchange", relies on the fundamental [[hardness|difficulty]] of [[computing]] the discrete logarithm of a number in the [[Group (mathematics)|group]] ''G''. It was invented by [[Whitfield Diffie]] and Martin Hellman in 1976. The protocol proceeds in three steps:
  
−
# Alice and Bob secretly decide on a large prime number ''p'' and a group ''G'' in which to work, with [[generator]] ''g''.
+
# Alice and Bob decide on a large prime number ''p'' and a group ''G'' in which to work, with [[generator]] ''g''.
−
# Alice chooses a secret integer ''a'', for example 6. She sends ''a<sup>g</sup>'' mod ''p'' to Bob.
+
# Alice chooses a secret integer ''a''. She sends ''g<sup>a</sup>'' mod ''p'' to Bob.
−
# Bob chooses a different integer ''b'', for example 7, and sends ''b<sup>g</sup>'' mod ''p'' to Alice.
+
# Bob chooses a different integer ''b'', and sends ''g<sup>b</sup>'' mod ''p'' to Alice.
−
# Alice computes ''(a<sup>g</sup>)<sup>b</sup>'', while Bob computes ''(b<sup>g</sup>)<sup>a</sup>''. Whoever finishes first sends their result to the other person.
+
# Alice computes ''(g<sup>b</sup>)<sup>a</sup>'', while Bob computes ''(g<sup>a</sup>)<sup>b</sup>''.
  
 
At this point both parties (Alice and Bob) have the same (secret) information, and can use the shared secret as a key for sending [[encryption|encrypted]] messages back and forth by the usual methods.
 
At this point both parties (Alice and Bob) have the same (secret) information, and can use the shared secret as a key for sending [[encryption|encrypted]] messages back and forth by the usual methods.
−
 
−
==El-Gamal encryption==
 
−
El-Gamal encryption was invented by the [[Egyptian]] mathematician [[Taher El-Gamal]] in 1984, shortly after the assassination of [[Anwar Sadat]]. Like the Diffie-Hellman protocol, El-Gamal encryption relies on the discrete logarithm function, which can be used to unobtrusively compute the inverse of the [[exponentiation]] operation within a cyclic group.
 
−
 
−
Unlike classical encryption schemes such as ''ENIGMA'' (see [[Encryption]]), El-Gamal's cryptosystem actually expands the plaintext by a factor of&nbsp;2, in order to make the message harder to [[decrypt]]. (Because information density is exponential, with ''two'' times as many bits in the ciphertext an attacker would have to work 2<sup>2</sup>&nbsp;=&nbsp;''four'' times as hard to decode the message, assuming he did not already possess the key.) However, the usual implementation simply sets these extra bits to zero by default, rendering the security gain infinitesimal at best.
 
−
 
−
The El-Gamal encryption algorithm was added to the [[C programming language]] in 1999, as the math function <tt>lgammal()</tt> [sic]. (Only implementations conforming to TR1 provide this function.)
 
  
 
==RSA encryption==
 
==RSA encryption==
−
"RSA" stands for "[[Ron Rivest|Rivest]]&ndash;[[Shamir]]&ndash;[[Adelson]]",<ref>[http://www.all-acronyms.com/?t=rsa&d=rivest%2Dshamir%2Dadelson ''AllAcronyms.com'']</ref><ref>[http://www.cogs.susx.ac.uk/courses/mct/Handouts/notes-6.pdf Course notes] from G6016 "Networks", at the [[University of Sussex]]</ref> the three [[MIT]] researchers who discovered the RSA algorithm in 1977, seven years before Taher El-Gamal developed his competing system.
+
"RSA" stands for "[[Ron Rivest|Rivest]]&ndash;[[Shamir]]&ndash;[[Adelman]]",<ref>[http://www.all-acronyms.com/?t=rsa&d=rivest%2Dshamir%2Dadelson ''AllAcronyms.com'']</ref><ref>[http://www.cogs.susx.ac.uk/courses/mct/Handouts/notes-6.pdf Course notes] from G6016 "Networks", at the [[University of Sussex]]</ref> the three [[MIT]] researchers who discovered the RSA algorithm in 1977.
  
−
RSA, unlike the previous two systems, is based on the fundamental difficulty of [[factoring]] large [[prime]]s. For example, although it is easy to factor 6=2&times;3, it is exponentially more difficult to factor 6000000=2000&times;3000. (Of course, the digital computers that implement RSA encryption use numbers that are bigger still; a "strong" key used by an organization such as the [[NSA]] might have 6000000=2000&times;3000 ''digits!'')
+
RSA is based on the fundamental difficulty of [[factoring]] large integers into [[prime]]s.  
  
 
The RSA algorithm was put to the test in 1991, when RSA Laboratories released the "RSA Factoring Challenge". The challenge consisted of a list of progressively larger numbers, which, when fully decrypted, read "The magic words are [[squeamish ossifrage]]."<ref>[http://citeseer.ist.psu.edu/1393.html "The Magic Words Are Squeamish Ossifrage"], by Atkins, Graff, Lenstra, and Leyl</ref> Although the challenge was withdrawn in 2007, the RSA algorithm is still widely considered acceptable for business purposes.
 
The RSA algorithm was put to the test in 1991, when RSA Laboratories released the "RSA Factoring Challenge". The challenge consisted of a list of progressively larger numbers, which, when fully decrypted, read "The magic words are [[squeamish ossifrage]]."<ref>[http://citeseer.ist.psu.edu/1393.html "The Magic Words Are Squeamish Ossifrage"], by Atkins, Graff, Lenstra, and Leyl</ref> Although the challenge was withdrawn in 2007, the RSA algorithm is still widely considered acceptable for business purposes.
Line 31: Line 22:
 
==Example==
 
==Example==
 
#
 
#
−
Fred needs to send documents to many people. They dont need to be secure , but its important that they know for certain that the messge actually came from Fred.  
+
Fred needs to send documents to many people. They don't need to be secure, but its important that they know for certain that the message actually came from Fred.  
 
* Fred '''encrypts''' the message using his ''private key''. (only fred knows this key)
 
* Fred '''encrypts''' the message using his ''private key''. (only fred knows this key)
−
* Fred sends the message  
+
* Fred sends the encrypted message  
 
* George gets the message (so do many other people , it's not important)
 
* George gets the message (so do many other people , it's not important)
−
* George '''decrypts''' the message using Freds ''Public key''.  
+
* George '''decrypts''' the message using Fred's ''Public key''.  
 
* Only a message coded with the private key can be decoded wth the public key so George knows it came from Fred.  
 
* Only a message coded with the private key can be decoded wth the public key so George knows it came from Fred.  
 
#  
 
#  

Revision as of 05:24, April 19, 2009

Public-key encryption is an encryption method in which both the encryption key is public. There is a private key used known only to the individual. This differs from the traditional (so-called "private-key") encryption, in which the key is kept secret from the intended recipient. Public-key encryption is a form of asymmetric encryption, meaning that it is much easier to encrypt a message than to decrypt it, at least without knowing the decryption key.

Well-known public-key encryption algorithms include Diffie-Hellman and RSA. In Diffie-Hellman, the hardness is based on the discrete logarithm; in RSA it is factoring.

Diffie-Hellman encryption

Diffie-Hellman encryption, also known as "Diffie-Hellman key exchange", relies on the fundamental difficulty of computing the discrete logarithm of a number in the group G. It was invented by Whitfield Diffie and Martin Hellman in 1976. The protocol proceeds in three steps:

  1. Alice and Bob decide on a large prime number p and a group G in which to work, with generator g.
  2. Alice chooses a secret integer a. She sends ga mod p to Bob.
  3. Bob chooses a different integer b, and sends gb mod p to Alice.
  4. Alice computes (gb)a, while Bob computes (ga)b.

At this point both parties (Alice and Bob) have the same (secret) information, and can use the shared secret as a key for sending encrypted messages back and forth by the usual methods.

RSA encryption

"RSA" stands for "Rivest–Shamir–Adelman",[1][2] the three MIT researchers who discovered the RSA algorithm in 1977.

RSA is based on the fundamental difficulty of factoring large integers into primes.

The RSA algorithm was put to the test in 1991, when RSA Laboratories released the "RSA Factoring Challenge". The challenge consisted of a list of progressively larger numbers, which, when fully decrypted, read "The magic words are squeamish ossifrage."[3] Although the challenge was withdrawn in 2007, the RSA algorithm is still widely considered acceptable for business purposes.

Example

Fred needs to send documents to many people. They don't need to be secure, but its important that they know for certain that the message actually came from Fred.

  • Fred encrypts the message using his private key. (only fred knows this key)
  • Fred sends the encrypted message
  • George gets the message (so do many other people , it's not important)
  • George decrypts the message using Fred's Public key.
  • Only a message coded with the private key can be decoded wth the public key so George knows it came from Fred.
  • George drafts a reply and encrypts it with Freds Public key.
  • only Freds private key can decrypt the message , so it is secure
  • Fred receives the message and decrypts it
  • it's a valid message but Fred cant know who sent it , anyone with the public key could send to him.

This form of public key encryption works best with sets of private and public keys.


References

  1. ↑ AllAcronyms.com
  2. ↑ Course notes from G6016 "Networks", at the University of Sussex
  3. ↑ "The Magic Words Are Squeamish Ossifrage", by Atkins, Graff, Lenstra, and Leyl

See Also

  1. | Public key encryption for Dummies
  2. http://www2.krellinst.org/UCES/archive/modules/charlie/pke/
Retrieved from "https://conservapedia.com/index.php?title=Public-key_encryption&oldid=654267"