Bugtraq mailing list archives
Re: Joint encryption?
From: John Richard Moser <nigelenki () comcast net>
Date: Sat, 19 Feb 2005 16:59:39 -0500
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 David Schwartz wrote:
The authentication works as below:
[...]
There's a ludicrously simple and incredibly brilliant way to do this. For a polynomial of order N, you need N points on the polynomial to find the equation that describes the polynomial. So if you want to share a secret amount 28 people such that any 15 are needed to know it, just make the secret the coefficients of a 15th order polynomial and compute 28 points that satisfy the polynomial. So, for the 28/15 example, pick 15 random coefficients (C1, C2, C3, ...), and then your 28 pieces of the key (K1 ... K25) are the solutions to: Kx = C1 + C2 * x + C3 * x^2 + C3 * x^3 ... C15 * x^14
Math check here, wikipedia seems to think: If the players store their shares on insecure computer servers, an attacker could hack in and steal the shares. If it is not practical to change the secret, the uncompromised (Shamir-style) shares can be renewed. The dealer generates a new random polynomial with constant term zero and calculates for each remaining player a new ordered pair, where the x-coordinates of the old and new pairs are the same. Each player then adds the old and new y-coordinates to each other and keeps the result as the new y-coordinate of the secret. -- http://en.wikipedia.org/wiki/Secret_sharing I'm confused: "polynomial with constant term zero" "The dealer encodes the secret as the curve's y-intercept" now after playing with my calculator I suddenly remember something about any polynomial's Y intercept being the constant term. See, if all the coefficients are 999999999999999999999999999999999999999999999999, multiplied by X=0, the result is still 0. Is wikipedia wrong here? Or do I have a misunderstanding of "constant term"?
For x=1 to 28. With any 15 solutions to the equation above, you can compute C1 through C15. With any 14, you can't even get started. DS DS
- -- All content of all messages exchanged herein are left in the Public Domain, unless otherwise explicitly stated. Creative brains are a valuable, limited resource. They shouldn't be wasted on re-inventing the wheel when there are so many fascinating new problems waiting out there. -- Eric Steven Raymond -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.5 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iD8DBQFCF7bKhDd4aOud5P8RAjh+AJ4kiBsTrlQPQm3X91tJA1SvzIZ/5ACfXsxU Wy9zXBIuwYn88tfDqvh65iY= =64ST -----END PGP SIGNATURE-----
Current thread:
- Re: Joint encryption?, (continued)
- Re: Joint encryption? Damian Menscher (Feb 19)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? Casper . Dik (Feb 19)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? Robert C. Helling (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? devnull (Feb 19)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? peter zulu (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 19)
- Re: Joint encryption? Gandalf The White (Feb 21)
- RE: Joint encryption? David Schwartz (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 21)
- Re: Joint encryption? Valdis . Kletnieks (Feb 21)
- Re: Joint encryption? John Richard Moser (Feb 21)
- Re: Joint encryption? Ruud H.G. van Tol (Feb 21)
- Re: Joint encryption? Damian Menscher (Feb 19)