splitting keys

Michael H. Warfield mhw@wittsend.com
Mon Mar 3 00:34:01 2003

Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sat, Mar 01, 2003 at 11:01:30AM +0100, Adrian 'Dagurashibanipal' von Bid=
der wrote:
> [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.

> greets
> -- vbi

> --=20
> 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!

Content-Type: application/pgp-signature
Content-Disposition: inline

Version: GnuPG v1.2.1 (GNU/Linux)