Linear transformation for symmetric-key ciphers

• US 20020101986A1
• Filed: 08/01/2001
• Published: 08/01/2002
• 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
• Granted Patent: US 7,450,720 B2
• Time in Patent Office: Days
• US Class Current: 380/42
• 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 generating a linear transformation matrix A for use in a symmetric-key cipher, the method including:

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

Z₂<sup>k×

n</sup> in a standard 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, and

deriving matrix A from matrix C.

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

n columns includes;

in an iterative manner;

(pseudo-)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 step of deriving matrix A from matrix C includes:

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∥

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 cipher includes a round function with an S-box layer with S-boxes operating on m-bit sub-blocks, 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 the step of determining the two permutation matrices P₁ and P₂ includes iteratively generating the matrices in a (pseudo-)random manner.

6. A method as claimed in claim 1, wherein the cipher includes a round function operating on 32-bit blocks and wherein the step of generating a [n,k,d] error-correcting code includes:

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

shortening this code to a [60,32,12] shortened XBCH code by deleting four rows.

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

8. A system for cryptographically converting an input data block into an output data block;

the data blocks comprising n data bits;

the system including;

an input for receiving the input data block;

a storage for storing a linear transformation matrix A, generated according to the method of claim 1,

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..