Systems and Methods for Efficient Fixed-Base Multi-Precision Exponentiation

• US 20180224882A1
• Filed: 01/19/2018
• Published: 08/09/2018
• Est. Priority Date: 01/20/2017
• Status: Active Grant

• Current Assignee: Enveil, Inc.
• Original Assignee: Enveil, Inc.
• Inventors: Carr, Ryan
• Granted Patent: US 10,693,627 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 1/0307 Logarithmic or exponential functions G06F1/0314, G06F1/035 take precedence
• CPC Class Codes: G06F 7/552 Powers or roots , e.g. Pythagorean sums
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/728 using Montgomery reduction
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: H03M 7/24 Conversion to or from floating-point codes
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

Systems and methods for efficient fixed-base multi-precision exponentiation are disclosed herein. An example method includes applying a multi-precision exponentiation algorithm to a base number, the multi-precision exponentiation algorithm comprises a pre-generated lookup table used to perform calculations on the base number, the pre-generated lookup table comprising pre-calculated exponentiated values of the base number.

Claims

1. A method, comprising:

applying a multi-precision exponentiation algorithm to a base number, the multi-precision exponentiation algorithm comprising a pre-generated lookup table used to perform calculations on the base number, the pre-generated lookup table comprising pre-calculated exponentiated values of the base number.

2. The method according to claim 1, further comprising:

identifying the base number as having a size that is more than 64 bits; and

determining if a time required for using the multi-precision exponentiation algorithm is less than a time required to perform the calculations of the base number directly using exponents; and

wherein the multi-precision exponentiation algorithm is used only when the time required for using the multi-precision exponentiation algorithm is less than the time required to perform the calculations of the base number directly using exponents.

3. The method according to claim 1, wherein the lookup table is pre-generated.

4. The method according to claim 1, further comprising determining that a base number has a size that exceeds a size threshold, wherein the size threshold is greater than 64 bits.

5. The method according to claim 1, further comprising selecting the exponents that will be used to exponentiate the base number.

6. The method according to claim 1, further comprising converting the base number into a form suitable for use in an encryption algorithm.

7. The method according to claim 1, wherein determining if a time required for using the multi-precision exponentiation algorithm is less than a time required to perform the calculations of the base number directly using exponents further comprises:

identifying an exponent size parameter;

estimating a number of multi-precision operations required using the exponent size parameter;

identifying which of the multi-precision operations are squarings or non-squarings; and

determining a one-time cost using calculations from the squarings and the non-squarings.

8. The method according to claim 7, wherein the exponent size parameter is selected to prevent the lookup table from growing to a point where memory of a multi-precision exponentiation algorithm application is exhausted.

9. The method according to claim 8, further comprising identifying an index of a highest bit set in the exponents.

10. The method according to claim 9, wherein an optimal value of the exponent size parameter is a function of a number of the exponents, the index of a highest bit set, and a highest possible value for the exponent size parameter.

12. A system, comprising:

a processor; and

a memory for storing executable instructions, the processing executing the instructions to;

apply a multi-precision exponentiation algorithm to a base number, wherein the multi-precision exponentiation algorithm comprises a pre-generated lookup table used to perform calculations on the base number, the pre-generated lookup table comprising pre-calculated exponentiated values of the base number; and

return a calculated value for the base number.

13. The system according to claim 12, wherein the processor is further configured to determine if a time required for using a multi-precision exponentiation algorithm to exponentiate the base number is less than a time required to perform exponentiation of the base number directly using exponents.

14. The system according to claim 13, further comprising identifying a base number with a size that is more than 64 bits.

15. The system according to claim 14, wherein the lookup table comprises raised values corresponding to exponentiation of the base number with the exponents.

16. The system according to claim 15, further comprising selecting the exponents that will be used to exponentiate the base number when generating the lookup table.

17. The system according to claim 16, further comprising converting the base number into a form suitable for use in an encryption algorithm.