hi:
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@comcast.net> wrote:
-----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-----
