Note: Descriptions are shown in the official language in which they were submitted.
CA 02306468 2000-04-13
WO 99/23781 I'CT/CA98/U1018
Signature Verification '
For ElGamal Schemes
This invention relates to a method of accelerating digital signature
verification
operations performed in a finite field and in particul~~r to a method for use
with processors
having limited computing power.
Background of tile Invention
One of the functions performed by a cryptosystem is the computation of digital
signatures that are used to confirm that a particular party has originated a
message and
that the contents have not been altered during transmission. A widely used set
of
signature protocols utilizes the ElGamal public key signature scheme that
signs a message
with the sender's private key. The recipient may then recover the message wish
the
sender's public key. The ElGamal scheme gets its security from calculating
discrete
logarithms in a finite field. Furthermore, the ElGamal-type signatures work in
any group
and in particular elliptic curve groups. For example given the elliptic curve
l,~roup E(Fq)
then for P E E(Fy) and Q= aP the discrete logarithm problem reduces to finding
the
integer a. Thus these cryptosystems can be computationally intensive.
Various protocols exist for implementing such a scheme. For example, a digital
signature algorithm DSA is a variant of the ElGamal scheme. In these schemes a
pair of
correspondent entities A and B each create a public key and a corresponding
private key.
The entity A signs a message m of arbitrary length. The entity B can verify
this signature
by using A's public key. In each case however, both the sender, entity A, and
the
recipient, entity B, are required to perform a computationally intensive
operations to
?5 generate and verify the signature respectively. Where either party has
adequate computing
power this does not present a particular problem but where one or both the
parties have
limited computing power, such as in a "Snarl card " application, the
computations may
introduce delays in the signature and verification process.
There are also circumstances where the signor is required to verify its own
signature. For example in a public key cryptographic system, the distribution
of keys is
easier than that of a symmetric key system. However, the integrity of public
keys is
critical. Thus the entities in such a system may use a trusted third party to
certify the
public key of each entity. This third parry may be a certifying authority
((~A), that has a
CA 02306468 2000-04-13
WO 99/23781 PC'r/CA98/01018
private signing aigoritiun ST and a verification algoritlun VT assumed to be-
known by all
entities. In its simplest form the CA provides a certificate binding the
identity of an entity
to its public key. This may consisi of sigmmg a message consisting of an
identifier and
the entity's authenticated public key. From time to time however the CA may
wish to
S authenticate or verify its own certificates. Thus in these instances it
would be convenient
to implement an improved signature verification algorithm to speed up this
verification
process.
Summary of the Invention
1 U It is therefore an object of the present invention to provide a method of
fast
signature verification.
This invention seeks to provide a digital signature verification method, which
may
he implemented relatively efficiently by a signor on a processor with limited
processing
capability, such as a smart card or where frequent verifications are performed
such as a
15 certification authority.
In accordance with this invention there is provided a method of verifying a
digital
signature generated by a signor in a computer system, the sigrtor having a
private key d
and a public key y, derived from an element g and the private key d the method
comprising the steps of:
2p a) in the computer system signing a message m by;
b) generating a first signature component by combining at least the element g
and
the signature parameter k according to a first mathematical fitnction;
c) generating a second signature component by mathematically combining the
first signature component with the private key d, the message rn and the
?5 signature parameter k; and
tl~e signor verifying the signature by:
d) recovering a value k' from the signature without using the public key y,
and ;
e) utilizing the recovered value k' in the first mathematical function to
derive a
value ~' to verify the signature parameter k and k' are eduivalent.
CA 02306468 2000-04-13
WO 99/23781 PCT/CA98/01018
Brief Description of the Drawings
Embodiments of the present invention will now he described by way of example
only with reference to the accompanying drawings in which:
Figure 1 is a schematic representation of a communication system; and
Figure 2 is a flow chart showing a signature algorithm according to the
present
tnvenUon.
Detailed Description of a Preferred Imhodiment
For the sake of convenience in the following discussion we use the
rnultiplicative
notation, although ElGamal-type signatures work in any group and in particular
in elliptic
cun~e groups.
Referring therefore to Figure 1, a data conutrunication system 10 includes a
pair of
correspondents, designated as a sender A(12), and a recipient 13(14), who are
connected
by a communication channel 16. Each of the correspondents A and B (12,14)
includes an
encryption unit 18,20 respectively that may process digital information and
prepare it for
transmission through the channel 16 as will be described below.
In accordance with a general embodiment, the sender A assembles a data string,
which includes amongst others the public key y of the sender, a message m, the
sender's
short-terns public key k and signature S of the sender A. When assembled the
data string
is sent over the channel 16 to the intended recipient I3, who then verifies
the signature
using A's public key. This public key inforniation may be obtained from a
certification
authority (C.'A) 24 or sometimes is set with the message. 'the CA generally
has a public
file of the entity's public key and identification.
For key generation in the ElGamal signature scheme, each correspondent A and B
2S creates a public key and corresponding private key. In order to set up ilre
scheme, tlm
entities A and Q select primes p and q such chat q divides p-1. A g is
selected such that it
is an element of order q in ly, and tire group used is ~g°, g', g-
,...g'''t.
The digital signature algorithm (I)SA) which is a special case of the CI(~amal
scheme, key generation is performed by selecting a random integer cl in the
interval [1, cl-
1 J and computing y=g'~ mod p. In the DSA the public key information is p, d,
g, y) arul
the private key is cl, while in the general ElGamal scheme the public key
information is
(1>> g, Y) uncl the private key is cl.
3
CA 02306468 2000-04-13
WO 99123781 PCTlCA98/01018
We consider firstly a signature scheme such as the DSA in which the signature
components r and s are given by:
r = (g" mod p) mod q ; and
s = k-'(It(1)r)+dr)mod q
where typically:
d is a random integer, the signors private key and is typically 160-bits;
p is typically a 1024-bit prime;
~J is a 160-bit prime where g divides p-1;
g is the generator such that y = g'r mod p ;
1 () h(m) is typically a S1-lA-1 hash of the message nr;
k is a randomly chosen 1 ci0-bit value for each signature; arid
the signature for m is the pair (r, s).
Normally to verify A's signature (r, s) on the message nr, the recipient B
should
obtain A's authentic public key (p, q, g, y), and verify that 0< r < q and 0 <
s < q. Next
the values
m = s~' mod q and h(m) are computed. This is followed by computing u,=w h(m)
mod q
and u2= r w mod q and v = (g~' y"'' mod p) mod q. The signature is accepted if
and only if
v = r. It may be seen therefore that in some cases if the owner of the
signature wants to
verify its own signature ai a later stage it may be time consuming to retrieve
the public
key information and perform the steps above, particularly since the signor is
verifying its
own signature.
Thus, in order to implement fast signature verification using tire private key
d, it
may be seen that the verifier, in this case the original signor, has knowledge
of p, q, g, y,
h(m), r and s. Thus the verifier need only recover the (secret) per signature
value k used
and verify this value of k thus obtained in order to verify the sig~r~ature.
The verifier thus
calculates z = (h(m) + dr) mod d . The value z' is calculated by inverting z
mod q. Next
calculate k'-' = s(z--' )modq and calculate k' by inverting k'-' modq . The
verifier then
evaluates r = g"~ mod p mod y this verifies k = k'. Thus it may be seen that
this
verillCatl()r7 Step rlSl'.S d not y and many of the calculations above can be
sped up using
pre-computed tables.
a
CA 02306468 2000-04-13
WO 99/23781 PCT/CA98/01018
Next we consider an alternate ElGamal signature method shown in figure 2 as
having signature components (s, e) where:
r=g' mode;
a = h(mI r) where ~~ indicates concantenation; and
$ s=(de+k)modp
The signature components are s and a where p is a large public prime, g is a
public
generator, m is a message, h is a hash fllIlCttOrl, d is a private key, y - g
° rnod E: is a
public key and k is a secret random integer.
In fast signature verification using the private key d we once again assume
knowledge of p, g, y, h, m, r, a and d. Thus the verifier need only recover
the k value
used and verify k in order to verify the signature. rfhus the verifier
calculates
k'= (s - de) mod p , r'= g=" mod p and e' = h(m~~r'). if a = e' this verifies
k = k'.
Thus it may be seen that an advantage of the present invention is where a
signor
signs data which for example may reside on the signors computer. This can be
later
verified without use of the correponding public key, instead the signor can
use its private
key to verify the data. This is also very useful for some applications with
limited
computational power such as smartcards.
In a data communication system that includes a certifying authority, the
certifying
authority (CA) or key distribution centre would sign data frequently before it
is installed
2U into the various communications systems and then could verity the
signatures later. Thus
the CA does not require the public key information to verify the signatures
but simply
uses the private key to verify, as all ttae other parameters are stored within
the secure
boundary of the signor.
A further application is in the verification of software such in pay-per-use
software applications.
While the invention has been described in connection with specific embodiments
thereof and in specific uses, various modifications thereol~will occur to
those skilled in
the art without departing from the spirit of the invention as set forth in the
appended
claims. Ivor example, in ilre above description of preferred embodiments, use
is made of
multiplicative notation however the method of the subject invention may be
equally well
duscriUeci utilizing additive notation. It is well known for example drat the
elliptic cun~e
5
CA 02306468 2000-04-13
WO 99/2381 PCT/CA98/01018
algorithm equivalent of the DSA, i.e: ECDSA is the elliptic curv.~e analog of
a discrete
logorithm algorithm that is usually described in a setting of F ~, , the
multiplicative group
of the integers modulo a prime. There is correspondence between the elements
and
operations of tire group F P and the elliptic curve group E(Fy). Furthermore,
this signature
technique is equally well applicable to functions perforn~ed in a field
defined over F2"
The present invention is thus generally concerned with an encryption method
and
system and particularly an elliptic curve encryption method and system in
which finite
field elements is multiplied in a processor efficient manner. The encryption
system can
comprise any suitable processor unit such as a suitably programmed general-
purpose
computer.
(i
