Agreeing a key in the open

Classroom resources

Load these into Waypoints Prepare: choose Load URL and paste the copied address, or download the file and import it. In Prepare, the worksheet's Teacher edition shows the answers; the student copy hides them.

• Slides Download Copy address for Prepare Present from the browser, or export to PowerPoint or PDF.
• Worksheet Download Copy address for Prepare Print the student copy; the Teacher edition has the answers.

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.

Timing

Predict and Run 12 min · Investigate 12 min · Modify 10 min · Make 18 min

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

1. Predict: let students work out the mixes on paper or with a calculator first.
2. 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

Answers to the checks

1. Predict: One micro:bit has private number 6 (this program) and the other has 15. Both press A, so each hears the other's mix. What does each micro:bit show?
   2 on both. The micro:bit with 6 receives 19 and shows 19⁶ mod 23 = 2; the one with 15 receives 8 and shows 8¹⁵ mod 23 = 2.
2. Mixes and keys: A micro:bit with private number 3 sends its mix: 5³ mod 23. What number goes out? (5³ = 125.)
   10
   125 ÷ 23 is 5 with remainder 10, so the mix is 10.
3. What goes across: Which of these cross the air, and which stay on one micro:bit?
   P and G → Crosses the air; The mix (8 or 19) → Crosses the air; A private number (6 or 15) → Stays on one micro:bit; The shared key (2) → Stays on one micro:bit
4. Why the toy numbers are weak: With P = 23 anyone who hears the mixes could simply try every private number from 1 to 22. Why is the real thing safe?
   The real P and private numbers have hundreds of digits, so there are far too many to try
   This is the same lesson as the Caesar cipher: a small number of keys can be tried one by one. Real systems use numbers so large that trying them all would take longer than the age of the universe.

Solutions

One possible solution for each task. Other correct programs are fine.

Modify

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))
})
input.onButtonPressed(Button.B, function () {
    radio.sendNumber(7 ^ shared)
})
radio.onReceivedValue(function (name, value) {
    if (name == "mix") {
        shared = modPow(value, secret, P)
        basic.showNumber(shared)
    }
})
radio.onReceivedNumber(function (receivedNumber) {
    basic.showNumber(receivedNumber ^ shared)
})

Make

let P = 23
let G = 5
let secret = randint(2, 20)
let shared = 0
let pin = 4271
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))
})
input.onButtonPressed(Button.B, function () {
    radio.sendNumber(pin ^ shared)
})
radio.onReceivedValue(function (name, value) {
    if (name == "mix") {
        shared = modPow(value, secret, P)
        basic.showIcon(IconNames.Yes)
    }
})
radio.onReceivedNumber(function (receivedNumber) {
    basic.showNumber(receivedNumber ^ shared)
})

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.

Exit ticket

Which of the numbers go across the air in a key exchange?

P, G and the two mixes. The private numbers and the shared key never do.

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.

Where it leads

Next: how does the receiver know a message was not changed on the way?