Associated Topics || Dr. Math Home || Search Dr. Math

### Missile Launch Code

```Date: 08/03/2003 at 15:55:55
From: Dave
Subject: Brain Teaser

Let's say that the President and 9 of his most trusted associates have
the power to launch nuclear missiles. There is typically a launch
code, and for our purpose, it is a number. However, the public doesn't
just trust one person to hold that much power. In fact, they don't
trust two people either. If there are 3 of those 10 people together,
then and only then can they launch the nuclear weapons.

What kind of information could you give all 10 people such that if any
3 of them were to get together, they would be able to launch the
missiles, but if there were only 2 of them, the information would be
insufficient to figure out the code?
```

```
Date: 08/05/2003 at 05:32:31
From: Doctor Jacques
Subject: Re: Brain Teaser

Hi Dave,

There is an easy technique for doing this.

As you certainly know, given two distinct points, there is one and
only one straight line through these points. More generally, given n
points (x,y) in the plane (where the x's are all different), there is
one and only one polynomial of degree n-1 whose graph passes through
the points. The coefficients of the polynomial can be computed, for
example, by Lagrange's interpolation formula; see:

http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html

or by solving a system of linear equations (one for each point) with
the coefficients of the polynomial as unknwons.

In this case, we want to have all information from 3 points, so we
will generate a (secret) second degree polynomial:

f(x) = a*x^2 + b*x + c

The actual secret key is the coefficient c, i.e. the y-intercept of
the parabola.

Each of the President's associates receives a pair of values
(x[i],f(x[i])), with x[i] <> 0. This gives one point on the parabola.

From three points, it is possible to determine the coefficients
a,b,c, and that gives the secret (of course, we assume that the
people will not do the computation themselves - they will each input
their own key into a computer that will do the computation and
launch the missiles).

Note that knowing 2 keys (i.e. two pairs (x,y)) does not give any
information at all. Indeed, for any value c (in some allowed range),
the point (0, c) defines a possible parabola with the other two
points, so any value of c remains possible.

In practice, there are some problems with this implementation. The
main problem is that we deal with real numbers, and this can give
rounding errors in the computations, since you can only manipulate a
finite number of digits; this may also imposes allowable ranges on
the coefficients a, b, c (not only on c), and that may alter the
probabilities of different keys.

The way to solve that is to note that the computation only uses the 4
standard operations of addition, subtraction, multiplication, and
division. The technique will work in any set where those operations
are "suitably" defined. Such a set is called a field.

In particular, for any prime number p, the set Zp of integers modulo
p is a field. This is rather obvious as far as addition, subtraction,
and multiplication are concerned. For division, note that, if a is
not a multiple of p, i.e. if a <> 0 (mod p), we can find x such that:

a*x = 1  (mod p)

and this allows us to use x as the inverse of a (1/a), and this
defines division by a as multiplication by (1/a) modulo p. You can
see how this is done by looking at:

Euclidean Modular Inverse Algorithm
http://mathforum.org/library/drmath/view/51895.html

(You may already know this; please write back if you want further
details.)

What we would do is to pick a large prime number p (to avoid the key
being discovered by accident or trial and error), and consider f(x)
as a function form Zp to Zp; the coefficients are defined modulo p.
Lagrange's formula and the linear equations technique still work, if
division is understood as explained above.

Let us look at a small example : we select p = 11, and:

f(x) = x^2 + x + 1

The secret key (the one that launches the missiles) is the constant
term, 1 in this case. As p = 11, this allows us to generate 10
different user keys, for example:

1, f(1) = 3
2, f(2) = 7
3, f(3) = 2
.....
10, f(10) = 1

(remember that everything is computed modulo 11).

Assume that the first three users want to activate their key. We have
the equations (modulo 11):

a*1 + b*1 + c = 3
a*4 + b*2 + c = 7
a*9 + b*3 + c = 2

We solve these equations using the standard method, but working
modulo 11 and with division defined as above. We first eliminate a
from the second and third equation by subtracting multiples of the
first:

a*1 + b*1 + c   = 3
b*9 + c*8 = 6
b*5 + c*3 = 8

We reduce the coefficient of b to 1 in the second equation, by
multiplying by 5 (since 5*9 = 1 mod 11):

a*1 + b*1 + c   = 3
b*1 + c*7 = 8
b*5 + c*3 = 8

We subtract 5 times the second from the third to get rid of b:

a*1 + b*1 + c   = 3
b*1 + c*7 = 8
c*1 = 1

and this gives us c = 1 (we do not need a and b).

There are also some practical issues to consider: the coefficients
must never leave the computer, only the individual pairs (x,y) have
to be produced; and you can also imagine a lot of other security
issues...

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Conic Sections/Circles
College Number Theory
High School Conic Sections/Circles
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search