Re: Joint encryption?Feb 19 2005 12:24PM John Richard Moser (nigelenki comcast net) (1 replies)
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
devnull (at) Rodents.Montreal.QC (dot) CA [email concealed] 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 (at) rodents.montreal.qc (dot) ca [email concealed]
> / \ 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
Hash: SHA1
devnull (at) Rodents.Montreal.QC (dot) CA [email concealed] 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 (at) rodents.montreal.qc (dot) ca [email concealed]
> / \ 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-----
[ reply ]