Using a secret generator in an elliptic curve cryptography (ECC) digital signature scheme

• US 9,800,411 B1
• Filed: 05/05/2016
• Issued: 10/24/2017
• Est. Priority Date: 05/05/2016
• Status: Active Grant

• Current Assignee: ISARA Corporation
• Original Assignee: ISARA Corporation
• Inventors: Brown, Michael Kenneth, Gutoski, Gustav Michael, Struik, Marinus, Yamada, Atsushi
• Primary Examiner(s): Schmidt, Kari
• Application Number:
  US15/147,845
• Time in Patent Office: 537 Days
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/32 including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes
• CPC Class Codes: H04W 12/06 Authentication

Abstract

In a general aspect, a secret generator is used in an elliptic curve cryptography (ECC) scheme. In some aspects, an elliptic curve subgroup is specified by a public generator of an ECC system, and the secret generator is an element of the elliptic curve subgroup. In some instances, the secret generator is used to generate an ECC key pair that includes a public key and a private key, and the private key is used to generate a digital signature based on a message. In some instances, the public key and the secret generator are used to verify the digital signature.

Claims

1. An elliptic curve cryptography (ECC) digital signature method comprising:

generating a shared secret generator, the shared secret generator being known to a signer and a verifier, the shared secret generator being an element of an elliptic curve subgroup specified by a public generator of an elliptic curve cryptography system, wherein generating the shared secret generator comprises;

using a point decompression function to generate a coordinate pair; and

designating the coordinate pair as the shared secret generator based on a determination that the coordinate pair belongs to the elliptic curve subgroup;

using the shared secret generator to generate, by operation of one or more processors, a key pair of the signer, the key pair of the signer comprising a public key and a private key;

using the private key to generate a digital signature of the signer based on a message; and

providing the digital signature of the signer for transmission to the verifier, the digital signature enabling the verifier to verify authenticity of the message.

2. The ECC digital signature method of claim 1, further comprising receiving the shared secret generator from a trusted third party.

3. The ECC digital signature method of claim 1, wherein generating the key pair of the signer comprises:

obtaining a random integer;

designating the random integer as the private key; and

computing the public key by combining the random integer with the shared secret generator.

4. The ECC digital signature method of claim 1, wherein generating the digital signature of the signer based on the message comprises:

using the shared secret generator to obtain an ephemeral key pair comprising an ephemeral private key;

using a hash function to compute a first signature component; and

using the first signature component, the private key and the ephemeral private key to generate a second signature component.

5. A system comprising:

a data processing apparatus;

a non-transitory computer-readable medium storing instructions that when executed by the data processing apparatus perform operations comprising;

generating a shared secret generator, the shared secret generator being known to a signer and a verifier, the shared secret generator being an element of an elliptic curve subgroup specified by a public generator of an elliptic curve cryptography system, wherein generating the shared secret generator comprises;

using a point decompression function to generate a coordinate pair; and

designating the coordinate pair as the shared secret generator based on a determination that the coordinate pair belongs to the elliptic curve subgroup;

using the shared secret generator to generate a key pair of the signer, the key pair of the signer comprising a public key and a private key; and

using the private key to generate a digital signature of the signer based on a message; and

a communication interface that sends the digital signature of the signer to the verifier, the digital signature enabling the verifier to verify authenticity of the message.

6. The system of claim 5, the operations further comprising receiving the shared secret generator from a trusted third party.

7. The system of claim 5, wherein generating the key pair of the signer comprises:

obtaining a random integer;

designating the random integer as the private key; and

computing the public key by combining the random integer with the shared secret generator.

8. The system of claim 5, wherein generating the digital signature of the signer based on the message comprises:

using the shared secret generator to obtain an ephemeral key pair comprising an ephemeral private key;

using a hash function to compute a first signature component; and

using the first signature component, the private key and the ephemeral private key to generate a second signature component.

9. An elliptic curve cryptography (ECC) signature verification method comprising:

receiving a digital signature of a signer, the digital signature of the signer being associated with a message;

generating a shared secret generator selected from an elliptic curve subgroup, the shared secret generator known to the signer and a verifier, the elliptic curve subgroup specified by a public generator of an elliptic curve cryptography system, wherein generating the shared secret generator comprises;

using a point decompression function to generate a coordinate pair; and

designating the coordinate pair as the shared secret generator based on a determination that the coordinate pair belongs to the elliptic curve subgroup;

accessing a public key of the signer; and

by operation of one or more processors, using the public key of the signer and the shared secret generator to verify the digital signature of the signer.

10. The ECC signature verification method of claim 9, further comprising receiving the shared secret generator from a trusted third party.

11. The ECC signature verification method of claim 9, wherein the public key of the signer is based on the shared secret generator and a private key of the signer.

12. The ECC signature verification method of claim 9, wherein verifying the digital signature of the signer comprises:

computing an elliptic curve point based on the shared secret generator, the public key of the signer and the digital signature of the signer;

computing a check value based on the elliptic curve point and the message; and

comparing a component of the digital signature of the signer with the check value modulo an integer.

13. A system comprising:

a data processing apparatus;

a communication interface that receives a digital signature of a signer, the digital signature of the signer associated with a message;

a non-transitory computer-readable medium storing instructions that when executed by the data processing apparatus perform operations comprising;

generating a shared secret generator selected from an elliptic curve subgroup, the shared secret generator known to the signer and a verifier, the elliptic curve subgroup specified by a public generator of an elliptic curve cryptography system, wherein generating the shared secret generator comprises;

using a point decompression function to generate a coordinate pair; and

designating the coordinate pair as the shared secret generator based on a determination that the coordinate pair belongs to the elliptic curve subgroup;

accessing a public key of the signer; and

using the public key of the signer and the shared secret generator to verify the digital signature of the signer.

14. The system of claim 13, the operations further comprising receiving the shared secret generator from a trusted third party.

15. The system of claim 13, wherein the public key of the signer is based on the shared secret generator and a private key of the signer.

16. The system of claim 13, wherein verifying the digital signature of the signer comprises:

computing an elliptic curve point based on the shared secret generator, the public key of the signer and the digital signature of the signer;

computing a check value based on the elliptic curve point and the message; and

comparing a component of the digital signature of the signer with the check value modulo an integer.