Overview of Encryption II
Submitted by BDub on January 20, 2006 - 4:56am.
Security
In last weeks article, we discussed symmetrical key encryption, or encryption where the same key is used to encrypt and decrypt the content. The obvious drawback of this is that if the key is made public then it becomes useless, as anybody can read your messages. Because of this, a trusted courier or initial contact is required in order to set the key. For two people wanting to communicate without ever meeting each other, this is impractical.
So how can we generate a shared key without the two parties ever meeting? One method of this is Diffie-Hellman-Merkle key exchange.
Diffie-Hellman-Merkle key exchange is a method where two parties can arrive at a common numerical key without ever transmitting the key in plaintext, or in a format that can be cracked without brute force. To start with, both parties agree on two numbers. These numbers are plaintext and are assumed to be readable by anyone. "P" must be a prime number. The larger the prime the better. In our example we'll be using "83" just to make it simple. "G" is a common base number. This can be any integer. In our example we'll use 4.
Let's say Bob and Alice want to establish a shared key. Bob's never met Alice, all he has is her address. He can send her a letter proposing encrypted communication, and in it send the values of "G" and "P". In our case, "4" and "83".
Once these are established, Alice and Bob both choose any integer they want. We'll say that Alice chooses 2 and Bob chooses 5. These are labeled "A" and "B" respectively.
Alice performs this equation on her side:
G ^ A mod P or, once we substitute in values, 4^2 mod 83.
This results in the value 16. Alice packages this into a letter and sends "16" to Bob.
Bob performs:
G ^ B mod P or, 4^5 mod 83.
His result is "28". He writes Alice a letter with the number 28 enclosed.
Now Bob and Alice both have a copy of the others number, but they need to find the same number. This is achieved by Alice using the following equation:
(G ^ B mod P) ^ A mod P
Alice doesn't have "B", as it was never sent plaintext to her. She does however have the answer to G ^ B mod P, which is 28. She substitutes in the values she has and finds the equation is now:
(28)^2 mod 83
This results in the number "37". This is the final key.
Bob receives Alices envelope and must execute the equation:
(G ^ A mod P) ^ B mod P
Alice has given him G ^ A mod P without ever revealing A. He substitutes in his values and gets:
(16)^5 mod 83
This resolves out to the value "37". Both now have a shared key. Any eavesdropper cannot establish the key without knowing either A or B, neither of which have been sent in the plaintext. In this way, with sufficiently large values, we can negotiate a common key, secure except for the possibility of an eavesdropper using brute force to break their encryption.