Circuit for the inner or scalar product computation in Galois fields

• US 7,206,410 B2
• Filed: 10/10/2001
• Issued: 04/17/2007
• Est. Priority Date: 10/10/2001
• Status: Expired due to Fees

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Fragneto, Pasqualina, Bertoni, Guido, Breveglieri, Luca
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): Tran; Ellen C.
• Application Number:
  US09/974,176
• Publication Number:
  US 20030068037A1
• Time in Patent Office: 2,015 Days
• Field of Search: 380/262, 380/28, 380/255, 708/492, 708/491, 708/490
• US Class Current: 380/255
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A circuit for computing the inner of scalar product of two vectors in a finite Galois field defined by a generator polynomial, wherein each vector includes at least two elements belonging to said finite field, comprises one or more look-up tables storing digital words indicative of said possible combinations and said possible reductions. The digital words in question are defined as a function of the second elements of said vectors and the generator polynomial of the field. The input register(s) and the look-up table(s) are configured to co-operate in a plurality of subsequent steps to generate at each step a partial product result identified by at least one of digital word addressed in a corresponding look-up table as a function of the digital signals stored in the input register(s). The circuit also includes an accumulator unit for adding up the partial results generated at each step to give a final product result deriving from accumulation of said partial results.

Claims

1. A circuit for use in a cryptosystem for computing a scalar product of a plurality of vectors in a finite Galois field identified by a generator polynomial, each vector including at least a first and a second element belonging to the finite Galois field, the circuit comprising:

at least one input register for storing a plurality of digital signals representative of the first element of each of the plurality of vectors;

at least one look-up table for storing a plurality of digital words representing a plurality of combinations and reductions of the first and second elements of the plurality of vectors, each of the plurality of digital words being a function of the second elements of the plurality of vectors and the generator polynomial, the at least one look-up table cooperating with said at least one input register partial product results each identified by at least one of the plurality of digital words stored in said at least one look-up table and based upon the plurality of digital signals stored in said at least one input register; and

an accumulator unit for adding the partial product results to give the scalar product of the plurality of vectors in the finite Galois field identified by the generator polynomial of the cryptosystem based upon an accumulation of the partial product results.

2. A circuit according to claim 1, wherein said at least one input register is configured to be scanned, and wherein said at least one input register and said at least one look-up table cooperate until the scanning of the plurality of digital signals is completed, whereby upon completion of the scanning said accumulator unit contains the scalar product.

3. A circuit according to claim 1, wherein said at least one input register comprises first and second input registers, the first input register for storing a digital signal representative of a first element of one of the plurality of vectors and the second input register for storing a digital signal representative of a first element of another of the plurality of vectors.

4. A circuit according to claim 1, wherein the at least one look-up table comprises:

a first look-up table for storing first digital words generated as a function of the second element of one of the plurality of vectors and the generator polynomial;

a second look-up table for storing second digital words generated as a function of the second element of another of the plurality of vectors and the generator polynomial;

a third look-up table for storing third digital words generated as a function of the generator polynomial and corresponding to at least one of the plurality of reductions; and

wherein said first, second and third look-up tables cooperate with said at least one input register so that;

a first address for said first look-up table is generated as a function of one of the plurality of digital signals representative of the first element of one of the plurality of vectors stored in said at least one input register and a first digital word is read out from said first look-up table at the first address,

a second address for said second look-up table is generated as a function of another of the plurality of digital signals representative of the first element of another of the plurality of vectors stored in said at least one input register and a second digital word is read out from said second look-up table at the second address,

a third address for said third look-up table is generated as a function of contents of said accumulator unit and a third digital word is read out from said third look-up table at the third address, and

the first, second and third digital words are added to the contents of said accumulator unit.

5. A circuit according to claim 4, wherein the first, second and third addresses are generated as a result of a shift operation in said at least one input register and in said accumulator unit.

6. A circuit according to claim 4, wherein said at least one input register comprises a first input register for storing a digital signal representative of one of the plurality of vectors and a second input register for storing a digital signal representative of another of the plurality of vectors.

7. A circuit according to claim 1, wherein said at least one look-up table comprises:

a first look-up table for storing first combined digital words representative of all possible two-by-two sums of digital words generated as a function of the second element of one of the plurality of vectors and said generator polynomial, and digital words generated as a function of the second element of another of the plurality of vectors and said generator polynomial,

a second look-up table for storing second digital words generated as a function of said generator polynomial and corresponding to at least one of the plurality of reductions; and

wherein said first and second look-up tables cooperate with said at least one input register so that;

a first address for said first look-up table is generated as a function of a concatenation of two digital signals stored in said at least one input register, one of the two digital signals being representative of the first element of one of the plurality of vectors and another of the two digital signals being representative of the first element of another of the plurality of vectors, and a first digital word is read out from said first look-up table at the first address,

a second address for said second look-up table is generated as a function of contents of said accumulator unit and a second digital word is read out from said second look-up table at said second address, and

the first and second digital words are added to the contents of said accumulator unit.

8. A circuit according to claim 7, wherein the first and second addresses are generated as a result of a shift operation in said at least one input register and in said accumulator unit.

9. A circuit according to claim 7, wherein said at least one input register comprises a first input register for storing a digital signal representative of a first element of one of the plurality of vectors and a second input register for storing a digital signal representative of a first element of another one of the plurality of vectors.

10. A circuit according to claim 1, wherein said at least one look-up table comprises:

a single look-up table storing consolidated combined digital words representative of all the possible three-by-three sums of first digital words generated as a function of the second element of one of the plurality of vectors and the generator polynomial, second digital words generated as a function of the second element of another of the plurality of vectors and the generator polynomial, and third digital words generated as a function of the generator polynomial and corresponding to at least one of the plurality of reductions; and

wherein said single look-up table cooperates with said at least one input register so that;

a first address generating word is generated as a function of the concatenation of two digital signals stored in said at least one input register, one of the two digital signals being representative of the first element of one of the plurality of vectors and the other of the two digital signals being representative of the first element of the other of the plurality of vectors, and a first digital word is read out from said first look-up table,

a second address generating word is generated as a function of contents of said accumulator unit and a second digital word is read out from said second look-up table,

a third address is generated by concatenating the first and second address generating words and a third digital word is read out of said single look-up table at the third address, and

the third digital word is added to the contents of said accumulator unit.

11. A circuit according to claim 10, wherein said first and second address generating words are generated as a result of a shift operation in said at least one input register and in said accumulator unit.

12. A circuit according to claim 10, wherein said at least one input register comprises a first input register for storing a digital signal representative of a first element of one of the plurality of vectors and a second input register for storing a digital signal representative of a first element of another of the plurality of vectors.

13. A circuit for use in a cryptosystem for computing a scalar product of a plurality of vectors in a finite Galois field identified by a generator polynomial, each vector including at least a first and a second element belonging to the finite field, the circuit comprising:

at least one input register for storing digital signals representative of the first element of each of the plurality of vectors;

at least one look-up table for storing a plurality of digital words, each of the plurality of digital words based on the second elements of the plurality of vectors and the generator polynomial, the at least one look-up table cooperating with said at least one input register to generate at least two partial product results identified by the plurality of digital words stored in said at least one look-up table and based upon at least two digital signals stored in said at least one input register; and

an accumulator unit for adding the at least two partial product results to give the scalar product of the plurality of vectors in the finite Galois field identified by the generator polynomial of the cryptosystem.

14. A circuit according to claim 13, wherein the at least one look-up table comprises:

a first look-up table for storing first digital words based on the second element of one of the plurality of vectors and the generator polynomial;

a second look-up table for storing second digital words based on the second element of another of the plurality of vectors and the generator polynomial;

a third look-up table for storing third digital words based on the generator polynomial; and

wherein said first, second and third look-up tables cooperate with said at least one input register so that;

a first address for said first look-up table is generated based on the first element of one of the plurality of vectors and a first digital word is read out from said first look-up table at the first address,

a second address for said second look-up table is generated based on the first element of another of the plurality of vectors and a second digital word is read out from said second look-up table at the second address,

a third address for said third look-up table is generated based on contents of said accumulator unit and a third digital word is read out from said third look-up table at the third address, and

the first, second and third digital words are added to the contents of said accumulator unit.

15. A circuit according to claim 13, wherein said at least one look-up table comprises:

a first look-up table for storing first combined digital words representative of a two-by-two sum of a digital word based on the second element of one of the plurality of vectors and said generator polynomial, and a digital word based on the second element of another of the plurality of vectors and said generator polynomial;

a second look-up table for storing second digital words generated as a function of said generator polynomial; and

wherein said first and second look-up tables cooperate with said at least one input register so that;

a first address for said first look-up table is generated based on a concatenation of two digital signals stored in said at least one input register, one of the two digital signals being representative of the first element of one of the plurality of vectors and another of the two digital signals being representative of the first element of another of the plurality of vectors, and a first digital word is read out from said first look-up table at the first address,

a second address for said second look-up table is generated based on contents of said accumulator unit and a second digital word is read out from said second look-up table at said second address, and

the first and second digital words are added to the contents of said accumulator unit.

16. A circuit according to claim 13, wherein said at least one look-up table comprises:

a single look-up table for storing consolidated combined digital words representative a three-by-three sum of a first digital word based on the second element of one of the plurality of vectors and the generator polynomial, a second digital word based on the second element of another of the plurality of vectors and the generator polynomial, and a third digital word based on the generator polynomial; and

wherein said single look-up table cooperates with said at least one input register so that;

a first address generating word is generated as a function of the concatenation of two digital signals stored in said at least one input register, one of the two digital signals being representative of the first element of one of the plurality of vectors and the other of the two digital signals being representative of the first element of the other of the plurality of vectors, and a first digital word is read out from said first look-up table,

a second address generating word is generated as a function of contents of said accumulator unit and a second digital word is read out from said second look-up table,

a third address is generated by concatenating the first and second address generating words and a third digital word is read out of said single look-up table at the third address, and

the third digital word is added to the contents of said accumulator unit.

17. A method for computing an inner product of a plurality of vectors belonging to a set identified by a generator polynomial for use in a cryptosystem, each said vector having at least a first and a second element belonging to said set, the circuit comprising:

providing at least one input register for storing digital signals representative of the first element of each of the plurality of vectors;

configuring at least one look-up table to store digital words based on the second elements of each of the plurality of vectors and the generator polynomial, and to cooperate with said at least one input register to generate partial product results each identified by at least one of said digital words addressed in said at least one look-up table; and

summing the partial product results in an accumulator unit to give the inner product of the plurality of vectors in the finite Galois field identified by the generator polynomial of the cryptosystem deriving from accumulation of said partial results.

18. A method according to claim 17, further comprising scanning said at least one input register and detecting the condition of digital signals representative of the first element of the plurality of vectors;

configuring said at least one look-up table to cooperate until the scanning of the digital signals is completed; and

providing the scalar product in the accumulator unit upon completion of the scanning.

19. A method according to claim 17, wherein configuring at least one look-up table comprises:

configuring a first look-up table for storing first digital words based on the second element of one the plurality of vectors and the generator polynomial;

configuring a second look-up table for storing second digital words based on the second element of another of the plurality of vectors and the generator polynomial;

configuring a third look-up table for storing third digital words based on the generator polynomial and corresponding to at least on reduction with respect to said generator polynomial; and

configuring said first, second and third look-up tables to cooperate with said at least one input register such that;

a first address for said first look-up table is generated based on digital signals representative of the first element of one of the plurality of vectors and a first digital word is read out from said first look-up table at said first address,

a second address for said second look-up table is generated based on digital signals representative of the first element of another of the plurality of vectors and a second digital word is read out from said second look-up table at said second address,

a third address for said third look-up table is generated based on the contents of said accumulator unit and a third digital word is read out from said third look-up table at said third address, and

the first, second and third digital words are added to the contents of said accumulator unit.

20. A method according to claim 17, wherein configuring at least one look-up table comprises:

configuring a first look-up table for storing first combined digital words representative of a two-by-two sum of a first digital word based on the second element of one of the plurality of vectors and the generator polynomial and a second digital word based on the second element of another of the plurality of vectors and the generator polynomial;

configuring a second look-up table for storing second digital words based on said generator polynomial and corresponding to at least one reduction with respect to said generator polynomial; and

configuring said first and second look-up tables to cooperate with said at least one input register such that;

a first address for said first look-up table is generated based on the concatenation of two digital signals, one of the two digital signals representative of the first element of one of the plurality of vectors and the other of the two digital signals representative of another of the plurality of vectors, and a first digital word is read out from said first look-up table at said first address,

a second address for said second look-up table is generated based on the contents of said accumulator unit and a second digital word is read out from said second look-up table at said second address, and

said first and second digital words are added to the contents of said accumulator unit.

21. A method according to claim 17, wherein configuring at least one look-up table comprises:

configuring a single look-up table for storing consolidated combined digital words representative of a three-by-three sum of a first digital word based on the second element of one of the plurality of vectors and the generator polynomial, a second digital word based on the second element of another of the plurality of vectors and said generator polynomial, and third digital words based on the generator polynomial and corresponding to at least one reduction with respect to the generator polynomial; and

configuring said single look-up table to cooperate with said at least one input register such that;

a first address generating word is generated based on the concatenation of two digital signals, one of the two digital signals being representative of the first element of one of the plurality of vectors and the other of the two digital signals being representative of the first element of the other of the plurality of vectors, and a first digital word is read out from said first look-up table at said first address,

a second address generating word is generated based on the contents of said accumulator unit and a second digital word is read out from said second look-up table at said second address,

a single address is generated by concatenating the first and second address generating words and a single digital word is read out of said single look-up table at said single address, and

said single digital word is added to the contents of said accumulator unit.