For various reasons I’m subscribed to the bugtraq mailing list in work and at home, mainly to spot what’s about to become a problem in terms of cracking systems, and also to make myself feel informed.
Sometimes, though, I get so lost in the jargon I have no clue whatsoever of what’s being discussed. Example: Last week, the security world was abuzz with news of SHA-1 being ‘broken’ by a team of Chinese cryptographers. It probably means nothing to the average punter for the next few years, but it’s still big news. Lots of discussion about what could replace the broken hash function.
Today, this appeared. I’m the first to admit that I’m a bit thick, but I’d like to think that understanding of this email marks you out as being, errrmm, ‘gifted’
On Sat, 19 Feb 2005, John Richard Moser wrote:
> Yeah I noticed that on the wikipedia
>
> http://en.wikipedia.org/wiki/Secret_sharingI would like to add that both schemes described there are essentially
equal as both make use of the fact that a T dimensional subspace U of an N
dimensional vector space V (for example a vector space of polynomials) is
encoded by giving T linearly independent vectors in U.Data can now be encoded by thinking of it as a functional
f: T —> F
that is a linear function that maps T into the field F over which T is a
vector space.Now for each bearer i of a part of the secret give him a vector b_i in U
(in terms of T coordinates) and his share of the data is e_i = f(b_i).If T bearers come together, they can combine their T vectors b_i into a
TxT matrix M and compute M^(-1) (if they are linearly independent).
Finally, acting with M^(-1) on the vector of the T e_i’s recovers the
original functional f.Note that if you want to share more data f1…fk you need to compute the
b_i and thus M^(-1) only once and then you pass on the f_n(b_i).For a practical implementation you could for example use the unique field
F_256 of dimension 256 and do arithmetic using look up tables. See for
example the perl scriptshttp://www.damtp.cam.ac.uk/user/rch47/split.pl
for the sharing/combining of the data and
http://www.damtp.cam.ac.uk/user/rch47/gf2.pl
for the finite field arithmetic.
Robert
Piece of piss. Problem solved and all that. (!) Now can we get back to breaking into IIS webservers? I can follow that.
