Koblitz exponentiation with bucketing

• US 7,139,396 B2
• Filed: 06/27/2002
• Issued: 11/21/2006
• Est. Priority Date: 06/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lauter, Kristin Estella, Montgomery, Peter L.
• Primary Examiner(s): Barron, Gilberto
• Assistant Examiner(s): KIM, JUNG W
• Application Number:
  US10/184,737
• Publication Number:
  US 20040005054A1
• Time in Patent Office: 1,608 Days
• Field of Search: 380/28, 380/29
• US Class Current: 380/30
• CPC Class Codes: G06F 7/725 over elliptic curves

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.

Claims

1. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of eltiptic 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;

merging the collections;

selecting the set of coefficients (c_i) from elements of Z[τ

] that are congruent to odd integers modulo 2^w; and

using the elliptic curve exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

2. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of 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;

merging the collections;

selecting the set of coefficients (c_i) from elements of Z[τ

] that are congruent to odd integers modulo 2^w, wherein τ

²±

τ

+2=0; and

using the elliptic curve exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

3. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of 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;

merging the collections;

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;

using the elliptic curve exponentiation during generation of at least art of a cryptographic key for securing data via encryption.

4. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of 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;

merging the collections;

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; and

using the elliptic curve exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

5. A computer-readable medium having at least one physical media and having computer-executable instructions that when executed by a computer, perform a method to improve the speed and security of 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;

merging the collections;

wherein during the merging, simultaneously performing multiple curve additions of points on the elliptic curve; and

using the elliptic curve exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

6. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of 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;

merging the collections;

wherein during the merging, performing joint addition/subtraction of points on the elliptic curve; and

using the elliptic curve exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

7. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of 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;

wherein during the merging, simultaneously performing multiple curve additions of points on an elliptic curve associated with the exponentiations; and

using the exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

8. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of 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;

wherein during the merging, performing joint addition/subtraction of points on an elliptic curve associated with the exponentiation; and

using the exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

9. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of elliptic curve exponentiation for Koblitz curves used in cryptography, the method comprising:

gathering elements of a Frobenius expansion of an exponent into collections of elements, the elements of a collection having matching coefficients,

wherein the Frobenius expansion is formed with a set of coefficients (c_i), powers of τ

, and expansion having a width (w);

merging the collections of elements;

wherein merging comprises simultaneously performing multiple curve additions of points on the elliptic curve; and

using the elliptic curve exponentiation during generation of at least part of a cryptographic key for securing data via encryption.

10. A computer-readable medium having at least one physical media and having computer-executable instructions that, when executed by a computer, perform a method to improve the speed and security of elliptic curve exponentiation for Koblitz curves used in cryptography, the method comprising:

gathering elements of a Frobenius expansion of an exponent into collections of elements, the elements of a collection having matching coefficients,

wherein the Frobenius expansion is formed with a set of coefficients (c_i), powers of τ

, and expansion having a width (w);

merging the collections of elements;

wherein merging comprises performing joint addition/subtraction of points on the elliptic curve; and

using the elliptic curve exponentiation during generation of at least part of a cryptographic key for securing data via encryption.