[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)
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/.
/~\ 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
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)
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/.
/~\ 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
[ reply ]