Modular exponentiation optimization for cryptographic systems

Patent metadata

Field	Value
Publication number	US-9444623-B2
Application number	US-201414567954-A
Country	US
Kind code	B2
Filing date	Dec 11, 2014
Priority date	Dec 20, 2013
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

Abstract

A processing device, such as logic on an integrated circuit may identify a cryptographic message stored in a first register. The processing device may determine a plurality of components for a second power of the cryptographic message using a plurality of components of the cryptographic message. The processing device may determine the plurality of components for the second power of the cryptographic message without storing the entire second power of the cryptographic message. Further, the processing device may determine a third power of the cryptographic message using modular arithmetic. The processing device may determine the third power by transforming the plurality of components for the second power of the cryptographic message and the plurality of components of the cryptographic message.

First claim

What is claimed is:

1. A method comprising:
identifying, by logic on an integrated circuit, a cryptographic message stored in a first register; determining a plurality of components for a second power of the cryptographic message using a plurality of components of the cryptographic message, wherein the determining of the plurality of components for the second power of the cryptographic message is performed without storing the entire second power of the cryptographic message; and determining a third power of the cryptographic message using modular arithmetic, wherein said determining comprises:
transforming the plurality of components for the second power of the cryptographic message and the plurality of components of the cryptographic message, wherein the plurality of components for the second power of the cryptographic message are determined without using modular arithmetic;
determining the third power of the cryptographic message (mod N) using modulo N multiplication, wherein N is a modulus; wherein the modulo N multiplication comprises at least one of Montgomery multiplication or Barrett multiplication, wherein the modulus N is part of a public key in an RSA cryptosystem, wherein a number of bits of the modulus N are fixed and storing the third power of the cryptographic message (mod N) in a second register, wherein a size of the first register and a size of the second register correspond to a size of the cryptographic message.

2. The method of claim 1 , wherein the modulo N multiplication comprises at least one of Montgomery multiplication or Barrett multiplication.

3. The method of claim 1 , wherein the modulus N is part of a public key in an RSA cryptosystem.

4. The method of claim 1 , wherein a number of bits of the modulus N are fixed.

5. The method of claim 1 , wherein a compute time for determining the third power of the cryptographic message using modular arithmetic is proportional to a square of a size of the cryptographic message.

6. An apparatus comprising:
a first register to store a plurality of components of cryptographic message;
a digital logic operatively coupled to the first register, the digital logic to:
determine a plurality of components for a second power of the cryptographic message using the plurality of components of the cryptographic message, wherein the determining of the plurality of components for the second power of the cryptographic message is performed without storing the entire second power of the cryptographic message; and
determine a third power of the cryptographic message using modular arithmetic, including
transforming the plurality of components for the second power of the cryptographic message and the plurality of components of the cryptographic message, wherein the plurality of components for the second power of the cryptographic message are determined without using modular arithmetic, and determining the third power of the cryptographic message (mod N) using modulo N multiplication, wherein N is a modulus; and

a second register to store the third power of the cryptographic message (mod N), wherein a size of the first register and a size of the second register correspond to a size of the cryptographic message.

7. The apparatus of claim 6 , wherein the modulo N multiplication comprises at least one of Montgomery multiplication or Barrett multiplication.

8. The apparatus of claim 6 , wherein the modulus N is part of a public key in an RSA cryptosystem.

9. The apparatus of claim 6 , wherein a number of bits of the modulus N are fixed.

10. The apparatus of claim 6 , wherein a compute time to determine the third power of the cryptographic message using modular arithmetic is proportional to a square of a size of the cryptographic message.

11. A non-transitory computer-readable storage medium including instructions that, when executed by a processing device, cause the processing device to perform operations comprising: identifying, the processing device, a cryptographic message stored in a first register; determining a plurality of components for a second power of the cryptographic message using a plurality of components of the cryptographic message, wherein the determining of the plurality of components for the second power of the cryptographic message is performed without storing the entire second power of the cryptographic message; and determining a third power of the cryptographic message using modular arithmetic, wherein said determining comprises: transforming the plurality of components for the second power of the cryptographic message and the plurality of components of the cryptographic message, and wherein the plurality of components for the second power of the cryptographic message are determined without using modular arithmetic; wherein determining the third power of the cryptographic message using modular arithmetic comprises: determining a third power of the cryptographic message (mod N) using modulo N multiplication, wherein N is a modulus, wherein the modulo N multiplication comprises at least one of Montgomery multiplication or Barrett multiplication, wherein the modulus N is part of a public key in an RSA cryptosystem and storing the third power of the cryptographic message (mod N) in a second register, wherein a size of the first register and a size of the second register correspond to a size of the cryptographic message.

12. The non-transitory computer-readable storage medium of claim 11 , wherein the modulo N multiplication comprises at least one of Montgomery multiplication or Barrett multiplication.

13. The non-transitory computer-readable storage medium of claim 11 , wherein the modulus N is part of a public key in an RSA cryptosystem.

14. The non-transitory computer-readable storage medium of claim 11 , wherein a compute time for determining the third power of the cryptographic message using modular arithmetic is proportional to a square of a size of the cryptographic message.

Assignees

• Cryptography Res Inc

Inventors

• Kocher Paul C
• Hamburg Michael A
• Kumar Ambuj

Classifications

• H04L2209/12

  Details relating to cryptographic hardware or logic circuitry · CPC title

• H04L9/302 Primary

  involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes · CPC title