|
Whether you're protecting a nuclear missile or your new recipe for burger sauce, polynomial encryption can prevent people from stealing your secrets.
June 30, 2007
URL:http://drdobbs.com/security/sharing-secrets-among-friends/200001792
Let's say you've invented a new, extra-gooey, extra-sweet, creme filling; or a burger sauce that is even more tasteless than before. This stuff is important; you have to keep the recipe secret. You can tell only your most trusted employees the exact mixture of ingredients, but what if one of them defects to the competition? Before, long every grease palace on the block would be making burgers as tasteless as yours. That just wouldn't do.
You can take a message and divide it up into secure pieces. Each of the pieces by itself means nothing, but put them all together and the message appears. If each employee has a piece of the recipe, then only together can they make the sauce (employees could type their portion into a central sauce-making computer or something). If any employee jumps ship with a piece of the recipe, the portion is useless by itself.
A message of any length can be divided up using these techniques, but for the purposes of illustration I am just going to work with a byte I'll call a message. Realistically, a message of arbitrary length would be encoded using a conventional cryptographic algorithm, such as the Digital Encryption Standard (DES). Then, the algorithm's key would be divided up. Longer messages can be divided, but it's more work. The simplest sharing problem is how to split a message between two people. The answer is simple; generate a random bit string of equal length and XOR it with the message. Give one person the random string and the other person the XOR result. Separately, the two pieces are worthless; XOR them together and the message reappears.
This technique, if done properly, is absolutely secure. No amount of computing power can determine the message from one of the pieces. If the random bit string is truly random, then any message is equally possible. For example, if the message is 00000000 and the random string is 10011011, the XOR is 10011011. A cryptanalyst trying to deduce the message from one part has no way of knowing what the other part is.
The random string could just as easily have been 01100100, making the message 11111111, or any other bit combination in between. A random bit string XORed with a nonrandom bit string produces a random bit string. No amount of computing power can change that result, and no amount of computing power can defeat it.
Any successful attacks against this scheme will be against the method used to generate the random bit string. If you use a linear-feedback shift register, linear congruential generator, or another cryptographically weak algorithm, you're asking for trouble. If you flip a penny (or listen to radioactive decay, atmospheric noise, or measure keyboard latency) you're safe. (T.A. Elkins's "A Highly Random Random-Number Generator" gives a pseudorandom number-generation algorithm that, while cryptographically useless for encryption, is probably good enough to generate a few 56-bit numbers.)
It is easy to extend this scheme to more people. To split a message among more than two people, just XOR more random bit strings into the mixture so all the parts XORed together reproduce the message. For example, 10011011, 11101001, and 01110010, XOR to form the message 00000000.
The only problem with this splitting scheme is that if any of the pieces gets lost, so does the message. So, if an employee with a piece of your sauce recipe quits without leaving the piece of the puzzle behind, you're out of business. The recipe can't be reproduced, but you can't use it either. This piece is as critical to the message as every other piece in the message combined.
A more complicated sharing scheme can fix that problem. Let's say you're setting up a launch program for a nuclear missile. You want to make sure that no single raving lunatic can initiate a launch. You also want to make sure that no two raving lunatics can initiate a launch. You want at least three out of five officers to be raving lunatics before you will allow a launch. Give each of the five officers a key and require three keys to blow up whoever is being blown up these days. Physical keys make it easy, but you can do the same thing mathematically.
Make the launch message the linear term of an otherwise random quadratic polynomial. That is, if the message is m, invent some polynomial of the form ax2 + bx + m. Give each officer the solution of the polynomial evaluated at a different x. If the polynomial were written as 49x2 - 28x + 72, Officer Smith might get the result at x = 21, Officer Jones might get the result at x = -2, Officer McDonald might get the result at x = 11, and so on. None of the officers would know the polynomial; they would just know that it was of the form ax2 + bx + m. Since the quadratic polynomial has three unknowns, any three officers can throw their pieces into a linear algebra program and solve for m. Two officers cannot. One officer cannot. Four or five officers are redundant.
This sharing scheme can be easily generalized. If you want to divide the message into 30 equal parts so any six people can get together and reproduce the message, give each of the 30 people the evaluation of a polynomial of degree five (ax6 + bx5 + cx4 + dx3 + ex2 + fx + m). Six people can solve for the six unknowns; five people can't do a thing.
We can get even more complicated. Maybe the general and two colonels can launch the missile, but if the general is indisposed, it takes five colonels all together. Embed the message in a polynomial of degree four. Then, give each colonel an evaluation, and give the general three different evaluations. Put the general together with any two colonels, and they can solve for the five unknowns. Five colonels could also solve the polynomial. But a general and one colonel only have four equations. They can't reconstruct the message and neither can four colonels.
In fact, any sharing scenario you can imagine can be modeled using variations on this scheme. A message can be divided up among two delegations, so you need two people from the seven in Delegation A and three people from the 12 in Delegation B. Make a polynomial of degree four that's the product of a linear and quadratic polynomial. Give everyone from Delegation A an evaluation of the linear polynomial, and give everyone from Delegation B an evaluation of the quadratic polynomial. Grind through the math yourself; it will work.
As an enhancement to the scheme, instead of making the message the constant term of the polynomial, split it into pieces and make the secret the XOR of all the coefficients of the polynomial. Or make different coefficients different messages.
The important thing to remember with all of these schemes is that the random numbers have to be generated properly. When inventing a random polynomial, all the coefficients have to be random. If they are not, then the scheme is only as good as the random number generator that generated them. If your random number generator is good, you can divide messages up however you like without any fear of anyone stealing the recipe for your new and improve TasteLess burger sauce.
Shamir, A. How to Share a Secret.
Simmons, G.J., How to (Really) Share a Secret.
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.