Agreeing a key in the open
Both ends need the same key, but anything sent by radio is public. Each end mixes a private number with public numbers, swaps the mixes, and both arrive at the same key without it ever being sent.
Every time you open a secure web page, your computer and a server agree a key with a stranger, in public, in less than a second. This lesson is the idea behind it, with numbers small enough to follow by hand.
The last lesson needs both micro:bits to hold the same key. How do they get it? If one sends the key by radio, everyone in the group hears it (lesson 1). Meeting in person works for two friends, but not for a phone and a web server.
The trick: agree a key in public without ever sending it.
- Two public numbers are known to everyone: P = 23 and G = 5.
- Each micro:bit picks a private number and never tells anyone: say 6 and 15.
- Each sends a mix: G to the power of its private number, remainder after dividing by P. 5⁶ mod 23 is 8; 5¹⁵ mod 23 is 19. These are sent over the air.
- Each takes the other's mix and raises it to its own private number, mod P. 19⁶ mod 23 = 2, and 8¹⁵ mod 23 = 2. They match, and the key 2 was never sent.
The function modPow does "base to the power, remainder after dividing by prime" with a loop.
Behind the code: the mix travels with radio send value (in Radio), which sends a short name and a number together: here the name mix and the number. on radio received value gives the receiver both, as name and value, and name == "mix" checks the name; text must match exactly, capital letters included. A name can be 8 characters at most: a longer name is cut short on the way, so it no longer matches.
- Predict: Read the code and say what it will do before you run anything. A wrong guess is fine: it shows you what to look for.
- Run: Run it and compare the result with your prediction.
- Investigate: Trace how each line of code connects to what you see.
- Modify: Change the code on purpose and check the result.
- Make: Build something new using what you have learned. Expect a few tries; that is normal.
Make your prediction first. Help opens once you've locked it in.
Predict
Show as code
// Public numbers everyone may know
let P = 23
let G = 5
// This micro:bit's own secret number (the other micro:bit has 15)
let secret = 6
let shared = 0
function modPow(base: number, power: number, prime: number): number {
let result = 1
for (let i = 0; i < power; i++) {
result = (result * base) % prime
}
return result
}
radio.setGroup(5)
input.onButtonPressed(Button.A, function () {
radio.sendValue("mix", modPow(G, secret, P))
})
radio.onReceivedValue(function (name, value) {
if (name == "mix") {
shared = modPow(value, secret, P)
basic.showNumber(shared)
}
})
Run
Each simulated micro:bit picks its own random private number. Press A on both (one after the other) and compare the numbers shown.
Show as code
let P = 23
let G = 5
let secret = randint(2, 20)
let shared = 0
function modPow(base: number, power: number, prime: number): number {
let result = 1
for (let i = 0; i < power; i++) {
result = (result * base) % prime
}
return result
}
radio.setGroup(5)
input.onButtonPressed(Button.A, function () {
radio.sendValue("mix", modPow(G, secret, P))
})
radio.onReceivedValue(function (name, value) {
if (name == "mix") {
shared = modPow(value, secret, P)
basic.showNumber(shared)
}
})
Investigate
Show as code
// Public numbers everyone may know
let P = 23
let G = 5
// This micro:bit's own secret number (the other micro:bit has 15)
let secret = 6
let shared = 0
function modPow(base: number, power: number, prime: number): number {
let result = 1
for (let i = 0; i < power; i++) {
result = (result * base) % prime
}
return result
}
radio.setGroup(5)
input.onButtonPressed(Button.A, function () {
radio.sendValue("mix", modPow(G, secret, P))
})
radio.onReceivedValue(function (name, value) {
if (name == "mix") {
shared = modPow(value, secret, P)
basic.showNumber(shared)
}
})
A micro:bit with private number 3 sends its mix: 5³ mod 23. What number goes out? (5³ = 125.)
Which of these cross the air, and which stay on one micro:bit?
Modify
First press A on both micro:bits, so each works out shared. Then let B send the number 7 locked with shared, and show it unlocked on the other.
Need a hint?
B sends a secret number locked with shared: radio send number (7 ^ shared). On radio received number, show received number ^ shared.
B sends a number locked with the agreed key; the other micro:bit unlocks it.
This ticks by itself when your blocks do what is asked.
Make
Put it together: A sends your mix and each micro:bit works out the shared key and shows a tick; B sends a PIN locked with it; the other micro:bit unlocks and shows the PIN. The key was never sent.
Need a hint?
A sends the mix; when a mix arrives, work out shared and show a tick.
Another hint
B sends pin ^ shared; a number received is shown after ^ shared.
A key exchange, then a locked PIN: A sends the mix and the key is worked out, B sends the PIN locked with it, and the receiver unlocks it.
This ticks by itself when your blocks do what is asked.
For teachers
Students agree a key over an open channel with a Diffie–Hellman style exchange using small numbers, then use it as the key for XOR. About 55 minutes.
Open the teacher guide: answers, solutions, slides and a worksheet.
Students will be able to
- I can explain why a key cannot simply be sent by radio.
- I can say which numbers cross the air and which stay private in a key exchange.
- I can use an agreed number as the key for a cipher.
Before class
The idea: two ends agree a shared key while everyone listens. Each mixes a private number with public numbers, swaps the mixes, and mixes again with its private number. Both reach the same number, which was never sent. This is the Diffie–Hellman key exchange, the idea behind the padlock in a browser.
Everyday picture: paint. Everyone knows the common colour (yellow). Each person adds a private colour and shares the mixture. Each then adds their private colour to the other's mixture. Both end with the same colour, and nobody can un-mix the shared one to find the private colours. Where it breaks: with numbers there is no real un-mixing for big numbers, but for tiny numbers you can just try them all.
The maths: students need only the pattern "power, then remainder". The check numbers are small. The program does the working (modPow, a loop, as in micro:bit Foundations).
Honest limits: P = 23 can be broken by trying all private numbers (the third Investigate task says so). Also, a key exchange does not say who you are talking to: an unknown micro:bit could do the exchange too. That need, to prove who is who, is the next lessons' job.
Running the lesson
- Predict: let students work out the mixes on paper or with a calculator first.
- Run: remind them to press A on both micro:bits before reading the numbers.
The hard part (on purpose)
Following a key exchange where the shared key never travels. Ask them to trace on paper what each micro:bit sends and what it keeps private.
When students get stuck
- The two micro:bits show different numbers. Ask: Did you press A on both before looking? Does each hear the other's mix? Fix: Both must send a mix and receive one. Use the same group.
- The numbers are far too large or wrong. Ask: Is modPow taking the remainder at every step? Fix: result = (result × base) % prime inside the loop.
Stretch and support
Stretch: Change P and G. Which private numbers still give a match? (All of them do: the method works for any P and G.)
Support: Give the exchange complete and ask only for the locked PIN.
Where it leads
Next: how does the receiver know a message was not changed on the way?
What each step is for
- Investigate: The shared key is worked out on each micro:bit from a private number that never leaves it. What goes through the air is not enough to find the key quickly, once the numbers are big.
- Modify: Once both ends have the same number, it can be the key for the cipher from the last lesson.
- Explain why a key cannot simply be sent by radio.
- Say which numbers cross the air and which stay private in a key exchange.
- Use an agreed number as the key for a cipher.