Method for speeding up the computations for characteristic 2 elliptic curve cryptographic systems
First Claim
1. A method in an elliptic curve cryptographic system comprising:
- pre-computing, for encryption, a multiplication routine according to an input operand length using one iteration graph-based multiplication;
computing, by a computing device, a first carry-less product of two input operands according to the pre-computed multiplication routine; and
computing, by the computing device, a second carry-less product between the first carry-less product and a sparse polynomial by performing a number of SHIFT and Exclusive-OR operations,where the sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to I in a polynomial defining an elliptic curve binary field.
1 Assignment
0 Petitions
Accused Products
Abstract
In some embodiments, an apparatus and method for speeding up the computations for characteristic 2 elliptic curve cryptographic systems are described. In one embodiment, a multiplication routine may be pre-computed using a one iteration graph-based multiplication according to an input operand length. Once pre-computed, the multiplication routine may be followed to compute the products of the coefficients of the polynomials representing a carry-less product of two input operands using a carry-less multiplication instruction. In one embodiment, the pre-computed multiplication routines may be used to extend a carry-less multiplication instruction available from an architecture according to an input operand length of the two input operands. Once computed, the carry-less product polynomial produces a remainder when the product is computed modulo a programmable polynomial that defines the elliptic cryptographic system to form a cryptographic key. Other embodiments are described and claimed.
-
Citations
18 Claims
-
1. A method in an elliptic curve cryptographic system comprising:
-
pre-computing, for encryption, a multiplication routine according to an input operand length using one iteration graph-based multiplication; computing, by a computing device, a first carry-less product of two input operands according to the pre-computed multiplication routine; and computing, by the computing device, a second carry-less product between the first carry-less product and a sparse polynomial by performing a number of SHIFT and Exclusive-OR operations, where the sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to I in a polynomial defining an elliptic curve binary field. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An article of manufacture including a non-transitory machine readable storage medium having instructions encoded thereon to program an elliptic curve cryptographic system to perform a method, comprising:
-
pre-computing, for encryption, a multiplication routine according to an input operand length using a one iteration graph-based multiplication; computing, by a computing device, a first carry-less product of two input operands according to the pre-computed multiplication routine; and computing, by the computing device, a second carry-less product between the first carry-less product and a sparse polynomial by performing a number of SHIFT and Exclusive-OR operations, where the sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to 1 in a polynomial defining an elliptic curve binary field. - View Dependent Claims (10, 11, 12)
-
-
13. An elliptic curve cryptograph system comprising:
-
a first computer device coupled to a first memory, the first computer device to execute an encryption program in the first memory, the encryption program to perform a method comprising; pre-computing a multiplication routine according to an input operand length using the one iteration graph-based multiplication; computing a first carry-less product of two input operands according to the pre-computed multiplication routine; and computing a second carry-less product between the first carry-less product and a sparse polynomial by performing a number of SHIFT and Exclusive-OR operations, where the sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to 1 in a polynomial defining an elliptic curve binary field; and a second computer device coupled to a second memory, the second computer device to execute the encryption program in the second memory, wherein the first computer device and the second computer device transfer encrypted data to one another over a network. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification