Method of generating cryptographic key pairs

• US 10,341,098 B2
• Filed: 01/24/2017
• Issued: 07/02/2019
• Est. Priority Date: 01/24/2017
• Status: Active Grant

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: NXP B.V. (NXP Semiconductors NV)
• Inventors: Bos, Joppe Willem, Fay, Bjorn, Murray, Bruce
• Primary Examiner(s): Zarrineh, Shahriar
• Application Number:
  US15/414,391
• Publication Number:
  US 20180212767A1
• Time in Patent Office: 889 Days
• Field of Search: 380 45
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A method is provided for performing elliptic curve cryptography that reduces the number of required computations to produce, for example, a key pair. The number of computations is reduced by changing how a random nonce used in the computations is selected. In an embodiment, a look-up table is generated having pre-computed scalar values and elliptic curve points. Every time a new pseudo-random value is created for use in the ECDSA, a combination of the look-up table values is used to create multiple intermediate values. One of the multiple intermediate values is randomly chosen as a replacement value for one of the existing table entries. Each time the look-up table is used, multiple entries in the look-up table are updated to new look-up table values as described. In this manner, new randomness is provided in every step to generate the next pseudo-random nonce as a combination of multiple internally stored temporary look-up table values. Alternately, another mathematical group may be used.

Claims

1. A method for generating cryptographic key pairs in public key cryptography, the method comprising:

A hardware Processor;

randomly generating a table having a plurality of table entries, each table entry comprising a plurality of group elements, each group element in a table entry of the plurality of table entries having a same discrete logarithm to a corresponding base, the corresponding bases of the discrete logarithms being the same for each table entry;

randomly selecting table entries from the plurality of table entries;

computing intermediate table entries from combinations of the selected table entries, each intermediate group element in an intermediate table entry having a same discrete logarithm to a corresponding base, and the corresponding bases of the discrete logarithms of the intermediate group elements being the same as for the table entries;

replacing the selected table entries with randomly selected intermediate table entries to produce an updated table; and

randomly selecting a table entry of the updated table and providing it as a cryptographic key pair, wherein a batch of cryptographic key pairs are generated, and wherein the updated table is transformed using simultaneous inversions of Z-components for point-coordinate transformations.

2. The method of claim 1, wherein the public key cryptography is implemented using an elliptic curve.

3. The method of claim 2, wherein computing intermediate table entries from combinations of the selected table entries further comprising using addition and subtraction operations for the computation of the intermediate table entries.

4. The method of claim 3, wherein computing intermediate table entries from combinations of the selected table entries further comprising using computations of sums and differences of points in a single operation.

5. The method of claim 1, further comprising providing shared secrets having a same discrete logarithm as the generated cryptographic key pair.

6. The method of claim 1, wherein randomly selecting table entries from the plurality of table entries further comprising storing latest selections of table entries and avoiding repeating the latest selections.

7. The method of claim 1, wherein the method for generating cryptographic key pairs in public key cryptography further comprising:

randomly selecting table entries from the updated table,

computing intermediate table entries from combinations of the selected table entries from the updated table, each intermediate table entry of the updated table comprising intermediate group elements, each intermediate group element in an intermediate table entry having a same discrete logarithm to a corresponding base and the corresponding bases of the discrete logarithms being the same as for the table entries from the updated table; and

replacing the selected table entries from the updated table with randomly selected intermediate table entries,

wherein the steps of randomly selecting, computing, and replacing are repeated before providing the key pair.

8. The method of claim 1, further comprising providing a hatch of the inverses of the private keys using simultaneous inversions on a batch of private keys.

9. A non-transitory machine-readable medium having instructions for generating cryptographic key pairs in public key cryptography, the non-transitory machine-readable medium comprising:

instructions for randomly generating a table having a plurality of table entries, each table entry comprising a plurality of group elements, each group element in a table entry of the plurality of table entries having a same discrete logarithm to a corresponding base, the corresponding bases of the discrete logarithms being the same for each table entry;

instructions for randomly selecting table entries from the plurality of table entries;

instructions for computing intermediate table entries from combinations of the selected table entries, each intermediate group element in an intermediate table entry having a same discrete logarithm to a corresponding base, and the corresponding bases of the discrete logarithms of the intermediate group elements being the same as for the table entries;

instructions for replacing the selected table entries with randomly selected intermediate table entries; and

instructions for randomly selecting a table entry and providing it as a cryptographic key pair, wherein a batch of cryptographic key pairs are generated, and wherein the updated table is transformed using simultaneous inversions of Z-components for point-coordinate transformations.

10. The non-transitory machine-readable medium of claim 9, wherein the public key cryptography is implemented using an elliptic curve.

11. The non-transitory machine-readable medium of claim 10, wherein the instructions for computing intermediate table entries from combinations of the selected table entries further comprising instructions using addition and subtraction operations for the computation of the intermediate table entries.

12. The non-transitory machine-readable medium of claim 11, wherein the instructions for computing intermediate table entries from combinations of the selected table entries further comprising instructions for using computations of sums and differences of points in a single operation.

13. The non-transitory machine-readable medium of claim 9, further comprising instructions for providing shared secrets having a same discrete logarithm as the generated cryptographic key pair.

14. The non-transitory machine-readable medium of claim 9, wherein the instructions for randomly selecting table entries from the plurality of table entries further comprising instructions for storing latest selections of table entries and avoiding repeating the latest selections.

15. The non-transitory machine-readable medium of claim 9, further comprising:

instructions for randomly selecting table entries from the updated table;

instructions for computing intermediate table entries from combinations of the selected table entries from the updated table, each intermediate table entry of the updated table comprising intermediate group elements, each intermediate group element in an intermediate table entry having a same discrete logarithm to a corresponding base and the corresponding bases of the discrete logarithms being the same as for the table entries from the updated table; and

instructions for replacing the selected table entries from the updated table with randomly selected intermediate table entries.

16. The non-transitory machine-readable medium of claim 9, further comprising instructions for providing a hatch of the inverses of the private keys using simultaneous inversions on a batch of private keys.