Modular reduction device

Patent metadata

Field	Value
Publication number	US-10740068-B2
Application number	US-201816121775-A
Country	US
Kind code	B2
Filing date	Sep 5, 2018
Priority date	Sep 5, 2017
Publication date	Aug 11, 2020
Grant date	Aug 11, 2020

Abstract

A modular reduction device particularly for cryptography on elliptical curves. The device includes a Barrett modular reduction circuit and a cache memory in which the results of some precalculations are carried out. When the result is not present in the cache memory, a binary division circuit makes the precalculation and stores the result in the cache memory.

First claim

The invention claimed is:

1. A modular reduction device to calculate the remainder of an integer x divided by a modulo (q), said integer being represented by a binary word of 2n bits and the modulo (q) by a binary word of n bits, comprising:
a circuit configured to implement a generalised Barrett reduction algorithm, called a Barrett circuit,
a cache memory, and
a binary division circuit, the Barrett circuit receiving said integer and a result of a precalculation (μ) relative to a value of the modulo (q) and a power of 2 (2 n+α ), the result of the precalculation (μ) being supplied directly by the cache memory to the Barrett circuit if it is already stored relative to said value of the modulo (q), and otherwise being calculated by the binary division circuit before being stored in the cache memory and input to the Barrett circuit,
wherein the cache memory comprises a first part called a tag memory, and a second part called a data memory, the first and second parts being addressed by ƒ(q) wherein ƒ is a projection function of n bits on m bits with m<n, the first part storing a tag value q′ that was used to calculate ƒ(q′) at address ƒ(q′), and the second part storing said result of the precalculation (μ(q′)) at the same address.

2. The modular reduction device according to claim 1 , wherein the binary division circuit performs the precalculation

μ
=

⌊

2

n
+
α

q

⌋

wherein

⌊

2

n
+
α

q

⌋

is the largest integer smaller than or equal to

2

n
+
α

q

wherein 2 n+α is said power of 2 and α is an integer such that α≥n+1.

3. The modular reduction device according to claim 2 , wherein the Barrett circuit shifts the binary word representing x by α+β bits towards the low order bits, in which β is an integer such that β≥−2, then multiplies the binary word representing x thus shifted by the result of the precalculation (μ), then shifts the result of this multiplication again by α−β bits towards the low order bits to obtain a second word, said second word being multiplied by the modulo (q) before being subtracted from the binary word representing x to supply a provisional value r′ of a remainder r, a value of the remainder r being chosen equal to r′ if r′−q is negative or zero and equal to r′−q if r′−q is positive.

4. The modular reduction device according to claim 1 , wherein the cache memory also receives the integer x and also provides the result of the precalculation (μ) for a value of the modulo (q), a sign value associated with an (x,q) pair, this sign value being input to the Barrett circuit.

5. The modular reduction device according to claim 4 , wherein the binary division circuit performs a precalculation

μ
=

⌊

2

n
+
α

q

⌋

wherein

⌊

2

n
+
α

q

⌋

is a largest integer smaller than or equal to

2

n
+
α

q

wherein 2 n+α is said power of 2 and α is an integer such that α≥n+1.

6. The modular reduction device according to claim 5 , wherein the Barrett circuit shifts the binary word representing x by α+β bits towards the low order bits, wherein β is an integer such that β≥−2, then multiplies the binary word representing x thus shifted by the result of the precalculation (μ), then shifts the result of this multiplication by another α−β bits towards the low order bits to obtain a second word, the sign value b being subtracted from the second word before it is multiplied by the modulo (q), the result of this multiplication then being subtracted from the integer x to give said remainder r.

7. The modular reduction device according to claim 1 , comprising a second cache memory receiving the integer x and the modulo (q) and outputting a sign value b stored at an address in relation to an (x,q) pair, the sign value b being input to the Barrett circuit.

8. The modular reduction device according to claim 7 , wherein the second cache memory comprises a second tag memory and a second data memory, the second tag and second data memories both being addressed by h (x,q) wherein h is a projection function of 3n bits onto m bits in which m<3n, the second tag memory storing a tag value (x′,q′) used to calculate h(x′,q′) at address h(x′,q′), and the second data memory storing said sign value (b (x′,q′)) associated with the tag value (x′,q′), at the same address h(x′,q′).

9. The modular reduction device according to claim 8 , wherein the sign value is b provided directly by the second cache memory to the Barrett circuit if the modulo value (q) is stored in the tag memory and the (x,q) pair is stored in the second tag memory, and otherwise the sign value b is obtained from the modulo value (q) and the integer x, the sign value b then being input to the Barrett circuit.

10. The modular reduction device according to claim 7 , wherein the second cache memory comprises a second data memory but does not comprise a tag memory, and the device comprises a comparator to verify if an output r from the Barrett circuit satisfies a condition 0≤r<q and that a sign value thus obtained (b (x,q)) is stored in the second data memory at address h (x,q) in relation to the (x,q) pair, wherein h is a projection function of 3n bits onto m bits wherein m<3n, is inverted if said condition is not satisfied.

11. A modular reduction device to calculate the remainder of an integer x divided by a modulo (q), said integer being represented by a binary word of 2n bits and the modulo (q) by a binary word of n bits, comprising:
a circuit configured to implement a generalised Barrett reduction algorithm, called a Barrett circuit,
a cache memory, and
a binary division circuit, the Barrett circuit receiving said integer and a result of a precalculation (μ) relative to a value of the modulo (q) and a power of 2 (2 n+α ), the result of the precalculation (μ) being supplied dir

Assignees

• Commissariat Energie Atomique

Inventors

• Hiscock Thomas

Classifications

• H04L2209/122

  Hardware reduction or efficient architectures · CPC title

• H04L9/302

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

• H04L9/3013

  involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems · CPC title

• G06F7/38

  Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation · CPC title

• G09C1/00

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title