Michael H. Warfield
Mon Mar 3 00:34:01 2003
Content-Type: text/plain; charset=us-ascii
On Sat, Mar 01, 2003 at 11:01:30AM +0100, Adrian 'Dagurashibanipal' von Bid=
> [no cc:s necessary. Thanks.]
> On Sat, 2003-03-01 at 05:09, Michael H. Warfield wrote:
> > There is a neat trick with RSA where you can distribute the
> > secret key between many computers and never need to reassemble them.
> > You give them all the same modulus (pq result) but you split the secret
> > exponent between them such that the sum of the exponent adds up to your
> > secret exponent.
> Funnily enough, I had an exam yesterday morning, and EXACTLY THIS was
> one of the exam questions...
> Ok, this thing with the RSA exponent works fine.
> The beautiful thing with the classical 'secret sharing' algorithms is
> that you can do things like 'any 3 out of 5 may sign a document'. I have
> not thought about it - with calculating in finite groups, it could be
> possible to do it. In any case: yes, it was such things that I was
> thinking about.
That same NDSS paper touches on "t out of k sharing". They claim
that standard Shamir secret sharing is inadequate specifically because the
secret key would have to be reconstructed at a single location in order to
be used. They present a method that works for reasonably small k (k < 20).
The paper includes sitations for both Shamir secret key sharing (A. Shamir,
"How to share a secret", Communications of the ACM, Vol 22, 1979, pp 612-61=
and an alternative to their approach (T. Rabin, "A simplified approach to
threshold and proactive RSA", Proceedings of Crypto '98). I'm sure there
are other references to t of k sharing which do not require reconstituting
the RSA key.
> -- vbi
> featured product: Debian GNU/Linux - http://debian.org
Michael H. Warfield | (770) 985-6132 | mhw@WittsEnd.com
/\/\|=3Dmhw=3D|\/\/ | (678) 463-0932 | http://www.wittsend.com/=
NIC whois: MHW9 | An optimist believes we live in the best of all
PGP Key: 0xDF1DD471 | possible worlds. A pessimist is sure of it!
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
-----END PGP SIGNATURE-----