Patent ID: 7543012

Claim:
A method to perform a squaring operation of an element A to output A 2 =C when a defining polynomial of a finite field GF(2 n ) is expressed as f ⁡ ( x ) = x n + ∑ i = 1 t ⁢ ⁢ x k i + 1 where n is odd, and the element A contained in the finite field is expressed as A=(a 0 ,a 1 ,a 2 , . . . ,a n−1 )∈GF(2 n ), and C=(c 0 ,c 1 , . . . , c n−1 )∈GF(2 n ), the method comprising: determining predefined coefficients V 0 , V ij , and V, and indices m i , I ij , such that the index m i satisfies a predetermined condition with respect to k i when 0≦i≦t is a natural number, the index I ij depends on n, k i , and j when 2≦j≦m i , the coefficients V 0 and V ij of n bits, respectively, depend on n, I ij , and k i , and obtaining the coefficient V with respect to m i according to the following formula, V i = V i ⁢ ⁢ 2 ⊕ V i ⁢ ⁢ 3 ⊕ … ⊕ V im i V = V 0 ⊕ ∑ m i ≠ 0 ⁢ V i ; determining a predefined coefficient s i according to k i and n and cyclically shifting the coefficient V by s i ; performing XOR operations on the cyclically shifted coefficient V and the element A; and rewiring terminals connected to receive a result of the XOR operations in a predefined order and outputting results of the squaring operation through the terminals as C.