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...

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/