Bugtraq mailing list archives
Re: Joint encryption?
From: John Richard Moser <nigelenki () comcast net>
Date: Sat, 19 Feb 2005 07:24:53 -0500
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 devnull () Rodents Montreal QC CA wrote:
[As usual when I write to bugtraq, the from address in the headers simply discards mail, so I don't have to deal with all the broken autoresponder mail that would otherwise land on me. To reach me, use the address in the signature.]The problem is that I need a guaranteed way to create data for any valid N and M where N >= 3 > M >= 2 in which access to M fragments of the key (each fragment is encrypted) can be used to gain access to the rest of the fragments, which in turn allows any selection of M users to authenticate and gain physical access to the key.You don't need the "...used to gain access to the rest of the fragments..." part. This is called "secret splitting", and there are a number of schemes by which you can split a secret into N shares, any M of which can reconstruct the secret, but any M-1 of which can discover nothing about the secret. One of the simplest, at least to my mind, is based on polynomials over a finite field. A handful of secret-splitting schemes, including this one, are described in Schneier's _Applied Cryptography_ (and doubtless many other places); the rest of this message is a brief description of this technique. Input: a secret S, and N and M as above. Choose a prime P, larger than S. Let c[0] be S. Choose random values less than P for c[1] through c[M-1]. For i from 1 through N, compute (all arithmetic mod P) h[i] = sum(j=0..M-1) (c[j] i^j) [^ is exponentiation] Share #i is then the triple <P,i,h[i]>. How the shares are stored is up to those charged with protecting them; they can store them encrypted if they want. Only the h[i] value needs to be protected. Now, given any M shares, you can set up M equations h[i] = sum(j=0..M-1) (c[j] i^j) (mod P, of course)
huh? No polynomial regression like in shamir's scheme? (as if I actually understand the math here)
for the i and h[i] values in the shares. (Of course, if the P values in the shares aren't all equal, at least one of the shares has been corrupted.) This is a system of M linear equations in M unknowns (the c[] values). Given how the coefficients of this system were chosen (the i^j values), they will be linearly independent and the system thus has a unique solution (since P is prime, division mod P works and Gaussian elimination can be performed). Solve it, and c[0] will be the secret. (You can throw away c[1] through c[M-1]; they were randomly chosen at split time and carry no information.) But if you have fewer than M shares, you can set up at most M-1 equations. Such a system is not solvable, and since we're working in the finite field Z_P, you actually cannot discover anything about S; by introducing a fictitious additional share with a suitable h[] value, you can arrange to make c[0] come out to any value you please. If you have more than M shares, the system is overdetermined. You can pick any M of the shares, reconstruct the c[] values, and check that what you get agrees with the redundant shares. (You actually don't *have* to check, but it allows you to catch some cases of corrupted shares.) I've written software that implements this. See ftp.rodents.montreal.qc.ca:/mouse/local/src/secretsplit/.
*brain explodes* ouch. OK I won't read that right now. . . maybe I'm better off trying to understand the math than the code.
/~\ The ASCII der Mouse \ / Ribbon Campaign X Against HTML mouse () rodents montreal qc ca / \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
- -- 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 iD8DBQFCFzAThDd4aOud5P8RApzXAJ9d2ITFaRnp5aeZAvVChln/VDSIpQCfbBvO VuECaAj0Xqt4dA8iVgS5zDU= =r0Jx -----END PGP SIGNATURE-----
Current thread:
- Joint encryption? John Richard Moser (Feb 19)
- 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)