Linear transformation for symmetric-key ciphers

• US 7,450,720 B2
• Filed: 08/01/2001
• Issued: 11/11/2008
• Est. Priority Date: 08/03/2000
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Roelse, Petrus Lambertus Adrianus
• Primary Examiner(s): Moise; Emmanuel L
• Assistant Examiner(s): PYZOCHA, MICHAEL J
• Application Number:
  US09/918,831
• Publication Number:
  US 20020101986A1
• Time in Patent Office: 2,659 Days
• Field of Search: 380/259, 380/44
• US Class Current: 380/259
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation

Abstract

A method of generating a linear transformation matrix A for use in a symmetric-key cipher includes generating a binary [n,k,d] error-correcting code, where k<n<2k, and d is the minimum distance of the binary error-correcting code. The code is represented by a generator matrix GεZ₂^k×n in a standard form G=(I_k∥B), with BεZ₂^k×(n−k). The matrix B is extended with 2k−n columns such that a resulting matrix C is non-singular. The linear transformation matrix A is derived from matrix C. Preferably, the error correcting code is based on an XBCH code.

Claims

1. A method of linear transformation in a symmetric-key cipher comprising:

inputting block data into a processing apparatus;

creating a linear transformation matrix A with the processing apparatus by;

generating a binary [n,k,d] error-correcting code, represented by a generator matrix Gε

Z₂<sup>k×

n</sup> in a form G=(I_k∥

B), with Bε

Z₂<sup>k×

(n−

k)</sup>, where k<

n<

2k, and d is the minimum distance of the binary error-correcting code;

shortening said error-correcting code; and

extending matrix B with 2k−

n columns such that a resulting matrix C is non-singular, and deriving the linear transformation matrix A from matrix C; and

transforming the input block data into diffused output block data with the processing apparatus by using the linear transformation matrix A.

2. A method as claimed in claim 1, wherein extending matrix B with 2k−

n columns comprises;

in an iterative manner;

randomly generating 2k−

n columns, each with k binary elements;

forming a test matrix consisting of the n−

k columns of B and the 2k−

n generated columns; and

checking whether the test matrix is non-singular, until a non-singular test matrix has been found; and

using the found test matrix as matrix C.

3. A method as claimed in claim 1, wherein the operation of deriving matrix A from matrix C comprises:

determining two permutation matrices P₁,P₂ε

Z₂<sup>k×

k</sup> such that all codewords in an [2k,k,d] error-correcting code, represented by the generator matrix (I_k∥

P₁C P₂), have a predetermined multi-bit weight; and

using P₁C P₂ as matrix A.

4. A method as claimed in claim 3, wherein the input block data is m-bit sub-block data, and the processing apparatus executes a round function with an S-box layer with S-boxes operating on the m-bit sub-blocks data, and the minimum predetermined multi-bit weight over all non-zero codewords equals a predetermined m-bit weight.

5. A method as claimed in claim 3, wherein determining the two permutation matrices P₁ and P₂ comprises iteratively generating the matrices in a random manner.

6. A method as claimed in claim 1, wherein the input block data is 32-bit block data and wherein the operation of generating a [n,k,d] error-correcting code comprises:

generating a binary extended Bose-Chaudhuri-Hocquenghem (XBCH) [64,36,12] code; and

shortening the XBCH [64,36,12] code to a [60,32,12] XBCH code by deleting four rows.

7. A computer program product stored on a computer readable medium, wherein the program product is operative to cause the processor to perform the method of claim 1.

8. A system for cryptographically converting an input data block into an output data block, the input data blocks comprising n data bits, the system comprising:

an input for receiving the input data block;

a storage for storing a linear transformation matrix A created by;

generating a binary [n,k,d] error-correcting code, represented by a generator matrix Gε

Z₂<sup>k×

n</sup> in a form G=(I_k∥

B), with Bε

Z₂<sup>k×

(n−

k)</sup>, where k<

n<

2k, and d is the minimum distance of the binary error-correcting code;

shortening said error-correcting code; and

extending matrix B with 2k−

n columns such that a resulting matrix C is non-singular, and deriving the linear transformation matrix A from matrix C;

a cryptographic processor performing a linear transformation on the input data block or a derivative of the input data block using the linear transformation matrix A; and

an output for outputting the processed input data block.

9. A system as claimed in claim 8, wherein extending matrix B with 2k−

n columns comprises;

in an iterative manner;

randomly generating 2k−

n columns, each with k binary elements;

forming a test matrix consisting of the n−

k columns of B and the 2k−

n generated columns; and

checking whether the test matrix is non-singular, until a non-singular test matrix has been found; and

using the found test matrix as matrix C.

10. A system as claimed in claim 8, wherein the operation of deriving matrix A from matrix C comprises:

determining two permutation matrices P₁,P₂ε

Z₂<sup>k×

k</sup> such that all codewords in an [2k,k,d] error-correcting code, represented by the generator matrix (I_k∥

P₁C P₂), have a predetermined multi-bit weight; and

using P₁C P₂ as the matrix A.

11. A system as claimed in claim 10, wherein the input block data is m-bit sub-block data, and the processing apparatus executes a round function with an S-box layer with S-boxes operating on the m-bit sub-block data, and the minimum predetermined multi-bit weight over all non-zero codewords equals a predetermined m-bit weight.

12. A system as claimed in claim 10, wherein determining the two permutation matrices P₁ and P₂ comprises iteratively generating the matrices in a random manner.

13. A system as claimed in claim 8, wherein the input data block is a 32-bit data block and wherein the operation of generating a [n,k,d] error-correcting code comprises:

generating a binary extended Bose-Chaudhuri-Hocquenghem (XBCH) [64,36,12] code; and

shortening the XBCH [64, 36, 12] code to a [60, 32, 12] XBCH code by deleting four rows.

14. A method of linear transformation in a symmetric-key cipher comprising:

inputting block data into a processing apparatus;

creating a linear transformation matrix A with the processing apparatus by;

generating a binary [n,k,d] error-correcting code, represented by a generator matrix Gε

Z₂<sup>k×

n</sup> in a form G=(I_k∥

B), with Bε

Z₂<sup>k×

(n−

k)</sup>, where k<

n<

2k, and d is the minimum distance of the binary error-correcting code;

extending matrix B with 2k−

n columns such that a resulting matrix C is non-singular;

determining two permutation matrices P₁,P₂ε

Z₂<sup>k×

k</sup> such that all codewords in an [2k,k,d] error-correcting code, represented by the generator matrix (I_k∥

P₁C P₂), have a predetermined multi-bit weight; and

using P₁C P₂ as matrix A; and

transforming the input block data into diffused output block data with the processing apparatus by using the linear transformation matrix A.