Asymmetric encryption explained

I looked for a basic explanation of how asymmetric encryption actually works to show to my students, but I couldn't find easily something that can be understood without some mathematical background.

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 17

to obtain the same example given in the nice Diffie-Hellman Key Exchange video.