Koblitz Exponentiation with Bucketing

Abstract

An implementation of a technology, described herein, for facilitating cryptographic systems and techniques. At least one implementation, described herein, maximizes the speed and security of fast exponentiation while minimizing its expense. At least one implementation, described herein, employs elliptic curves with a fast exponentiation technique so that it maximizes speed and security while minimizing expense. At least one implementation, described herein, employs Koblitz exponentiation with “bucketing” techniques to maximize speed and security of cryptosystems while minimizing expense of such techniques. This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims.

1 . A computer-executable method for performing elliptic curve exponentiation for subfield curves used in cryptography, the method comprising:
 forming, with a set of coefficients (c i ), a Frobenius expansion of an exponent, the Frobenius expansion having a width (w);   gathering elements of the Frobenius expansion into collections of elements having matching coefficients; and   using the elliptic curve exponentiation to generate at least part of a cryptographic key for securing data via encryption.   
   
   
       2 . The method as recited in  claim 1 , wherein the subfield curves are Koblitz curves. 
   
   
       3 . The method as recited in  claim 1 , wherein forming the Frobenius expansion uses the powers of an algebraic integer τ. 
   
   
       4 . The method as recited in  claim 1 , wherein the method further comprises selecting the set of coefficients (c i ) from elements of Z[τ] that are congruent to odd integers modulo 2 w . 
   
   
       5 . The method as recited in  claim 1 , wherein the method further comprises selecting the set of coefficients (c i ) from elements of Z[τ] that are congruent to odd integers modulo 2 w , wherein τ 2 ±τ+2=0. 
   
   
       6 . The method as recited in  claim 1 , wherein the method further comprises selecting the set of coefficients (c i ) from elements of Z[τ] that are congruent to odd integers modulo 2 w  or to the negative of odd integers modulo 2 w . 
   
   
       7 . The method as recited in  claim 1 , wherein the method further comprises selecting the set of coefficients (c i ) from elements of Z[τ] that are congruent to odd integers modulo 2 w , for the width w, wherein the selecting is under 2-adic homomorphism. 
   
   
       8 . The method as recited in  claim 1 , wherein the method further comprises merging the collections of elements. 
   
   
       9 . The method as recited in  claim 1 , wherein during the merging, simultaneously performing multiple curve additions. 
   
   
       10 . The method as recited in  claim 9 , wherein during the merging, performing joint addition/subtraction. 
   
   
       11 . A computer-executable method for performing exponentiation used in cryptography, the method comprising:
 gathering elements of an expansion of an exponent into collections of elements, wherein the elements of a collection have matching coefficients;   merging the collections of elements; and   using the exponentiation to generate at least part of a cryptographic key for securing data via encryption.   
   
   
       12 . The method as recited in  claim 11 , wherein the exponentiation is binary exponentiation. 
   
   
       13 . The method as recited in  claim 11 , wherein the exponentiation is elliptic curve exponentiation for subfield curves. 
   
   
       14 . The method as recited in  claim 11 , wherein the exponentiation is elliptic curve exponentiation for Koblitz curves. 
   
   
       15 . The method as recited in  claim 11 , wherein the expansion comprises a Frobenius expansion of the exponent. 
   
   
       16 . The method as recited in  claim 11 , wherein the expansion comprises a Frobenius expansion of the exponent, which is formed with a set of coefficients (c i ), powers of algebraic integer τ, and expansion having a width (w). 
   
   
       17 . The method as recited in  claim 11 , wherein during the merging, simultaneously performing multiple curve additions. 
   
   
       18 . The method as recited in  claim 11 , wherein during the merging, performing joint addition/subtraction. 
   
   
       19 . A crypto-system comprising:
 a memory to store a set of computer program modules;   a processor coupled to the memory, the processor to execute the computer program modules to perform elliptic curve exponentiation for Koblitz curves;   a first module of the computer program modules to form, with a set of coefficients (c i ) having powers of algebraic integer τ, a Frobenius expansion of an exponent the Frobenius expansion having a width (w);   a second module of the computer program modules to gather elements of the Frobenius expansion into collections of elements having matching coefficients; and   a cryptographic key generator to secure data via encryption using the elliptic curve exponentiation.   
   
   
       20 . The crypto-system as recited in  claim 19  further comprising a third module of the computer program modules to merge the collections of elements.