Management of signature keys for government

[Bodo Moeller]

Brian Gladman <gladman@seven77.demon.co.uk>:
> Dave Howe <DHowe@tecsun.demon.co.uk>:

>> I don't know why, but I seem completely unable to see why
>> users can't generate their own keys for use in smart cards,
>> using their own trusted software, and uplink their own trusted
>> copy of the key to the smartcard.

> One issue in the self generation of keys is how to prevent a user
> repudiating their own key by revealing its private component.

If DSA or the ElGamal signature algorithm in a prime-order subgroup
of  (Z/pZ)*  is employed, then there is no need to argue who should
generate the signing key.

Assume that parameters  p,  q,  and  g  (with the usual meaning of
those letters) have already been determined, e.g. by using the
parameter generation algorithm from FIPS 186 with seeds provided by
customer Carol.  Then the following scheme could be employed:

(All computations are understood to be in the appropriate groups;
i.e., those computations where  g  appears are  "mod p"  and the
others are  "mod q".)
   When Carol obtains her card, it already has a "temporary key"
y = g^x  provided by the issuer of the card.  Of course, the card
issuer is expected to use high quality randomness, not to store  x
etc.  Carol can read out   y,  but the card will not reveal the secret
exponent  x.  Now Carol creates a random number  z  and sends it to
the card.  The card computes and stores a new private key
     X := x*z
and a new public key
     Y := g^X   (= g^(x*z) = y^z).
The card may then delete  x  and  y.

Y  (together with  p, q, g)  is Carol's public key.  She computes it
as  y^z  and can thus verify that the smartcard really used her random
number  z.

If at least one party -- the card issuer or Carol -- used a good random
number generator (for  x  or  z, respectively), then the new private
key  X  is also a good random number.  Specifically, if the card
issuer tries to cheat, but Carol uses a good randomness source, then
her key is okay.  The other way around, if the card issuer is fair and
uses good random numbers, then deficiencies of Carol's random number
generator do not hurt.  For Carol, finding out  X  is as hard as it is
in the case where key generation is entirely the card issuer's job.
(Of course, both parties should check the plausibility of parameters
provided by the other one:  p  and  q  are really prime and have the
correct length [and were created using the FIPS 186 algorithm with the
correct seed];  q  divides  p-1;  g, y and  Y  are generators of the
order  q  subgroup of  (Z/pZ)*.)


This is the scheme from G.J. Simmons' paper at the 1993 IEEE Computer
Security Workshop.  There, it is used during signing in order to
thwart subliminal channels; i.e., two parties contribute to an
ephemeral value  k  rather than to the private key  X  as in our
application.  Here, it should probably be used for both purposes (so
that Carol's card can't leak her private key in the  r (= g^k)
components of her signatures).

Bodo M"oller
<Bodo_Moeller@public.uni-hamburg.de>