CN108173639A - A Two-Party Cooperative Signature Method Based on SM9 Signature Algorithm - Google Patents

Abstract

The invention discloses a two-party cooperative signature method based on the SM9 signature algorithm. This method is: KGC multiplies and splits the coefficient t ₂ of the user's private key ds _A , that is, t ₂ =(a ^‑1 )·(at ₂ ); takes a ^‑1 as the private key of signer A ₁ [at ₂ ]P ₁ as the private key of signer A ₂ A ₁ sends the encrypted r ₁ to A ₂ , and A ₂ encrypts r ₃ (r ₁ r ₂ ‑h) to obtain c ₃ , and calculates And send c ₃ and c ₄ to A ₁ , A ₁ gets s ₁ = r ₃ (r ₁ r ₂ ‑h) through decryption, but can’t get r ₂ and r ₃ , A ₁ calculates And verify whether (h, S) is a legal signature, if so, A ₁ and A ₂ signed successfully; otherwise, abort the signature.

Description

A Two-Party Cooperative Signature Method Based on SM9 Signature Algorithm

technical field

The invention belongs to the technical field of information security, and relates to a threshold signature (two-party cooperative signature) method, specifically a two-party cooperative signature method based on an SM9 signature algorithm, which can ensure the safety and overall efficiency of protocol execution.

Background technique

1. SM9 digital signature algorithm

A.Shamir proposed the concept of Identity-Based Cryptography in 1984. In the Identity-Based Cryptography System, the user's private key is calculated by the Key Generation Center (KGC) based on the master key and the user ID. The user's The public key is uniquely determined by the user ID, so the user does not need a third party to guarantee the authenticity of his public key. Compared with the certificate-based public key cryptosystem, the key management link in the identity cryptosystem can be appropriately simplified.

Elliptic curve pairs have the property of bilinearity, which establishes a connection between the cyclic subgroup of elliptic curves and the multiplicative cyclic subgroup of the extended field. In 1999, K.Ohgishi, R.Sakai, and M.Kasahara proposed in Japan an identity-based key sharing scheme using elliptic curve pairs (pairing); in 2001, D.Boneh and M.Franklin, and R.Sakai, K.Ohgishi and M.Kasahara et al independently proposed a public key encryption algorithm using elliptic curve pair construction. These works have led to new developments in identification cryptography. In 2016, my country released the SM9 identification cryptography algorithm implemented with elliptic curve pairs, including digital signature algorithms, key exchange protocols, key encapsulation mechanisms, and public key encryption algorithms.

The system parameters in the SM9 digital signature algorithm include: the parameters of the elliptic curve base domain F _q ; the parameters a and b of the elliptic curve equation; the prime factor N of the elliptic curve order and the cofactor cf relative to N; the elliptic curve E(F _q ) embedding number k with respect to N; elliptic curve Generator P ₁ of N-th order cyclic subgroup G ₁ (d ₁ divisible by k); elliptic curve The generator P ₂ of the Nth-order cyclic subgroup G ₂ (d ₂ divisible by k); the range of the bilinear pair e is the N-factorial cyclic group G _T . Use ID _A to represent the identity of user A, and M to represent the message to be signed, then the process for user A to generate a signature is as follows:

● Key generation phase

1) KGC generates a random number ks∈[1,N-1] as the signature master private key; calculates the element P _pub-s = [ks]P ₂ in G ₂ as the signature master public key;

2) KGC selects and discloses the signature private key generation function identifier hid identified by one byte;

3) KGC calculates t ₁ =H ₁ (ID _A ||hid,N)+ks on the finite field F _N , if t ₁ =0, regenerates the signature master private key, calculates and discloses the signature master public key, and Update the signature private key of an existing user; otherwise, calculate Then calculate ds _A =[t ₂ ]P ₁ as the user signature private key.

●Signature stage

4) Calculate the element g=e(P ₁ ,P _pub-s ) in the group _GT ;

5) Generate a random number r∈[1,N-1];

6) Calculate the element ω=g ^r in the group _GT ;

7) Calculate the integer h=H ₂ (M||ω,N);

8) Calculate the integer l=(r-h)modN, if l=0 then return 5);

9) Calculate the element S=[l]ds _A in the group _G1 ;

10) The signature of message M is (h, S).

Note 1: H _i (Z,n), i=1,2, is a cryptographic function given in SM9 (GM/T 0044.2-2016), the input is a bit string Z and an integer n, and the output is an integer h∈ [1,N-1].

Note 2: [u]P refers to u times of element P in additive groups G ₁ and G ₂ .

2. Signature of cooperation between the two parties

In the network environment, a large amount of information needs to be stored and transmitted. Digital signature technology is an information security technology to ensure the validity of information transmission and solve the contradictions between communicating parties. Two-party cooperative signature means that for a certain signature algorithm, its private key is split into two parts, which are kept secretly by two signers. Each signer can only generate part of the signature, which must be generated through interaction. The complete signature verified by the public key of the original signature algorithm. Therefore, the two-party cooperative signature is a special case of t=2, n=2 in the (t,n)-threshold signature.

As an important research content of threshold cryptography, threshold signature was first proposed by Desmedt et al. Afterwards, threshold signature algorithms based on RSA, ElGamal, Schnorr signature, DSA, etc. were proposed one after another. From the calculation structure of the signature, the signature can be divided into two categories, one is that there is only an addition operation between the random number and the private key. The other type is that the calculation process involves the inverse operation of the random number and the product operation between the random number and the private key. For example, in the examples given by MacKenzie and Reiter in the paper "Two-party generation of DSA Signatures", the algorithm proposed by Harn in the paper "Group-oriented(t,n) threshold digital signature scheme and digital multisignature" (referred to as Harn Algorithm) and DSA algorithm are described as representatives of these two types of signature algorithms. Assume that the public parameters of the signature algorithm are <g, p, q>, the public-private key pair is <y=g ^x modp, x>, the random number is k, and the message to be signed is m. In the Harn signature, it is necessary to calculate s←x(hash(m))-krmodq, where r=g ^k modp, and the final signature is: (r,s). In the DSA signature, it is necessary to calculate s←k ^-1 (hash(m)+xr)modq, where r=g ^k modp, and the final signature is: (rmodq,s). Judging from the current research situation at home and abroad, the threshold signature technology based on the first type of signature algorithm is relatively mature, but the threshold signature design based on the second type of signature algorithm is relatively difficult.

There are two reasons for the research on two-party cooperative signatures. One is due to the above-mentioned difficulties, that is, the design of threshold signatures based on the second type of signature algorithm is relatively difficult. Second, the two-party cooperative signature is suitable for private key protection in the mobile network environment. The server assists in storing part of the secret information and completes the digital signature with the mobile terminal, which can greatly reduce the damage caused by the mobile terminal being compromised. risk, the two-party cooperative signature algorithm with t=n=2 can take into account the requirements of mobile network environment on usability and private key confidentiality.

Lindell proposed a provably secure and efficient ECDSA-based two-party cooperative signature in the paper "Fast secure two-party ECDSA signing". Assuming that the order of the elliptic curve point cyclic group in ECDSA signature is q, G is its generator, and the public-private key pair is: (Q=x·G,x), the ECDSA signature process is as follows:

1) Select random number k←Z _q ;

2) Calculate R=k·G;

3) Calculate r=r _x modq, wherein, R=(r _x , r _y );

4) Calculate s=k ^-1 (hash(m)+rx) modq;

5) Output (r, s).

It can be seen that although the ECDSA signature algorithm involves the doubling operation on the elliptic curve in step 2), its final signature is essentially an arithmetic operation, that is, when calculating the signature in step 4), the r used is The abscissa of the point on the elliptic curve taken in step 3); and when the SM9 signature algorithm calculates the final signature in step 9), the ds _A used is the point on the elliptic curve, and the point multiplication operation on the elliptic curve is performed. For SM9, the signature form is the second type above, and the final signature involves the signature algorithm of doubling points on the elliptic curve. Therefore, there is no corresponding threshold signature or even two-party cooperative signature algorithm in the known methods. The present invention aims to provide a two-party cooperative signature method based on the SM9 signature algorithm.

Contents of the invention

Aiming at the technical problems existing in the prior art, the purpose of the present invention is to provide a two-party cooperative signature method based on the SM9 signature algorithm. In this algorithm, user A’s private key ds _A is split into two parts, which are kept by signers A ₁ and A ₂ respectively. Through interaction, A ₁ and A ₂ can complete the SM9 signature on behalf of user A. In order to highlight the key points of the present invention and the brevity of description, it is assumed that the two signers in this algorithm are semi-honest ("semi-honest" in the present invention means that the participating parties implement the agreement honestly, can record intermediate results and derive useful information, but cannot modify intermediate results). Under the malicious model, the signer can be forced to perform according to the agreement by means of "commitment input", "authenticated calculation", "zero-knowledge proof", because when it does not perform according to the agreement, it will be discovered by the other party, so that the other party The agreement may be terminated early.

Assuming that the message to be signed is M, a safe and efficient SM9 two-party cooperative signature algorithm, the steps include:

● Key generation phase

1) The key generation center KGC generates a random number ks∈[1,N-1] as the signature master private key; calculates the element P _pub-s in G ₂ =[ks]P ₂ as the signature master public key;

2) KGC selects and discloses the signature private key generation function identifier hid identified by one byte;

3) KGC calculates t ₁ =H ₁ (ID _A ||hid,N)+ks on the finite field F _N , if t ₁ =0, regenerates the signature master private key, calculates and discloses the signature master public key, and Update the signature private key of the existing user (that is, use the newly generated signature master private key to regenerate the signature private key of the existing user and send it to them); otherwise, calculate

4) KGC selects a random number a∈[1,N-1], calculates and send it to A ₁ , computing and send it to A ₂ .

●Signature stage

5) A ₁ and A ₂ respectively calculate the element g=e(P ₁ ,P _pub-s ) in the group _GT ;

6) A ₁ generates a random number r ₁ ∈ [1,N-1], and calculates the elements in the group G _T

7) A ₁ selects an additive homomorphic encryption algorithm whose public-private key pair is (pk,sk), uses this encryption algorithm to encrypt the random number r ₁ to obtain c ₁ , that is, calculate c ₁ =Enc _pk (r ₁ ), and send g ₁ and c ₁ to A ₂ ;

8) A ₂ generates random numbers r ₂ , r ₃ ∈ [1, N-1], and calculates the elements in the group G _T and send g ₂ to A ₁ ;

9) A ₁ calculates the elements in the group G _T A ₂ computes the elements in the group G _T

10) A ₁ and A ₂ respectively calculate the integer h=H ₂ (M||ω,N);

11) A ₂ uses the additive homomorphic encryption algorithm selected by A ₁ in 7) to encrypt the integer h to obtain c ₂ , that is, calculate c ₂ =Enc _pk (h); perform r ₃ (r ₁ r ₂ -h) Encrypt to obtain c ₃ , that is, c ₃ =Enc _pk (r ₃ (r ₁ r ₂ -h))=r ₃ (r ₂ c ₁ -c ₂ ). And, calculate Send c ₃ and c ₄ to A ₁ ; (Note: c ₄ here is not the ciphertext, but to maintain the consistency of symbols).

12) A ₁ uses the private key sk of the additive homomorphic encryption algorithm selected in 7) to decrypt c ₃ to obtain:

s ₁ = Dec _sk (c ₃ ) = Dec _sk Enc _pk (r ₃ (r ₁ r ₂ -h)) = r ₃ (r ₁ r ₂ -h),

then calculate

13) A ₁ uses the SM9 verification algorithm to verify whether (h, S) is a legal signature, and if so, publish the signature; otherwise, terminate the agreement.

The two-party cooperative signature algorithm in the present invention can be seen from the execution process of the agreement, and the result is correct; and the method based on simulation can prove that the algorithm is safe (the private information of both parties is not disclosed during the agreement execution process) . In practical applications, the key generation stage only needs to be executed once, and then the two signers can sign any message that needs to be signed according to the agreement in the signature stage.

Compared with prior art, positive effect of the present invention is:

Aiming at the signature algorithm whose signature form is the above-mentioned second type, and the final signature involves point doubling operation on the elliptic curve, the present invention provides a two-party cooperative signature method for the first time. Its innovations are:

(1) In step 4) of the key generation stage, the private key of user A is divided into two parts by multiplication. The splitting technique is to multiply and split the coefficient t ₂ of user A’s private key ds _A in the original algorithm, that is, t ₂ =(a ^-1 )·(at ₂ ); and keep the point P ₁ on the elliptic curve constant. And take a ^-1 as the private key of signer A ₁ [at ₂ ]P ₁ as the private key of signer A ₂

(2) In step 7) and step 11) of the signature phase, A ₁ sends the encrypted r ₁ , that is, c ₁ to A ₂ , and A ₂ utilizes the property of additive homomorphic encryption, without knowing r ₁ , It is possible to encrypt r ₃ (r ₁ r ₂ -h), and send the encrypted result c ₂ to A ₁ , and A ₁ can get r ₃ (r ₁ r ₂ -h) through decryption, but not r ₂ and r ₃ . That is to say, using additive homomorphic encryption, the necessary calculations are completed while protecting the private information of both parties in the protocol.

(3) Step 11) of the signature stage, by calculating Using the difficult problem of elliptic curve discrete logarithms, the protection privacy.

Compared with the original SM9 signature algorithm, the two-party cooperative signature algorithm provided by the present invention has an additional selection of an additive homomorphic encryption scheme, three addition and decryption operations and three multiplication operations in the signature stage. Compared with Lindell's ECDSA-based two-party cooperative signature, there is only one more encryption operation for each signature. However, it should be noted that the SM9 signature algorithm itself involves more complex operations than ECDSA.

Description of drawings

Fig. 1 is a schematic diagram of an example of the signature phase of the present invention.

Detailed ways

In order to make the above objects, features and advantages of the present invention more obvious and understandable, the present invention will be further described below through specific embodiments and accompanying drawings.

The application modes of the present invention can be divided into two categories. One type is used for power distribution, at this time, the user ID refers to the ID of a company, group or organization. The signature issued in the name of a company, group or organization requires the cooperation of two signers, that is, the user's private key corresponding to the user ID is split into two parts, which are held by the two signers respectively, to avoid potential problems caused by power concentration. corruption etc. The other type is used for private key protection. At this time, the user ID refers to the ID of a single user, but the private key is split into two parts and stored in different devices. Both devices need to be online at the same time to complete the signature operate. The following uses the first type of application mode as an example for description.

In the actual application process, assuming that the identity of company A is ID _A , the signature issued in the name of the company needs to be completed by two signers A ₁ and A ₂ , assuming that A ₁ and A ₂ already have their own private keys and Then the signing process is as follows:

1) A ₁ and A ₂ respectively calculate the element g=e(P ₁ ,P _pub-s ) in the group _GT ;

2) A ₁ generates a random number r ₁ ∈ [1,N-1], and calculates the elements in the group G _T

3) A ₁ selects the Paillier encryption scheme (N _PE , p _PE , q _PE ), the public key is pk=N _PE , the private key is sk=(p _PE ,q _PE ), and the calculation c ₁ =Enc _pk (r ₁ ) , and send g ₁ and c ₁ to A ₂ ;

4) A ₂ generates random numbers r ₂ , r ₃ ∈ [1, N-1], and calculates the elements in the group G _T and send g ₂ to A ₁ ;

5) A ₁ calculates the elements in the group G _T A ₂ computes the elements in the group G _T

6) A ₁ and A ₂ respectively calculate the integer h=H ₂ (M||ω,N);

7) A ₂ calculates c ₂ =Enc _pk (h), c ₃ =Enc _pk (r ₃ (r ₁ r ₂ -h)) = r ₃ (r ₂ c ₁ -c ₂ ), and send _c3 and _c4 to _A1 ;

8) A ₁ decrypts c ₃ to get s ₁ = Dec _sk (c ₃ ) = Dec _sk Enc _pk (r ₃ (r ₁ r ₂ -h)) = r ₃ (r ₁ r ₂ -h), calculate

9) A ₁ uses the SM9 verification algorithm to verify whether (h, S) is a legal signature, and if so, publish the signature; otherwise, terminate the agreement.

In this algorithm, compared with the original SM9 signature algorithm, the signature stage has one more selection of Paillier homomorphic encryption scheme, three encryption and decryption operations and three multiplication operations. Compared with Lindell's two-party cooperative signature based on ECDSA, this algorithm only needs one more encryption operation for each signature. However, because the SM9 signature algorithm itself involves more complex operations than ECDSA, there is only one more encryption operation, and Under the condition that the encryption operation can be implemented quickly, the two-party cooperative signature with the same security can be realized. It can be considered that the algorithm in the present invention and the ECDSA two-party cooperative signature are equally safe and efficient.

The above embodiments are only used to illustrate the technical solution of the present invention and not to limit it. Those of ordinary skill in the art can modify or equivalently replace the technical solution of the present invention without departing from the spirit and scope of the present invention. The scope of protection should be determined by the claims.

Claims (7)

1. A two-party cooperative signature method based on the SM9 signature algorithm, characterized in that: 1) Key generation phase The key generation center KGC generates the signature master private key ks and the signature master public key P _pub-s ; then selects and discloses the signature private key generation function identifier hid; The key generation center KGC calculates t ₁ =H ₁ (ID _A ||hid,N)+ks on the finite field F _N , Among them, ID _A represents the identity of user A, N is the prime factor of the elliptic curve order in the SM9 digital signature algorithm, H _i (Z, n) is a cryptographic function given in the SM9 signature algorithm, i=1 or 2, The input is a bit string Z and an integer n; The key generation center KGC selects a random number a, and calculates and send it to signer A ₁ , computing And send it to the signer A ₂ ; P ₁ is the generator of the N-order cyclic subgroup G ₁ , and P ₂ is the generator of the N-order cyclic subgroup G ₂ ; 2) Signature stage The signer A ₁ and the signer A ₂ respectively calculate the element g=e(P ₁ ,P _pub-s ) in the group G _T ; G _T is the value range of the bilinear pair e, which is a cyclic group of N factorial method; The signer A ₁ generates a random number r ₁ and calculates the elements in the group G _T Then signer A ₁ encrypts r ₁ to get c ₁ , and sends g ₁ and c ₁ to signer A ₂ ; Signer A ₂ generates random numbers r ₂ , r ₃ ; calculates the elements in group G _T and send g ₂ to signer A ₁ ; Signer A ₁ computes elements in group G _T Signer A ₂ computes elements in group G _T Signers A ₁ and A ₂ respectively calculate the integer h=H ₂ (M||ω,N); Signer A ₂ encrypts r ₃ (r ₁ r ₂ -h) to obtain c ₃ , and calculates and send _c3 and _c4 to _A1 ; Signer A ₁ decrypts c ₃ to get s ₁ =r ₃ (r ₁ r ₂ -h), calculate Signer A ₁ uses the SM9 verification algorithm to verify whether (h, S) is a legal signature, and if so, signer A ₁ and signer A ₂ cooperate to sign successfully; otherwise, abort the signature. 2. The method according to claim 1, characterized in that, the signature master private key ks∈[1,N-1], the signature master public key P _pub-s =[ks]P ₂ . 3. The method according to claim 1, characterized in that P ₁ is an elliptic curve The generator of the N-th order cyclic subgroup G ₁ , d ₁ divides k; P ₂ is an elliptic curve The generator of the N-order cyclic subgroup G ₂ of , d ₂ divides k; k is the embedding number of the elliptic curve E(F _q ) relative to N. 4. The method according to claim 1, wherein, in the key generation stage, the key generation center KGC calculates t ₁ =H ₁ (ID _A ||hid, N)+ks on the finite field F _N ; if t ₁ = 0, then regenerate the signature master private key, calculate and publish the signature master public key, and update the signature private key of the existing signer; otherwise, calculate 5. The method according to claim 1, wherein the encryption algorithm is an additive homomorphic encryption algorithm in which a public-private key pair is (pk, sk). 6. The method according to claim 1 or 5, wherein the encryption algorithm is a Paillier encryption algorithm. 7. The method according to claim 1, characterized in that, random number r ₁ ∈ [1, N-1], random number r ₂ , r ₃ ∈ [1, N-1], random number a ∈ [1 ,N-1].