Performing block form reductions modulo non-Mersenne primes in cryptographic protocols

1. A method of performing a cryptography protocol, the method comprising:

producing an integer during execution of a cryptography protocol defined by a cryptosystem;

identifying a prime modulus, a first constant and a second, distinct constant defined by the cryptosystem, wherein the prime modulus is defined by the cryptosystem in terms of a plurality of constants comprising the first constant and the second constant;

computing, by operation of one or more processors, a plurality of block coefficients to represent the integer in a block form, the plurality of block coefficients comprising:

a first block coefficient obtained by a first modular reduction modulo the first constant; and

a second block coefficient obtained by a second modular reduction modulo the second constant;

computing, by operation of one or more processors, a reduced representation of the integer based on the plurality of block coefficients, wherein the reduced representation is less than the prime modulus; and

using the reduced representation of the integer in the execution of the cryptography protocol in a communication system, wherein the execution of the cryptography protocol further comprises exchange of cryptographic correspondence over a communication network between a first computing device and a second computing device in the communication system.

2. The method of claim 1 , wherein computing the plurality of block coefficients comprises:

obtaining a quotient from the first modular reduction;

converting the quotient from a first number system representation to a second number system representation; and

applying the second modular reduction to the second number system representation of the quotient.

3. The method of claim 1 , wherein each of the plurality of constants has the form l i e i , where each l i represents a distinct prime less than the prime modulus, and each e i represents a respective integer value.

4. The method of claim 1 , wherein:

the prime modulus p has the form p=f(l 1 e 1 , . . . , l k e k ) where each l i represents a distinct prime for 1<i≤k, each e i represents a respective integer value for 1<i≤k, the plurality of constants is the set of l i e i for 1<i≤k, the first constant is l 1 e 1 , and the second constant is l 2 e 2 ; and

computing the plurality of block coefficients comprises performing at least one reduction modulo l i e i for 1<i≤k.

5. The method of claim 1 , wherein:

the prime modulus p has the form p=l 1 e 1 ⋅ . . . ⋅l k e k f±d, where each l i represents a distinct prime for 1<i≤k, each e i represents a respective integer value for 1<i≤k, the plurality of constants is the set of l i e i for 1<i≤k, the first constant is l 1 e 1 , the second constant is l 2 e 2 , and f and d represent integer values; and

computing the plurality of block coefficients comprises performing at least one reduction modulo l i e i for 1<i≤k.

6. The method of claim 1 , wherein the prime modulus p has the form p=ab±d, where the first constant is a, the second constant is b, the first constant a and the second constant b are relatively prime, and d represents an integer value.

7. The method of claim 1 , wherein the prime modulus p has the form p=2 e A 3 e B f±d, where the first constant is 2 e A , the second constant is 3 e B , and f and d represent integer values.

8. The method of claim 7 , comprising performing the first modular reduction in hardware by:

representing a first value in binary memory;

identifying a first block of the binary memory as a first remainder; and

identifying a second block of the binary memory as a first quotient,

wherein the method comprises identifying the first remainder as the first block coefficient.

9. The method of claim 8 , comprising converting the first quotient from a binary representation to a ternary representation, wherein the second modular reduction comprises reducing the ternary representation of the first quotient modulo the second constant 3 e B .

10. The method of claim 8 , comprising performing the second modular reduction in hardware by:

representing the first quotient in a ternary memory;

identifying a first block of the ternary memory as a second remainder; and

identifying a second block of the ternary memory as a second quotient,

wherein the method comprises identifying the second remainder as the second block coefficient.

11. The method of claim 7 , wherein:

computing a plurality of block coefficients comprises computing the first block coefficient c 0 , the second block coefficient c 1 , a third block coefficient c 2 , and a fourth block coefficient c 3 ;

the first block coefficient c 0 comprises a first remainder obtained by performing the first modular reduction modulo the first constant 2 e A ; and

the second block coefficient c 1 comprises a second remainder obtained by performing the second modular reduction modulo the second constant 3 e A .

12. The method of claim 7 , wherein:

computing a plurality of block coefficients comprises:

computing a first remainder c 0 and a first quotient d 0 by reducing the integer modulo the first constant 2 e A ;

computing a second remainder c 1 and a second quotient d 1 by reducing the first quotient d 0 modulo the second constant 3 e B ; and

computing a third remainder c 2 and a third quotient c 3 by reducing the second quotient d 1 modulo the first constant 2 e A ; and

computing the reduced representation of the integer based on the plurality of block coefficients comprises computing a sum (c 0 +c 2 )+(c 1 +c 3 )2 e A .

13. The method of claim 12 , wherein computing the reduced representation of the integer based on the plurality of block coefficients further comprises, in response to a determination that the sum is greater than or equal to the prime modulus, subtracting the prime modulus from the sum.

14. The method of claim 1 , wherein the prime modulus p has the form p=2 e A 3 e B f±d, where the first constant is 3 e B , the second constant is 2 e A , and f and d represent integer values.

15. The method of claim 14 , comprising performing the first modular reduction in hardware by:

representing a first value in ternary memory;

identifying a first block of the ternary memory as a first remainder; and

identifying a second block of the ternary memory as a first quotient,

wherein the method comprises identifying the first remainder as the first block coefficient.

16. The method of claim 15 , comprising converting the first quotient from a ternary representation to a binary representation, wherein the second modular reduction comprises reducing the binary representation of the first quotient modulo the second constant 2 e A .

17. The method of claim 15 , comprising performing the second modular reduction in hardware by:

representing the first quotient in a binary memory;

identifying a first block of the binary memory as a second remainder; and

identifying a second block of the binary memory as a second quotient,

wherein the method comprises identifying the second remainder as the second block coefficient.

18. The method of claim 14 , wherein:

computing a plurality of block coefficients comprises computing the first block coefficient c 0 , the second block coefficient c 1 , a third block coefficient c 2 , and a fourth block coefficient c 3 ;

the first block coefficient c 0 comprises a first remainder obtained by performing the first modular reduction modulo the first constant 3 e A ; and

the second block coefficient c 1 comprises a second remainder obtained by performing the second modular reduction modulo the second constant 2 e A .

19. The method of claim 14 , wherein:

computing a plurality of block coefficients comprises:

computing a first remainder c 0 and a first quotient d 0 by reducing the integer modulo the first constant 3 e B ;

computing a second remainder c 1 and a second quotient d 1 by reducing the first quotient d 0 modulo the second constant 2 e A ; and

computing a third remainder c 2 and a third quotient c 3 by reducing the second quotient d 1 modulo first constant 3 e B ; and

computing the reduced representation of the integer based on the plurality of block coefficients comprises computing a sum (c 0 +c 2 )+(c 1 +c 3 )3 e B .

20. The method of claim 1 , wherein:

the cryptosystem comprises a supersingular isogeny-based cryptosystem, the prime modulus represents a prime characteristic of a finite field defined by the supersingular isogeny-based cryptosystem;

the prime modulus p has the form p=l A e A l B e B f±1, where l A and l B are distinct prime integers and f is another integer;

the first constant is l A e A ; and

the second constant is l B e B .

21. The method of claim 20 , wherein the cryptography protocol comprises a supersingular isogeny-based key agreement protocol.

22. The method of claim 1 , further comprising storing the reduced representation of the integer in a ternary memory.

23. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations comprising:

producing an integer during execution of a cryptography protocol defined by a cryptosystem;

identifying a prime modulus, a first constant and a second, distinct constant defined by the cryptosystem, wherein the prime modulus is defined by the cryptosystem in terms of a plurality of constants comprising the first constant and the second constant;

computing a plurality of block coefficients to represent the integer in a block form, the plurality of block coefficients comprising:

a first block coefficient obtained by a first modular reduction modulo the first constant; and

a second block coefficient obtained by a second modular reduction modulo the second constant;

computing a reduced representation of the integer based on the plurality of block coefficients, wherein the reduced representation is less than the prime modulus; and

using the reduced representation of the integer in the execution of the cryptography protocol in a communication system, wherein the execution of the cryptography protocol further comprises exchange of cryptographic correspondence over a communication network between a first computing device and a second computing device in the communication system.

24. The non-transitory computer-readable medium of claim 23 , wherein computing the plurality of block coefficients comprises:

obtaining a quotient from the first modular reduction;

converting the quotient from a first number system representation to a second number system representation; and

applying the second modular reduction to the second number system representation of the quotient.

25. The non-transitory computer-readable medium of claim 23 , wherein:

the cryptosystem comprises a supersingular isogeny-based cryptosystem, the prime modulus represents a prime characteristic of a finite field defined by the supersingular isogeny-based cryptosystem;

the prime modulus p has the form p=l A e A l B e B f±1, where l A and l B are distinct prime integers and f is another integer;

the first constant is l A e A ; and

the second constant is l B e B .

26. The non-transitory computer-readable medium of claim 23 , wherein each of the plurality of constants has the form l i e i , where each l i represents a distinct prime less than the prime modulus, and each e i represents a respective integer value.

27. A system comprising:

one or more processors;

memory storing instructions that are operable when executed by the one or more processors to perform operations comprising:

producing an integer during execution of a cryptography protocol defined by a cryptosystem;

identifying a prime modulus, a first constant and a second, distinct constant defined by the cryptosystem, wherein the prime modulus is defined by the cryptosystem in terms of a plurality of constants comprising the first constant and the second constant;

computing a plurality of block coefficients to represent the integer in a block form, the plurality of block coefficients comprising:

a first block coefficient obtained by a first modular reduction modulo the first constant; and

a second block coefficient obtained by a second modular reduction modulo the second constant;

computing a reduced representation of the integer based on the plurality of block coefficients, wherein the reduced representation is less than the prime modulus; and

using the reduced representation of the integer in the execution of the cryptography protocol in a communication system, wherein the execution of the cryptography protocol further comprises exchange of cryptographic correspondence over a communication network between a first computing device and a second computing device in the communication system.

28. The system of claim 27 , wherein computing the plurality of block coefficients comprises:

obtaining a quotient from the first modular reduction;

converting the quotient from a first number system representation to a second number system representation; and

applying the second modular reduction to the second number system representation of the quotient.

29. The system of claim 27 , wherein:

the cryptosystem comprises a supersingular isogeny-based cryptosystem, the prime modulus represents a prime characteristic of a finite field defined by the supersingular isogeny-based cryptosystem;

the prime modulus p has the form p=l A e A l B e B f±1, where l A and l B are distinct prime integers and f is another integer;

the first constant is l A e A ; and

the second constant is l B e B .

30. The system of claim 27 , wherein each of the plurality of constants has the form l i e i , where each l i represents a distinct prime less than the prime modulus, and each e i represents a respective integer value.