CN100440776C - Elliptic Curve Signature and Verification Signature Method and Device - Google Patents

Abstract

The invention is an elliptic curve signature method. The sender discloses the system parameters and its public key Y _A , then generates a random number k, and performs elliptic curve point multiplication operation on k and the base point G of the curve to obtain the point kG on the curve, and uses the function d to combine the obtained point kG with the plaintext m operation, get r=d(m, kG); function f ₀ , f ₁ , g ₀ , g ₁ are all functions of r, use function f ₀ , f ₁ , g ₀ , g ₁ and random number and private Key x _A solves the equation f ₀ (r)+f ₁ (r)s=kx _A (g ₀ (r)+g ₁ (r)s) to get s=(kx _A g ₀ (r)-f ₀ ( r))(f ₁ (r)+x _A g ₁ (r)) ^-1 ; the receiver uses the sender's public key Y _A , elliptic curve base point G and functions f ₀ , f ₁ , g ₀ , g ₁ Calculate P=(f ₀ (r)+f ₁ (r)s)G+(g ₀ (r)+g ₁ (r)s)Y _A , use the function d' to calculate m'=d'(r, P ); compare the calculated m' with the received m; wherein the above-mentioned function d and function d' must have the following properties: if the function d is D=d(x, y), it can be deduced from the function that d Obtain y=d'(x, D). The invention can shorten the length of the signature with the same security strength and speed up the signature speed.

Description

Elliptic Curve Signature and Verification Signature Method and Device

technical field

The invention relates to a data signature and a verification signature, which is a signature and a verification signature method using the discrete logarithm problem of an elliptic curve.

Background technique

Cryptographic systems are divided into symmetric cryptosystems and asymmetric cryptosystems.

Symmetric ciphers are sometimes called traditional cipher algorithms, that is, the encryption key can be deduced from the decryption key, and vice versa. In most algorithms, the encryption/decryption key is the same. These algorithms, also called secret-key algorithms or single-key algorithms, require the sender and receiver to agree on a key before communicating securely. The security of symmetric cryptography depends on the key, and leaking the key means that anyone can encrypt/decrypt messages. Therefore, although the speed of symmetric encryption is very fast, how to securely distribute the key to legitimate users is a problem.

In the patent "cryptographic equipment and method" ("CRYPTOGRAPHIC APPARATUS METHOD", patent number: US4200770), a method and equipment that can exchange keys in an open channel are given. This method is called public key exchange or Diffie- Hellman key exchange method. The patent enables communicating parties to negotiate and transfer their secret information using a modular exponentiation function. If an attacker wants to obtain the secret information passed, he must solve the discrete logarithm problem. Solving the discrete logarithm problem is an intractable problem if the parameters used are large enough.

Public key cryptography, also known as asymmetric cryptography, can effectively solve the above authentication problems. Public-key cryptography is different from symmetric cryptography that uses only one key. Public-key cryptography is asymmetric. It uses two independent but mathematically related keys: a public key and a private key. In this way, the receiver in the communication keeps its private key secret and discloses its public key. The most important progress in public key cryptography is digital signature, which can effectively solve the above-mentioned identity verification problems by implementing digital signature through public key cryptography. Before user A sends information to B, he uses his own private key to digitally sign the information. After receiving the information sent by A, user B uses A's public key to verify A's signature, because only A has its private key. , which ensures that the information received by B is indeed from A and has not been tampered with, and also confirms A's identity.

The patent "CRYPTOGRAPHIC COMMUNICATIONS SYSTEM AND METHOD" ("CRYPTOGRAPHIC COMMUNICATIONS SYSTEM AND METHOD", patent number: US4405829) proposes a public key encryption method invented by Rivest, Shamir and Adleman - RSA. The security of the RSA public key cryptography method is based on the intractability of the factorization problem of large integers. However, with the continuous improvement of the current security requirements, the requirements for the length of the RSA key are also getting higher and higher.

Taher ElGamal proposed a public key digital signature mechanism based on Euler's algorithm. In this mechanism, the sender A uses a modular exponentiation function to hide the private key x, calculates y=g ^x mod p, and makes the public key y public. Receiver B uses the private key to sign, and B uses A's public key to verify the signature. The specific algorithm is as follows:

1. Preprocessing process: obtaining the parameters required for the signature

1.1: Determine the finite field GF(p), that is, determine the prime number p;

1.2: Determine the generator g;

1.3: Select a random number x _A so that 1≤x _A ≤p-1, and use x _A as the signature key, that is, the private key;

1.4: Calculation ${\mathrm{the\; y}}_A=g^{x_A},$ y _A is used as the public key to verify the signature;

1.6: Public parameters g, p, and public key y _A .

2. Signature process:

2.1: The sender publicizes parameters g, p, and public key y _A ;

2.2: Generate a random number k, where 1≤k≤p-1, and use the modular exponentiation function to calculate r=g ^k ;

2.3: Calculation for plaintext m: s=k ^-1 (m-xr) mod p;

2.4: The (r, s) obtained above is the signature of the sender on the plaintext m, and the sender sends (r, s) and the plaintext m to the receiver.

3. Verification process:

3.1: Receiver B receives plaintext m and its signature (r, s);

3.2: According to the known parameters p, g and the public key y A of _A , judge whether y _A ^r r ^s mod p is equal to g ^m mod p, if yes, the verification passes, otherwise, the verification fails

4. End.

This method is subsequently referred to as Digital Signature Algorithm (DSA).

The mathematical basis related to the ElGamal digital signature mechanism is quite complicated, and the signature length is quite long. In the US patent "Method for Identifying Subscribers and for Generating and Verifying Electronic Signatures in a Data Exchange System" ("Method for Identifying Subscribers and for Generating and Verifying Electronic Signatures in a Data Exchange System" Patent No. US4,995,082), a security The method of generating shorter digital signatures is based on other mathematical methods with lower complexity.

In the US patent "Digital Signature Algorithm" ("Digital Signature Algorithm" Patent No. US5,231,668), the length of the ElGamal digital signature is shortened while maintaining the same mathematical complexity.

Subsequently, Rueppel of Switzerland and Nyberg of Australia obtained the patent "Digital Signature Method and Key Agreement Method" ("Digital Signature Method and KeyAgreement Method" Patent No. US5,600,725) in the United States. Fast speed and message recovery function. The specific signature verification process is as follows:

1. Preprocessing process: obtaining the parameters required for the signature

1.1: Determine the finite field GF(p);

1.2: Determine the generator g;

1.3: Select a random number x _A so that 1≤x _A ≤p-1, and use x _A as the user's private key;

1.4: Calculation ${\mathrm{the\; y}}_A=g^{x_A}\mathrm{mod}p,$ y _A is used as the user public key;

1.6: Publicly g, p and public key y _A .

2. Signature process:

2.1: Obtain the signature message m;

2.2: The signer generates a random number k, where 1≤k≤p-1, and uses the modular exponentiation function to calculate r=mg ^-k mod p;

2.3: Calculate s=k-xr mod p;

2.4: The signer sends the message m and its signature (r, s) to the receiver.

3. Verification process:

3.1: The receiver receives the message m and its signature (r, s);

3.2: According to the known parameters p, g, y _A , judge whether g ^s y _A ^r mod p is equal to m(modp), if they are equal, the verification passes, otherwise, the verification fails;

4. End.

In 1985, Neal Koblitz and Victor Miller respectively proposed the use of elliptic curves for public key cryptosystems, and implemented existing public key cryptographic algorithms with elliptic curves. The cryptographic algorithm based on the insolvability of the discrete logarithm problem of elliptic curves is called Elliptic Curve Cryptography (ECC for short), and has become a public key cryptographic algorithm widely accepted by the international cryptographic community.

Subsequently, the DSA signature mechanism and NR signature mechanism mentioned above were transplanted to the elliptic curve one after another, becoming the ECDSA signature algorithm and the ECNR signature algorithm, which made the mathematical problem on which the signature mechanism is based improved from the discrete logarithm problem to Intractability of discrete logarithm problems based on elliptic curves.

Contents of the invention

The purpose of the present invention is to propose a new elliptic curve signature method. The signature method is based on the elliptic curve discrete logarithm problem, which has higher complexity in mathematics, so it has the characteristics of higher unit security strength, that is, it can greatly shorten the length of digital signatures with the same security strength and speed up the signature. , so that it can better meet the needs of restricted environments such as mobile communications; and the signature algorithm can construct a more efficient algorithm than the application of the DSA digital signature algorithm on the elliptic curve through the selection of parameters. ECDSA elliptic curve digital signature algorithm can also make This algorithm has the function of message recovery, so that users can perform signature verification even if they do not deliver signed messages.

The invention provides a method for signature and signature verification. The system first determines the finite field GF(q), selects the elliptic curve equation E; selects the base point G of the elliptic curve, and calculates the order N of the elliptic curve point group on the finite field. The sender A, as the signer, uses these system parameters to generate its own private key x _A , where 1≤x _A ≤N-1, and then uses the base point G to calculate the point product to obtain the point Y _A = x _A G on the elliptic curve as the public key key. The steps of sender A’s signature process for plaintext m are as follows:

First, the sender A discloses the system parameters and its public key Y _A , and then generates a random number k so that k falls on the interval [1, N-1], and performs elliptic curve point multiplication between k and the base point G of the curve to obtain The point kG on the curve; use the function d to calculate the obtained point kG and the plaintext m, where it is guaranteed that the value of k cannot be obtained from d, and r=d(m, kG) is obtained. Functions f ₀ , f ₁ , g ₀ , g ₁ are all functions of r, use functions f ₀ , f ₁ , g ₀ , g ₁ and random numbers and private key x _A to solve equation f ₀ (r)+f ₁ ( r)s=kx _A (g ₀ (r)+g ₁ (r)s) to solve s=(kx _A g ₀ (r)-f ₀ (r))(f ₁ (r)+x _A g ₁ (r)) ^-1 , the obtained (r, s) is A's signature on the plaintext m. Sender A sends plaintext m and its signature (r, s) to B.

Receiver B receives the plaintext m and its signature (r, s), first uses the public key Y _A , the elliptic curve base point G and the functions f ₀ , f ₁ , g ₀ , g ₁ to calculate P=(f ₀ (r) +f ₁ (r)s)G+(g ₀ (r)+g ₁ (r)s)Y _A , using function d' to calculate m'=d'(r,P). Compare the calculated m' with the received m. If they are the same, the signature is legal. At the same time, m' is the plaintext recovered from the signature result. If they are different, the signature is illegal.

Wherein the above-mentioned function d and function d' must have the following properties: let the function d form be D=d(x, y), can deduce y=d'(x, D) from function d, the function d obtained like this can be Effectively hide the plaintext information and random number information in the above-mentioned signature and verification process; the function d' can recover the hidden plaintext information in the above-mentioned verification process.

According to another aspect of the present invention, there is provided a device for signing and verifying signatures using the elliptic curve signature and verifying signature method;

Description of drawings

Fig. 1 is a flowchart of the signature process of the present invention.

Fig. 2 is a flow chart of the verification signature process of the present invention.

Fig. 3 is a block diagram of the signing and verifying signature apparatus of the present invention.

Detailed ways

Fig. 1 shows a flowchart of the signature process of the present invention.

In step 101, receiver A discloses its public key Y _A and system parameters: curve E, base point G of elliptic curve point group, order N of elliptic curve point group;

In step 102, receiver A generates a random number k, where 1≤k≤N-1, where N is the order of the point group of the elliptic curve;

In step 103, k and the base point G are used for the point product operation of the elliptic curve to obtain the point kG on the curve;

In step 104, the plaintext m is obtained. When the length of the actual message is longer than the length of the message that can be signed, the message m can be replaced by the result of the Hash function h(m), that is, the private key is used to sign the Hash value h(m) of the message m; during verification, the The received message m first Hash to get h(m), and then use h(m) to verify the signature;

In step 105, the plaintext m and kG acquired in step 104 are calculated by using the function d to obtain r=d(m, kG). Among them, the function d must have the following properties: let the d function form be D=d(x, y), the function d' can be deduced from the function d, and there is y=d'(x, D), and the d function obtained in this way can be obtained in Effectively hide plaintext information and random number information in the above-mentioned signature and verification process; the d' function can recover and obtain hidden plaintext information in the following verification process step 204;

In step 106, the plaintext m and P acquired in step 104 are calculated by using the function d to obtain r=d(m, P). Use r's functions f ₀ , f ₁ , g ₀ , g ₁ and random numbers and private key x _A to solve the equation f ₀ (r)+f ₁ (r)s=kx _A (g ₀ (r)+g ₁ ( r)s) get s=(kx _A g ₀ (r)-f ₀ (r))

(f ₁ (r)+x _A g ₁ (r)) ^-1 ,

In step 107, before sending the signature result, it must be judged whether the obtained signature r and s are zero, if they are zero, then it is necessary to skip to step 102, re-select the random number k, and re-sign the plaintext m;

In step 108, when the r and s obtained in step 107 are not zero, then the signature result (r, s) of A on the plaintext m is obtained. Sender A sends plaintext m and its signature (r, s) to B.

At this point, the signing process is over.

Fig. 2 shows a flowchart of the verification signature process of the present invention.

In step 201, receiver B receives plaintext m and signature (r, s) sent by A;

In step 202, B obtains system parameters and A's public key Y _A ;

In step 203, _B calculates P=(f ₀ ( _{r )} +f _{1 (} r)s)G+( _{g 0} (r)+g ₁ (r)s) Y _A ;

In step 204, B uses the function d' to calculate m'=d'(r, P);

In step 205, B compares the m' obtained in step 204 with the received m, if they are equal, then go to step 206, if not equal, then go to step 207;

In step 206, m' is equal to the received m, the verification is passed, and the signature is legal;

In step 206, m' is not equal to the received m, and the signature is invalid.

At this point, the signature verification process is over.

In step 104, when the length of the actual message is longer than the length of the message that can be signed, the message m can be replaced with the result of the Hash function h (m), that is, the Hash value h (m) of the message m is signed; in the verification step 201 In this method, the received message m is first processed using the Hash function to obtain h(m), and then the signature is verified for h(m).

If the padding information is embedded in the signed message m, the message m may not be sent when the signature is sent, but only the signature (r, s) is sent; during verification, the message m is recovered using the signature (r, s) , and then use the padding (Padding) information to verify the authenticity and integrity of the signature.

Function d in step 105 and the function d' of step 204 must have the following properties: let d function shape be D=d(x, y), can deduce y=d'(x, D) from function d, like this The obtained d function can effectively hide plaintext information and random number information in the above-mentioned signature and verification process; the d' function can recover and obtain hidden plaintext information in the above-mentioned verification process. d and d' can contain the following forms:

a) d(m, kG) can be taken as: d(m, kG)=m(kG) _x =r, then $d^{,}(r,P)=r{P}_x^{-1}=m,$ Wherein (kG) _X and P _X refer to the abscissas of points kG and P respectively;

b) d(m, kG) can take the value: d(m, kG) = m(kG) _y = r, then $d^{,}(r,P)=r{P}_{\mathrm{the\; y}}^{-1}=m,$ Wherein (kG) _x and P _x refer to the vertical coordinates of points kG and P respectively;

运算也可以使用

运算来代替；c)d(m, kG) can take the following values: $d(m,\mathrm{kG})=m\⊕{\left(\mathrm{kG}\right)}_x=r,$ but $d^{,}(r,P)=m,$ in

Operations can also use

operation instead of

运算也可以使用

运算来代替；d) d(m, kG) can take the following values: $d(m,\mathrm{kG})=m\⊕{\left(\mathrm{kG}\right)}_{\mathrm{the\; y}}=r,$ but $d^{,}(r,P)=r\⊕P_{\mathrm{the\; y}}=m,$ in

Operations can also use

operation instead of

e) d(m, kG) can be taken as: d(m, kG)=(m+(kG) _x ) mod N=r, then d'(r, P)=(rP _x ) mod N=m, Where N is the order of point G in the elliptic curve point group;

f) d(m, kG) can take the value of a symmetric encryption function with m as the plaintext and kG as the key, and d'(r, P) can take the value of the corresponding r as the ciphertext and P as the key The symmetric decryption function;

g) and so on.

The functions f ₀ , f ₁ , g ₀ , and g ₁ in step 106 and step 203 are all linear functions of r. In order to obtain higher calculation efficiency, the following simple functions of r can be taken:

h) The functions f ₀ , f ₁ , g ₀ , and g ₁ can respectively take the values of f ₀ (r)=c ₀ *r, f ₁ (r)=c ₁ , g ₀ (r)=c ₂ , g ₁ (r)=c ₀ *r, where c ₀ , c ₁ , and c ₂ are constants and the functions f ₀ , f ₁ , g ₀ , and g ₁ are interchangeable;

i) The functions f ₀ , f ₁ , g ₀ , and g ₁ can take the values of f ₀ (r)=c ₁ , f ₁ (r)=c ₂ , g ₀ (r)=c ₀ *r, g ₁ (r)=c ₃ , where c ₀ , c ₁ , c ₂ , and c ₃ are constants and the functions f ₀ , f ₁ , g ₀ , and g ₁ are interchangeable;

j) and so on.

Fig. 3 shows the signing and verifying signature apparatus of the present invention. When the sender A and the receiver B communicate on a communication channel, the sender A uses the key generation device 340 to generate a key pair: public key Y _A and private key x _A , and publish its public key and system parameters. A uses the signer 320 to sign the plaintext m in conjunction with the signature process described in FIG. 1 , and sends the plaintext m and the signature result S to B.

The recipient B receives the plaintext m and the signature result S, obtains the system parameters and the public key Y _A of A, uses the verification signer 350, and obtains the verification result by verifying the signature result S of the plaintext m as described in Fig. 2 .

The present invention has been described above in conjunction with the preferred embodiments of the present invention, and those skilled in the art can make various modifications and changes to it without departing from the scope of the present invention.

Claims (32)

1. ellipse curve signature and certifying signature method, it is right that wherein transmit leg has oneself key: private key x _AWith PKI Y _A, and public address system parameter and PKI Y _A, transmit leg uses the private key x of oneself _APlaintext m is realized digital signature, and plaintext m and signature are sent to the recipient, the recipient uses the PKI Y of transmit leg _AVerify that whether transmit leg is legal to the signature of plaintext m, comprises following steps:

Open system parameters of transmit leg and PKI Y thereof _A, generate random number k then, make k drop on the interval [1, N-1], wherein N is the some order of a group of elliptic curve, and the basic point G of k and curve is carried out the elliptic curve point multiplication operation, obtains the some kG on the curve; Use some kG that function d will obtain and expressly m carry out computing, wherein guarantee from d, to obtain the value of k, obtain r=d (m, kG); Function f ₀, f ₁, g ₀, g ₁Be all the function of r, use function f ₀, f ₁, g ₀, g ₁With random number and private key x _ASolving equation f ₀(r)+f ₁(r) s=k-x _A(g ₀(r)+g ₁(r) s) solve s=(k-x _Ag ₀(r)-f ₀(r)) (f ₁(r)+x _Ag ₁(r)) ^-1, obtain like this (r s) is the signature of transmit leg to plaintext m; (r s) sends to the recipient to transmit leg with its signature with plaintext m;

The recipient receives expressly m and transmit leg, and (r s), at first uses the PKI Y of transmit leg to the signature of m _A, elliptic curve basic point G and function f ₀, f ₁, g ₀, g ₁Calculate P=(f ₀(r)+f ₁(r) G+ (g s) ₀(r)+g ₁(r) Y s) _A, use function d ' and calculating m '=d ' (r, P); M ' that calculates and the m that receives are compared, if identical then sign legally, simultaneously m ' recovers the plaintext that obtains from the signature result, if difference then sign illegal;

Wherein above-mentioned function d and function d ' must have following character: establish function d shape and be D=d (x, y), from function d push away y=d ' (x, D).

2. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein when the length of real messages m was longer than the message-length that can sign, message m was replaced with the result of Hash function h (m), promptly used private key that the hash value h (m) of message m is signed; When checking, the Hash of message m elder generation that receives is obtained h (m), re-use h (m) certifying signature.

3. ellipse curve signature as claimed in claim 1 and certifying signature method wherein, if embed filling information in the message m of signature, then do not send message m when sending signature, and only send signature (r, s); When checking, (r s) recovers message m, utilizes the authenticity and integrity of filling information certifying signature then to utilize signature.

4. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' must have following character: establishing d function shape is D=d (x, y), from function d push away y=d ' (x, D), the d function that obtains is so effectively hidden cleartext information and random number information in above-mentioned signature and proof procedure; D ' function recovers the cleartext information that obtains hiding in above-mentioned proof procedure.

5. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' be taken as: when d (m, kG) value be d (m, kG)=m (kG) _xDuring=r, then $d^{,}(r,P)=r{P}_x^{-1}=m,$ Wherein (kG) _xAnd P _xRefer to the abscissa of getting a kG and P respectively.

6. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' be taken as: when d (m, kG) value be d (m, kG)=m (kG) _yDuring=r, then $d^{,}(r,P)=r{P}_y^{-1}=m,$ Wherein (kG) _xAnd P _xRefer to the ordinate of getting a kG and P respectively.

7. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m\⊕{\left(\mathrm{kG}\right)}_x=r$ The time, then $d^{,}(r,P)=r\⊕P_x=m.$

8. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m{\⊗\left(\mathrm{kG}\right)}_x=r$ The time, then $d^{,}(r,P)=r\⊗P_x=m.$

9. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m\⊕{\left(\mathrm{kG}\right)}_y=r$ The time, then $d^{,}(r,P)=r\⊕P_v=m.$

10. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m{\⊗\left(\mathrm{kG}\right)}_y=r$ The time, then $d^{,}(r,P)=r\⊗P_y=m.$

11. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function d and function d ' be taken as: when d (m, kG) value is for being expressly with m, when kG is the symmetric cryptography function of key, d ' (r, P) value is for being ciphertext accordingly with r, P is the symmetrical decryption function of key.

12. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function f ₀, f ₁, g ₀, g ₁Be the linear function of r.

13. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function f ₀, f ₁, g ₀, g ₁Be taken as: f ₀(r)=c ₀* r, f ₁(r)=c ₁, g ₀(r)=c ₂, g ₁(r)=c ₀* r, wherein c ₀, c ₁, c ₂Be constant.

14. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function f ₀, f ₁, g ₀, g ₁Be taken as: f ₁(r)=c ₀* r, f ₀(r)=c ₁, g ₁(r)=c ₂, g ₀(r)=c ₀* r, wherein c ₀, c ₁, c ₂Be constant.

15. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function f ₀, f ₁, g ₀, g ₁Value is f respectively ₀(r)=c ₁, f ₁(r)=c ₂, g ₀(r)=c ₀* r, g ₁(r)=c ₃, c wherein ₀, c ₁, c ₂, c ₃Be constant.

16. ellipse curve signature as claimed in claim 1 and certifying signature method, wherein function f ₀, f ₁, g ₀, g ₁Value is f respectively ₁(r)=c ₁, f ₀(r)=c ₂, g ₁(r)=c ₀* r, g ₀(r)=c ₃, c wherein ₀, c ₁, c ₂, c ₃Be constant.

17. ellipse curve signature and certifying signature system comprise key generating device (340), signature device (320) and certifying signature device (350), and it is right that wherein the transmit leg of this system uses described key generating device (340) generation key: private key x _AWith PKI Y _A, and public address system parameter and PKI Y _A, and use described signature device (320) to utilize the private key x of oneself _APlaintext m is realized digital signature, and wherein said signature device (320) is carried out:

Open system parameters and PKI Y thereof _A, generate random number k then, make k drop on the interval [1, N-1], wherein N is the some order of a group of elliptic curve, and the basic point G of k and curve is carried out the elliptic curve point multiplication operation, obtains the some kG on the curve; Use some kG that function d will obtain and expressly m carry out computing, wherein guarantee from d, to obtain the value of k, obtain r=d (m, kG); Function f ₀, f ₁, g ₀, g ₁Be all the function of r, use function f ₀, f ₁, g ₀, g ₁With random number and private key x _ASolving equation f ₀(r)+f ₁(r) s=k-x _A(g ₀(r)+g ₁(r) s) solve s=(k-x _Ag ₀(r)-f ₀(r)) (f ₁(r)+x _Ag ₁(r)) ^-1, obtain like this (r s) is the signature of transmit leg to plaintext m; (r s) sends to the recipient to transmit leg with its signature with plaintext m;

Described certifying signature device (350) is carried out:

(r s), at first uses the PKI Y of transmit leg to the signature of m to receive expressly m and transmit leg _A, elliptic curve basic point G and function f ₀, f ₁, g ₀, g ₁Calculate P=(f ₀(r)+f ₁(r) G+ (g s) ₀(r)+g ₁(r) Y s) _A, use function d ' and calculating m '=d ' (r, P); M ' that calculates and the m that receives are compared, if identical then sign legally, simultaneously m ' recovers the plaintext that obtains from the signature result, if difference then sign illegal;

Wherein above-mentioned function d and function d ' must have following character: establish function d shape and be D=d (x, y), from function d push away y=d ' (x, D).

18. ellipse curve signature and certifying signature system as claim 17, wherein when the length of real messages m is grown than the message-length that can sign, the signature device replaces with the result of Hash function h (m) with message m, promptly uses private key that the hash value h (m) of message m is signed; When checking, the certifying signature device obtains h (m) with the Hash of message m elder generation that receives, and re-uses h (m) certifying signature.

19. as the ellipse curve signature and the certifying signature system of claim 17, wherein,, then when sending signature, do not send message m if in the message m of signature, embed filling information, and only send signature (r, s); When checking, (r s) recovers message m, utilizes the authenticity and integrity of filling information certifying signature then to utilize signature.

20. ellipse curve signature and certifying signature system as claim 17, wherein function d and function d ' must have following character: establishing d function shape is D=d (x, y), from function d push away y=d ' (x, D), the d function that obtains is so effectively hidden cleartext information and random number information in above-mentioned signature and proof procedure; D ' function recovers the cleartext information that obtains hiding in above-mentioned proof procedure.

21. as the ellipse curve signature and the certifying signature system of claim 17, wherein function d and function d ' be taken as: when d (m, kG) value be d (m, kG)=m (kG) _xDuring=r, then $d^{,}(r,P)=r{P}_x^{-1}=m,$ Wherein (kG) _xAnd P _xRefer to the abscissa of getting a kG and P respectively.

22. as the ellipse curve signature and the certifying signature system of claim 17, wherein function d and function d ' be taken as: when d (m, kG) value be d (m, kG)=m (kG) _yDuring=r, then $d^{,}(r,P)=r{P}_y^{-1}=m,$ Wherein (kG) _xAnd P _xRefer to the ordinate of getting a kG and P respectively.

23. as the ellipse curve signature and the certifying signature system of claim 17, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m\⊕{\left(\mathrm{kG}\right)}_x=r$ The time, then $d^{,}(r,P)=r\⊕P_x=m.$

24. as the ellipse curve signature and the certifying signature system of claim 17, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m\⊗{\left(\mathrm{kG}\right)}_x=r$ The time, then $d^{,}(r,P)=r\⊗P_x=m.$

25. as the ellipse curve signature and the certifying signature system of claim 17, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m\⊕{\left(\mathrm{kG}\right)}_y=r$ The time, then $d^{,}(r,P)=r\⊕P_y=m.$

26. as the ellipse curve signature and the certifying signature system of claim 17, wherein function d and function d ' be taken as: (m, kG) value is as d $d(m,\mathrm{kG})=m\⊗{\left(\mathrm{kG}\right)}_y=r$ The time, then $d^{,}(r,P)=r\⊗P_y=m.$

27. as the ellipse curve signature and the certifying signature system of claim 17, wherein function d and function d ' be taken as: when d (m, kG) value is for being expressly with m, when kG is the symmetric cryptography function of key, d ' (r, P) value is for being ciphertext accordingly with r, P is the symmetrical decryption function of key.

28. ellipse curve signature and certifying signature system, wherein function f as claim 17 ₀, f ₁, g ₀, g ₁Be the linear function of r.

29. ellipse curve signature and certifying signature system, wherein function f as claim 17 ₀, f ₁, g ₀, g ₁Be taken as: f ₀(r)=c ₀* r, f ₁(r)=c ₁, g ₀(r)=c ₂, g ₁(r)=c ₀* r, wherein c ₀, c ₁, c ₂Be constant.

30. ellipse curve signature and certifying signature system, wherein function f as claim 17 ₀, f ₁, g ₀, g ₁Be taken as: f ₁(r)=c ₀* r, f ₀(r)=c ₁, g ₁(r)=c ₂, g ₀(r)=c ₀* r, wherein c ₀, c ₁, c ₂Be constant.

31. ellipse curve signature and certifying signature system, wherein function f as claim 17 ₀, f ₁, g ₀, g ₁Value is f respectively ₀(r)=c ₁, f ₁(r)=c ₂, g ₀(r)=c ₀* r, g ₁(r)=c ₃, c wherein ₀, c ₁, c ₂, c ₃Be constant.

32. ellipse curve signature and certifying signature system, wherein function f as claim 17 ₀, f ₁, g ₀, g ₁Value is f respectively ₁(r)=c ₁, f ₀(r)=c ₂, g ₁(r)=c ₀* r, g ₀(r)=c ₃, c wherein ₀, c ₁, c ₂, c ₃Be constant.

Images