Efficient method for multiplication over galois fields

• US 7,003,106 B2
• Filed: 12/04/2001
• Issued: 02/21/2006
• Est. Priority Date: 08/04/2000
• Status: Active Grant

• Current Assignee: Innomedia Pte Ltd
• Original Assignee: Innomedia Pte Ltd
• Inventors: Ouyang, Jing Zheng
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Pich, Ponnoreay
• Application Number:
  US10/005,291
• Publication Number:
  US 20030128841A1
• Time in Patent Office: 1,540 Days
• Field of Search: 714/784, 380/46
• 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 implemented via hardware circuit(s) including multiplication over a finite field, the improvement comprising:

obtaining the result of multiplication over a finite field using a primitive power and log table comprising 2 rows, wherein obtaining the result of multiplication over the 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.