US8649511B2ActiveUtilityA1
Method and processing circuit for dealing with galois field computation
Est. expiryJun 22, 2029(~3 yrs left)· nominal 20-yr term from priority
G06F 7/726H04L 9/0631H04L 2209/122
62
PatentIndex Score
2
Cited by
32
References
19
Claims
Abstract
A method for dealing with Galois Field computation includes: providing an operating circuit which has at least a multiplicative inverse unit; and using the multiplicative inverse unit to execute at least a plurality of isomorphism maps for deriving a multiplicative inverse at a specific Galois Field corresponding to an input data, wherein the plurality of isomorphism maps include at least a change of basis.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1. A method for dealing with Galois Field computation, comprising:
providing an operating circuit which has at least a multiplicative inverse unit; and
using the multiplicative inverse unit to execute at least a plurality of isomorphism maps for deriving a multiplicative inverse of an input data on a specific Galois Field, wherein the plurality of isomorphism maps comprise at least a change of basis, wherein providing the operating circuit comprises selecting coefficients of an irreducible polynomial for designing the multiplicative inverse unit,
wherein the coefficients are selected according to a Hamming weight, a power operation matrix, and the plurality of isomorphism maps,
wherein the irreducible polynomial is m(x)=x 2 +λx+ρ and wherein λ and ρ are the coefficients of the irreducible polynomial,
wherein the step of deriving the multiplicative inverse of the input data on the specific Galois Field comprises:
executing a first isomorphism map for transferring the input data from a polynomial basis over the specific Galois Field GF(2 K ) to a polynomial basis over a composite field GF(2 L ) M , wherein K=L*M;
executing a second isomorphism map for transferring from the polynomial basis over the composite field GF(2 L ) M to a normal basis over the specific Galois Field (2 K );
executing a power operation at the normal basis over the specific Galois Field GF(2 K ) for deriving a predetermined power of the input data;
executing a third isomorphism map for transferring the predetermined power of the input data to the polynomial basis over the composite field GF(2 L ) M ;
deriving a product of the input data after processing by the first isomorphism map, and the predetermined power of the input data after processing by the third isomorphism map;
deriving a multiple inverse of the product at a ground field GF (2 L );
deriving a product of the input data after processing by the third isomorphism map and the multiplicative inverse of the product for deriving a multiple inverse of the input data over the basic field GF(2 L ); and
executing a fourth isomorphism map for transferring the multiple inverse over the basic field GF(2 L ) from the polynomial basis over the composite field GF(2 L ) M to the polynomial basis over the specific Galois Field GF(2 K ).
2. The method of claim 1 , further comprising plural change of basis that include the at least the change in basis, wherein the plural change of basis comprises transformations between a polynomial basis, a polynomial composite basis, and a normal basis.
3. The method of claim 1 , wherein the plurality of isomorphism maps comprise a first isomorphism map, a second isomorphism map, a third isomorphism map, and a fourth isomorphism map; the first isomorphism map transfers from a polynomial basis over the specific Galois Field GF(2 K ) to a polynomial basis over a composite field GF(2 L ) M , wherein K=L*M; the second isomorphism map transfers from the polynomial basis over the composite field GF(2 L ) M to a normal basis over the specific Galois Field GF(2 K ); the third isomorphism map transfers from the normal basis over the specific Galois Field GF(2 K ) to a polynomial basis over the composite field GF(2 L ) M ; and the fourth isomorphism map transfers from the polynomial basis over the composite field GF(2 L ) M to a polynomial basis over the specific Galois Field GF(2 K ).
4. The method of claim 3 , wherein the composite field GF(2 L ) M is constructed by a Galois Field (finite field) GF(2 L ) and an M th order irreducible polynomial.
5. The method of claim 1 , wherein the step of deriving the multiplicative inverse of the input data on the specific Galois Field further comprises:
deriving the multiplicative inverse by executing the power operation on a normal basis over the composite field GF(2 L ) M .
6. The method of claim 5 , wherein the plurality of isomorphism maps and the power operation are linear operations, and the step of designing the multiplicative inverse unit comprises:
merging at least two linear operations of the linear operations to provide a corresponding transform matrix.
7. The method of claim 6 , wherein the specific Galois Field is a finite field GF(2 8 ) and the composite field GF(2 L ) M is a composite field GF(2 4 ) 2 .
8. The method of claim 7 , wherein the coefficients λ and ρ are chosen according to an equation as follows:
(
λ
,
ρ
)
=
arg
min
λ
,
ρε
GF
(
2
4
)
w
(
T
poly
comp
)
+
w
(
T
norm
comp
ST
comp
norm
)
+
w
(
T
comp
poly
)
+
4
w
(
ρ
)
,
where w is the Hamming weight, S is a matrix corresponding to the power operation, T poly comp is the first isomorphism map, T comp norm is the second isomorphism map, T norm comp is the third isomorphism map, T comp poly is the fourth isomorphism map, and the step of designing the multiplicative inverse unit merges the linear operations T norm comp , S and T comp norm to provide a corresponding transform matrix.
9. The method of claim 7 , wherein the operating circuit executes an S-box operation which complies with an advanced encryption standard (AES); the operating circuit further comprises an affine transform unit; the method further comprises:
utilizing the affine transform unit to execute an affine transform upon an output of the multiplicative inverse unit; and the step of designing the multiplicative inverse unit further comprises:
merging the second isomorphism map, the power operation, and the third isomorphism map to provide a corresponding first transform matrix; and
merging the fourth isomorphism map and a linear part of the affine transform to provide a corresponding second transform matrix.
10. The method of claim 9 , wherein the coefficients λ and ρ are chosen according to an equation as follows:
(
λ
,
ρ
)
=
arg
min
λ
,
ρε
GF
(
2
4
)
w
(
T
ploy
comp
)
+
w
(
T
norm
comp
ST
comp
norm
)
+
w
(
FT
comp
poly
)
+
4
w
(
ρ
)
,
where w is the Hamming weight, S is a matrix corresponding to the power operation, T poly comp is the first isomorphism map, T comp norm is the second isomorphism map, T norm comp is the third isomorphism map, T comp poly is the fourth isomorphism map, and F is the linear part of the affine transform.
11. The method of claim 7 , wherein the operating circuit executes an inverse S-box operation which complies with an advanced encryption standard (AES); the operating circuit further comprises an inverse affine transform unit; the method further comprises:
utilizing the inverse affine transform unit to execute an inverse affine transform to generate the input data to the multiplicative inverse unit; and the step of designing the multiplicative inverse unit further comprises:
merging a linear part of the inverse affine transform and the first isomorphism map to provide a corresponding first transform matrix; and
merging the second isomorphism map, the power operation, and the third isomorphism map to provide a corresponding second transform matrix.
12. The method of claim 11 , wherein the coefficients λ and ρ are chosen according to an equation as follows:
(
λ
,
ρ
)
=
arg
min
λ
,
ρε
GF
(
2
4
)
w
(
T
poly
comp
F
-
1
)
+
w
(
T
norm
comp
ST
comp
norm
)
+
w
(
T
comp
poly
)
+
4
w
(
ρ
)
,
where w is the Hamming weight, S is a matrix corresponding to the power operation, T poly comp is the first isomorphism map, T comp norm is the second isomorphism map, T norm comp is the third isomorphism map, T comp poly is the fourth isomorphism map, and F −1 is the linear part of the inverse affine transform.
13. The method of claim 7 , wherein the operating circuit utilizes the multiplicative inverse unit to execute both an S-box operation and an inverse S-box operation complied with an advanced encryption standard (AES); the operating circuit further comprises an affine transform unit and an inverse affine transform; the method further comprises:
utilizing the affine transform unit to execute an affine transform upon an output of the multiplicative inverse unit when the operating circuit executes the S-box operation, and utilizing the inverse affine transform unit to execute an inverse affine transform to generate the input data to the multiplicative inverse unit when the operating circuit executes the inverse S-box operation; and the step of designing the multiplicative inverse unit further comprises:
merging a linear part of the inverse affine transform and the first isomorphism map to provide a corresponding first transform matrix;
merging the second isomorphism map, the power operation, and the third isomorphism map to provide a corresponding second transform matrix; and
merging the fourth isomorphism map and a linear part of the affine transform to provide a corresponding third transform matrix.
14. The method of claim 13 , wherein the coefficients λ and ρ are chosen according to an equation as follows:
(
λ
,
ρ
)
=
arg
min
λ
,
ρε
GF
(
2
4
)
w
(
T
poly
comp
F
-
1
)
+
w
(
T
norm
comp
ST
comp
norm
)
+
w
(
FT
comp
poly
)
+
4
w
(
ρ
)
,
where w is the Hamming weight, S is a matrix corresponding to the power operation, T poly comp is the first isomorphism map, T comp norm is the second isomorphism map, T norm comp is the third isomorphism map, T comp poly is the fourth isomorphism map, F is the linear part of the affine transform, and F −1 is the linear part of the inverse affine transform.
15. The method of claim 3 , wherein the second isomorphism map comprises:
transferring from the polynomial basis over the composite field GF(2 L ) M to the polynomial basis over the specific Galois Field GF(2 K ); and
transferring from the polynomial basis over the specific Galois Field GF (2 K ) to the normal basis over the specific Galois Field GF(2 K ).
16. The method of claim 3 , wherein the third isomorphism comprises:
transferring from the normal basis over the specific Galois Field GF(2 K ) to the polynomial basis over the GF(2 K ); and
transferring from the polynomial basis over the specific Galois Field GF(2 K )to the polynomial basis over the composite field GF(2 L ) M .
17. A processing circuit for dealing with Galois Field computation, comprising:
a multiplicative inverse unit, for deriving a multiplicative inverse of an input data on a specific Galois Field, wherein the multiplicative inverse unit executes at least a plurality of isomorphism maps, and the plurality of isomorphism maps comprises at least a change of basis;
a plurality of selectors for sharing the multiplicative inverse unit for S-Box operations and inverse S-Box operations, wherein coefficients for the multiplicative inverse unit are selected according to a Hamming weight;
an affine transform unit for executing an affine transform upon an output of the multiplicative inverse unit when the operating circuit executes the S-box operation, wherein a first selector is coupled to the output of the affine transform unit; and
an inverse affine transform unit for executing an inverse affine transform to generate an input data to the multiplicative inverse unit when the operating circuit executes the inverse S-box operation, wherein a second selector is coupled to the output of the inverse affine transform unit.
18. The processing circuit of claim 17 , wherein the change of basis comprises a transformation between a polynomial basis and a normal basis.
19. A method for dealing with Galois Field computation, comprising:
providing an operating circuit which has at least a multiplicative inverse unit; and
using the multiplicative inverse unit to execute at least a plurality of isomorphism maps for deriving a multiplicative inverse of an input data on a specific Galois Field, wherein the plurality of isomorphism maps comprise at least a change of basis, wherein providing the operating circuit comprises selecting coefficients of an irreducible polynomial for designing the multiplicative inverse unit,
wherein the coefficients are selected according to a Hamming weight, a power operation matrix, and the plurality of isomorphism maps,
wherein the irreducible polynomial is m(x)=x 2 +λx+ρ and wherein λ and ρ are the coefficients of the irreducible polynomial,
wherein the plurality of isomorphism maps comprise a first isomorphism map, a second isomorphism map, a third isomorphism map, and a fourth isomorphism map; the first isomorphism map transfers from a polynomial basis over the specific Galois Field GF(2 K ) to a polynomial basis over a composite field GF(2 L ) M , wherein K=L*M; the second isomorphism map transfers from the polynomial basis over the composite field GF(2 L ) M to a normal basis over the specific Galois Field GF(2 K ); the third isomorphism map transfers from the normal basis over the specific Galois Field GF(2 K ) to a polynomial basis over the composite field GF(2 L ) M ; and the fourth isomorphism map transfers from the polynomial basis over the composite field GF(2 L ) M to a polynomial basis over the specific Galois Field GF(2 K ),
wherein the second isomorphism map comprises:
transferring from the polynomial basis over the composite field GF(2 L ) M to the polynomial basis over the specific Galois Field GF(2 K ); and
transferring from the polynomial basis over the specific Galois Field GF (2 K ) to the normal basis over the specific Galois Field GF(2 K ).Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.