Method to calculate square roots for elliptic curve cryptography
A method is presented to compute square roots of finite field elements from the prime finite field of characteristic p over which points lie on a defined elliptic curve. Specifically, while performing point decompression of points that lie on a standardized elliptic curve over a prime finite field of characteristic 2 224 −2 96 +1, the present method utilizes short Lucas sub-sequences to optimize the implementation of a modified version of Mueller's square root algorithm, to find the square root modulo of a prime number. The resulting method is at least twice as fast as standard methods employed for square root computations performed on elliptic curves.
1. A method of computing a square root of an element q of a prime finite field, the method comprising:
determining a value of a finite field element t yielding an initial value P=q*t*t−2 such that P−2 is not a quadratic residue, wherein P is an initial parameter of a Lucas function;
calculating a factored representation of (p−1)/4, the factored representation consisting of a set of factors that, when multiplied together, yield (p−1)/4, wherein p is a characteristic of the prime finite field on which coordinates of an elliptic curve are defined;
calculating a value of the Lucas function of P for one of the factors of the set of factors;
setting P to the computed Lucas function value;
computing a Lucas function value of P for another factor of the set of factors;
repeating the setting and computing steps for all remaining factors of the set of factors in the factored representation of (p−1)/4 to generate a final Lucas function value;
outputting the square root of the finite field element q, the square root being calculated as the final Lucas function value divided by the element t; and
using the square root of the finite field element q in at least one digital signature cryptographic application.
2. The method of claim 1 , wherein the Lucas function has two parameters P and Q, and Q=1.
3. The method of claim 1 , wherein the initial value P is computed based on one of a Jacobi symbol computation and a Legendre symbol computation.
4. The method of claim 1 , wherein the element t equals 2 c , wherein c is an integer.
5. The method of claim 1 , wherein the calculating step comprises calculating a prime factorization of (p−1)/4 as the factored representation of (p−1)/4.
6. The method of claim 5 , wherein p=2 224 −2 96 +1 and the prime factorization of (p−1)/4 is 2 94 , 3, 5, 17, 257, 641, 65537, 274177, 6700417, and 6728021310721.
7. The method of claim 1 , where the step of calculating the value of the Lucas function of P comprises:
determining a Lucas sub-sequence using an heuristic search; and
calculating the value of the Lucas function of P using the determined Lucas sub-sequence.
8. The method of claim 7 , wherein the step of determining a Lucas sub-sequence comprises determining a minimum-length Lucas sub-sequence.
9. An apparatus to perform a square root computation of an element q of a prime finite field, comprising:
a processor configured to:
determine a value of a finite field element t yielding an initial value P=q*t*t−2 such that P−2 is not a quadratic residue, wherein P is an initial parameter of a Lucas function;
calculate a factored representation of (p−1)/4, the factored representation consisting of a set of factors that, when multiplied together, yield (p−1)/4, wherein p is a characteristic of the prime finite field on which coordinates of an elliptic curve are defined;
calculate a value of the Lucas function of P for one of the factors of the set of factors;
set P to the computed Lucas function value;
compute a Lucas function value of P for another factor of the set of factors;
repeat the setting and computing steps for all remaining factors of the set of factors in the factored representation of (p−1)/4 to generate a final Lucas function value;
output the square root of the finite field element q, the square root being calculated as the final Lucas function value divided by the element t; and
use the square root of the finite field element q in at least one digital signature cryptographic application.
10. The apparatus to perform a square root computation of claim 9 , wherein the Lucas function has two parameters P and Q, and Q=1.
11. The apparatus to perform a square root computation of claim 9 , wherein the initial value P is computed based on one of a Jacobi symbol computation and a Legendre symbol computation.
12. The apparatus to perform a square root computation of claim 9 , wherein the element t equals 2 c , wherein c is an integer.
13. The apparatus to perform a square root computation of claim 9 , wherein the calculating step comprises calculating a prime factorization of (p−1)/4 as the factored representation of (p−1)/4.
14. The apparatus to perform a square root computation of claim 13 , wherein p=2 224 −2 96 +1 and the prime factorization of (p−1)/4 is 2 94 , 3, 5, 17, 257, 641, 65537, 274177, 6700417, and 6728021310721.
15. The apparatus to perform a square root computation of claim 9 , where the step of calculating the value of the Lucas function of P comprises:
determining a Lucas sub-sequence using an heuristic search; and
calculating the value of the Lucas function of P using the determined Lucas sub-sequence.
16. The apparatus to perform a square root computation of claim 15 , wherein the step of determining a Lucas sub-sequence comprises determining a minimum-length Lucas sub-sequence.
17. A non-transitory computer-readable medium having stored thereon a program that when executed by a computer causes the computer to execute the steps of:
determining a value of a finite field element t yielding an initial value P=q*t*t−2 such that P−2 is not a quadratic residue;
calculating a factored representation of (p−1)/4, wherein p is a characteristic of the prime finite field on which coordinates of an elliptic curve are defined, the factored representation consisting of a set of factors that, when multiplied together, yield (p−1)/4;
calculating a value of the Lucas function of P for one of the factors of the set of factors;
setting P to the computed Lucas function value;
computing a Lucas function value of P for another factor of the set of factors;
repeating the setting and computing steps for all remaining factors of the set of factors in the factored representation of (p−1)/4 to generate a final Lucas function value;
outputting the square root of the finite field element q, the square root being calculated as the final Lucas function value divided by the element t; and
using the square root of the finite field element q in at least one digital signature cryptographic application.
18. The non-transitory computer-readable medium of claim 17 , wherein the Lucas function has two parameters P and Q, and Q=1.
19. The non-transitory computer-readable medium of claim 17 , wherein the calculating step comprises calculating a prime factorization of (p−1)/4 as the factored representation of (p−1)/4.
20. The non-transitory computer-readable medium of claim 19 , wherein p=2 224 −2 96 +1 and the prime factorization of (p−1)/4 is 2 94 , 3, 5, 17, 257, 641, 65537, 274177, 6700417, and 6728021310721.