System and method to optimize generation of coprime numbers in cryptographic applications

Patent metadata

Field	Value
Publication number	US-11902432-B2
Application number	US-202117532460-A
Country	US
Kind code	B2
Filing date	Nov 22, 2021
Priority date	Nov 25, 2020
Publication date	Feb 13, 2024
Grant date	Feb 13, 2024

Abstract

Aspects of the present disclosure involve a method, a system and a computer readable memory to perform a cryptographic operation that includes identifying a first set of mutually coprime numbers, obtaining a second set of input numbers coprime with a corresponding one of the first set of mutually coprime numbers, obtaining an output number that is a weighted sum of the second set of input numbers, each of the second set of input numbers being taken with a weight comprising a product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers, and performing the cryptographic operation using the output number.

First claim

What is claimed is:

1. A method comprising:
receiving a ciphertext that comprises a message encrypted with a public key associated with a key pair comprising the public key and a private key;
identifying, by a processing device, a first set of mutually coprime numbers;
obtaining, by the processing device, a second set of input numbers associated with the private key of the key pair, wherein each of the second set of input numbers is coprime with a corresponding one of the first set of mutually coprime numbers;
obtaining, by the processing device, an output number, wherein the output number is a weighted sum of the second set of input numbers, each of the second set of input numbers taken with a weight comprising a product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers;
obtaining, by the processing device, the private key using the output number; and
decrypting, by the processing device, the message using the ciphertext and the private key.

2. The method of claim 1 , wherein each of the first set of mutually coprime numbers is a prime number.

3. The method of claim 1 , wherein each of the second set of input numbers is taken with the weight that is equal to the product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers.

4. The method of claim 1 , wherein the weighted sum of the second set of input numbers is computed modulo a product of all of the first set of mutually coprime numbers.

5. The method of claim 1 , wherein obtaining the output number comprises performing a plurality of iterations, each of the plurality of iterations comprising updating an accumulator value, wherein updating the accumulator value comprises multiplying a current accumulator value by a next one of the first set of mutually coprime numbers.

6. The method of claim 5 , wherein updating the accumulator value further comprises adding, to the multiplied current accumulator value, a product of a next one of the second set of input numbers weighted with a running product of the first set of mutually coprime numbers.

7. The method of claim 6 , wherein each of the plurality of iterations further comprises updating the running product of the first set of mutually coprime numbers by multiplying the running product by the next one of the first set of mutually coprime numbers.

8. The method of claim 7 , wherein each of the plurality of iterations further comprises reducing the updated accumulator value modulo the updated running product.

9. The method of claim 5 , wherein obtaining the output number comprises reducing, modulo a product of all of the first set of mutually coprime numbers, the accumulator value after completion of the plurality of iterations.

10. The method of claim 1 , wherein obtaining the output number comprises performing one or more Montgomery multiplication operations.

11. The method of claim 1 , wherein obtaining the output number is performed without computing or loading, from a memory, a modular inverse number.

12. A method comprising:
receiving a ciphertext that comprises a message encrypted with a public key associated with a key pair comprising the public key and a private key;
identifying, by a processing device, a first set of mutually coprime numbers;
obtaining, by the processing device, a second set of input numbers associated with the private key of the key pair, wherein each of the second set of input numbers is quadratic non-residue modulo a corresponding one of the first set of mutually coprime numbers;
obtaining an output number, wherein the output number is a weighted sum of the second set of input numbers, each of the second set of input numbers taken with a weight comprising a square of a product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers;
using, by the processing device, the output number to generate a prime number;
obtaining, by the processing device, the private key using the output number; and
decrypting, by the processing device, the message using the ciphertext and the private key.

13. The method of claim 12 , wherein each of the first set of mutually coprime numbers is a prime number.

14. The method of claim 12 , wherein each of the second set of input numbers is taken with the weight that is equal to the product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers.

15. A system to perform a cryptographic operation, the system comprising:
a memory device; and
a processing device communicatively coupled to the memory device, the processing device to:
receive a ciphertext that comprises a message encrypted with a public key associated with a key pair comprising the public key and a private key;
identify a first set of mutually coprime numbers;
obtain a second set of input numbers associated with the private key of the key pair, wherein each of the second set of input numbers is coprime with a corresponding one of the first set of mutually coprime numbers;
obtain an output number, wherein the output number is a weighted sum of the second set of input numbers, each of the second set of input numbers taken with a weight comprising a product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers;
obtain the private key using the output number; and
decrypt the message using the ciphertext and the private key.

16. The system of claim 15 , wherein each of the second set of input numbers is taken with the weight that is equal to the product of all of the first set of mutually coprime numbers except the corresponding one of the first set of mutually coprime numbers.

17. The system of claim 15 , wherein to obtain the output number, the processing device is to perform a plurality of iterations, each of the plurality of iterations comprising updating an accumulator value, wherein updating the accumulator value comprises multiplying a current accumulator value by a next one of the first set of mutually coprime numbers.

18. The system of claim 17 , wherein updating the accumulator value further comprises adding, to the multiplied current accumulator value, a product of a next one of the second set of input numbers weighted with a running product of the first set of mutually coprime numbers.

19. The system of claim 18 , wherein each of the plurality of iterations further comprises updating the running product of the first set of mutually coprime numbers by multiplying the running product by the next one of the first set of mutually coprime numbers.

20. The system of claim 17 , wherein to obtain the output number, the processing device is to reduce, modulo a product of all of the first set of mutually coprime numbers, the accumulator value after completion of the plurality of iterations.

Assignees

• Cryptography Res Inc

Inventors

• Tunstall Michael
• Hamburg Michael Alexander
• Xiao Qinglai

Classifications

• H04L9/0861 Primary

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title

• G06F7/02

  Comparing digital values (G06F7/06, {G06F7/22,} G06F7/38 take precedence) · CPC title

• G06F7/72 Primary

  using residue arithmetic · CPC title

• G06F2207/7204

  Prime number generation or prime number testing · CPC title

• H04L9/3006

  underlying computational problems or public-key parameters · CPC title