Digital signature method

Details Digital signature method Digital signature method

1998-12-18

2002-12-24

Barrón, Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S170000, C713S171000, C713S177000, C713S178000, C713S180000, C713S168000, C380S028000, C380S030000

Reexamination Certificate

active

06499104

ABSTRACT:

The present invention relates in particular to a method for generating a digital signature (c,d) of a message M as well as a method for authenticating such a signature.
The purpose of digital signature methods is to certify the origin of an electronic document. Similarly to a handwritten signature, a digital signature is added to an electronic message to ensure its authenticity. Consider the practical case in which an entity A of a communications system wishes to address a message M to an entity B. In a first signature generation phase the sender A, after writing his message, carries out a number of mathematical operations according to the message M to be signed and operands which can be either secret or public. These calculations will generate a digital entity which will be called the signature. The message M. and its signature, are then transmitted electronically. In a second phase, after receiving the message and the signature, recipient B will in turn perform mathematical operations. The validity of the signature received can be verified from the result of the latter calculations. It should be noted that the goal of the signature function is to authenticate a message M, not to ensure the confidentiality of its content. This message can thus be transmitted either in cleartext or in code by an encryption function that is fully independent of the signature mechanism.
Overall, a digital signature method does the following in a modern communications system:
(a) Definitely authenticates the identity of the message sender.
(b) Ensures the integrity of the contents of a message (verifies that the message was not altered during its transmission).
In digital signature methods, security is based on the extreme difficulty of reversing certain mathematical functions. Because of the power of today's computers, it is now impossible to solve some of these equations without knowing the secret elements of the algorithm.
At the present time, there are various digital signature methods.
A first type, developed by Rivest-Shamir-Adelman, is based on the difficulty of factoring large whole numbers (see “A Method for Obtaining Digital Signatures and Public Key Cryptosystems,” Communications of the ACM, February 1978, Vol. 21, No. 2, pp. 120-126, and U.S. Pat. No. 4,405,829 referring thereto).
A second type, developed by Taher El-Gamal, proposes signature algorithms based on the discrete logarithm problem involving discrete exponentiation (see “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Trans. on Inform. Theory, Vol. IT-31, pp. 469-472, July 1985).
Discrete exponentiation has three arguments, the exponentiation base g the exponent x, and the modulo N. The discrete logarithm problem, given the mathematical relationship: Y-g
x
modulo N (which means: Y is the remainder when g
x
is divided by N), consists of finding x when N, g, and Y are known.
A method of the same type, but simpler, was disclosed by Schnorr and was the subject of U.S. Pat. No. 4,995,082. It is distinguished from that of El-Gamal by consisting of reducing the size of the exponents of the discrete exponentiations to speed up calculation. Here, an element g generates a subgroup of order q, with q on 160 bits for example. Also, a hash function is used in calculating the signature.
The digital signature thus generated is small in size.
In general, discrete exponentiation be either modular exponentiation in which one is working with whole numbers having a well-chosen number for a modulo, or multiplication by a whole number on an elliptical curve which is an operation similar to modular exponentiation, but is defined in a group noted additively and not multiplicatively.
In numerous applications, the digital signature must be created and verified in real time. Certain methods, such as the El-Gamal method, require a heavy financial outlay because the algorithms demand very powerful computers. To obviate these constraints, optimization of the algorithms simplifies the calculations while retaining comparable security.
The discrete exponentiation solution is today the most broadly used solution in cryptographic systems, and certain improvements have been made to the algorithms to increase the speed of calculation while retaining maximum security.
With this perspective, reducing the size (number of bits) of the exponent is very important because the calculation time of modular exponentiation is proportional to this size.
Also, in algorithms known to date, the cardinal of the group in which one is working must be known. The cardinal of this group is a function of the choice of modulo N. Since the security of the algorithm is based on discrete exponentiation, it must be made impossible to solve. This security implies certain constraints in the choice of modulo N.
In the case of modular exponentiation, the security of discrete exponentiation offered only two options as to choice of modulo in the prior art.
With the first possibility, N is the product of two whole numbers. El-Gamal proposed choosing N so that (N−1)/2 is prime and the divisor used is (N−1).
The second option concerns algorithms based on discrete exponentiation where a subgroup must be known as well as its cardinal, the cardinal of this subgroup being a divisor of N−1 if N is prime, or a divisor of the number of points on the curve in the case of an elliptical curve. Schnorr proposes choosing q as the cardinal of the subgroup, q being such that it divides N−1.
The invention overcomes these drawbacks by proposing a method for decreasing the complexity of the calculations so that one can work in real time with a PC computer.
It also overcomes the aforesaid limitations, as the choice of modulo N is no longer limited to the two above options or calculation of the number of points on the elliptical curve is no longer necessary.
For this purpose, a method for generating a digital signature (c,d) of a message M consists of:
defining a modulo N and a base g, a public key Y, and a private key x, these parameters N, g, Y, and x being linked by the relationship:
Y=g
x
(
mod N
)
defining a hash function H the size of whose result has S bits
choosing a number r of T bits with
T>=
2
S
calculating u from the following relationship:
u=g
r
*Y
z
where
Z=
2
S
by function H, hashing the concatenation of M and u, the number thus obtained being the value c of the signature,
calculating the value d of the signature by the relationship: d=r+c*x.
According to an additional characteristic enabling computing time to be reduced still further, message M is hashed by a function h
1
before being hashed by function H then concatenated with u, the functions h
1
and H possibly being identical.
According to one particular characteristic, private key x is defined before public key Y, the latter then being calculated by the relationship:
 
Y=g
x
(
mod N
).
According to another characteristic, characterized in that public key Y is defined before private key x, and in that modulo N is chosen to be not a prime.
According to another characteristic, the number r is a random number.
The invention also relates to a method of authenticating the digital signature (c,d) of a message M generated according to the invention, this method being characterized by consisting, when public key Y, modulo N, and base g and hash function H, hence the value of S, are known, of:
calculating u by the relationship
u=g
d
*Y
(z−c)
with
Z=
2
S
hashing the concatenation of M and u by the function H,
verifying that the value thus obtained is equal to c if the signature is authentic.
According to an additional characteristic of this method, message M is hashed by function h
1
* before being hashed by function H then concatenated with u.


REFERENCES:
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4995082 (1991-02-01), Schnorr
patent: 5150411 (1992-09-01), Maurer
L.Harn and Y.Xu, Design of generalised ElGamal type digital signatures schemes,Nov. 1994,IEEE).*
Okamoto, An efficient digital signature sch

Affiliated with

Also associated with

Rating

Digital signature method does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2953424