METHOD OF GENERATING AN ELLIPTIC CURVE CRYPTOGRAPHIC KEY PAIR

• US 20180115419A1
• Filed: 10/26/2016
• Published: 04/26/2018
• Est. Priority Date: 10/26/2016
• 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
• Granted Patent: US 10,680,810 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• 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/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing

Abstract

A method is provided for generating an elliptic curve cryptography key pair that uses two topologically identical pseudo-random number generators operating in parallel and in step with each other. One generator operates in the scalar number domain and the other generator operates in the elliptic curve point domain. Parallel sequences of pseudo-random elliptic curve points aG and corresponding scalars a are generated in this manner. A scalar a becomes a private key and an elliptic curve point aG is a public key of a key pair. Each generator is advanced by one iteration successively, and the isomorphic relationship ensures that the point domain generator always contains values which are multiples of the system base point according to values contained in the corresponding position in the number domain generator. In one embodiment, the pseudo-random number generators are each characterized as being lagged Fibonacci generators.

Claims

1. A method for generating an cryptographic key pair for use in a processor, the method comprising:

generating a first pseudo-random number using a first pseudo-random number generator operating in a scalar number domain;

generating a pseudo-random group element using a second pseudo-random number generator; and

providing a private key from the first random number and a public key from the pseudo-random group element, the private key and the public key being a key pair,

wherein the first and second random number generators are operating in step with each other to produce a plurality of key pairs.

2. The method of claim 1, wherein generating the first pseudo-random number using the first pseudo-random number generator further comprises using only one out of p generated pseudo-random numbers, where p is an integer.

3. The method of claim 1, wherein the method is embodied in a non-transitory machine-readable storage medium.

4. The method of claim 1, wherein the first and second random number generators are characterized as being lagged Fibonacci generators.

5. The method of claim 4, wherein generating the first pseudo-random number using the first random pseudo-number generator operating in the scalar number domain, further comprises running the first pseudo-random number generator as a circular buffer.

6. The method of claim 1, wherein the pseudo-random group element is characterized as being a pseudo-random elliptic curve point.

7. The method of claim 6, wherein the first and second random number generators are characterized as being defined by linear recurrence relations computed over a modulus equivalent to the order of an elliptic curve upon which the plurality of key pairs is generated.

8. The method of claim 1, wherein generating the random elliptic curve point using the second random number generator operating in a point domain further comprises using the second generator to perform a point addition of two points on the elliptic curve.

9. The method of claim 1, wherein generating the first random number using the first random number generator operating in a scalar number domain further comprises performing a modulo operation using the first random number generator.

10. A method for generating an cryptographic key pair for use in a processor, the method comprising:

generating a first pseudo-random number using a first pseudo-random number generator operating in a scalar number domain;

generating a pseudo-random member of a mathematical group using a second pseudo-random number generator which performs computations in the mathematical group; and

providing a private key from the first pseudo-random number and a public key from the pseudo-random member of the mathematical group, the private key and the public key being a key pair,

wherein the first and second pseudo-random number generators operate in step with each other to produce a plurality of key pairs.

11. The method of claim 10, wherein generating the first pseudo-random number using a first pseudo-random number generator operating in a scalar number domain further comprises running the first pseudo-random number generator as a circular buffer.

12. The method of claim 10, wherein the first and second pseudo-random number generators are characterized as being lagged Fibonacci generators.

13. The method of claim 10, wherein generating the pseudo-random member of the mathematical group using the second random number generator further comprises using the second random number generator to perform a group operation on two elements of the mathematical group.

14. The method of claim 13, wherein the first and second random number generators are characterized as being defined by linear recurrence relations computed over a modulus equivalent to the order of the elliptic curve upon which the plurality of key pairs is generated.

15. The method of claim 10, wherein generating the first pseudo-random number using the first pseudo-random number generator operating in the scalar number domain further comprises performing a modulo operation using the first pseudo-random number generator.

16. The method of claim 10, wherein generating the first pseudo-random number using the first pseudo-random number generator further comprises using only one out of p generated pseudo-random numbers, where p is an integer.

17. A method for generating an elliptic curve cryptographic key pair for use in a processor, the method comprising:

generating a first pseudo-random number using a first random number generator operating in a scalar number domain as a circular buffer;

generating a pseudo-random elliptic curve point using a second random number generator operating in a point domain as a circular buffer; and

providing a private key from the first random number and a public key from the pseudo-random elliptic curve point, the private key and the public key being a key pair,

wherein the first and second random number generators are characterized as being lagged Fibonacci generators operating in step with each other.

18. The method of claim 17, wherein generating the first pseudo-random number using the first random number generator further comprises using only one out of p generated random numbers, where p is an integer.

19. The method of claim 17, wherein generating the pseudo-random elliptic curve point using the second random number generator operating in the point domain further comprises using the second random number generator to perform a point addition of two points on the elliptic curve.

20. The method of claim 17, wherein generating the first pseudo-random number using the first random number generator operating in the scalar number domain further comprises performing a modulo operation using the first random number generator.