as a former cryptanalyst i've found simple solutions are usually best
(and quite often if cryptography is the answer, the problem isn't very
well understood.) i don't have enough information to understand
precisely what you're trying to accomplish, but assuming your primary
objective is to retrieve a key if a 'trusted' participant is missing,
why not look into RSA's nightingale?
it's good for splitting a key into two pieces. if you want to split
it among more, you can use shamir, but don't forget that what appears
mathematically elegant isn't usually efficient computationally.
if you need to split keys across more than two parties, and you can
afford to pre-judge the maximum number of participating parties (N),
you could always try using a polynomial curve in which you pick an
equation of order N-1. if you really want to tax your springer-verlag
library, try using a dynamical system (cyclotomic polynomials are
interesting.)
cheers-
peter
On Sat, 19 Feb 2005 07:24:53 -0500, John Richard Moser
<nigelenki (at) comcast (dot) net [email concealed]> wrote:
> -----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
>
> iD8DBQFCFzAThDd4aOud5P8RApzXAJ9d2ITFaRnp5aeZAvVChln/VDSIpQCfbBvO
> VuECaAj0Xqt4dA8iVgS5zDU=
> =r0Jx
> -----END PGP SIGNATURE-----
>
as a former cryptanalyst i've found simple solutions are usually best
(and quite often if cryptography is the answer, the problem isn't very
well understood.) i don't have enough information to understand
precisely what you're trying to accomplish, but assuming your primary
objective is to retrieve a key if a 'trusted' participant is missing,
why not look into RSA's nightingale?
http://www.rsasecurity.com/rsalabs/node.asp?id=2424
it's good for splitting a key into two pieces. if you want to split
it among more, you can use shamir, but don't forget that what appears
mathematically elegant isn't usually efficient computationally.
if you need to split keys across more than two parties, and you can
afford to pre-judge the maximum number of participating parties (N),
you could always try using a polynomial curve in which you pick an
equation of order N-1. if you really want to tax your springer-verlag
library, try using a dynamical system (cyclotomic polynomials are
interesting.)
cheers-
peter
On Sat, 19 Feb 2005 07:24:53 -0500, John Richard Moser
<nigelenki (at) comcast (dot) net [email concealed]> wrote:
> -----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
>
> iD8DBQFCFzAThDd4aOud5P8RApzXAJ9d2ITFaRnp5aeZAvVChln/VDSIpQCfbBvO
> VuECaAj0Xqt4dA8iVgS5zDU=
> =r0Jx
> -----END PGP SIGNATURE-----
>
[ reply ]