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 (a slight variant of) 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 (or try it online!):A
# 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.
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. $\endgroup$