splitting keys

[Michael H. Warfield]

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

On Fri, Feb 21, 2003 at 10:02:14AM +0100, Adrian 'Dagurashibanipal' von Bid=
der wrote:
> On Fri, 2003-02-21 at 01:14, David Picon Alvarez wrote:

> > Is it likely that secret sharing will be ever incorporated in GnuPG? By
> > secret sharing I understand the following, but maybe I'm wrong:

> The big problem with key sharing algorithm is: where do you do the
> computation? Where do you assemble the key, and how do you guarantee
> that the owner of that computer does not keep a copy of the assembled
> key? IIRC, the classical key sharing algorithms work by distributing a
> secret (without any knowledge about what that secret is), the assembled
> secret is then used as key.

	I'm not sure if you are referring to the case where you have
a "trusted broker" create a secret key and then, after distributing
the pieces, destroys the complete key OR if you are implying that the
key must be reassembled to be used.  If you mean the former, see further
down.  If you mean the later...

	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.

	To sign...  Each computer computes a signature.  Then you take
the product of the signatures and modulo the modulus.  Voila...  You
have the signature and nobody reassembled the key.  If you can sign, you
can decrypt, but I've mostly seen this for signing.

	Let N =3D pq be a product of two large primes.

	Let e be a public signature verification exponent.

	Let d be the corresponding private signing exponent.

	A private RSA key is the pair <d,N>

	To share the private key between three entities, you pick three
random numbers d1, d2, d3 in the range [-N,...+N] such that d1+d2+d3 =3D d.

	To sign, each site computes s(i) =3D m**d(i) mod N, i =3D 1,2,3

	You then compute the final signature as s1*s2*s3 mod N

	This works because (m**d1 mod N) * (m**d2 mod N) =3D m**(d1 + d2) mod N

	(It's basic exponetiation but the mod N makes it look a little
funny.  If you work the math, it works...)

> I'm told this problem can be solved, there are algorithms where you can
> distribute the computation without the whole key ever being assembled.
> But I'm not into that, so you'll have to do your own research
> (especially: I don't know if any of these algorithms are developed far
> enough to be acutally useable).

	At NDSS 1999 there was a paper presented on GENERATING an RSA
private key using distributed computing methods so that no machine ever
even HAD the complete private key.  The usual method is to compute a
keypair and then divide it up between machines by splitting the private
exponent so that each machine gets and exponent in the range of +-modulus
and the all add up to the final exponent.  This requires that an initial
machine have the complete secret key.  Their paper, "Experimenting with
Shared Generation of RSA Keys" described a method and protocol for a
group of cooperating systems which derives a distributed key with no
single system ever in possession of the complete secret key.

	http://crypto.stanford.edu/~dabo/abstracts/ShareExp.html

> It's just my opinion that unless this problem is solved, key
> distribution/sharing algorithms shouldn't go into gpg. As soon as you
> require one designated computer to be trusted, you've lost.

	I would like to see this where I could distribute a key, using
RSA exponent sharing, between smart cards.  Same method applies.  Except,
you can generate multiple SETS of smart cards with different combinations
of exponents.  Generate them using a secure, isolated, box.  Keep one
set as an isolated backup set.  If one of the cards in the working set
is ever compromised, any one of the other owners can destroy the entire
set simply by destroying his card.  Then all have to resort to the backup
set (and regenerate a new random backup set).  The private key is preserved
because a SET of cards exists to access it, yet the compromised card can
be rendered useless by any of the other cards in a given set and none of
the cards in a given set are useful without the complete set.

> (corrections welcome - I'm not that sure about it all)

	My question is that, given this technique for RSA keys, does a
similar technique exist for DSA keys?

> cheers
> -- vbi
>=20
> P.S.
> > -----BEGIN PGP SIGNATURE-----

> Is that still your insanely big key? I dare not verify your signatures,
> because gpg is sooooo slooooooowwww. Really defeats the purpose of
> digital signatures...

> --=20
> featured link: http://fortytwo.ch/smtp


	Mike
--=20
 Michael H. Warfield    |  (770) 985-6132   |  mhw@WittsEnd.com
  /\/\|=3Dmhw=3D|\/\/       |  (678) 463-0932   |  http://www.wittsend.com/=
mhw/
  NIC whois:  MHW9      |  An optimist believes we live in the best of all
 PGP Key: 0xDF1DD471    |  possible worlds.  A pessimist is sure of it!

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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iQCVAwUBPmAyl+HJS0bfHdRxAQFaCQP/SDQDKn1PRkKI/YLofQXtax7SNE3hGefq
IjuoElpRp0AlC75Q2pRyZcdntziTZO2iHS5f4cAdDej8iF574EK4hMtQMCOhXxsn
zZ6SFBO3DDdDfqizCIUw44Q/myi6xyZKR6GVCT7uOrg/LU0aIill25ZYp4uRskzM
YMFFduVsG48=
=Zlmk
-----END PGP SIGNATURE-----

--jI8keyz6grp/JLjh--