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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.