Public key encryption is based on a mathematical relationship between prime numbers, and the (presumed) computational difficulty of doing particular mathematical operations on large numbers( such as factoring (RSA) or discrete log (ElGamal)).
Here's an example of a particular public key system (RSA) whose strength depends upon the difficulty of factoring large numbers:
Two prime numbers are picked. In practice, these are very large multi-digit numbers. Here, we use small values to make it easier to understand.
Two prime numbers are chosen p1 and p2, say 3 and 11. We obtain an exponent value from the following equation:
(p1-1) x (p2-1) + 1 = x
For our numbers, this works out to be:
(3-1) x (11-1) + 1
= 2 x 10 + 1
= 21
Now, multiply p1 by p2 to obtain a 'modulus' value (m). For our numbers, this equals:
3 x 11
= 33
For any value (v) from 0 to (m-1), there is an equation that holds true:
v = vx mod m
Now we factor the exponent value such that factor 1 (f1) multiplied by factor 2 (f2) is equal to the exponent value. In our case:
f1 x f2 = x
3 x 7 = 21
So f1 = 3 and f2 = 7
One of the factors is chosen as our public key, the other our private key. Choosing the smaller of the two makes life easier for the public.
To encrypt a message, someone takes the (known) public key and uses that to encrypt the message using the following formula:
Encrypted = Plain ^ f1 mod m
For our example, let's say the letter G is being encoded and (to make the math easier) it's the 7th letter in our alphabet. We assign it a value of 7. So:
Encrypted = 7^3 mod 33
= 13
To decrypt, you use the formula 'in reverse':
Decrypted = Encrypted ^ f2 mod 33
In our case, this yields:
Decrypted = 13 ^ 7 mod 33
= 7
We have our original message back. Math weenies go nuts for this stuff!
Public key encryption has a point of weakness in that two vital pieces of information are known by the attacker - the public key and the algorithm chosen for encryption. Although no civilian scientist has published an elegant method of attacking the algorithm mathematically, it has not been proven to be invulnerable to attack. It may already be the case that military or government scientists have discovered a computationally simple way of cracking this method of encryption. It is certainly a possibility. Meantime, a modified brute force method leaves public key encryption highly suspect. Here's why:
Although it is computationally very difficult to examine and try all of the prime numbers in the 'open' range, in practice the method of generating keys is such that once one of the keys is chosen, the other falls within a range that can be narrowed down using the public key. Once you have chosen a limited selection of numbers to try, you simply run the whole set through the known algorithm until you reveal the private key. Once a private key has been discovered, it's useless and all messages encoded with that key are open to examination.
