Efficient method for multiplication over galois fields

• US 20030128841A1
• Filed: 12/04/2001
• Published: 07/10/2003
• Est. Priority Date: 08/04/2000
• Status: Active Grant

• Current Assignee: Innomedia Pte Ltd
• Original Assignee: Innomedia Pte Ltd
• Inventors: Ouyang, Jing Zheng
• Granted Patent: US 7,003,106 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

The improved AES processing method provides an efficient alternative to both Mips intensive multiplication and to conventional table lookup, used to multiply terms over a Galois field (GF). The improved method takes advantage of the fact that in the GF, any non zero element X can be represented by a power of a primitive element P. The improved method thereby results in a 2 by 256 table. The log base P of the terms being multiplied are looked up and summed, and the anti-log of the sum is looked up in the same table.

Claims

1. An improved method for encryption, comprising:

receiving original data to be encrypted;

performing cipher steps to process the original data into encrypted data, including;

looking up logs of terms being multiplied over a finite field;

summing the logs to obtain a sum; and

looking up the anti-log of the sum;

outputting the encrypted data.

2. The method of claim 1, wherein looking up the log of terms comprises looking up the log of terms in a primitive power and log table.

3. The method of claim 2, wherein looking up the anti-log of the sum comprises looking up the anti-log of the sum in the primitive power and log table.

4. The method of claim 2, wherein:

the finite field is a Galois field; and

looking up the log of terms in a primitive power and log table comprises looking up the log of terms in a primitive power and log table, of a primitive element of the Galois field.

5. The method of claim 1, wherein:

the encryption utilizes the AES algorithm, wherein the AES algorithm includes a Cipher and an Inverse Cipher, and wherein the Cipher includes a MixColumns transform, and wherein the Inverse Cipher includes an InvMixColumns transform; and

looking up the log of terms being multiplied comprises looking up the logs of terms being multiplied over a finite field in the MixColumns transform of the Cipher and in the InvMixColumns transform of the Inverse Cipher.

6. The method of claim 5, wherein looking up the logs of terms being multiplied over a finite field in the MixColumns transform of the Cipher and in the InvMixColumns transform of the Inverse Cipher comprises looking up the logs of terms being multiplied over a Galois field in the MixColumns transform of the Cipher and in the InvMixColumns transform of the Inverse Cipher.

7. The method of claim 1, wherein looking up the log of terms being multiplied over a finite field comprises looking up the log of terms being multiplied over a Galois field.

8. The method of claim 1, wherein looking up the log of terms comprises looking up the log of terms in a table comprising 2 rows.

9. The method of claim 1, further including:

transmitting the encrypted data;

receiving the encrypted data;

performing Inverse Cipher steps including;

looking up the log of terms being multiplied over the finite field;

summing the logs to obtain a sum;

looking up the anti-log of the sum; and

outputting the original data.

10. An encryption system comprising:

a first communications device adapted to receive original data and including;

means for encrypting the original data to generate encrypted data, including;

means for performing a MixColumns transform including;

means for looking up logs of terms being multiplied over a finite field;

means for summing the logs to obtain a sum;

means for looking up the anti-log of the sum; and

means for outputting the encrypted data.

11. The system of claim 10, wherein the means for encrypting the original data comprises a processor adapted to exercise the AES algorithm.

12. The system of claim 10, wherein the finite field is a Galois filed (2⁸).

13. An inverse encryption system comprising:

a second communications device adapted to receive encrypted data, and including;

means for inverse encrypting the encrypted data to generate original data, including;

means for performing an InvMixColumns transform including;

means for looking up logs of terms being multiplied over a finite field;

means for summing the logs to obtain a sum;

means for looking up the anti-log of the sum; and

means for outputting the original data.

14. The system of claim 13, wherein the means for encrypting the original data comprises a processor adapted to exercise the AES algorithm.

15. The system of claim 13, wherein the finite field is a Galois filed (2⁸).

16. An improved method for encryption including multiplication over a finite field, the improvement comprising:

obtaining the result of multiplication over the finite field using a primitive power and log table comprising 2 rows.

17. The method of claim 16, wherein obtaining the result of multiplication over a finite field comprises:

looking up logs of terms being multiplied over the finite field;

summing the logs to obtain a sum; and

looking up the anti-log of the sum.

18. The method of claim 16, wherein obtaining the result of multiplication over a finite field comprises obtaining the result of multiplication over a Galois field(2⁸) performed in the MixColumns transformation and in the InvMixColumns transformation of the AES algorithm, using a 2 by 256 primitive power and log table, comprising the steps of:

looking up logs of terms being multiplied over the Galois field(2⁸);

summing the logs to obtain a sum; and

looking up the anti-log of the sum.

19. The improvement of claim 16, wherein the primitive power and log table is based on a primitive is selected from the set consisting of the 128 primitives of the Galois field(2⁸).

20. The improvement of claim 16, wherein the improvement is implemented in C code.

21. The improvement of claim 16, wherein the improvement is implemented in assembly code in a Digital Signal Processing (DSP) chip.