Cryptography – Particular algorithmic function encoding – Nbs/des algorithm
Patent
1997-03-06
1999-06-08
Gregory, Bernarr E.
Cryptography
Particular algorithmic function encoding
Nbs/des algorithm
380 23, 380 29, 380 30, 380 49, H04L 900, H04L 906, H04L 930
Patent
active
059109890
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method for the generation of digital signatures for electronic messages.
The method can be applied especially to the signing of messages by portable devices of the microprocessor-based smart card type.
For example, it may be necessary to sign messages sent by the card to a reading terminal or to a central authority. Or again, it may be necessary to carry out a transaction (an electronic cheque transaction) and to sign this transaction so that it can be authenticated first of all by the reading terminal in which the transaction is made and then by a central authority that manages the transaction.
The method that shall be described is related to the algorithms for the generation of digital signatures published in recent years, especially by the U.S. National Institute of Standards and Technology, for example the DSA (Digital Signature Algorithm) described in the U.S. patent application Ser. No. 07/736451 filed Jul. 26, 1991 and now U.S. Pat. No. 5,231,668 and published on the 30the of Aug. 1991 in the Federal Register kept by this Institute, pages 42980-42982.
The invention is aimed at modifying the known methods, in particular to make them adaptable to microprocessor-based cards that do not have physical resources (processor, memories) sufficient to swiftly carry out mathematical operations on big numbers. The known algorithms, especially the DSA, use big numbers to generate signatures with a sufficient degree of security.
2. Description of the Related Art
In order to provide for a clear understanding of the invention, first of all a reminder shall be given of what is the DSA algorithm.
A DSA signature consists of a pair {r, s} of big numbers represented in computers by long strings of binary digits (160 digits). The digital signature is computed by means of a series of computation rules defined by the algorithm and a set of parameters used in these computations. The signature enables both the certifying of the identity of the signer (because it brings into action a secret key proper to the signer) and the integrity of the signed message (because it brings into action the message itself). The algorithm makes it possible firstly to generate signatures and secondly to check signatures.
The generation of DSA signatures brings into action a secret key. The check brings into action a public key that corresponds to the secret key but is not identical to it. Each user has a pair of keys (secret, public). The public keys may be known to all while the secret keys are never revealed. Anybody has the capacity to check the signature of a user by using the public key of this user but only the possessor of the secret key can generate a signature corresponding to the pair of keys.
The parameters of the DSA are the following: 1024 (including the limits) and L=64a for a as any integer; q; fixed for a given user); modular operations defined here below, modulo p or modulo q, shall be designated by mod p or mod q respectively;
The integers p, q and g are parameters of the system that can be published and/or shared by a group of users. The secret and public keys of a signer are respectively x and y. The parameter k which is a random parameter must be regenerated for each new signature. The parameters x and k are used for the generation of signatures and must be kept secret.
In order to sign a message m (which will generally be a hashed value of an initial file M), the signer computes the signature {r, s} by: number k' such that kk'=1 mod q; for example if q=5 and k=3, then 1/k=2 for 3.times.2=6, giving 1 mod 5).
After the fact that r and s are different from zero has been tested, the signature {r, s} is sent to the verifier. The verifier is generally the terminal into which the smart card that sends the message m and the signature {r, s} is inserted.
The verifier, which knows p, q, g (related to the application), y (related to the user) and m (the message that he has received from the card), computes: s has the value (m+xr)/s mod q.
Consequently,
REFERENCES:
patent: 4710613 (1987-12-01), Shigenaga
patent: 5231668 (1993-07-01), Kravitz
patent: 5625695 (1997-04-01), M'Raihi et al.
Byte, vol. 18, No. 12, Nov. 1993, Digital Signatures, Bruce Schneier, pp. 309-312.
Journal of Cryptology, vol. 4, No. 3, 1991, Efficient Signature Generation by Smart Cards, C.P. Schnorr, pp. 161-174.
Gemplus
Gregory Bernarr E.
LandOfFree
Method for the generation of electronic signatures, in particula does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for the generation of electronic signatures, in particula, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the generation of electronic signatures, in particula will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1687120