Method and device for generating digital signature

Patent metadata

Field	Value
Publication number	US-10038561-B2
Application number	US-201414911143-A
Country	US
Kind code	B2
Filing date	Aug 14, 2014
Priority date	Aug 16, 2013
Publication date	Jul 31, 2018
Grant date	Jul 31, 2018

Abstract

Disclosed are a method and device for generating a digital signature. The method comprises: a device generating a digital signature parameter r that meets an effective determining condition; generating a digital signature parameter s according to the following formula s=((1+d A ) −1 ·(r+k)−r)mod n, by using a private key d A , a random number k, r, and an elliptic curve parameter n, a value range of k being [1, n−1]; determining if the generated s is 0; if s is 0, regenerating r that meets the effective determining condition, and regenerating s by using d A , the regenerated k with the value range of [1, n−1] and the regenerated r and n, until s is not 0; converting data types of r and s that is not 0 into byte strings, to obtain a digital signature (r, s). According to the technical solutions provided by embodiments of this application, a digital signature parameter s is obtained by using a simplified calculation formula, and the number of times that big integers are calculated can be reduced, so that the calculation efficiency of generating a digital signature based on an SM2 digital signature generation algorithm is improved.

First claim

The invention claimed is:

1. A method of generating a digital signature applied in a field of user identity authentication, the method comprising:
generating, by a digital signature generator, a digital signature parameter r satisfying a validity judgment condition;
generating, by the digital signature generator, a digital signature parameter s using a private key d A , a random number k in the range [1, n−1], the digital signature parameter r, and an elliptical curve parameter n in the equation of:
s =((1+ d A ) −1 ·( r+k )− r )mod n;

judging, by the digital signature generator, whether the digital signature parameters is 0, and if the digital signature parameter s is 0, then regenerating a digital signature parameter r satisfying the validity judgment condition, and regenerating the digital signature parameter s using the private key d A , a regenerated random number k in the range [1, n−1], the digital signature parameter r regenerated, and the elliptical curve parameter n until the digital signature parameters is not 0; and
converting, by the digital signature generator, the data type of the resulting digital signature parameter r and digital signature parameter s which is not 0 into a string of bytes to obtain a digital signature (r, s);
outputting, by the digital signature generator, the digital signature (r, s), so that the digital signature (r, s) can be used by a digital signature user to participate in the user identity authentication; wherein the digital signature user is a system or a device or a network node participating in the user identity authentication;
wherein generating, by the digital signature generator, the digital signature parameter s in the equation of s=((1+d A ) −1 ·(r+k)−r) mod n comprises:
after performing a large integer addition operation on the digital signature parameter r and the random number k, performing, by the digital signature generator, an operation of a result (r+k) of the large integer addition operation modulo the elliptical curve parameter n, and after adding 1 to the private key d A , calculating, by the digital signature generator, a modular inverse of (1+d A ) modulo the elliptical curve parameter n;
performing, by the digital signature generator, a large integer multiplication operation on a result of the large integer addition operation result modulo n, and a result of the modular inverse; and
performing, by the digital signature generator, an operation of the large integer multiplication operation result, after the digital signature parameter r being subtracted, modulo the elliptical curve parameter n to obtain the digital signature parameter s; or performing, by the device digital signature generator, an operation of the result of the large integer multiplication operation result module n, after the digital signature parameter r being subtracted, modulo the elliptical curve parameter n to obtain the digital signature parameter s.

2. The method according to claim 1 , wherein before the digital signature parameter s is generated, the method further comprises:
obtaining, by the digital signature generator, an operation result r+k of the validity judgment condition on r to generate the digital signature parameter s using the private key d A , the operation result r+k of the validity judgment condition on r, the digital signature parameter r, and the elliptical curve parameter n.

3. The method according to claim 1 , wherein before the digital signature parameter s is generated, the method further comprises:
obtaining, by the digital signature generator, an operation result (r+k) mod n of the validity judgment condition on r to generate the digital signature parameter s using the private key d A , the operation result (r+k) mod n of the validity judgment condition on r, the digital signature parameter r, and the elliptical curve parameter n.

4. A digital signature generator, applied in a field of user identity authentication, the digital signature generator comprising a memory and a processor, the memory communicatively connected to the processor, wherein:
the memory stores instructions executable by the processor; and
the processor executes the instructions to obtain a hash value Z A and a message M to be signed;
perform a cascading operation on the hash value Z A , and the message M to be signed to generate M ;
perform a cryptographic hash operation on M to generate message digest information e;
generate a random number k in the range [1, n−1];
perform an elliptical curve point multiplication operation (x 1 , y 1 )=kG according to the random number k to obtain the abscissa x 1 of an elliptical curve point, wherein G represents an elliptical curve parameter;
convert the data type of the message digest information e into an integer type, and further convert the data type of the abscissa x 1 of the elliptical curve point into an integer type;
generate a digital signature parameter r using the message digest information e and abscissa x 1 of the elliptical curve point;
judge the validity of the digital signature parameter r; and
if the digital signature parameter r does not satisfy a validity judgment condition, then regenerates a random number k in the range [1, n−1]; obtain again an abscissa x 1 of an elliptical curve point using the random number k; converts the data type of the abscissa x 1 of the elliptical curve point, obtained again; regenerate a digital signature parameter r using the message digest information e and the abscissa x 1 of the elliptical curve point converted; and judges again the validity of the digital signature parameter r regenerated using the digital signature parameter r regenerated and the random number k regenerated;
wherein the processor is further configured to generate a digital signature parameters using a private key d A , the random number k, the digital signature parameter r, and an elliptical curve parameter n in the equation of: s=((1+d A ) −1 ·(r+k)−r)mod n;
the processor is further configured to judge whether the digital signature parameter s is 0; if the digital signature parameter s is 0, then regenerate a random number k in the range [1, n−1], and regenerate a digital signature parameter r, and if the digital signature parameter r regenerated satisfies the validity judgment condition, then regenerates a digital signature parameter s using the private key d A , the random number k regenerated in the range [1, n−1], the digital signature parameter r regenerated, and the elliptical curve parameter n;
the processor is further configured to convert the data type of the digital signature parameter r, and the digital signature parameter s which is not 0, finally generated into a string of bytes to obtain a digital signature (r, s); and
the processor configured to output the digital signature (r, s), so that the digital signature (r, s) can be used by a digital signature user to participate in the user identity authentication; wherein the digital signature user is a system or a device or a network node participating in the user identity authentication;
wherein the processor configured to generate the digital signature parameter s is configured to:
perform a large integer addition operation on the digital signature parameter r, and the random number k, and then perform an operation of a result (r+k) of the large integer addition operation modulo the elliptical curve parameter n, and to add 1 to the private key d A , and then calculate a modular inverse of (1+d A ) modulo the elliptical curve parameter n;

perform a large integer multiplication operation on a result of the large integer addition operation result modulo n, and a result of the modular inverse; and
perform an operation of a result of the large integer multiplication operation, after the digital signature parameter r being subtracted, modulo the ellipt

Assignees

• China Iwncomm Co Ltd

Inventors

• Li Zhiyong
• Wan Hongtao
• Yan Xiang

Classifications

• H04L9/3066

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title

• H04L9/0861

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title

• H04L9/3252 Primary

  using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes · CPC title