Cryptographic method and apparatus for non-linearly merging a data block and a key

• US 7,079,651 B2
• Filed: 08/08/2001
• Issued: 07/18/2006
• Est. Priority Date: 05/20/1996
• Status: Expired due to Fees

• Current Assignee: Irdeto B.V. (MultiChoice Group Ltd.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Den Boer, Huibert
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Parthasarathy, Pramila
• Application Number:
  US09/924,990
• Publication Number:
  US 20020034295A1
• Time in Patent Office: 1,805 Days
• Field of Search: 380/28, 380/29, 380/277, 713/193, 707 1- 10
• US Class Current: 380/37
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI

Abstract

A method and apparatus for cryptographically converting a digital input data block into a digital output data block. The apparatus has an input for supplying the input data block and a further input for supplying a code conversion digital key K1. Cryptographic processing merges a selected part M1 of the digital input data block with the key K1 to produce a data block B1 that is non-linearly dependent on M1 and K1. The merging is performed in one sequentially inseparable step. The digital output block is derived from a selected part of the data block B1.

Claims

1. A program segment stored on a computer readable medium for cryptographically converting a digital input data block M into a digital output data block;

said program segment comprising;

a program portion for merging a selected part M1 of said digital input data block M with a first digital key B1 to produce a data block B1 which non-linearly depends on said selected part M1 and said first digital key K1; and

a program portion for deriving said digital output block from said data block B1 end the remaining part of the digital input data block M, wherein said merging step is performed by executing a non-linear function g for non-linearly merging said selected part M1 and said first key K1 in a single step.

2. A program segment as claimed in claim 1, comprising:

a program portion for splitting said digital input block into said selected part M1 and a second part M2 before executing said program portion for merging;

a program portion for executing a non-linear function g<sup>−

1</sup> to merge said second block M2 with a second key K2 in one step, producing a data block B2 as output;

said non-linear function g<sup>−

1</sup> being the inverse of said non-linear function g; and

a program portion for forming combined data from data in said data black B1 and in said data block B2;

said digital output block being derived from said combined data.

3. A program segment as claimed in claim 1, wherein said program portion for merging comprises:

a program portion for splitting said selected part M1 in a first plurality n of sub-blacks m₀, . . . , m<sub>n−

1</sub> of equal length;

a program portion for splitting said first key K1 in said first plurality n of sub-keys k₀, . . . , k<sub>n−

1</sub> having equal length, the sub-key K1 corresponding to the sub-block m₁, for i=0 to n−

1;

a program portion for separately processing each of said sub-blocks m_i by executing for each of said sub-blocks m_i a same non-linear function h for non-linearly merging a sub-block b_i derived from said sub-block m_i with said corresponding sub-key k_i in one, sequentially inseparable step and producing said first plurality of output sub-blocks h(b_i, k_i); and

a program portion for combining sub-blocks t_i derived from said first plurality of said output sub-blocks h(b_i, k_i) to form said data block B1.

4. A program segment as claimed in claim 2, wherein said program portion for executing said non-linear function g⁻

1 comprises;

a program portion for splitting said second part M2 in said first plurality n of sub-blocks m_n, . . . , m<sub>2n−

1</sub>, having equal length;

a program portion for splitting said key K2 in said first plurality n of sub-keys k_n, . . . , k<sub>2n −

1</sub>, having equal length, the sub-key k_i corresponding to the sub-block m_i, for i=n to 2n−

1;

a program portion for executing for each of said sub-blocks m_i a same non-linear function h<sup>−

1</sup> for non-linearly merging a sub-block b_i derived from said sub-block m_i with said corresponding sub-key k_i and producing said first plurality of an output sub-block h<sup>−

1</sup>(b_i, k_i);

said function h<sup>−

1</sup> being the inverse of said function h; and

a program portion for combining sub-blocks t_i derived from said first plurality of output sub-blocks h<sup>−

1</sup>(b_i, k_i) to form said data block B2.

5. A program segment as claimed in claim 3, wherein said sub-block b_i is derived from said sub-block m_i by bit-wise adding a constant p_i to said sub-block m_i, said constant p_i having equal length as said sub-block m_i.

6. A program segment as claimed in claim 3, characterised in that said function h(b_i,k_i) is defined by:

h(b_i,k_i)=(b_i,k_i)<sup>−

1</sup>, if b_i≠

0, k_i≠

0, and b_i≠

k_i

h(b_i,k_i)=(k_i)<sup>−

2</sup>, if b_i=0

h(b_i,k_i)=(b_i)<sup>−

2</sup>, if k_i=0

h(b_i,k_i)=0, if b_i=k_i,

where the multiplication and inverse operations are predetermined Galois Field multiplication and inverse operations.

7. A program segment as claimed in claim 6, wherein deriving said sub-blocks t_i from said output sub-blocks h(b_i, k_i) comprises bit-wise adding a constant d_i to said output sub-block h(b_i,k_i), said constant d_i having equal length as said sub-block m_i.

8. A program segment as claimed in claim 7, wherein deriving said sub-blocks t_i from said output sub-blocks h(b_i, k_i) further comprises raising h(b_i,k_i)⊕

d_i to a power 2¹, using said predetermined Galois Field multiplication.

9. A program segment as claimed in claim 6, wherein deriving said sub-blocks t_i from said output sub-blocks h(b_i, k_i) comprises raising said output sub-block h(b_i,k_i) to a power 2ⁱ, using said predetermined Galois Field (GF) multiplication.

10. A program segment as claimed in claim 4, wherein said combined data is formed by:

swapping the sub-blocks t_i and t<sub>2n−

1−

i</sub>, for i =0 to n−

1.

11. A program segment as claimed in claim 6, wherein said sub-block m_i comprises eight data bits, and wherein said multiplying of two elements b and c of GF(2⁸) comprises executing a series of multiplications and additions in GF(2⁴).

12. A program segment as claimed in claim 11, wherein said multiplying of said two elements b and c comprises:

representing b as a₀+a₁.D and c as a₂+a₃.D, where a₀, a₁, a₂ and a₃ are elements of GF(2⁴), and where D is an element of GF(2⁸) defined as a root of an irreducible polynomial k(x)=x²+x+β

over GF(2⁴) where β

is an element of GF(2⁴); and

calculating (a₀a₂+a₁a₃β

)+(a₁a₂+a₀a₃+a₁a₃).D.

13. A program segment as claimed in claim 12, wherein β

is a root of an irreducible polynomial h(x)=x⁴+x³+x²+x+1 over GF(2).

14. A program segment as claimed in claim 6, wherein said sub-block m_i comprises eight data bits, and wherein calculating the inverse of an element b of GF(2⁸) comprises performing a series of calculations in GF(2⁴).

15. A program segment as claimed in claim 14, wherein calculating the inverse of said element b comprises:

representing b as a₀+a₁.D, where a₀ and a₁ are elements of GF(2⁴), and where D is an element of GF(2⁸) defined as a root of an irreducible polynomial k(x)=x²+x+β

over GF(2⁴), where β

is an element of GF(2⁴); and

calculating (a₀²+a₀a₁+a₁²β

<sup>−

1</sup> ((a₀+a₁)+a₁D).

16. A processor for cryptographically converting a digital input block into a digital output block, said processor comprising:

a first input means for obtaining said digital input block;

a second input means for obtaining a first key K1; and

a cryptographic processing means for converting the digital input block into the digital output block by executing a non-linear funtion g for non-linearly merging said selected part M1 and said first key K1 in one step and producing a data block B1 which non-linearly depends on said selected part M1 and said first key K1, where a selected part of said digital output block is derived from said data block B1.

17. A processor as claimed in claim 16, wherein said processor comprises a third input means for obtaining a second key K2, and wherein said processor is arranged to:

split said digital input block into said selected part M1 and a second part M2 before performing said merging;

perform a non-linear function g<sup>−

1</sup> to merge said second block M2 with said second key K2 in one step, producing a data block B2 as output;

said non-linear function g<sup>−

1</sup> being the inverse of said non-linear function g; and

combine data from data in said data block B1 and in said data block B2;

said digital output block being derived from said combined data.

18. A processor as claimed in claim 16, wherein said merging comprises:

splitting said selected part M1 in a first plurality n of sub-blocks m₀, . . . , m<sub>n−

1</sub> of equal length;

splitting said first key K1 in said first plurality a of sub-keys k₀, . . . , k<sub>n−

1</sub>, having equal length, the sub-key k_i corresponding to the sub-block m_i, for i=0 to n−

1; and

separately processing each of said sub-blocks m_i by executing for each of said sub-blocks m_i a same non-linear function h for non-linearly merging a sub-block b_i derived from said sub-block m_i with said corresponding sub-key k_i in one, sequentially inseparable step and producing said first plurality of output sub-blocks h(b_i, k_i); and

combining sub-blocks t_i derived from said first plurality of said output sub-blocks h(b_i, k_i) to form said data block B1.

19. A processor as claimed in claim 18, wherein said function

h(b_i,k_i)=(b_i,k_i)⁻

1, if b_i≠

0, k_i≠

0, and b_i≠

k_i

h(b_i,k_i)=(k_i)<sup>−

2</sup>, if b_i=0

h(b_i,k_i)=(b_i)<sup>−

2</sup>, if k_i=0

h(b_i,k_i)=0, if b_i=k_i,

where the multiplication and inverse operations are predetermined Galois Field multiplication and inverse operations.

20. A processor as claimed in claim 19, wherein said sub-block m_i comprises eight data bits, and wherein said multiplying of two elements b and c of GF(2⁸) comprises:

representing b as a₀+a₁.D and c as a₂+a₃.D, where a₀, a₁, a₂ and a₃ are elements of GF(2⁴), and where D is an element of GF(2⁸) defined as a root of an irreducible polynomial k(x)=x²+x+β

over GF(2⁴), where β

is an element of GF(2⁴); and

calculating (a₀a₂+a₁a₃β

)+(a₁a₂+a₀a₃+a₁a₃).D;

and wherein calculating the inverse of an element b of GF(2⁸) comprises calculating (a₀²+a₀a₁+a₁²β

)<sup>−

1</sup>(a₀+a₁D).