# In search of a pedagogically simple example of asymmetric encryption routine?

(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?

• Unfortunately, the simplest we have that is real assymetric crypto with modern security requires the notion of modular exponentiation. That can be done in a few lines of python, though (thanks to the optional third argument of pow). Would you be interested in that ? The candidates are RSA, and ElGamal encryption. The second is actually simpler if you do not want to fool the audience by oversimplifying. – fgrieu Sep 27 '19 at 17:22
• Here's a little parable I made up a while ago to illustrate how RSA works. You might perhaps find it useful. – Ilmari Karonen Sep 28 '19 at 0:28
• What toy examples do you use for symmetric cryptography? Does it have to be asymmetric encryption or would asymmetric key agreement or signature (which are generally more important in practice than public-key anonymous encryption) serve too? – Squeamish Ossifrage Sep 28 '19 at 2:18

## Asymmetric encryption: What?

Alice wants to be able to receive messages sent by anyone, posted on a public website or whatsapp group, that only her will be able to decipher. Traditional cryptography would require that the sender and her share some secret (key or password), used for encryption and decryption.

In asymmetric encryption, Alice generates and keep a secret private key, and openly shares a corresponding public key. Anyone with Alice's public key can encipher a message to her. Alice's private key is necessary to decipher it.

Asymmetric cryptography also includes digital signature: Alice signs data with her private key, then anyone with Alice's trusted public key can verify that she signed that exact data. All this was thought impossible until the 1970's. It is now commonplace, e.g. in web browsers.

## Asymmetric encryption: How?

It's done with mathematics. Only a computer can realistically perform the computations. One of the commonly used method is ElGamal encryption. We can illustrate that with a little Python.

We'll use Python's pow(a, x, n). It computes "a to the power x modulo n". In this, "a to the power x" means x copies of the number a multiplied together; and "modulo n" means that we keep what remains when dividing by n.

Take pow(2, 4, 10) for example. "2 to the power 4" is 2×2×2×2, that is 16. When we split 16 things among 10 persons, each gets 1 and it remains 6.
Therefore, pow(2, 4, 10) yields 6.

Alice will chose a private key at random, and compute her public key as
PublicKey = pow(2, PrivateKey, n). This is easy and fast in Python, but computing PrivateKey from PublicKey is believed infeasible by even the most powerful computer, when n is a large-enough safe prime, and PrivateKey is random and large. n is typically made public, like this. We'll use something just as safe but easier to key-in:

# Setup
import secrets                      # needed for randbits
n = 2**4096 - 3**2542 + 3547696     # some public 4096-bit safe prime

# Alice generates her keys
PrivateKey = secrets.randbits(400)  # generate secret Private Key
PublicKey = pow(2, PrivateKey, n)   # compute Public Key

# Barnabé got PublicKey and wants to send a message to Alice
M = "Surprise for you in my locker, code 47918. Barnabé"
# turn M into an integer m, at most 500 bytes
m = int.from_bytes(bytes(M, 'utf-8'), byteorder='big')
assert m.bit_length()<=4000         # bark if message is too large

# encryption of m into Ciphertext
x = secrets.randbits(400)           # number used once
r = pow(2, x, n)                    # Alice need this to decipher
s = pow(PublicKey, x, n)            # shared one-time secret
c = (s%(2**4000)) ^ m               # produce ciphertext using XOR

# remove Barnabé's secrets
del M, m, x, s

# Alice receives ciphertext c and r, and deciphers that using PrivateKey
s = pow(r, PrivateKey, n)           # shared one-time secret
m = (s%(2**4000)) ^ c               # decipher using XOR
# turn integer m into a string M
M = str(m.to_bytes((m.bit_length()+7)//8, byteorder='big'), 'utf-8')
print(M)                            # show the deciphered message

# remove Alice's secrets, except her PrivateKey which can be reused
del s, m, M


The values of s computed by the sender during encryption is pow(pow(2, PrivateKey, n), x, n), that used by Alice during decryption is pow(pow(2, x, n), PrivateKey, n), and thanks to mathematical properties of pow these are the same.

Summary: with asymmetric encryption, nothing secret is needed to send a confidential message. We can do with some clever math, a trusted computer able to generate random numbers, and the trusted public key of the intended receiver.

## Pedagogical notes

While I believe that a sizable fraction of a 17yo audience would be able to grasp/appropriate/extend the above, only a small fraction of 11-13yo would. Thus I think the best with such young audience is to explain what asymmetric encryption does (and if possible digital signature, which is at least as useful). Illustrate that using key generation/encryption/decryption boxes with the corresponding Python code inside as small characters or truncated, and the values exchanged shortened with ellipsis, but do not dive into exactly what the code does. But give access to material (source code) showing how this is done and allowing to reproduce it. Those ready for that might use it.

ElGamal encryption is a direct transposition for encryption of Diffie-Hellman key exchange, one of the first asymmetric cryptosystem published. It is using that for all positive integers $$a,n,\text{PrivateKey},x$$, $${\left(a^\text{PrivateKey}\right)}^x\equiv a^{\text{PrivateKey}\,x}\equiv a^{x\,\text{PrivateKey}}\equiv{\left(a^x\right)}^\text{PrivateKey}\pmod n$$ and, for $$n$$ a large safe prime and most $$a$$ including 2, if $$x$$ and $$\text{PrivateKey}$$ are chosen at random, with $$a$$, $$n$$, $$a^\text{PrivateKey}\bmod n$$ and $$a^x\bmod n$$ public but $$\text{PrivateKey}$$ and $$x$$ are large random unknowns, then $$a^{x\,\text{PrivateKey}}\bmod n$$ is believed computationally indistinguishable from random in $$\Bbb Z_n^*$$ except for 1 bit of information. If we spare some high-order bits, the low-order ones are a shared secret, which we use for symmetric encryption using XOR.

This is not toy cryptography. That's IND-CPA secure asymmetric encryption in the academic sense. Parameters give a very high security level. The later has no penalty in a pedagogical context since the computations can't be done by hand anyway, and the code remains fast enough on anything running Python 3.

However, it must be noted that ElGamal encryption, and the code, have serious shortcomings:

• There's nothing to prevent alteration of Alice's public key on its way to Barnabé, and that allows an attack. Barnabé could be tricked to use some adversary's public key instead of Alice's, and then the adversary could decipher the message and access Barnabé's locker.
• There's no authentication: Alice is not sure that the message is from Barnabé. Anyone can encipher any message towards her.
• There's worse: an adversary can subtly alter the message and get some information. For example: guessing that the message ends in Barnabé (because he always do that), an adversary could alter the ciphertext so that what Alice deciphers ends with a different name. Alice might try and fail to open that other person's locker; and if the adversary rigged that locker to beam Alice's attempted code, the attacker now can access Barnabé's locker before Alice can. More generally, the scheme lacks IND-CCA2 security.
• Secure storage of keys and key distribution are not illustrated.
• Ciphertext transmission/reception is eluded.
• The code is not protected against implementation attacks (e.g. padding oracle, timing and side-channels).

Small parameters would limit the message size, or make the code more complex. That would also be teaching kids to make unnecessary compromise (in the same spirit, I have not limited the message to ASCII, and it's size is range-checked, because we should promote sound coding habits when possible). However, there can be imperatives to use smaller values, like adapting the demo code to an environment without built-in support for large integers, or actually transferring the values between individuals on paper. In that case, perhaps limit message to 24 bits (3 bytes, good for 3 or 4 characters), change n to 2147481143, 2**4000 to 16777216, and use random integers in range [1, 1073740570] for PrivateKey and x. Of course, all security is lost: a programmable calculator can find the private key.

I have refrained from introducing RSA, because it uses heavier math (we need modular inversion and the little Fermat theorem to explain why it works), and RSA is harder to implement. Worse, most pedagogical implementations have a fundamental shortcoming: a guess of the plaintext (e.g. a name on the class roll) can be verified from the ciphertext. Independently, the parameters are typically so small that this check can be made letter by letter; and re-encrypting the ciphertext a small and fixed number of time is enough to decipher without any guesswork. Also the modulus can be factored, typically by hand (perhaps with Fermat's method).

My point of view is that it is best not to mislead an audience, especially a young one, into believing they understand how asymmetric encryption works, or that it can be done with 10-digit numbers. It took centuries of effort to devise it, and that's because it's hard.

I’ve had some success by starting with “Imagine a world where everyone can multiply numbers, but division is extremely hard” (plus there exists an algorithm to generate two numbers with product 1). That plus the padlock analogy seems to be enough to get the point across. I can conclude by outlining some examples of real-life hard-to-invert functions.

Bear in mind not many children aged 11–13 are well-versed in functions, function composition, inverse functions etc. Plus you can’t really do much without group theory, and despite it being a fascinating subject with introductory examples readily accessible to young learners, together with cryptography it might be too much.

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.

• Yes, we'll do this. I've found lots of good examples like this. The problem then becomes "but how do you do that in math?" And with only massive numbers and lots of steps, it's just "another kind of magic." I want to be able to take a "Hello World" message of a few characters, and then let them see how a math algorithm (even if easily intuited) can do this. Once they can see that, then you can talk about trap door functions and their role in the process. – Travis Griggs Sep 27 '19 at 16:41
• I love the "open padlock" metaphor. I don't know why I've never run across it before! – schroeder Sep 27 '19 at 22:21

You can create a scheme that's similar to RSA using modular multiplication. It's far from secure, but it's feasible to calculate the values by hand.

public key = (e, n) = (23, 839)

private key = (d, n) = (73, 839)

message = m = 628

cyphertext = c = (m * e) % n = 538

decrypted = (c * d) % n = 628

The trick is that (e * d) % n = 1

• I think that's a fine introductory example for beginners. The teacher would provide a lot of additional description... they may need an explanation of the mod function, and the difficulty of finding prime factors (when the numbers are large), but the essence of asymmetric encryption is there. – Elroy Flynn Sep 28 '19 at 20:53
• I'll add that you can find a similar example, with more formality, in Paar and Pelzl's excellent textbook "Understanding Cryptography". See example 7.1 – Elroy Flynn Sep 28 '19 at 21:02
• The only asymmetric thing about it is that the encryption and decryption keys are different. That would be true for modular addition too. This is security by obscurity, where obscurity comes from most of the audience not yet knowing modular inversion. – fgrieu Sep 29 '19 at 8:14
• @fgrieu, yes this algorithm does not reall offer any security. But I think it fits OP's requirements of a "pedagogically simple example". – Nathan FD Sep 29 '19 at 14:47

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. A brief recap: Alice and Bob each produce shared secret by mixing three colors: own private + [base + the other's private]. The observer, Eve, can only obtain the publicly seen [base + the other's private] mixture for each, but from that she cannot obtain the final mix because she does not know the private colors. Alice and Bob use the shared secret to encrypt their messages* and their private keys to decrypt. * Technically, what's described above is the process for obtaining a shared assymetric key, which is then used to agree on a computationally faster symmetric key, which will be used from then on in the communication.

• This is almost a link-only answer. Could you explain a bit more?' – kelalaka Sep 27 '19 at 21:13
• I love the link though. That is a great resource. – Travis Griggs Sep 28 '19 at 2:45
• Yeah, this would be a great answer if you could explain the basic principles in the answer itself instead of link-only. – jpa Sep 28 '19 at 6:09
• @fgrieu I updated my answer – postoronnim Sep 30 '19 at 15:48
• Got it. The assumption is that knowing the Public color obtained by mixing paint of Base and a secret Private color, one can not find the Private color. "Without an encyclopedic knowledge of all combinations of paint, Eve cannot know what private colors have been used to generate the public ones. So her only apparent option is to keep trying candidates, mixing each of them with the base coat until she arrives at one of the public colors by sheer luck. This brute force approach will obviously take a very long time!". With that assumption, the system kinda works. But a 11yo can prove it wrong. – fgrieu Sep 30 '19 at 16:39

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 the demonstration, at least for mice.

Note: If you consider a trapdoor is bad for ages 11-13 you can go for locked cash boxes; 