Process and apparatus for finite field multiplication (FFM)
AssigneeSystemonic AG
InventorWolfram Drescher
Life of this patent
Estimating the term…
Abstract
Finite field multiplication of first and second Galois elements having n bit places and belonging to a Galois field GF 2n described by an irreducible polynomial is performed by forming an intermediate result Z of intermediate sums of partial products of bit width 2n−2 in an addition part of a Galois multiplier. The intermediate result Z is processed in a reduction part of a Galois multiplier by modulo dividing by the irreducible polynomial, whereby after all XOR's are traversed a result E with n bits is computed.
Claims25
A method for performing a finite field multiplication of a first Galois element a, having bit places a0 to an−1, provided to a first input register and a second Galois element b, having bit places b0 to bn−1, provided to a second input register, the Galois elements a and b belonging to a Galois field GF 2n described by an irreducible polynomial PR with bit places PR0 to PRn−1, comprising forming in an addition part of a Galois multiplier an intermediate result Z of intermediate sums of partial products of bit width 2n−1, said intermediate sums not representing any element of said Galois field, and processing said intermediate result Z in a reduction part of said Galois multiplier by modulo dividing by the irreducible polynomial PR, whereby the result E, with bit places En−1 to E0 is computed from the bit places resulting from the modulo dividing by XOR connections and wherein said modulo dividing is carried out in two steps, in a first process stage all bit places Z2n−2 to Zn are each AND connected with an expanded form PE of the irreducible polynomial PR having bit places PEn−1 to PE0 and then assembled by a first parallel operating adder tree structure effectively realizing the operation XOR, and these assembled partial results are subsequently each AND connected in a second process stage with the bit places PRn−1 to PR0 of the irreducible polynomial PR and using a second parallel-operating adder tree structure effecting the logic operation XOR, assembled with the bit places Zn−1 to Z0 of the intermediate result Z to form the result E with bit places En−1 to E0.
A finite field multiplier comprising a composite of individual cellular array multipliers assembled in a modulo reduction arrangement forming a most significant bit first matrix Galois multiplier, said Galois multipliers comprising an adder part, connected to first and second input registers, and including a partial product adder expansion structure and a partial product adder key structure connected together by first, second, third and fourth partial product expansion terminals;
- and a reducer part connected to receive an intermediate result output of said partial product adder and data derived from an irreducible polynomial PR, said reducer part arranged to combine said data and said intermediate result and provide a multiplication result to an output register.
Dependencies are inferred from the claim text.