Masked digital signatures

Details Masked digital signatures Masked digital signatures

1997-11-10

2001-08-21

Barron, Jr., Gilberto (Department: 2131)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S168000, C380S030000

Reexamination Certificate

active

06279110

ABSTRACT:

BACKGROUND OF THE 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 E
1
Gamal public key signature scheme that signs a message with the sender's private key. The recipient may then recover the message with the sender's public key. The E
1
Gamal scheme gets its security from calculating discrete logarithms in a finite field. Furthermore, the E
1
Gamal-type signatures work in any group and in particular elliptic curve groups. For example given the elliptic curve group E(F
q
) then for &egr;E(F
q
) 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 E
1
Gamal 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 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 ‘smart card’ application, the computations may introduce delays in the signature and verification process.
Public key schemes may be implemented using one of a number of multiplicative groups in which the discrete log problem appears intractable, but a particularly robust implementation is that utilizing the characteristics of points on an elliptic curve over a finite field. This implementation has the advantage that the requisite security can be obtained with relatively small orders of field compared with, for example, implementations in Z
p
* and therefore reduces the bandwidth required for communicating the signatures.
In a typical implementation of such a digital signature algorithm such as the Elliptic Curve Digital Signature Algorithm (ECDSA) a signature component s has the form:
s=k
−1
(
e+dr
)mod
n
where:
d is a long term private key random integer of the signor;
Q is a public key of the signor derived by computing the point Q=dP;
P is a point (x, y) on the curve which is a predefined parameter of the system;
k is a random integer selected as a short term private or session key, and has a corresponding short term public key R=kP;
e is a secure hash, such as the SHA-
1
hash function of a message; and
n is the order of the curve.
In this scheme the signor represents the x coordinate of the point kP as an integer z and then calculates a first signature component r=z mod n. Next, the second signature component s above is calculated. The signature components s and r and a message M is then transmitted to the recipient. In order for the recipient to verify the signature (r,s) on M, the recipient looks up the public key Q of the signor. A hash e′ of the message M is calculated using a hash function H such that e′=H(M). A value c=S
−1
mod n is also calculated. Next, integer values u
1
and u
2
are calculated such that u
1
=e′c mod n and u
2
=rc mod n. In order that the signature be verified, the value u
1
P+u
2
Q must be calculated. Since P is known and is a system wide parameter, the value u
1
P may be computed quickly. The point R=u
1
P+u
2
Q is computed. The field element x of the point R=(x
1
,y) is converted to an integer z, and a value v=z mod n is computed. If v=r, then the signature is valid.
Other protocols, such as the MQV protocols also require similar computations when implemented over elliptic curves which may result in slow signature and verification when the computing power is limited. The complexity of the calculations may be explained by observing a form of the elliptic curve. Generally, the underlying elliptic curve has the form y
2
+xy=x
3
+ax+b and the addition of two points having coordinates (x
1
,y
1
) and (x
2
,y
2
) results in a point (x
3
,y
3
) where:
x
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
2
⊕
y
1
⊕
y
2
x
1
⊕
x
2
⊕
x
1
⊕
x
2
⊕
a
⁢
 
⁢
(
P
≠
Q
)
⁢

⁢
y
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
⊕
(
x
1
⊕
x
3
)
⊕
x
3
⊕
y
1
⁢
 
⁢
(
P
≠
Q
)
The doubling of a point i.e. P to 2P, is performed by adding the point to itself so that
y
3
=
{
x
1
2
⊕
(
x
1
⊕
y
1
x
1
)
}
⁢
x
3
⊕
x
3
x
3
=
x
1
2
⊕
b
x
1
2
It may be seen in the above example of the ECDSA algorithm that the calculation of the second signature component involves at least the computation of an inverse. Modulo a number the generation of each of the doubled points requires the computation of both the x and y coordinates and the latter requires a further inversion. These steps are computationally complex and therefore require either significant time or computing power to perform. Inversion is computationally intensive, and generally performed within a secure boundary where computational power is limited thus it would be advantageous to perform such calculations outside the secure boundary, particularly where computational power is more readily available. This however cannot be done directly on the ECDSA signature scheme without potentially compromising the private key information. Therefore there exists a need for a method of performing at least part of a signature operation outside a secure boundary while still maintaining an existing level of security in current signature schemes.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a method and apparatus in which at least some of the above disadvantages are mitigated.
This invention seeks to provide a digital signature method, which may be implemented relatively efficiently on a processor with limited processing capability, such as a ‘smart card’ or the like.
In general terms, the present invention provides a method and apparatus in which signature verification may be accelerated.
In accordance with this invention there is provided; a method of signing and authenticating a message m in a public key data communication system, comprising the steps of:
in a secure computer system:
(a) generating a first short term private key k;
(b) computing a first short term public key derived from the first short term private key k;
(c) computing a first signature component r by using the first short term public key;
(d) generating a second short term private key t;
(e) computing a second signature component s by using the second short term private key t on the message m, the long term private key and the first signature component r;
(f) computing a third signature component c using the first and second short term private keys k and t respectively, and sending the signature components (r, s, c) as a masked digital signature of the message m to a receiver computer system; in the receiver system;
(g) using said second and third signature components (s,c) computing a normal signature component {overscore (s)} and sending the signature components ({overscore (s)}, r) as a normal digital signature to a verifer computer system; and
(h) verifying normal signature.
In accordance with a further aspect of the invention there is provided a processing means for signing a message m without performing inversion operations and including a long term private key contained within a secure boundary and a long term public key derived from the private key and a gener

Affiliated with

Also associated with

Rating

Masked digital signatures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Masked digital signatures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Masked digital signatures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2497887