 |
Description  |
|
|
TECHNICAL FIELD
The present invention relates generally to secure communications and more
particularly to computationally-efficient yet highly-secure digital
signature schemes.
BACKGROUND OF THE INVENTION
In recent years, there has been a dramatic increase in the need for systems
that can protect digital data from potential eavesdroppers, forgers, and
other adversaries. This is largely due to the fact that an unprecedented
portion of all commercial transactions and communications are now handled
with digital electronics. In addition, the sophistication of potential
adversaries has increased, which has made the problem of protecting
digital data even more pressing.
In response to this need, a wide variety of interesting and novel schemes
have been developed for protecting and authenticating digital data. The
problem now faced by many corporations and government bodies is to choose
a scheme from among the many that will be both secure and economical.
NIST, in particular, is faced with the task of selecting "standard"
methods for encrypting and authenticating data.
Traditionally, written data has been authenticated by appending the
handwritten signature of the appropriate individual to the data. Modern
methods for authenticating digital data proceed in a similar fashion
except that the handwritten signature is replaced with a digital
signature. The digital signature consists of a stream of bits which is
computed by the signer based on the message being signed. The digital
signature should have the properties that anyone can verify that a
signature is the valid signature of the signer for the associated message,
and that only the signer is able to generate the signature.
An exemplary method for computing digital signatures today is the RSA
scheme. In the RSA scheme, each individual is provided with a secret pair
of large (e.g., 500-digit) prime numbers P.sub.1 and P.sub.2. The pair
(P.sub.1,P.sub.2) is referred to as the secret key for the individual. The
corresponding public key for the individual is the pair (Q,r) where
Q=P.sub.1 P.sub.2 and r is a fixed positive integer that is relatively
prime to P.sub.1 -1 and P.sub.2 -1. The signature for a message M is a
number x for which x.sup.r =h(M)mod Q. The function h is a
publicly-available hash function that maps any data string M into a k-bit
number where generally k.ltoreq.log Q. The step of computing h(M) is known
as pre-hashing. This initial step is common to all known digital signature
algorithms because applying the signing procedure directly to M, rather
than h(M), may be either impossible or impossibly time-consuming. The hash
function h used for pre-hashing needs to be secure, i.e., easy to compute
and behaving in practice like a random function (such a secure function H
has two important properties: it is easy to compute h(M) given M but
impossibly hard to compute M given h(M), i.e., h is "one-way", and it is
impossibly hard to find two strings M and M' such that h(M)=h(M')).
Many similar schemes have also been proposed, including the well-known DSA
algorithm. The practicality of schemes such as RSA and DSA is based on
several factors: it is not overly difficult for an individual's computer
to produce a signature x for a message M given that the computer knows the
secret key (P.sub.1, P.sub.2), the fact that it is relatively easy for
someone else's computer to verify that x is a signature for M given
knowledge of the public key (Q,r), the fact that the signature itself is
relatively short (e.g., it consists of about 1000 bits), and the fact that
the public key is also relatively short (e.g., it also consists of about
1000 bits).
For a digital signature algorithm to be secure, it must be practically
impossible for an adversary to produce a signature for any message M
without knowledge of the private key, even if the adversary is aware of
the public key and can obtain valid signatures for messages other than M.
More specifically, the security of RSA and DSA schemes is based on the
hope that number-theoretic problems such as factoring and computing
discrete logarithms are impossibly hard for almost all large numbers, the
hope that the hash function used for pre-hashing is secure, and, most
importantly, the hope that the adversary must be able to factor or solve
the discrete log problems in order to be able to forge a signature. In
fact, there is no proof that forging RSA signatures is as hard as
factoring or that forging DSA signatures is as hard as computing discrete
logs even if a secure hash function were used for prehashing.
For example, if the adversary is able to factor, then he can compute the
private key from the public key, whereupon he can begin to forge
signatures at will for the RSA scheme. If the adversary can compute
discrete logarithms, then he can compute forged signatures for the DSA
scheme directly, without knowledge of the secret key. Moreover, if the
adversary can find two messages M and M' for which h(M)=h(M'), then he can
forge a signature for M' by obtaining a legitimate signature for M (since
the signatures for M and M' are the same). If the adversary can invert h,
then he can forge signatures by an alternative method using a slightly
more complex attack. Finally, and most importantly, it might be possible
for an adversary to forge signatures using an altogether different
as-yet-unknown attack. Hence, in addition to the hope that it is not
possible to achieve a known attack, the security of schemes such as RSA
depend on the hope that there are no easier alternative attacks. In
summary, this means that the security of signature schemes such as RSA and
DSA is based on assumptions which may not always be defensible.
BRIEF SUMMARY OF THE INVENTION
It is an object of the invention to provide a new digital signature scheme
that requires substantially less time for signing and verifying than prior
art schemes such as RSA.
It is another object of the invention to provide a signature scheme which
uses a secure hash function to prevent any known or future attack from
succeeding in forging signatures without solving a very hard computational
problem such as factoring.
It is a further object of the invention to provide a digital signature
scheme that can be implemented with very cheap and simple hardware or
software.
It is a still further object of the invention to describe a secure
communications system implementing the new signature scheme and in which
all users of a group share the same public key. In particular, if this
common public key includes a composite number, the users will not know the
key's factorization. This obviates certification of individual public keys
for the users in the group.
As a further object, the present invention shows how to implement the new
digital signature scheme to produce relatively short "certificates" of
public keys if desired.
These and other objects are provided in a digital signature scheme wherein
the signature of a message M relative to a public key is computed by means
of a secret key. The scheme begins by having the user select a number x
independent of M. This step may occur off-line and before there is any
knowledge of the particular message M to be signed. To sign the message,
the routine computes a description of a function G which is dependent of
the message M, and then applies the function G to x to produce a string z.
The routine outputs z and a description of a second function F as the
desired signature of the message M. Thus according to the invention a
signature of the message is obtained by applying to an independent
argument x a function dependent on M. This operation provides enhanced
efficiency and security over the prior art and facilitates use of the
scheme to allow multiple users of a secure communications system to share
the same public key; alternatively, the scheme is useful for generating
short certificates of public keys used in such systems.
The foregoing has outlined some of the more pertinent objects of the
present invention. These objects should be construed to be merely
illustrative of some of the more prominent features and applications of
the invention. Many other beneficial results can be attained by applying
the disclosed invention in a different manner or modifying the invention
as will be described. Accordingly, other objects and a fuller
understanding of the invention may be had by referring to the following
Detailed Description of the preferred embodiment.
For a more complete understanding of the present invention and the
advantages thereof, reference may be made to the following drawings:
FIG. 1 is a flowchart representation of the preferred technique for
generating a digital signature according to the present invention; and
FIG. 2 is a flowchart representation of the preferred technique for
verifying the digital signature generated in accordance with FIG. 1.
DETAILED DESCRIPTION
The following preliminary background is provided to facilitate the
understanding of the new digital signature algorithm. Let n be the product
of two large primes, p.sub.1 .ident.3 mod 8 and p.sub.2 .ident.7 mod 8.
Define F.sub.0 (x)=x.sup.2 mod n, F.sub.1 (x)=4x.sup.2 mod n, and for any
non-empty string of bits .sigma.=b.sub.1 b.sub.2 . . . b.sub.k, let
F.sub..sigma. =F.sub.bk (. . . (F.sub.b2 (F.sub.b1 (x)) . . . ). Thus,
each string .sigma. is the description of a function, namely,
F.sub..sigma., mapping numbers modulo n to numbers modulo n. Then, the
following four properties hold for functions with such descriptions.
First, F.sub.0 and F.sub.1 are permutations over the squares mod n, and so
is F.sub..sigma. for any string .sigma.. More specifically, because
F.sub.0 is a permutation, if x is a square mod n, then exactly one of its
four square roots mod n is itself a square mod n; and this root will be
denoted by .sub.x 2.sup.-1. In general, if k is a positive integer, .sub.x
2.sup.-k will denote the unique square mod n, z, such that .sub.z 2.sup.k
.ident.x mod n. Second, the integer 2 is not a square mod n, and thus
.sub.4 2.sup.- 1 .notident.2 mod n. Third, if one computes any two squares
mod n, x and y, and any two different strings of equal length, .sigma. and
.tau., such that F.sub..sigma. (x)=F.sub..tau. (y), then one can easily
factor n. Finally, let k be a positive integer, let s=.sub.4 2.sup.-k mod
n, let .sigma. be a k-bit string, let int(.sigma.) be the natural number
whose binary representation is .sigma. without its leading O's (i.e.,
int(011)=3), and let X and z be squares mod n such that X=F.sub..sigma.
(z). Then as the fourth property, z=.sub.X 2.sup.-k /s.sup.int(.sigma.)
mod n.
With this background, the digital signature algorithm of the present
invention can now be described. The inventive algorithm makes uses of a
secure hash function H, which may be common to all users. For the
following description of the algorithm, it is assumed that H produces
80-bit outputs and that the expression a.vertline.b denotes the
concatenation of strings a and b (though other operators may be used to
combine such strings).
The scheme begins with each user choosing a pair of public and secret keys.
In particular, each user selects a large prime p.sub.1 .ident.3 mod 8 and
a large prime p.sub.2 .ident.7 mod 8, and lets n=p.sub.1 p.sub.2 be her
public key and s=1/.sub.4 2.sup.-81 mod n be her secret key. For
simplicity of notation, all the following computations are mod n unless
otherwise specified. It should be appreciated that the value .sub.4
2.sup.-81 can be obtained easily by (1) computing ((p.sub.i +1)/4).sup.81
mod p.sub.i -1, (2) computing v.sub.i =4.sup.u1 mod p.sub.i -1, and (3)
applying the Chinese remainder theorem to v.sub.1 and v.sub.2 with moduli
P.sub.1 and P.sub.2.
A user whose public and secret keys are n and s, respectively, signs a
message M as follows. In a first "off-line" step, the user randomly
selects a square x and computes X=.sub.x 2.sup.81. It is important that x,
and thus X, be selected afresh for each message to be signed. In the
second or "on-line" step, the signer computes .sigma.=H(X.vertline.M),
t=s.sup.int(0.sigma.), and z=xt, and then outputs (z,.sigma.) as the
signature of M. It should be noted that .sigma. (=H(X.vertline.M)) is a
description of a function G.sub..sigma. (i.e., G.sub..sigma.
(x)=xs.sup.int(0.sigma.) mod n) as well as the description of a second
function F.sub..sigma. referred to above. Thus both the functions
G.sub..sigma. and F.sub..sigma. depend on the message M because .sigma.
has been computed on input M. Then, z consists of applying G.sub..sigma.
to x so as to produce a string z. It should further be noted that by the
fourth property described above, X=F.sub.0.sigma. (z)=F.sub..sigma.
(z.sup.2). Thus, the signature (z,.sigma.) of message M consists of a
value z and the description of a function, namely F.sub..sigma., which
depends on M. It should also be appreciated that the following
relationship holds between G.sub..sigma. and F.sub..sigma. :
F.sub.0.sigma. (G.sub..sigma. (x))=X. (Notice that the redundant 0 has
been added to totally preserve the fourth property and may be dispensed
with.)
For verification, given a message M and an alleged signature (z,.sigma.)
relative to the public key n, the scheme computes X=F.sub..sigma.
(z.sup.2), and then checks whether H(X.vertline.M)=.sigma.. This check
assumes that the concatenation operation was performed during signing;
obviously other operations and/or additional inputs (such as the date, the
name of the signer, the name of the recipient, or some other transaction
identifier, etc.) may be used. If so, the signature is accepted. It should
be noted that z.sup.2 is a computationally- easy transformation of z. Also
note that .sigma. is the description of the function F.sub..sigma. and
this function was chosen by the signer to be dependent on M because
.sigma. was computed via M. Further, it should be noted that from the
result X of applying function F.sub..sigma. to input z.sup.2, one can
easily get back the description of F.sub..sigma., namely .sigma., by
applying H on inputs X and M.
The above-described digital signature scheme is illustrated in FIG. 1,
which is a flowchart of the basic steps used to implement the invention.
The method begins with box 12 in which a number x independent of the
message M is selected. Box 14 represents the message M. At box 16, the
message and preferably the number x are used to compute a string .sigma.
dependent on the message M. String .sigma. is then output as part of the
digital signature as indicated by the arrow, which goes to the digital
signature box 18. The other input to box 18 is a string z, which is formed
in the following manner. String .sigma. is provided as one input to box
20, which also receives the secret key SK. The string .sigma. together
with the secret key specify a permutation G.sub..sigma. composed from a
given set of permutations. At box 22, the permutation G.sub..sigma. is
applied to the number x to produce the string z. As noted above, the
string z and the string .sigma. are then released as the digital signature
of the message M.
A method for verifying a digital signature of a message M relative to a
public key is illustrated in FIG. 2. The method begins with the digital
signature (box 18) of FIG. 1, which includes the string z and the string
.sigma.. The string .sigma. is applied box 24, which also receives the
public key PK. The output of box 24 is a permutation F.sub..sigma.
composed from a given set of permutations and specified by the string
.sigma. and the public key. The method continues at box 26 by applying
permutation F.sub..sigma. to string z to yield a string y. Box 28 then
verifies whether string .sigma. is easily computable in polynomial time
from at least string y and the message M.
The above-described algorithm is very efficient. To perform the off-line
signing steps 82 multiplications are sufficient. To perform the on-line
signing step, roughly 121 multiplications are sufficient if only the
secret key s is remembered. Alternatively, if all the .sub.s 2.sup.i
values are precomputed and then remembered, only about 41 multiplications
are sufficient. This number may be further decreased if one is willing to
precompute and store additional values. For verifying the signature of a
message, about 81 multiplications are sufficient. Thus, the disclosed
algorithm is much faster than RSA. In particular, the algorithm is at
least 5 times faster if no extra .sub.s 31 2.sup.1 value is stored, and at
least 15 times faster if 81 such values are stored. Consequently the
algorithm can be implemented with cheaper and simpler hardware than RSA.
Further, if H is a secure hash function, then the digital signature scheme
of the present invention is very secure. For example, assume that an enemy
chooses a number z and a 80-bit string .sigma. and computes
X=F.sub..sigma. (z.sup.2). Then he will be able to easily sign a message M
only if H returns exactly the bit-pattern .sigma. on input X.vertline.M.
But this will happen only with probability 2.sup.-80 since a secure H
behaves randomly, and the adversary cannot easily increase this negligible
probability. In fact, if he could concoct an X such that he could forge
the signature of any message that, hashed with X, yields either of two
different 80-bit patterns, .sigma. and .tau., then he should be able to
produce two pairs (z,.sigma.) and (.omega.,.tau.) for which F.sub..sigma.
(z.sup.2)=F.sub..tau. (.OMEGA..sup.2)=X. But then, by the third property
described above, the enemy could easily factor n.
Thus, if the hash function H is secure, forging signatures in the above
algorithm is as hard as factoring n. Given the many and unpredictable ways
by which an enemy can attack a signature scheme, knowing that no attack
could bypass the difficulty of integer factorization if the hash function
is secure is of fundamental importance. By comparison, no proof of
equivalence to integer factorization exists for RSA. Indeed, one might be
able to break RSA without being able to factor integers.
The disclosed scheme differs from RSA in further important respects. In the
RSA scheme, the signature of a message M is computed by applying to
ARGUMENT M a FIXED function. To the contrary, a signature of a message M
according to the present invention is obtained by applying to an
INDEPENDENT argument x a function DEPENDENT on M. Indeed, the disclosed
scheme multiplies x by s.sup.int(0.sigma.), where x is independent of M
(because x is selected at random before M is even known), and .sigma.
depends on M because .sigma.=H(X.vertline.M). The dramatic difference
between RSA and the inventive scheme is also evident from their
verification process. The RSA scheme verifies the signature of a message M
by applying a fixed function to it and checking that the result is the
original message M. In the present invention, the algorithm verifies the
signature (z,.sigma.) of a message M by applying to a z a function that
depends on M and checking that the description of the same function can be
easily obtained from the result.
Those skilled in the art will recognize that many variants are possible for
the digital signature scheme disclosed herein. For instance, one may omit
the redundant 0, use a secure hash function mapping to a different number
of bits, give the hash function additional inputs, or use composites of a
different form. In addition, the number 4 can be replaced with another
square S, preferably such that its square-root mod n is not known to an
enemy. For instance, one may define F.sub.0 (x)=x.sup.2 and F.sub.1
(x)=Sx.sup.2 mod n. Also, rather than using one bit at a time, different
patterns may be used. For instance, without intending to be restrictive,
one may use 3-bit long strings and 8 squares S.sub.0, S.sub.1, . . . ,
S.sub.7 such that F.sub.000 (x)=S.sub.0 x.sup.2, F.sub.001 (x)=S.sub.1
x.sup.2, and so on. In fact, the routine can use totally different
functions for F.sub.0 and F.sub.1, or for the F.sub..sigma. 's.
The inventive algorithm (which for convenience will be referred to as the
SM algorithm in the following discussion) can be used to provide
additional properties and advantages, for example, enabling a group of
users to share the same public key or to allow a group of users to sign
without encrypting. In particular, assume that there is an agent A, who
has selected an SM public key n keeping in storage its secret
factorization. Then, A may use the SM algorithm to guarantee that (a) the
users in the group can sign messages relative to n, so that each user is
kept individually accountable for what he signs, and (b) the users in the
group cannot encrypt messages. (Thus, revealing n's factorization to every
user is not a solution. This way, in fact, the signatures produced by some
user could have been produced by any other user and no one could be kept
accountable for what he or she signs). In this situation, the following
properties apply. Each user in the group, A.sub.i, is guaranteed that
another user A.sub.j cannot forge his signatures. Moreover, given A.sub.i
's signature of a message M, anyone can verify that A.sub.i is the signer.
The users further cannot use the keys that allow them to sign in order to
encrypt messages to each other. Finally, A may act as a higher authority
and can sign messages for the group. Alternatively, it can be arranged
that no such higher authority exists e.g., without intending to be
restrictive, it can be arranged that the factorization of n is not known
to any individual user, but is only collectively known to a group of
agents (e.g., a subgroup of users or possibly the whole group.)
The above properties are useful in a variety of settings. For instance,
when A is a bank and the A.sub.i 's its branches, or when A is the
Government and the A.sub.i 's government agencies or employees. In either
case, A can safely delegate signing transactions without introducing any
complications about encryption. The important point is that all users in
the group share the same public key n without knowing its factorization.
This fact thus provides the additional benefit that there is no need to
certify individual public keys for the users in the group. In such case
only a single composite number n needs to be certified outside the group,
if it is not already universally known.
The SM algorithm may be used to achieve any of the above properties in a
variety of ways. Without limiting such examples, one such technique uses
the following theorem described by H. C. Williams, A Modification of the
RSA Public-Key Cryptosystem, IEEE Trans. Inform. Theory, IT-26, 1980, at
726-729: let n be the products of two primes, one congruent to 3 mod 8 and
the other to 7 mod 8. Then, for any member of Z.sub.n *, exactly one of x,
-x, 2x, -2x mod n is a square mod n. Assume now that A has selected one
such n, and has stored its secret prime factorization (which need not be
done in the basic SM algorithm). Then, A allows his users to share
essentially his same public key n as follows.
A computes S.sub.i =H(n.vertline.i)(i.e., the hash of the concatenation of
n and the name of the user himself). Then, A computes .alpha..sub.i
.epsilon.[1, -1, 2, -2] such that .alpha..sub.i S.sub.i is a square mod n,
computes the value s.sub.i =1/.sub.(.alpha..sbsb.i.sub.S.sbsb.i.sub.)
2.sup.-81 and gives s.sub.i to A.sub.i as a secret key. In essence, the
corresponding public key of A.sub.i can be considered (n,i,.alpha..sub.i).
Note that if n is universally known, the recipient of a signature of
A.sub.i knows all of A.sub.i 's public key, except for the two bits needed
to specify .alpha..sub.i. Also, it is not crucial that S.sub.i
=H(n.vertline.i), but it is important that S.sub.i be sufficiently random,
though computable from i so that i's secret key is sufficiently
unpredictable and unrelated to that of j).
To sign, A.sub.i signs a message M as in the basic SM scheme described
above, but uses s.sub.i instead of .sub.4 2.sup.-81 and S.sub.i instead of
4. To the resulting signature (z,.sigma.), A.sub.i also adds its own
.alpha..sub.i. To verify the signature ((z,.sigma.),.alpha..sub.i) of
A.sub.i for message M, the verifier computes S.sub.i =H(n.vertline.i) and
.alpha..sub.i S.sub.i. Then, he computes X=F.sub..sigma. (z.sup.2), but
using F.sub.0 (x)=x.sup.2 and F.sub.1 (x)=.alpha..sub.i S.sub.i x.sup.2 as
basic permutations, and accepts (z,.sigma.) to be A.sub.i 's signature of
M if H(X.vertline.M)=.sigma..
This use of the SM algorithm not only differs from the schemes cited above,
but also from those cryptosystems similar to other known systems where
many users share both public and secret keys, or from other identity-based
schemes.
The above way to use the SM algorithm to allow many users to essentially
share the same public key also can be advantageously used to issue short
certificates for the public keys of a digital signature system. By way of
brief background, in any digital signature scheme, each user has a pair of
matching verification and signing keys. The user's verification key must
be as "public" as possible to allow as universal as possible verification
of U's digital signatures. For these reasons, U's verification key is also
referred to as U's public key, and the corresponding :signing key as U's
secret key.
The question of how a user can make his own public key truly public is an
important problem, and many possibilities exist. Moreover, techniques for
building "certificates" of public keys are also known in the art. The
traditional way envisions a hierarchy of authorities. For example, assume
that there is a simple two-level hierarchy: a few thousand first-level
authorities, A'.sub.1,A'.sub.2, . . . , and a single second-level
authority, A". It is assumed that each of the first-level authorities is
capable of digitally signing, that their public keys, PK'.sub.1,PK'.sub.2,
. . . , are already known to A", and that the public-key of A", PK", is
universally known. When a user U wishes to have his chosen public key,
PK.sub.U, certified, he goes to the authority, A'.sub.c, closest to (or
most convenient for) him. After verifying U's identity and the fact that
he wishes to elect PK.sub.U as his own signing key (alternatively,
A'.sub.c may receive a traditional notarized document to this effect),
A'.sub.c provides U with a certificate consisting of (1) his own digital
signature of PK.sub.U (relative to PK'.sub.c) (2) his own public key
PK'.sub. c and (3) the digital signature of A" of PK'.sub.c (relative to
PK".) The second and third pieces of data are necessary since there may be
a sufficiently-high number of first-level authorities and their public
keys may not be universally known. Such a certificate is either given to
user U, so that he will send it along with any digital signature of his
(in order to enable anyone to verify it), or the certificate is posted in
a sufficiently accessible database (so that anyone who wishes verify U's
digital signature of a given message can retrieve the certificate of U's
public key from the database).
In either case, a traditional certificate for PK.sub.U is quite long
because it includes at least two pieces of data in addition to the
signature of PK.sub.U. This is undesirable, since public-key certificates
must be sent along or retrieved with almost every single digital
signature. Moreover, the recipient of a digital signature may wish to
store its associated public-key certificate for a long time period to
maintain proof of the signer's commitment. Such long certificates are thus
very costly, because sending bits across communication lines (e.g., via a
long-distance phone call) is expensive and because storing bits is
expensive. Obviously the longer the certificate, the higher the cost
associated with transmission and storage thereof.
The present invention provides a new and useful way of producing "short"
certificates. Let n be the universally-known public key of A" within the
SM digital signature scheme, and let A" store n's secret factorization.
Then, as previously discussed in the context of allowing many users to
share the same public key, A" may assign to each sub-authority a
corresponding square with its corresponding secret signing key. For
instance, A" may assign to A.sub.i ' the square .alpha..sub.i S.sub.i
(where S.sub.i =H(n.vertline.i) and .alpha..sub.i .epsilon.[1, -1, 2, -2],
for which no one knows a square root mod n, and the corresponding secret
signing key PK.sub.i '=1/.sub.(.alpha..sbsb.i.sub.S.sbsb.i.sub.)
2.sup.-81, relative to the public key (n,i,.alpha..sub.i). Assume now that
each user U goes to A.sub.i ' to have certified his own public key
PK.sub.U. Then A.sub.i ' gives to U his own signature of PK.sub.U, plus a
few additional bits, i.e., "i" and ".alpha..sub.i ". These additional
bits, in principle, need not be more than about 22, if there are at most
10.sup.6 authorities of level 1. More realistically, if the first-level
authorities were the post offices, for example, the "i" would look
something like "MA02146", which is a zip code in a particular state, and
.alpha..sub.i would consist of just 2 bits. (Indeed, the bits describing i
may be unnecessary because the user going to the post office may know the
name of it).
Since n is universally known, anyone can compute S.sub.i =H(n.vertline.i)
and .alpha..sub.i S.sub.i, and thus verify the signature of A.sub.i ' of
PKU relative to public key (n,i,.alpha..sub.i). Thus an SM certificate is
some 500 bits shorter than a traditional DSA certificate or 1000 bits than
an RSA certificate. Indeed, SM certification is so simple that it is worth
using even if another signature scheme were adopted for the individual
users.
While the present invention has been described generally, it should be
appreciated that the algorithm is preferably implemented on a program
storage device readable by a processor and tangibly embodying a program of
instructions executable by the processor to perform the algorithm steps. A
suitable processor for signing is a personal computer (e.g., a .times.86
processor running OS/2 or Windows, with suitable I/o devices) or a smart
card, etc. A suitable verifier is a computing unit coupled to a card
reader or capable of receiving messages from any convenient similar input
(e.g., a telephone line or RF link).
It should be further appreciated by those skilled in the art that the
specific embodiments disclosed above may be readily utilized as a basis
for modifying or designing other structures for carrying out the same
purposes of the present invention. It should also be realized by those
skilled in the art that such equivalent constructions do not depart from
the spirit and scope of the invention as set forth in the appended claims.
* * * * *
|
|
 |
|
 |
Description |
|
