Mfcttrf

(I am not a cryptography expert; I do write software)

I am working with some youth (ages 11-13) and wanted to explore for an hour or so some basic cryptography. Doing symmetric ciphers is pretty straightforward. It's easy to explain the various "two key" metaphors of asymmetric encryption, but I'm finding it hard to find a good easy-to-work mathematical example of asymmetric encryption. There are lots of good examples of RSA broken down, but even with small numbers you get into "big" numbers fast because of the power functions.

Is there a good example of a "toy" algorithm to illustrate the asymmetric encryption/decryption process?

This might not be the mathematical example you are looking for, but it is an easy-to-understand metaphor.

In symmetric encryption, Alice and Bob each have a copy of the same key. They exchange messages by putting them in a box locked with a padlock that can be locked and unlocked with the keys. The padlock needs a key to be locked. They then exchange the locked box between themselves, using postal services.

In the corresponding asymmetric encryption metaphor, the public key is an open padlock, and the private key is the corresponding key. Alice gives identical padlocks to everyone asking for it. Bob gets one. Bob puts its message with his open padlock in a box, locks it with Alice's padlock, then sends it to Alice using postal services. In the same way, Alice can reply to Bob, and so on. Alice and Bob do not need to share the same key, and the open padlocks can be stolen or copied without consequences.

There is probably little sense in trying to explain the math before they get a good high-level grasp of what's happening. And for that, there is a paint-mixing analogy, http://maths.straylight.co.uk/archives/108.

I would hate lying to any audience and presenting something as asymmetric crypto, when it is actually a poor caricature of that. Most introductions using RSA fall into that trap because the numbers used are unrealistically small, and the oversimplified system allows to check a guess of plaintext, and to decipher letter by letter with less effort than it takes the legitimate receiver to decipher. On top of that, the math in RSA is relatively complex: even adults with some math background get lost on computing d from p, q, and e.

I'll thus use a simpler system: ElGamal encryption, which uses much simpler math.

I believe that a sizable fraction of a 17yo audience would be able to understand and even reproduce it. But only a very small fraction of 11-13yo would. It took centuries of effort to find asymmetric crypto, that's for a reason.

We'll agree on a large number obtained in Python with p = 2**3753 + 3**2368. [1].

Given two integers g and x, Python can quickly compute the integer r = pow(2, x, p) [2]. However, for large random x, the problem of finding x from r is believed intractable by all computers that exist today.

During a so-called key generation phase, Alice chose a large secret integer PrivateKey, and from that compute and publish Publickey. In Python that's 4 lines:

import secrets
p = 2**3753 + 3**2368
PrivateKey = secrets.randbits(500)
Publickey = pow(2, PrivateKey, p)

In order to send a message M of b bytes (up to 450 bytes, enough for most tweets) to Alice, someone enciphers as follows:

• obtains Alice's Publickey
  


• chooses a large random x using secrets.randbits(500) as above


• computes s = pow(2, x, p)
  


• computes r = pow(Publickey , x, p)
  


• keeps the low-order b bytes of that r
  


• transforms message M using XOR with the above b bytes, giving ciphertext C
  


• sends s and C to Alice

Upon receiving s and C, Alice deciphers as follows:

• finds the length b of the ciphertext C
  


• computes r = pow(s, PrivateKey , p) which will be the same r as in encryption [3]


• keeps the low b bytes of that r
  


• transforms ciphertext C using XOR with the above b bytes, giving the original message M.

The amazing thing is that the sender needs nothing secret to send a confidential message to Alice, something that symmetric crypto does not allow.

[1] That p = 2**3753 + 3**2368 is a prime with a simple form because that's easier to key (yet not so simple as to enable SNFS attacks); is more than 128-bit larger than our maximum message size of 450 bytes (because that avoids a mostly theoretical attack); and such that pow(2, (p-1)//2, p) == 1 (because that's customary, and is the case for about half the primes).

[2] pow(g, x, p) is defined as the integer r in the interval [0, p) such that g multiplied by itself x times is r above some multiple of p. Python's pow computes that r quickly by a method similar to:

• set r to 1
  


• while x is not zero
  
  
  • if x is odd
  
  
  • compute (r*g)%p giving r
    
  
  
  • compute (g*g)%p giving g
    
  
  
  • compute x//2 giving x
    
  
  

[3] By applying the definition of pow at the beginning of [2], it follows that the values of r computed by the sender and Alice both are pow(2, x*PrivateKey, p).

The classical trapdoor cage for lobsters is a good analogy.

The lobsters can enter very easily -> Everybody can encrypt with the public key

The lobsters can not get out without the opening the lock. Only the key owner of the lock can open -> Only private key holder can decrypt.

This analogy one more merit: There is a negligible chance that some lobsters can escape -> there is a negligible chance that you can find the key by trying some values ( assuming the scheme is secure)

And, you can buy some trapdoor for demonstration, at least for mice.

To teach 11-13 yo kids, i wouldn't talk about symmetric/asymmetric crypto cause, IMHO, it's far too complicated and will probably be boring for that audience.

Instead, i would mostly talk about Caesar Cipher because it's easy to understand and they can experiment by themself.
Then, to conclude, i would have some words about "real life" crypto, but no more than 10/15 minutes.