On Wed, 16 Jul 2003 [EMAIL PROTECTED] wrote:
>Hi,
>
>I remember reading (many years ago) a description on some web page somewhere
>of an algorithm by which an arbitrary file F could be split into M pieces,
>such that:
>(1) given any N pieces, F can be reconstructed precisely, and
>(2) given fewer than N pieces, it is impossible to determine even a single
>bit of information about F.
>
>Unfortunately, that was many years ago, and -- search as I might -- I
>haven't been able to find it on web now.
>
>Does anyone have any idea where I might learn about this algorithm - or
>indeed any algorithm which does the job.
>[Moderator's note: look for "Shamir Sharing" -- the trick is just
>turning the secret into a polynomial of degree N so that with enough
>points you determine the polynomial uniquely and with too few you
>can't determine it. I'm pretty sure that Schneier and all of the other
>standard references explain this trick. --Perry]
Perry has it exactly right, although he was pretty brief and gave no
examples.
Let's say you want to be able to reconstruct a message given any
two out of three splits of the message. What you do is plot the
message as the y-intercept on a cartesian graph, and draw a line
in some random direction. (where random != straight up)
Now, the line you've drawn crosses the x=0 vertical line at the
message, and it crosses the x=5000 line at some other point whose y
coordinate is A, and it crosses the x=10000 line at some other point
whose Y coordinate is B, and it crosses the x=15000 line at yet some
other point, whose Y coordinate is C.
A, B, and C are your three secret splits. Unless someone has at least
two of them, they have no information about the slope of the line and
they can't project it back to the (x=0, y=M) point to get the message.
If you want two out of four, or two out of six, or whatever else, it's
the same thing; two points establish a line, so you can just pick more
points along the line.
If you want a 3-out-of-N secret split, you need to use a curve that
requires three points to establish (such curves include functions
of X^2). And so on...
Bear
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
