I will give a simple example of Shamir secret sharing. Suppose you have some data D which you want to split up into n pieces such that any 2 of them are sufficient to reconstruct D. Shamir solves the problem for any k of them being sufficient, but the case k=2 is especially simple. Pick a random number m which will be the slope of a line. Take the equation y = mx + D, and substitute x = 1, x = 2, ... x = n. Pass out the y's for each value of x as the secret shares. For example, if D=12, pick random m = 4, and pass out (1,16), (2,20), (3,24), (4,28), and so on. Now, suppose an enemy gets hold of one of these - say (2,20). What does this tell him about the value of D? Nothing! D could be anything, depending on the value of m. But suppose we have two of these values - say (1,16) and (2,20). From these it is easy to calculate m=4, and from that it is easy to see that D=12. Two points determine a line. In the actual Shamir scheme, integers mod a prime p are used, where p>D. The math is basically the same. For k=3, a parabola is used instead of a line, so that 3 points are needed; for k=4, a third-degree polynomial is used, and for general k, a (k-1)-degree polynomial is used. In each case, knowing k-1 points tells you nothing, because there will be a (k-1)-degree polynomial that would pass through any possible value of D. Hal
David Koontz <koontzd@lrcs.loral.com> writes:
With a key K of size j (goddamn fortran anyway), i parties can share the secret with a threshold of i (requiring all i parties key part) by generating i parts P such that K = Pi XOR Pi-1 XOR ... P1. All the parts P are the same size as K, which keeps the effort of guessing a missing part equal to j, or the size of the key k itself.
Such a scheme is not ideal for keys K that have a deterministic characteristic.
I might be missing something, but I don't see how this could be made to work when you're missing more than one key. For example, suppose you create a system with 5 keys. Take each of the five keys and XOR them to create a known constant. Now, if you have four keys, you can easily find the fifth by xoring them with the known constant, and unlock the cipher. But, what if you wanted to have three of the five keys be able to unlock the cipher. There isn't any way to do this. I worked with this system many years ago, trying to create an insurance against data loss. If you have some blocks of data, you take each byte in each block and xor it with the same byte position in all of the other blocks, and then save this new block that you created. If you then lose one of the blocks, you can recreate it from the remaining blocks. But if you lost two blocks, there is no way to recreate it. I gave up on the idea and never wrote the program. I like the line/polynomial idea that Hal Finney posted tho...
participants (2)
-
hfinney＠shell.portal.com -
Matthew J Ghio