Method to calculate square roots for elliptic curve cryptography
AssigneeCerticom Corp.
InventorRobert John LAMBERT
Life of this patent
Estimating the term…
Abstract
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 2224−296+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.
Claims10
A method of computing a square root of an element q of a prime finite field of characteristic p for use in elliptic curve cryptography, 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;
- 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;
- calculating a value of a 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;
- and
- 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.
An apparatus to perform a square root computation of an element q of a prime finite field of characteristic p on which the coordinates of an elliptic curve are defined, for use in elliptic curve cryptography, 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;
- 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;
- calculate a value of a 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;
- and
- 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 .
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, the factored representation consisting of a set of factors that, when multiplied together, yield (p−1)/4;
- calculating a value of a 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;
- and
- 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.
Dependencies are inferred from the claim text.