Date: Sat, 19 Feb 2005 07:24:53 -0500
From: John Richard Moser <nigelenki@...cast.net>
To: devnull@...ents.Montreal.QC.CA
Cc: bugtraq@...urityfocus.com
Subject: Re: Joint encryption?


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



devnull@...ents.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@...ents.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-----

Powered by blists - more mailing lists