| Line 5: |
Line 5: |
| | 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]]. | | 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 key exchange protocol== |
| − | 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:
| + | This is a method to secure a channel from eavesdroppers, by agreeing on an encryption key. It is used to let 2 parties agree on a key to be used for encrypting their communications, without actually transmitting said key on the channel between them. If somebody is eavesdropping he will not be able to deduce the key agreed upon from listening to the data. |
| | | | |
| − | # Alice and Bob decide on a large prime number ''p'' and a group ''G'' in which to work, with [[generator]] ''g''.
| + | 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. |
| − | # Alice chooses a secret integer ''a''. She sends ''g<sup>a</sup>'' mod ''p'' to Bob.
| |
| − | # Bob chooses a different integer ''b'', and sends ''g<sup>b</sup>'' mod ''p'' to Alice.
| |
| − | # 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. | + | 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. |
| | + | |
| | + | "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 decides on a large prime number ''p'' which defines a multiplicative group ''G'' in which to work, with [[generator]] ''g'' |
| | + | # Alice chooses a secret integer ''a''. She sends ''g<sup>a</sup>'' mod ''p'' to Bob |
| | + | # Bob chooses a different integer ''b'', and sends ''g<sup>b</sup>'' mod ''p'' to Alice |
| | + | # 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 (g<sup>a*b</sup> mod p), and can use the shared secret as a key for sending [[encryption|encrypted]] messages back and forth by the usual methods. |
| | + | |
| | + | 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 [[generator]], 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 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<sup>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> (the value she received from Bob) : (g<sup>b</sup>)<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 = 4 |
| | + | Alice 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 (although some algorithms can do it in slightly less steps) to determine a. |
| | | | |
| | ==RSA encryption== | | ==RSA encryption== |