Implementation of a switch-box using a subfield method

• US 20060093136A1
• Filed: 10/28/2004
• Published: 05/04/2006
• Est. Priority Date: 10/28/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Zhang, Ming, Nemat, Awais Bin
• Granted Patent: US 7,532,721 B2
• Time in Patent Office: Days
• US Class Current: 380/29
• CPC Class Codes: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms

Abstract

Methods and systems for implementing a switch box (S-box) in a cryptographic application are described. An input to the S-box is converted from a Galois field representation GF(N²) to a Galois subfield representation GF(N)². The input is converted using a generating polynomial of the form x²+Ax+B, where A and B are elements in GF(N) and where A has a value other than unity. The multiplicative inverse of the Galois subfield representation GF(N)² is determined. The multiplicative inverse is converted back to the Galois field representation GF(N²). An affine transformation of the multiplicative inverse is then performed.

Claims

1. A method of implementing a switch box (S-box) in a cryptographic application, said method comprising:

converting an input to said S-box from a Galois field representation GF(N²) to a Galois subfield representation GF(N)², wherein said converting of said input uses a generating polynomial of the form x²+Ax+B, wherein A and B are elements in GF(N) and wherein A has a value other than unity;

determining the multiplicative inverse of said Galois subfield representation GF(N)²;

converting said multiplicative inverse back to said Galois field representation GF(N²); and

performing an affine transformation of said multiplicative inverse after said converting of said multiplicative inverse back to said Galois field representation GF(N²).

2. The method of claim 1 wherein A has a value of (0010) and wherein B has a value of (0010).

3. The method of claim 1 wherein said cryptographic application is substantially compliant with the Advanced Encryption Standard (AES).

4. The method of claim 1 wherein N is 16.

5. The method of claim 1 wherein said multiplicative inverse is represented as a first matrix, wherein said converting said multiplicative inverse uses a second matrix and said affine transformation uses a third matrix, wherein said third matrix is multiplied by said second matrix to produce a fourth matrix that is multiplied by said first matrix.

6. The method of claim 1 wherein values for A and B are selected so that said Galois subfield representation GF(N)² is isomorphic to said Galois field representation GF(N²).

7. The method of claim 1 further comprising:

performing an inverse affine transformation of a second input received at a reverse S-box;

converting said second input from a second Galois field representation GF(N²) to a second Galois subfield representation GF(N)², wherein said converting uses said generating polynomial of the form x²+Ax+B;

determining the multiplicative inverse of said second Galois subfield representation GF(N)²; and

converting said multiplicative inverse back to said second Galois field representation GF(N²).

8. A computer-usable medium having computer-readable program code embodied therein for causing a computer system to perform a cryptographic method, said cryptographic method comprising:

converting an input to a switch box (S-box) from a Galois field representation GF(N²) to a Galois subfield representation GF(N)², wherein said converting uses an irreducible generating polynomial of the form x²+Ax+B, wherein A and B are elements in GF(N) and wherein A has a value other than unity;

determining the multiplicative inverse of said Galois subfield representation GF(N)²;

converting said multiplicative inverse back to said Galois field representation GF(N²); and

performing an affine transformation of said multiplicative inverse after said converting of said multiplicative inverse back to said Galois field representation GF(N²).

9. The computer-usable medium of claim 8 wherein A has a value of (0010) and wherein B has a value of (0010).

10. The computer-usable medium of claim 8 wherein said cryptographic method is substantially compliant with the Advanced Encryption Standard (AES).

11. The computer-usable medium of claim 8 wherein N is 16.

12. The computer-usable medium of claim 8 wherein said multiplicative inverse is represented as a first matrix, wherein said converting said multiplicative inverse uses a second matrix and said affine transformation uses a third matrix, wherein said third matrix is multiplied by said second matrix to produce a fourth matrix that is multiplied by said first matrix.

13. The computer-usable medium of claim 8 wherein values for A and B are selected so that said Galois subfield representation GF(N)² is isomorphic to said Galois field representation GF(N²).

14. A system for implementing a switch box (S-box) in a cryptographic application, said system comprising:

means for converting an input to said S-box from a Galois field representation GF(N²) to a Galois subfield representation GF(N)², wherein said means for converting said input uses a generating polynomial of the form x²+Ax+B, wherein A and B are elements in GF(N) and wherein A has a value other than unity;

means for determining the multiplicative inverse of said Galois subfield representation GF(N)²;

means for converting said multiplicative inverse back to said Galois field representation GF(N²); and

means for performing an affine transformation of said multiplicative inverse after said means for converting converts said multiplicative inverse back to said Galois field representation GF(N²).

15. The system of claim 14 wherein A has a value of (0010) and wherein B has a value of (0010).

16. The system of claim 14 wherein said cryptographic application is substantially compliant with the Advanced Encryption Standard (AES).

17. The system of claim 14 wherein N is 16.

18. The system of claim 14 wherein said multiplicative inverse is represented as a first matrix, wherein said means for converting said multiplicative inverse uses a second matrix and said means for performing said affine transformation uses a third matrix, wherein said third matrix is multiplied by said second matrix to produce a fourth matrix that is multiplied by said first matrix.

19. The system of claim 14 wherein values for A and B are selected so that said Galois subfield representation GF(N)² is isomorphic to said Galois field representation GF(N²).

20. The system of claim 14 further comprising:

means for performing an inverse affine transformation of a second input received at a reverse S-box;

means for converting said second input from a second Galois field representation GF(N²) to a second Galois subfield representation GF(N)², wherein said means for converting said second input uses said generating polynomial of the form x²+Ax+B;

means for determining the multiplicative inverse of said second Galois subfield representation GF(N)²; and

means for converting said multiplicative inverse of said second Galois subfield representation GF(N)² back to said second Galois field representation GF(N²).

21. A system for implementing a switch box (S-box) in a cryptographic application, said system comprising:

circuitry for converting an input to said S-box from a Galois field representation GF(N²) to a Galois subfield representation GF(N)², wherein said converting of said input uses a generating polynomial of the form x²+Ax+B, wherein A and B are elements in GF(N) and wherein A has a value other than unity; and

circuitry for converting the multiplicative inverse of said Galois subfield representation GF(N)² back to said Galois field representation GF(N²) and for performing an affine transformation of said multiplicative inverse after said converting of said multiplicative inverse back to said Galois field representation GF(N²), wherein said multiplicative inverse is determined using a lookup table.

22. The system of claim 21 wherein A has a value of (0010) and wherein B has a value of (0010).

23. The system of claim 21 wherein said cryptographic application is substantially compliant with the Advanced Encryption Standard (AES).

24. The system of claim 21 wherein N is 16.

25. The system of claim 21 wherein values for A and B are selected so that said Galois subfield representation GF(N)² is isomorphic to said Galois field representation GF(N²).

26. The system of claim 21 wherein said multiplicative inverse is represented as a first matrix, wherein said converting of said multiplicative inverse uses a second matrix and said affine transformation uses a third matrix, wherein said third matrix is multiplied by said second matrix to produce a fourth matrix that is multiplied by said first matrix.