So, I wrote a few scripts that tell a story with some little and understandable numbers.

Here's the result:

ASYMMETRIC CRYPTOGRAPHY: A TALE This is a demonstration of how asymmetric cryptography works. Two people, Alice and Bob, want to send messages each other without sharing a common secret. So, they both choose a private key and generate a public key from that, sharing only the latter. How can this work? Imagine that Alice and Bob choose a common prime number, that they both know. Here, suppose they chose Y=17. Alice chooses her own private key as 11. She computes her public key as (17 ^ 11) = 34271896307633, and then sends it to Bob. On the other side, Bob computes his public key as 17 ^ 13 = 9904578032905937, and sends it to Alice. Now, Alice has her own private key (11) and Bob's public key (9904578032905937). Since she wants to send her message, she first computes a session key using her own private key and Bob's public key, like here: The session key is computed as 9904578032905937 ^ 11. Its value is 89990311908498647045788321790870571946973640519785658861481127970769\ 43851269888414365573845679912196161685840518138931586759580137729961\ 7421026433812938863796708814458356310513 With this session key, Alice can encrypt a message with a symmetric key program. When Bob receives the file, he computes the session key using his own private key and Alice's public key, much like Alice did herself. The session key is computed as 34271896307633 ^ 13, which is exactly the same Alice has used: 89990311908498647045788321790870571946973640519785658861481127970769\ 43851269888414365573845679912196161685840518138931586759580137729961\ 7421026433812938863796708814458356310513 Why are the two session keys equal? Because on one side you have (17 ^ 13) ^ 11 (which is Bob's public key to the power of Alice's private key) and on the other side you have (17 ^ 11) ^ 13 (which is Alice's public key to the power of Bob's private key) And, of course 17 ^ 13 ^ 11 = 17 ^ 11 ^ 13.

The source code of the script is available on google code. You can run the script setting other values on the command line, like for instance:

./public_key_cryptography_explained.sh 11 13 17

But still, there is a problem. Given the power and the base, it is relatively easy to find the exponent, even with very large numbers. That explains why public and session keys are computed with modular arithmetic: this adds strength to the algorithm because it makes reversibility much much harder. Let's see it in action with a second tale (where the percentage symbol stands for the modulus operator).

ASYMMETRIC CRYPTOGRAPHY: A TALE This is a demonstration of how asymmetric cryptography works. Two people, Alice and Bob, want to send messages each other without sharing a common secret. So, they both choose a private key and generate a public key from that, sharing only the latter. How can this work? Imagine that Alice and Bob choose a common prime number, that they both know. Here, suppose they chose Y=30983. They also choose a number to be used for modulus computation. Here, suppose they chose P=40993. Alice chooses her own private key as 1087. She computes her public key as (30983 ^ 1087) % 40993 = 1771, and then sends it to Bob. On the other side, Bob computes his public key as (30983 ^ 2083) % 40993 = 26537, and sends it to Alice. Now, Alice has her own private key (1087) and Bob's public key (26537). Since she wants to send her message, she first computes a session key using her own private key and Bob's public key, like here: The session key is computed as (26537 ^ 1087) % 40993. Its value is 7225. With this session key, Alice can encrypt a message with a symmetric key program. When Bob receives the file, he computes the session key using his own private key and Alice's public key, much like Alice did herself. The session key is computed as (1771 ^ 2083) % 40993, which is exactly the same Alice has used: 7225.The source code of this script is available on google code.

You can run it on the command line like this:

./public_key_cryptography_explained_with_mod.sh 15 13 3 17to obtain the same example given in the nice Diffie-Hellman Key Exchange video.