Data processing apparatus and method for reducing the size of a lookup table

• US 8,943,118 B2
• Filed: 07/31/2012
• Issued: 01/27/2015
• Est. Priority Date: 07/31/2012
• Status: Active Grant

• Current Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Original Assignee: Arm Ltd. (United Kingdom) (SoftBank Group Corp.)
• Inventors: Burgess, Neil, Lutz, David Raymond
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US13/562,497
• Publication Number:
  US 20140040334A1
• Time in Patent Office: 910 Days
• Field of Search: 708/492
• US Class Current: 708/492
• CPC Class Codes: G06F 1/0353 by using symmetrical properties of the function, e.g. using most significant bits for quadrant control
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• 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

A lookup table receives an n-bit input value and returns an output value that would be obtained by performance of a predetermined operation on the input value. The number of entries in the lookup table is less than 2ⁿ. An n-bit input data value is received, a modification condition is detected if any of a predetermined number of significant bits of the input data value are logic zeroes, and a shift operation is performed on the input data value if the modification condition is detected, prior to providing the input to the lookup table. If the modification condition is detected, an output value derivation operation is performed on the output value received from the lookup table to modify it prior to returning it to for processing. The derivation operation accounts for the shift operation. This approach can lead to a significant reduction in the lookup table size.

Claims

1. A data processing apparatus, comprising:

processing circuitry configured to perform operations on data; and

lookup table circuitry configured to receive from the processing circuitry an n-bit input data value, and to return to the processing circuitry an output data value that would be obtained by performance of a predetermined operation on said input data value, the predetermined operation having a first property that the output data value is a function of the input data value, and a second property that a first output data value produced for a first input data value is derivable from a second output data value produced for a second input data value, the lookup table circuitry comprising;

a lookup table including a plurality of entries, each entry identifying a possible input data value and a corresponding output data value, said plurality of entries being less than 2ⁿ;

input interface circuitry configured to receive the n-bit input data value and to generate an intermediate input data value for provision to the lookup table, the input interface circuitry being configured to detect a modification condition if any of a predetermined number of significant bits of the input data value are logic zero values, the input interface circuitry being configured, if said modification condition is not detected, to retain the input data value as the intermediate input data value, and being configured, if said modification condition is detected, to perform a shift operation on the input data value in order to generate said intermediate input data value;

output interface circuitry configured to receive from the lookup table an intermediate output data value corresponding to the intermediate input data value generated by the input interface circuitry, and to generate, from the intermediate output data value, the output data value to be returned to the processing circuitry;

the output interface circuitry being configured, if said modification condition is not detected by the input interface circuitry, to retain the intermediate output data value as said output data value, and being configured, if said modification condition is detected by the input interface circuitry, to perform an output data value derivation operation on the intermediate output data value in order to generate said output data value, the output data value derivation operation at least taking account of the shift operation performed by the input interface circuitry.

2. A data processing apparatus as claimed in claim 1, wherein said predetermined operation is a multiplicative inverse operation.

3. A data processing apparatus as claimed in claim 2, wherein the processing circuitry is configured to implement one of an AES encryption process and an AES decryption process.

4. A data processing apparatus as claimed in claim 1, wherein the input interface circuitry is configured to detect said modification condition if any of a predetermined number of most significant bits of the input data value are logic zero values, and the shift operation is a left shift operation.

5. A data processing apparatus as claimed in claim 1, wherein said output data value derivation operation comprises a shift of the intermediate output data value by the same number of bits as the associated input data value was shifted by said shift operation in order to produce a modified intermediate output data value, and then an adjustment operation on the modified intermediate output data value if a logic 1 value was present in a predetermined number of significant bits of the intermediate output data value.

6. A data processing apparatus as claimed in claim 5, wherein said adjustment operation comprises addition of at least one predetermined constant to said modified intermediate output data value.

7. A data processing apparatus as claimed in claim 6, wherein said predetermined operation is a finite field arithmetic operation, and said adjustment operation includes an exclusive OR operation.

8. A data processing apparatus as claimed in claim 1, wherein the input interface circuitry is configured to detect said modification condition if any of said predetermined number of most significant bits of the input data value are logic zero values, and the immediately following most significant bit is a logic one value.

9. A data processing apparatus as claimed in claim 8, wherein the input interface circuitry is configured to detect said modification condition if the most significant two bits of the input data value are “

01”

.

10. A data processing apparatus as claimed in claim 9, wherein said lookup table includes ¾

×

2ⁿ entries.

11. A data processing apparatus as claimed in claim 9, wherein said shift operation is a one-bit left shift operation.

12. A data processing apparatus as claimed in claim 11, wherein said output data value derivation operation comprises a one-bit left shift on the intermediate output data value in order to produce a modified intermediate output data value, and then addition of a predetermined constant to the modified intermediate output data value if the most significant bit of the intermediate output data value was a logic 1 value.

13. A method of configuring lookup table circuitry to receive from processing circuitry an n-bit input data value, and to return to the processing circuitry an output data value that would be obtained by performance of a predetermined operation on said input data value, the predetermined operation having a first property that the output data value is a function of the input data value, and a second property that a first output data value produced for a first input data value is derivable from a second output data value produced for a second input data value, the method comprising:

providing a lookup table having a plurality of entries, each entry identifying a possible input data value and a corresponding output data value, said plurality of entries being less than 2ⁿ;

generating, from the n-bit input data value, an intermediate input data value for provision to the lookup table, by;

(i) detecting a modification condition if any of a predetermined number of significant bits of the input data value are logic zero values;

(ii) if said modification condition is not detected, retaining the input data value as the intermediate input data value; and

(iii) if said modification condition is detected, performing a shift operation on the input data value in order to generate said intermediate input data value;

receiving from the lookup table an intermediate output data value corresponding to the generated intermediate input data value;

generating, from the intermediate output data value, the output data value to be returned to the processing circuitry by;

(a) if said modification condition is not detected in said step (i), retaining the intermediate output data value as said output data value;

(b) if said modification condition is detected in said step (i), performing an output data value derivation operation on the intermediate output data value in order to generate said output data value, the output data value derivation operation at least taking account of the shift operation performed in said step (iii).

14. A data processing apparatus, comprising:

processing means for performing operations on data; and

lookup means for receiving from the processing means an n-bit input data value, and for returning to the processing means an output data value that would be obtained by performance of a predetermined operation on said input data value, the predetermined operation having a first property that the output data value is a function of the input data value, and a second property that a first output data value produced for a first input data value is derivable from a second output data value produced for a second input data value, the lookup means comprising;

lookup table means for providing a plurality of entry means, each entry means for identifying a possible input data value and a corresponding output data value, said plurality of entry means being less than 2ⁿ;

input interface means for receiving the n-bit input data value and for generating an intermediate input data value for provision to the lookup table means, the input interface means for detecting a modification condition if any of a predetermined number of significant bits of the input data value are logic zero values, the input interface means, if said modification condition is not detected, for retaining the input data value as the intermediate input data value, and, if said modification condition is detected, for performing a shift operation on the input data value in order to generate said intermediate input data value;

output interface means for receiving from the lookup table means an intermediate output data value corresponding to the intermediate input data value generated by the input interface means, and for generating, from the intermediate output data value, the output data value to be returned to the processing means;

the output interface means, if said modification condition is not detected by the input interface means, for retaining the intermediate output data value as said output data value, and, if said modification condition is detected by the input interface means, for performing an output data value derivation operation on the intermediate output data value in order to generate said output data value, the output data value derivation operation at least taking account of the shift operation performed by the input interface means.

15. Lookup table circuitry for use by processing circuitry performing operations on data, the lookup table circuitry being configured to receive from the processing circuitry an n-bit input data value, and to return to the processing circuitry an output data value that would be obtained by performance of a predetermined operation on said input data value, the predetermined operation having a first property that the output data value is a function of the input data value, and a second property that a first output data value produced for a first input data value is derivable from a second output data value produced for a second input data value, the lookup table circuitry comprising:

a lookup table including a plurality of entries, each entry identifying a possible input data value and a corresponding output data value, said plurality of entries being less than 2ⁿ;

input interface circuitry configured to receive the n-bit input data value and to generate an intermediate input data value for provision to the lookup table, the input interface circuitry being configured to detect a modification condition if any of a predetermined number of significant bits of the input data value are logic zero values, the input interface circuitry being configured, if said modification condition is not detected, to retain the input data value as the intermediate input data value, and being configured, if said modification condition is detected, to perform a shift operation on the input data value in order to generate said intermediate input data value;

output interface circuitry configured to receive from the lookup table an intermediate output data value corresponding to the intermediate input data value generated by the input interface circuitry, and to generate, from the intermediate output data value, the output data value to be returned to the processing circuitry;

the output interface circuitry being configured, if said modification condition is not detected by the input interface circuitry, to retain the intermediate output data value as said output data value, and being configured, if said modification condition is detected by the input interface circuitry, to perform an output data value derivation operation on the intermediate output data value in order to generate said output data value, the output data value derivation operation at least taking account of the shift operation performed by the input interface circuitry.