Cryptography.

The Scene at this step

Alice's secret

6

Locked message / The maths

The maths

Accepted within

± 0.01

A fixed value in the question

Wrong answers it recognises

• 3 ± 0.01

  Misconception: Gives the quotient of the division (how many times it goes in) instead of the remainder.

  Feedback from the catalogue

  “$a \bmod n$⁠” is the remainder when $a$⁠ is divided by $n$⁠, not the result of the division. In $17 \div 5$⁠ five goes in $3$⁠ times, $3 \times 5 = 15$⁠, and $2$⁠ is left: so $17 \bmod 5 = 2$⁠. The remainder is always between $0$⁠ and $n - 1$⁠, like a place on a clock with $n$⁠ places.

• 3.4 ± 0.01

  Misconception: Gives the quotient of the division (how many times it goes in) instead of the remainder.

  Feedback from the catalogue

  “$a \bmod n$⁠” is the remainder when $a$⁠ is divided by $n$⁠, not the result of the division. In $17 \div 5$⁠ five goes in $3$⁠ times, $3 \times 5 = 15$⁠, and $2$⁠ is left: so $17 \bmod 5 = 2$⁠. The remainder is always between $0$⁠ and $n - 1$⁠, like a place on a clock with $n$⁠ places.

Hint

Worked solution

The Scene at this step

Alice's secret

6

Locked message / The maths

The maths

Accepted within

± 0.01

A fixed value in the question

Wrong answers it recognises

• 17 ± 0.01

  Misconception: Forgets to wrap round: gives the plain result instead of its remainder mod n.

  Feedback from the catalogue

  In modular arithmetic every result wraps back onto the clock: after $n - 1$⁠ comes $0$⁠. Nine o’clock plus $8$⁠ hours is not $17$⁠ on a $12$⁠-hour clock, but $17 \bmod 12 = 5$⁠. Powers too: $5^2 = 25$⁠, but $5^2 \bmod 23 = 2$⁠. After each calculation, divide by $n$⁠ and keep only the remainder.

Hint

Worked solution

The Scene at this step

Alice's secret

2fixed

Locked message / The maths

Mixing paintfixed

Accepted within

± 0.01

Computed from the Scene at this step’s setting

What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic

Wrong answers it recognises

• 25 ± 0.01

  Misconception: Forgets to wrap round: gives the plain result instead of its remainder mod n.

  Feedback from the catalogue

  In modular arithmetic every result wraps back onto the clock: after $n - 1$⁠ comes $0$⁠. Nine o’clock plus $8$⁠ hours is not $17$⁠ on a $12$⁠-hour clock, but $17 \bmod 12 = 5$⁠. Powers too: $5^2 = 25$⁠, but $5^2 \bmod 23 = 2$⁠. After each calculation, divide by $n$⁠ and keep only the remainder.

• 10 ± 0.01

  Misconception: Multiplies the base by the exponent (5 × 6) instead of raising it to that power (5⁶).

  Feedback from the catalogue

  $g^a$⁠ means multiplying $g$⁠ by itself $a$⁠ times, not multiplying $g$⁠ by $a$⁠. $5^3 = 5 \times 5 \times 5 = 125$$5^3 =$$5 \times 5 \times 5 =$$125$⁠, not $5 \times 3 = 15$⁠. Mod $p$⁠ you do it step by step: each power is the one before times $g$⁠, then the remainder. From $5^2 \bmod 23 = 2$⁠ you get $5^3 \bmod 23 = 2 \times 5 = 10$$5^3 \bmod 23 =$$2 \times 5 =$$10$⁠.

• 1 ± 0.01

  Misconception: Gives the quotient of the division (how many times it goes in) instead of the remainder.

  Feedback from the catalogue

  “$a \bmod n$⁠” is the remainder when $a$⁠ is divided by $n$⁠, not the result of the division. In $17 \div 5$⁠ five goes in $3$⁠ times, $3 \times 5 = 15$⁠, and $2$⁠ is left: so $17 \bmod 5 = 2$⁠. The remainder is always between $0$⁠ and $n - 1$⁠, like a place on a clock with $n$⁠ places.

Hint

Worked solution

The Scene at this step

Alice's secret

1

Locked message / The maths

The mathsfixed

Read from the Scene at

What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic

One setting that reaches it

Alice's secret

3

Hint

Worked solution

The Scene at this step

Alice's secret

3fixed

Locked message / The maths

The mathsfixed

Once the prediction is locked in, the Scene changes

Alice's secret

4fixed

The Scene then shows: 4 · What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic

A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.

Hint

Worked solution

The Scene at this step

Alice's secret

3fixed

Locked message / The maths

The mathsfixed

Choices

• Correct $1$⁠: after $22$⁠ steps the powers come back to the start

• Wrong $22$⁠, the last place on the dial

  Feedback

  There is no reason the $22$⁠nd power should land on place $22$⁠: the powers leap about, and $5^{11} \bmod 23$⁠ already lands there.

• Wrong $0$⁠: the power is so big that it reaches a multiple of $23$⁠

  Feedback

  $5^{22}$⁠ is a product of fives only, and $23$⁠ is prime, so $23$⁠ never divides it: the remainder is never $0$⁠, however large the exponent.

Once the prediction is locked in, the Scene changes

Alice's secret

22fixed

The Scene then shows: 1 · What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic

A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.

Hint

Worked solution

The Scene at this step

Count up to

100

Sieve the spiral

Spiralfixed

Choices

More than one choice is correct: every one must be selected.

• Wrong $1$⁠

  Misconception: Counts 1 as a prime number.

  Feedback from the catalogue

  A prime is a whole number with exactly two divisors: $1$⁠ and itself. $1$⁠ has only one divisor, so it is neither prime nor composite. The definition was chosen so that every number has only one way to be written as a product of primes: if $1$⁠ were prime, you could write $6 = 2 \times 3 = 1 \times 2 \times 3$$6 =$$2 \times 3 =$$1 \times 2 \times 3$⁠ and in endless other ways.

• Correct $2$⁠

• Wrong $51$⁠

  Misconception: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.

  Feedback from the catalogue

  An odd number is not divisible by $2$⁠, but it can be divisible by $3$⁠, $7$⁠ or any other prime. $51 = 3 \times 17$⁠, $91 = 7 \times 13$⁠ and $99 = 9 \times 11$⁠. To know a number is prime, check that no prime up to its square root divides it: for $91$⁠, check $2$⁠, $3$⁠, $5$⁠ and $7$⁠, and $7$⁠ divides it.

• Wrong $91$⁠

  Misconception: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.

  Feedback from the catalogue

  An odd number is not divisible by $2$⁠, but it can be divisible by $3$⁠, $7$⁠ or any other prime. $51 = 3 \times 17$⁠, $91 = 7 \times 13$⁠ and $99 = 9 \times 11$⁠. To know a number is prime, check that no prime up to its square root divides it: for $91$⁠, check $2$⁠, $3$⁠, $5$⁠ and $7$⁠, and $7$⁠ divides it.

• Correct $97$⁠

Hint

Worked solution

The Scene at this step

Count up to

100fixed

Sieve the spiral

Spiralfixed

Accepted within

± 0.1

Computed from the Scene at this step’s setting

The largest prime from 1 to count/nodes/spiral/outputs/largestPrime

Wrong answers it recognises

• 99 ± 0.1

  Misconception: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.

  Feedback from the catalogue

  An odd number is not divisible by $2$⁠, but it can be divisible by $3$⁠, $7$⁠ or any other prime. $51 = 3 \times 17$⁠, $91 = 7 \times 13$⁠ and $99 = 9 \times 11$⁠. To know a number is prime, check that no prime up to its square root divides it: for $91$⁠, check $2$⁠, $3$⁠, $5$⁠ and $7$⁠, and $7$⁠ divides it.

Hint

Worked solution

The Scene at this step

Count up to

400fixed

Sieve the spiral

Spiralfixed

Choices

• Correct $8$⁠: the primes up to $20$⁠

• Wrong $78$⁠: every prime up to $400$⁠

  Misconception: Thinks the sieve must cross out multiples of every prime up to the count, not just of the primes up to its square root.

  Feedback from the catalogue

  A composite number up to $n$⁠ always has a prime factor no bigger than $\sqrt{n}$⁠: if both its factors were bigger than $\sqrt{n}$⁠, their product would be bigger than $n$⁠. So once the sieve has run through the primes up to $\sqrt{n}$⁠, every composite has been crossed out. Up to $400$⁠, $\sqrt{400} = 20$⁠, and eight primes are enough: $2$⁠ to $19$⁠.

• Wrong $4$⁠: the primes $2$⁠, $3$⁠, $5$⁠ and $7$⁠

  Feedback

  $2$⁠, $3$⁠, $5$⁠ and $7$⁠ are enough up to $120$⁠, but not up to $400$⁠: $11^2 = 121$⁠, $13^2 = 169$⁠, $17^2 = 289$⁠ and $19^2 = 361$⁠ are composites none of them crosses out.

Once the prediction is locked in, the Scene changes

Sieve the spiral

0.62 (Spiral → Sieve and gaps)fixed

The Scene then shows: 8 · How many primes the sieve runs through (those up to √count)/nodes/spiral/outputs/sievingPrimes

A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.

Hint

Worked solution

The Scene at this step

Count up to

100

Sieve the spiral

Spiralfixed

Read from the Scene at

How many primes there are from 1 to count/nodes/spiral/outputs/primeCount

One setting that reaches it

Count up to

1000

Hint

Worked solution

The Scene at this step

Count up to

10000fixed

Sieve the spiral

Spiralfixed

Accepted within

± 0.05

Computed from the Scene at this step’s setting

How many primes there are from 1 to count/nodes/spiral/outputs/primeCount

Wrong answers it recognises

• 25 ± 0.05

  Misconception: Thinks primes keep the same share of the numbers however far you count, as the quarter below 100.

  Feedback from the catalogue

  The primes thin out. Up to $100$⁠ there are $25$⁠, a quarter of the numbers; up to $1000$⁠ there are $168$⁠, under a sixth; up to $10\,000$⁠ there are $1229$⁠, about an eighth. The bigger a number, the more smaller primes there are that might divide it. The chance that a number near $n$⁠ is prime is about $\tfrac{1}{\ln n}$⁠, which shrinks slowly. And still they never run out: Euclid proved there are infinitely many primes.

• 16.8 ± 0.05

  Misconception: Thinks primes keep the same share of the numbers however far you count, as the quarter below 100.

  Feedback from the catalogue

  The primes thin out. Up to $100$⁠ there are $25$⁠, a quarter of the numbers; up to $1000$⁠ there are $168$⁠, under a sixth; up to $10\,000$⁠ there are $1229$⁠, about an eighth. The bigger a number, the more smaller primes there are that might divide it. The chance that a number near $n$⁠ is prime is about $\tfrac{1}{\ln n}$⁠, which shrinks slowly. And still they never run out: Euclid proved there are infinitely many primes.

Hint

Worked solution

The Scene at this step

Count up to

10000

Sieve the spiral

Sieve and gaps

Choices

Shown in a random order.

• Correct It is a product of two primes, and finding them takes far longer than multiplying them

• Wrong It is prime, because it is not divisible by $2$⁠, $3$⁠, $5$⁠ or $7$⁠

  Misconception: Takes an odd number that has no obvious small factor, such as 51, 91 or 99, to be prime.

  Feedback from the catalogue

  An odd number is not divisible by $2$⁠, but it can be divisible by $3$⁠, $7$⁠ or any other prime. $51 = 3 \times 17$⁠, $91 = 7 \times 13$⁠ and $99 = 9 \times 11$⁠. To know a number is prime, check that no prime up to its square root divides it: for $91$⁠, check $2$⁠, $3$⁠, $5$⁠ and $7$⁠, and $7$⁠ divides it.

• Wrong Its factors are found as fast as you multiply

  Feedback

  To find the factors you have to try primes one after another, up to $\sqrt{8633} \approx 93$$\sqrt{8633} \approx$$93$⁠: twenty-four tries, and only the last, $89$⁠, works. All that instead of one multiplication.

Hint

Worked solution

The Scene at this step

Key size

56 bits

Unlock step by step

Locked messagefixed

Choices

Shown in a random order.

• Correct Eve copies the key too, and opens every message with it

• Wrong No trouble: the key is short, and Eve will not notice it

  Feedback

  Eve copies every capsule that passes, short or long. A key that went down the open tube is hers too.

• Wrong No trouble: lock the key with a second key

  Feedback

  Then Bob needs the second key, and down which tube? The problem only moves one step back. That is why for generations keys travelled by hand, by courier and at meetings.

Hint

Worked solution

The Scene at this step

Key size

8 bitsfixed

Unlock step by step

Locked messagefixed

Accepted within

± 0.5

A fixed value in the question

Wrong answers it recognises

• 512 ± 0.5

  Misconception: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.

  Feedback from the catalogue

  An $n$⁠-bit key has $2^n$⁠ values, because each bit doubles the number of possibilities. A key eight bits longer does not hold eight more keys, nor $\tfrac{64}{56}$⁠ times as many, but $2^8 = 256$⁠ times as many. And a key twice as long, $256$⁠ bits instead of $128$⁠, holds not twice as many keys but $2^{128}$⁠ times as many. That is why keys only a little longer put guessing out of all reach.

• 32 ± 0.5

  Misconception: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.

  Feedback from the catalogue

  An $n$⁠-bit key has $2^n$⁠ values, because each bit doubles the number of possibilities. A key eight bits longer does not hold eight more keys, nor $\tfrac{64}{56}$⁠ times as many, but $2^8 = 256$⁠ times as many. And a key twice as long, $256$⁠ bits instead of $128$⁠, holds not twice as many keys but $2^{128}$⁠ times as many. That is why keys only a little longer put guessing out of all reach.

Hint

Worked solution

The Scene at this step

Key size

56 bitsfixed

Unlock step by step

Locked messagefixed

Choices

• Correct $256$⁠ times

• Wrong $1.14$⁠ times, because the key is a seventh longer

  Misconception: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.

  Feedback from the catalogue

  An $n$⁠-bit key has $2^n$⁠ values, because each bit doubles the number of possibilities. A key eight bits longer does not hold eight more keys, nor $\tfrac{64}{56}$⁠ times as many, but $2^8 = 256$⁠ times as many. And a key twice as long, $256$⁠ bits instead of $128$⁠, holds not twice as many keys but $2^{128}$⁠ times as many. That is why keys only a little longer put guessing out of all reach.

• Wrong $8$⁠ times, because eight bits were added

  Misconception: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.

  Feedback from the catalogue

  An $n$⁠-bit key has $2^n$⁠ values, because each bit doubles the number of possibilities. A key eight bits longer does not hold eight more keys, nor $\tfrac{64}{56}$⁠ times as many, but $2^8 = 256$⁠ times as many. And a key twice as long, $256$⁠ bits instead of $128$⁠, holds not twice as many keys but $2^{128}$⁠ times as many. That is why keys only a little longer put guessing out of all reach.

Once the prediction is locked in, the Scene changes

Key size

64 bitsfixed

The Scene then shows: 0.5845 · The same in years of 365.25 days/nodes/kx/outputs/yearsToTryAll

A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.

Hint

Worked solution

The Scene at this step

Key size

40 bitsfixed

Unlock step by step

Locked messagefixed

Once the prediction is locked in, the Scene changes

Key size

48 bitsfixed

The Scene then shows: 281.5 s · Seconds Eve needs to try every key at guessRate keys a second/nodes/kx/outputs/secondsToTryAll

A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.

Hint

Worked solution

The Scene at this step

Key size

128 bits

Unlock step by step

Locked messagefixed

Read from the Scene at

The same in years of 365.25 days/nodes/kx/outputs/yearsToTryAll

One setting that reaches it

Key size

64 bits

Hint

Worked solution

The Scene at this step

Key size

128 bits

Unlock step by step

Locked message

Choices

Shown in a random order.

• Correct $2^{128}$⁠ times, about $3.4 \times 10^{38}$⁠

• Wrong $2$⁠ times

  Misconception: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.

  Feedback from the catalogue

  An $n$⁠-bit key has $2^n$⁠ values, because each bit doubles the number of possibilities. A key eight bits longer does not hold eight more keys, nor $\tfrac{64}{56}$⁠ times as many, but $2^8 = 256$⁠ times as many. And a key twice as long, $256$⁠ bits instead of $128$⁠, holds not twice as many keys but $2^{128}$⁠ times as many. That is why keys only a little longer put guessing out of all reach.

• Wrong $128$⁠ times, because $128$⁠ bits were added

  Misconception: Thinks the number of keys grows in step with the key's length, doubling when the length doubles, instead of doubling with every bit added.

  Feedback from the catalogue

  An $n$⁠-bit key has $2^n$⁠ values, because each bit doubles the number of possibilities. A key eight bits longer does not hold eight more keys, nor $\tfrac{64}{56}$⁠ times as many, but $2^8 = 256$⁠ times as many. And a key twice as long, $256$⁠ bits instead of $128$⁠, holds not twice as many keys but $2^{128}$⁠ times as many. That is why keys only a little longer put guessing out of all reach.

Hint

Worked solution

The Scene at this step

Alice's secret

6hidden

Bob's secret

15hidden

Locked message / The maths

Mixing paintfixed

Choices

Shown in a random order.

• Correct Yes: each mixes a secret colour of their own into the public one, sends the mixture, and adds their secret to what they receive

• Wrong No: first they must meet, or send the secret by courier

  Misconception: Thinks two parties can only agree on a secret key if some secret has already passed between them, in advance or down the channel.

  Feedback from the catalogue

  Everyone thought so until 1976, when Diffie and Hellman showed it is not true. In their key exchange no secret passes down the channel: each side keeps its secret, $a$⁠ or $b$⁠, and sends only $g^a \bmod p$⁠ or $g^b \bmod p$⁠. Each side combines the value it received with its own secret, and both reach the same $s$⁠. Eve sees everything that passes, and still has no fast way to reach $s$⁠.

• Wrong Yes, if each sends their secret colour fast enough

  Feedback

  Speed does not help: Eve copies every capsule, and a secret colour that goes down the tube is no longer secret.

Hint

Worked solution

The Scene at this step

Alice's secret

6fixed

Bob's secret

15fixed

Locked message / The maths

Mixing paintfixed

Accepted within

± 0.1

Computed from the Scene at this step’s setting

What Alice sends, A = gᵃ mod p/nodes/kx/outputs/alicePublic

Wrong answers it recognises

• 30 ± 0.1

  Misconception: Multiplies the base by the exponent (5 × 6) instead of raising it to that power (5⁶).

  Feedback from the catalogue

  $g^a$⁠ means multiplying $g$⁠ by itself $a$⁠ times, not multiplying $g$⁠ by $a$⁠. $5^3 = 5 \times 5 \times 5 = 125$$5^3 =$$5 \times 5 \times 5 =$$125$⁠, not $5 \times 3 = 15$⁠. Mod $p$⁠ you do it step by step: each power is the one before times $g$⁠, then the remainder. From $5^2 \bmod 23 = 2$⁠ you get $5^3 \bmod 23 = 2 \times 5 = 10$$5^3 \bmod 23 =$$2 \times 5 =$$10$⁠.

• 15630 ± 0.1

  Misconception: Forgets to wrap round: gives the plain result instead of its remainder mod n.

  Feedback from the catalogue

  In modular arithmetic every result wraps back onto the clock: after $n - 1$⁠ comes $0$⁠. Nine o’clock plus $8$⁠ hours is not $17$⁠ on a $12$⁠-hour clock, but $17 \bmod 12 = 5$⁠. Powers too: $5^2 = 25$⁠, but $5^2 \bmod 23 = 2$⁠. After each calculation, divide by $n$⁠ and keep only the remainder.

• 679 ± 0.1

  Misconception: Gives the quotient of the division (how many times it goes in) instead of the remainder.

  Feedback from the catalogue

  “$a \bmod n$⁠” is the remainder when $a$⁠ is divided by $n$⁠, not the result of the division. In $17 \div 5$⁠ five goes in $3$⁠ times, $3 \times 5 = 15$⁠, and $2$⁠ is left: so $17 \bmod 5 = 2$⁠. The remainder is always between $0$⁠ and $n - 1$⁠, like a place on a clock with $n$⁠ places.