Protecting modular inversion operation from external monitoring attacks

Patent metadata

Field	Value
Publication number	US-11418334-B2
Application number	US-201816756099-A
Country	US
Kind code	B2
Filing date	Oct 8, 2018
Priority date	Oct 18, 2017
Publication date	Aug 16, 2022
Grant date	Aug 16, 2022

Abstract

Systems and methods for performing modular inversion operations in a manner protected from external monitoring attacks. An example method comprises: determining, by a processor, a first masked value based on a public cryptographic key and a first random integer value; determining a second masked value based on the public cryptographic key and a second random integer value, and determining, based on the first masked value and the second masked value, a private cryptographic key represented by a modular inversion of the public cryptographic key.

First claim

What is claimed is:

1. A method of performing a cryptographic data processing operation in a manner protected from external monitoring attacks, the method comprising:
determining, by a cryptographic data processing device, a first masked value equal to a remainder of integer division of a product of a public cryptographic key and a first random integer value by a modulus value;
determining a second masked value based on the public cryptographic key and a second random integer value; and
determining, based on the first masked value and the second masked value, a private cryptographic key represented by a modular multiplicative inversion of the public cryptographic key.

2. The method of claim 1 , wherein the second masked value is represented by a sum of the modulus value and a remainder of integer division of a product of the public cryptographic key and the second random integer value by the modulus value.

3. The method of claim 1 , wherein the modulus value is represented by a value of Euler totient function of a product of two random prime numbers.

4. The method of claim 1 , wherein the public cryptographic key is represented by an integer value which is co-prime with the modulus value.

5. The method of claim 1 , wherein the first masked value is represented by a product of the public cryptographic key and the first random integer value.

6. The method of claim 5 , wherein the second masked value is represented by a sum of a modulus value and a product of the public cryptographic key and the second random integer value.

7. The method of claim 1 , wherein determining the private cryptographic key further comprises:
computing a sum of a product of a first integer multiplier and the first random integer value and a product of a second integer multiplier and the second random integer value.

8. The method of claim 7 , wherein a sum of a product of the first integer multiplier and the first masked value and a product of the second integer multiplier and the second masked value equals to a pre-defined integer constant.

9. The method of claim 1 , further comprising:
utilizing the public cryptographic key and the private cryptographic key for performing a cryptographic data processing operation.

10. The method of claim 1 , further comprising:
utilizing the private cryptographic key for decrypting a cyphertext that has been encrypted with the public cryptographic key.

11. A computer-readable non-transitory storage medium comprising executable instructions for perform a cryptographic data processing operation in a manner protected from external monitoring attacks, wherein the executable instructions, when executed by a computing device, cause the computing device to:
determining, by a cryptographic data processing device, a first masked value equal to a remainder of integer division of a product of a public cryptographic key and a first random integer value by a modulus value;
determining a second masked value based on the public cryptographic key and a second random integer value; and
determining, based on the first masked value and the second masked value, a private cryptographic key represented by a modular multiplicative inversion of the public cryptographic key.

12. The computer-readable non-transitory storage medium of claim 11 , wherein the second masked value is represented by a sum of the modulus value and a remainder of integer division of a product of the public cryptographic key and the second random integer value by the modulus value.

13. The computer-readable non-transitory storage medium of claim 12 , wherein the modulus value is represented by a value of Euler totient function of a product of two random prime numbers.

14. The computer-readable non-transitory storage medium of claim 12 , wherein the public cryptographic key is represented by an integer value which is co-prime with the modulus value.

15. The computer-readable non-transitory storage medium of claim 11 , wherein determining the private cryptographic key further comprises:
computing a sum of a product of a first integer multiplier and the first random integer value and a product of a second integer multiplier and the second random integer value.

16. The computer-readable non-transitory storage medium of claim 15 , wherein a sum of a product of the first integer multiplier and the first masked value and a product of the second integer multiplier and the second masked value equals to a pre-defined integer constant.

17. The computer-readable non-transitory storage medium of claim 11 , further comprising:
utilizing the public cryptographic key and the private cryptographic key for performing a cryptographic data processing operation.

Assignees

• Cryptography Res Inc

Inventors

• Hamburg Michael Alexander
• Tunstall Michael

Classifications

• H04L9/003

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title

• H04L9/302

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

• G06F21/602

  Providing cryptographic facilities or services · CPC title

• H04L2209/12

  Details relating to cryptographic hardware or logic circuitry · CPC title

• H04L2209/046

  of operations, operands or results of the operations · CPC title