Two Strangers Shout Numbers at Each Other Across a Crowded Room and Walk Away Sharing a Secret Nobody Else Heard

Last timeWhat a Watcher Can See

The central trick of the whole subject, worked by hand with numbers small enough to check. Two parties agree a secret while an eavesdropper records every message they send.

The trick in colours

Two people want a shared secret. They have never met, they have no prior

arrangement, and everything they say to each other is heard by a third person

who writes it all down. This sounds impossible, and the usual way to see that

it is not involves paint.

Both agree publicly on a starting colour, say yellow. Each privately chooses a

secret colour and mixes a litre of it into their own yellow. Each sends the

mixture to the other. Each then mixes their own private colour into the

mixture they received.

Both now hold yellow plus both private colours, which is the same thing. The

listener holds yellow, and the two mixtures, and cannot separate a mixture back

into its components.

FIG 1The exchange, with what the listener records

Note that the two sides never send anything twice and never need a prior shared anything. One message each way, and a secret exists that neither of them had a minute earlier. This is the step that makes encryption between strangers possible at all.

Doing it with numbers

The paint is an analogy and it is worth doing the real thing once, with numbers

small enough to check on paper.

The public starting values are a prime, call it the modulus, and a base. Take

the modulus to be 23 and the base to be 5. Both are public and an eavesdropper

knows them.

FIG 2The whole exchange with a modulus of 23

plaintext

public values: modulus 23, base 5

one side picks the private value 6
  sends 5 to the power 6, remainder 23
  5^6 is 15625, and 15625 remainder 23 is 8
  so it sends 8

other side picks the private value 15
  sends 5 to the power 15, remainder 23
  5^15 is 30517578125, remainder 23 is 19
  so it sends 19

one side computes 19 to the power 6, remainder 23, which is 2
other side computes 8 to the power 15, remainder 23, which is 2

both now hold 2, and the listener holds 23, 5, 8 and 19

Eight and nineteen crossed the wire. Six and fifteen never did, and two is known to both sides and to nobody else. The numbers here are small enough that a listener could simply try every private value from one to twenty-two, which is exactly the attack that large numbers are chosen to prevent.

FIG 3Why both sides reach the same value

: the shared secret both sides end up with
: the public base, known to everyone including the listener
: the private value chosen by one side and never sent
: the private value chosen by the other side and never sent

Everything happens with remainders after dividing by the modulus, which is left out here to keep the identity visible. The whole method is this line: raising to one power and then another gives the same answer in either order, so two parties applying their own exponent to the other published value arrive at the same place.

FIG 4Who knows what at the end

	one side knows it	the other side knows it	it was sent on the wire	the listener knows it
the public values	1	1	1	1
the first private value	1	1	0	1
the second private value	1	0	1	1
the shared secret	1	1	1	0

The two marked cells are the result. The shared secret is known to both sides, was never sent, and is not known to the listener. Read the third column on its own and notice that only public values ever crossed the wire, which is what makes this usable between strangers.

What the difficulty rests on

The listener holds the modulus, the base, and the two published values, and

needs one of the private values. Recovering an exponent from the result of

raising a base to it, with a remainder taken, is the problem in question.

There is no known fast method for it at the sizes used. That is the whole

claim, and it is worth being precise about what kind of claim it is.

It is not a proof. Nobody has shown that no fast method exists, and if one were

found tomorrow a great deal of deployed encryption would stop working. What

exists instead is fifty years of a great many capable people trying, and a

steady but slow improvement in the best known methods, which is enough to

choose sizes against but is not a guarantee.

This is the general situation in the subject and it is better understood than

feared. The methods in use are the ones that have survived the most sustained

public attempt to break them, which is a different and more reliable thing than

a method nobody has examined.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents