'''Public-key encryption''' is a kind of an asymmetric [[encryption]] method in which both the message and the public key 2 complementary keys are publicused. There is a private key used known What gets encrypted by one of the keys can be decrypted only to by the individualother. This differs from Generally one key of the traditional pair (so-called the "private-key") encryption, in which the key is kept secret from safe by an individual and the intended recipient. Public-other 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 "public key; this ") is the reason that the key has to distributed freely, after which two things can be made publicdone.
Well-known If a message can be decrypted using the widely distributed ("public-") key encryption algorithms include '''Diffie-Hellman''','''El-Gamal''', and '''RSA'''. These algorithms all work on it proves that the same basicmodel, which author of the message is the individual that of holds the private key. Conversely, if a [[cyclic group]] ''G'' distributing over an operation ''o'' which may or may not message is encrypted by the public key, it can only be [[commutative]]. In Diffie-Hellman and El-Gamaldecrypted by the key that was kept safe (the "private key"), making it possible to send a confidential message to the basic operation holder of the private key knowing only the public key. While this is the [[discrete logarithm]]; general principle of operation, many modifications are made in RSA it is [[factoring]]order to ensure practical and quick encryption.
==DiffieWell-Hellman encryption==Diffie-Hellman encryption, also known as "Diffiepublic-Hellman key exchange", relies on the fundamental [[hardness|difficulty]] of [[computing]] the discrete logarithm encryption algorithms include ''g<sup>a</sup>'Diffie-Hellman' of a number ''xand '' in the [[Group (mathematics)|group]] 'RSA'G''. It was invented by In Diffie-Hellman, the hardness is based on the [[Whitfield Diffiediscrete logarithm]] and ; in RSA it is [[Lillian Hellmanfactoring]] in 1976. The protocol proceeds in three steps:
# Alice and Bob secretly decide on a large prime number ''p'' and ==Diffie-Hellman key exchange protocol==This is a group ''G'' in which method to work, with [[generator]] ''g''.# Alice chooses a secret integer ''secure a''channel from eavesdroppers, for example 6by agreeing on an encryption key. She sends ''It is used to let 2 parties agree on a<sup>g</sup>'' mod ''p'' key to Bob.# Bob chooses a different integer ''b'', be used for example 7encrypting their communications, and sends ''b<sup>g</sup>'' mod ''p'' without actually transmitting said key on the channel between them. If somebody is eavesdropping he will not be able 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 deduce the key agreed upon from listening to the other persondata.
At this point both parties (Alice and Bob) have the same (secret) information"Diffie-Hellman key exchange", and can use relies on the shared secret as fundamental [[hardness|difficulty]] of [[computing]] the discrete logarithm of a key for sending number in the [[encryptionGroup (mathematics)|encryptedgroup]] messages back and forth ''G''. It was invented by the usual methods[[Whitfield Diffie]] and Martin Hellman in 1976.The protocol proceeds in three steps:
==El-Gamal encryption==El-Gamal encryption was invented by the [[Egyptian]] mathematician [[Taher El-Gamal]] # Alice decides on a large prime number ''p'' which defines a multiplicative group ''G'' in 1984which to work, shortly after the assassination of with [[Anwar Sadatgenerator]]''g''# Alice chooses a secret integer ''a''. Like the Diffie-Hellman protocolShe sends ''g<sup>a</sup>'' mod ''p'' to Bob# Bob chooses a different integer ''b'', El-Gamal encryption relies on the discrete logarithm function, which can be used and sends ''g<sup>b</sup>'' mod ''p'' to unobtrusively compute the inverse of the [[exponentiation]] operation within Alice# Alice computes ''(g<sup>b</sup>)<sup>a cyclic group.</sup>'', while Bob computes ''(g<sup>a</sup>)<sup>b</sup>''
Unlike classical encryption schemes such as ''ENIGMA'' At this point both parties (see [[Encryption]]Alice and Bob), El-Gamal's cryptosystem actually expands have the plaintext by a factor of 2, in order to make the message harder to [[decrypt]]. same (Because secret) information density is exponential, with ''two'' times as many bits in the ciphertext an attacker would have to work 2(g<sup>2a*b</sup> = ''four'' times as hard to decode the messagemod p), assuming he did not already possess and can use the shared secret as a key.) However, for sending [[encryption|encrypted]] messages back and forth by the usual implementation simply sets these extra bits to zero by default, rendering the security gain infinitesimal at bestmethods.
The El-Gamal encryption algorithm was added An example conversation (in practice much larger prime numbers will be used) : # Alice chooses a prime p = 43, which defines a multiplicative group with 43 elements, 0 to 42. Our secret key will be one of the elements in the group, which means it will be a value from 0 to 10. Since p is prime, any element is a [[C programming languagegenerator]] in 1999, as so we can pick any number between 0 and 42, let's say we pick 28. Any number between 0 and 42 will do for the math function generator. In practice the generator needs to be "relatively" prime to p, modulo p. This means g and p must have no common factors, when calculating mod p. # Alice then sends p and g to Bob, who now also knows p = 43 and g = 28# Alice chooses her secret number a, let's say 58. She calculates g<ttsup>a</sup> mod p = 28<sup>58</sup> mod 43 = 17, and sends 17 to Bob# Bob chooses his secret number b, let's say 39. Bob sends g<sup>b</sup> mod p = 28<sup>39</sup> mod 43 = 2 to Alice# Alice calculates her version of the secret value g<sup>ab</sup> using g<sup>b</sup>lgammal(the value she received from Bob): (g<sup>b</ttsup> [sic])<sup>a</sup> mod p = 2<sup>58</sup> mod 43 = 4# Bob calculates his version of the secret value g<sup>ab</sup> using g<sup>a</sup> (the value he received from Alice) : (g<sup>a</sup>)<sup>b</sup> mod p = 17<sup>39</sup> mod 43 = 4Alice and Bob have agreed on an encryption key, g<sup>ab</sup> = 4, and only sent values that can only be used to calculate the key with great difficulty : p = 43, g = 28, g<sup>a</sup> = 17 and g<sup>b</sup> = 39. If you want to find out the key, your only choice is to try and determine either a or b. This can only be done by calculating g<sup>1</sup>, g<sup>2</sup>, g<sup>3</sup>, g<sup>4</sup>, g<sup>5</sup>, ... and compare with the g<sup>a</sup> value, until found. By increasing p, the procedure of looking for a can be made arbitrarily difficult. These days p is generally chosen to be "relatively large", meaning that it should require "a bit less" than 256 bits to represent. Determining a would take on average 2<sup>255</sup> steps (Only implementations conforming although some algorithms can do it in slightly less steps) to TR1 provide this functiondetermine a. The main problem is the "man in the middle attack". Instead of merely eavesdropping, an attacker would place himself between the 2 parties trying to communicate, and he would participate in the key exchange. The spy would agree on one key with the first party, agree on another key with the second party. Then he is able to decrypt (and re-encrypt and retransmit)the data sent over the channel. However the protocol is useful because it raises the difficulty of eavesdropping. A spy would have to be able to place himself "in between" the two parties he intends to spy on. Also, the spy needs to actively participate in the conversation in order to be able to spy. If he were to put a listening device on the cable, for example, he would not be able to understand the messages sent.
==RSA encryption==
"RSA" stands for "[[Ron Rivest|Rivest]]–[[Shamir]]–[[AdelsonAdelman]]",<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. It is probably the most commonly used public key encryption at this time.
RSA, unlike the previous two systems, is based on the fundamental difficulty of [[factoring]] large integers into [[prime]]s. For example, although it is easy to factor 6=2×3, it is exponentially more difficult to factor 6000000=2000×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×3000 ''digits!'')
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.
==GCHQ==
The mathematics of public key cryptography, and specifically RSA, are now generally recognized to have been first developed at the British government signals intelligence department [[GCHQ]] (Government Communications Headquarters). In 1975 three mathematicians at GCHQ, James Ellis, Clifford Cocks and Malcolm Williamson devised the mathematics for a public key system. However, due the limited computing power available at the time, the idea was not developed into a practical system, and due to the secret nature of the established, papers on the subject were not released to the general mathematical community. The discoveries of Rivest, Shamir and Adelman, although later, were entirely independent.<ref>https://www.bbc.co.uk/news/uk-england-gloucestershire-11475101</ref>
==Example==
#Step 1 Fred needs to send documents to many people. They dont don't need to be secure , but its important that they know for certain that the messge 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 others may as well, its but that is not important)* George '''decrypts''' the message using Freds Fred's ''Public key''. * Only a message coded with the private key can be decoded wth with the public key so George knows it came from Fred. # Step 2* George drafts a reply and '''encrypts''' it with Freds Fred's ''Public key''.* only Freds Only Fred's ''private key'' can '''decrypt''' the message , so it is secure
* Fred receives the message and decrypts it
* its It's a valid message but Fred cant can't know who sent it , anyone with the public key could send to him. This form of public key encryption works best For this reason, George may encrypt the message with sets of his private and key as well as Fred's public keyskey, to prove it came from George while ensuring that only Fred can read it.
==References==
<references/>
== See also ==
# [http://www.networkworld.com/news/64452_05-17-1999.html Public key encryption for Dummies]
# http://www2.krellinst.org/UCES/archive/modules/charlie/pke/
[[Category:Cryptography]]
[[Category:Privacy]]