Block cipher method

• US 6,182,216 B1
• Filed: 09/16/1998
• Issued: 01/30/2001
• Est. Priority Date: 09/17/1997
• Status: Expired due to Fees

• Current Assignee: Frank C. Luyster
• Original Assignee: Frank C. Luyster
• Inventors: Luyster, Frank C.
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/154,391
• Time in Patent Office: 867 Days
• Field of Search: 380/28, 380/44, 713/168, 713/171, 713/182, 713/200, 713/201
• US Class Current: 713/168
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• 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 data encryption system for encrypting an n-bit block of input in a plurality of rounds is presented, where n is preferably 128 bits or more. The data encryption system includes a computing unit for the execution of each round; memory for storing and loading segments; a bit-moving function capable of rotating, shifting, or bit-permute round segments by predetermined numbers of bits preferably to achieve active and effective fixed rotation; a linear combination function which provides new one-to-one round segments using a round operator generally from one algebraic group to combine two different one-to-one round segments taken from one one-to-one round segment set; and a nonlinear function which affects a one-to-one round segment from a particular one-to-one round segment set based on a value which depends on a preselected number of bits in a preselected location from a different one-to-one round segment from the same one-to-one round segment set. The nonlinear function is a variable rotation function or an s-box. A subkey combining function is generally employed in each round to provide new round segments by combining a round segment typically linearly with a subkey segment.

Claims

1. A method of encrypting an n-bit block of data, comprising:

representing an n-bit block of data having at least 128 bits to first and second round segments of data; and

encrypting the n-bit block of data using a secret key and a block cipher comprising;

performing a plurality of encrypting rounds on said first and second round segments of data, at least five of said encrypting rounds comprising,

modifying said first round segment of data with values from the first linear combining of first, second, and third variable segments, said first variable segment of at least 64 bits comprising at least 50 variable bits derived solely from said first round segment of data, said second variable segment of at least 64 bits comprising at least 50 variable bits from a first derivation from said second round segment of data, and said third variable segment comprising a value from a second derivation from at least 50 bits selected from a lookup table in response to at least a portion of the n-bit block of data, where said first linear combining is selected from a group consisting of either direct linear combination, indirect linear combination, and

first bit-moving variable bits of a round segment of data derived from one of said first and second round segments of data by predetermined numbers of bits where most of the resulting bits affect the n-bit block of data, and where first bit-moving is an operation selected from a group consisting of circular bit-rotation by non-zero numbers of bits, logical bit-shift by non-zero numbers of bits, non-identity bit-permutation.

2. The method of encrypting of claim 1 wherein at least three of said encrypting rounds further comprises:

modifying said second round segment of data with values from the second linear combining of fourth, fifth, and sixth variable segments, said fourth variable segment of at least 64 bits comprising at least 50 variable bits derived solely from said second round segment of data, said fifth variable segment of at least 64 bits comprising at least 50 variable bits from a third derivation from said first round segment of data, and said sixth variable segment comprising a value from a fourth derivation from at least 64 bits selected from a lookup table in response to at least a portion of the n-bit block of data, and where said second linear combining is selected from a group consisting of direct linear combination, indirect linear combination, and

second bit-moving variable bits of a round segment of data derived from one of said first and second round segments of data by predetermined numbers of bits where most of the resulting bits affect the n-bit block of data, and where second bit-moving is an operation selected from a group consisting of circular bit-rotation by non-zero numbers of bits, logical bit-shift by non-zero numbers of bits, non-identity bit-permutation.

3. The method of encrypting of claim 2 wherein the third variable segment is selected from said lookup table in response to a portion of the second round segment of data, and the sixth variable segment is selected from said lookup table in response to a portion of said first round segment of data, and said first and second round segments of data contain in total at least (n−

20) bits of data, and the first derivation, second derivation, third derivation, and fourth derivation are each derivations solely from their input round segments.

4. The method of encrypting of claim 1 wherein said first linear combining comprises:

linearly combining said first variable segment and said second variable segment using a first linear operator; and

linearly combining said first variable segment and said third variable segment using a second linear operator,

wherein the first linear operator and second linear operator are non-commutative with each other.

5. The method of encrypting of claim 1 wherein the sbox is optimized so that consecutive sections of 20 bits or fewer are guaranteed to have at least a 1 bit output difference for each input bit difference.

6. The method of encrypting of claim 1 wherein the sbox is optimized so that it has a guaranteed minimum number of bits of output difference given any input difference, where that number is greater than what would be expected by chance.

7. The method of encrypting of claim 3 wherein the first bit-moving and second bit-moving are selected from a group consisting of logical shifts by predetermined numbers of bits, circular bit-rotation by predetermined numbers of bits.

8. The method of encrypting of claim 7 wherein the first linear combining comprises:

linearly combining said first variable segment and said second variable segment using a first linear operator; and

linearly combining said first variable segment and said third variable segment using a second linear operator,

wherein the first and second linear operator are non-commutative with each other.

9. The method of encrypting of claim 8 wherein the second linear combining comprises:

linearly combining said fourth variable segment with said fifth variable segment using a first linear operator; and

linearly combining said fourth variable segment with said sixth variable segment using a second linear operator,

wherein the first and second linear operator are non-commutative with each other.

10. The method of encrypting of claim 9 wherein the first linear operator is exclusive-OR and the second linear operator is from a group consisting of SIMD addition, SIMD subtraction.

11. A binary block cipher data transformation system for changing ordered n-bit cipher input into ordered n-bit cipher output using a secret key, wherein an n-bit block of data is represented by first and second round segments of data, each round segment having n/2 bits, wherein is at least 128 bits, and there are at least 5 rounds, each round comprising,

a) a computing unit for executing the operation of each particular round;

b) memory for loading and storing round segments;

c) a bit-moving function, which is executed on the computing unit in each round where each time it is executed does a preselected operation on bits of a round segment from the group consisting of circular bit-rotation by non-zero numbers of bits, logical bit-shift by non-zero numbers of bits, non-identity bit-permutation, and has an input which is a variable segment and an output which is a variable round segment, and at least 75 percent of its output bits affect the n-bit round output;

d) an sbox function, which is executed on the computing unit in each round where each time it is executed uses an input of a number of variable bits dependent on at least a portion of the n-bit block of data to select an sbox output segment of at least 64 bits from a lookup table, and substantially all of the bits of the sbox output segment affect n-bit round output; and

e) a linear combination function, which is executed on the computing unit in each round where each time it is executed directly combines a first variable round segment with a second variable round segment, where at least 75 percent of the bits of said first variable round segment are variable bits, where at least 75 percent of the bits of said second variable round segment are variable bits, to produce an output which is a variable round segment where at least 75 percent of its output bits affect the n-bit round output, where the linear function is preselected from a group consisting of exclusive-OR, addition, subtraction, SIMD addition, SIMD subtraction, and where the sizes of the input and output segments of the linear combination function are at least 64 bits.

12. The data transformation system of claim 11 wherein the bit-moving function is selected from a group consisting of a bit-rotation by non-zero numbers of bits, logical bit-shift by non-zero numbers of bits, and each round contains at least 2 uses of the bit-moving function, 2 uses of the sbox function, and at least 2 uses of the linear combination function.

13. The data transformation system of claim 12 wherein each of the first and second round segments are in each round affected by an sbox output segment and by the output round segment of the linear combination function.

14. The data transformation system of claim 13 wherein the bit-moving function is placed in the rounds such that in each round the number of specified isolated bits equals the bit-size of the n-bit cipher data block.

15. A method of key expansion for block ciphers, which use data dependent rotation of round segments in at least three rounds where in each said block cipher round the number of bits of variable rotation of one round segment depends on some portion of another different round segment, comprising:

performing a plurality of expansion rounds on key segments to generate subkeys, comprising

linearly combining variable key-dependent segments with predetermined values to generate other segments, where said other segments are in a group of near-to-final results consisting of intermediate values used to generate subkey segments, final subkey segments, and

where use of all mathematical operators used in the expansion rounds are minimized so that the operator ratio, which is the ratio of the total number of bits produced by said mathematical operators to the total number of subkey bits produced, is less than 3.5 to 1.

16. The method of key expansion of claim 15 wherein the operator ratio is less than 2 to 1.

17. The method of key expansion of claim 16 wherein said mathematical operators are mostly linear.

18. The method of key expansion of claim 17 wherein the operator ratio is less than 1.25 to 1.

19. The method of key expansion of claim 18 wherein the input key is divided up into y key segments, and the y key segments are directly combined using linear operations with said predetermined values from a lookup table to produce subkey values.

20. A binary block cipher data transformation system for changing ordered variable n-bit cipher input into ordered variable n-bit cipher output using a secret key, wherein an n-bit block of data is represented by x round segments of data, where x is between 2 and 8, and there are at least 5 rounds, each round comprising,

a) a computing unit for executing the operation of each particular round;

b) memory for loading and storing round segments;

c) a bit-moving function, which is executed on the computing unit in each round where each time it is executed does a preselected operation on bits of a round segment from the group consisting of circular bit-rotation by non-zero numbers of bits, logical bit-shift by non-zero numbers of bits, non-identity bit-permutation, and has an input which is a variable round segment and an output which is a variable round segment where there are some bits of the output of the bit-moving function which can affect the n-bit round output;

d) a variable rotation function, which is executed on the computing unit in each said round where each time it is executed rotates the bits of a first round segment by a value dependent on a preselected number of bits in a preselected location of bits in a second round segment, and has an output which is a round segment and substantially all of the resulting bits affect the n-bit round output; and

e) a linear combination function, which is executed on the computing unit in each said round where each time it is executed combines one variable round segment with another variable round segment to produce a variable round segment where most of the resulting bits affect the n-bit round output, where one of the variable round segment inputs of the linear combination function is of substantially the same bit-size as the resulting output bits.

21. The data transformation system of claim 20 wherein each of said rounds receives n-bit round output, and modifies at least x different round segments to provide n-bit cipher round output, and where at least x said round segments are rotated by the variable rotation function.

22. The data transformation system of claim 21 wherein said bit-moving function is selected from a group consisting of circular bit-rotation by a non-zero number of bits, and any crytographically equivalent use of logical bit-shift by a non-zero number of bits.

23. The data transformation system of claim 21 wherein the number of specific isolated bits in each round is greater than 50 percent of all bits in the n-bit data block.

24. The data transformation system of claim 22 wherein the bit-moving function is effective rotation, and x is less than 5.

25. The data transformation system of claim 22 wherein most of the output bits of the bit-moving function affect n-bit round output.

26. The data transformation system of claim 22 wherein the number of specific isolated bits in each round of the block cipher is greater than 50 percent of all bits in the n-bit data block, and x is less than 5, and n is a predetermined value of at least 64 bits.

27. The data transformation system of claim 26 wherein said first round segment rotated by the variable rotation function is a one-to-one round segment and the bits which control said variable rotation of the first round segment are not derived from the first round segment.

28. The data transformation system of claim 27 wherein both inputs of the linear combination function are different one-to-one round segments from the same one-to-one segment set, and the bit-moving function is selected from a group consisting of rotation by f, and the mathematical equivalent of such rotation by f using logical shift, where f equals the log base 2 of the bit-size of a round segment rotated in round in a data-dependent manner.

29. The data transformation system of claim 28 wherein each of the x round segments are in each round affected by the output of the variable rotation function, and the output of the linear combination function.

30. A method of encrypting an n-bit block of data, comprising:

representing an n-bit block of data by a number x of round segments between two and four, where the potential round segments are called a first round segment, second round segment, third round segment, and fourth round segment; and

encrypting using a secret key and block cipher, said block cipher comprising,

performing a plurality of encrypting rounds on said first and second round segments of data, at least five of said encrypting rounds comprising,

modifying said first round segment of data with output of a first linear combining of first and second variable segments, the first variable segment having a derivation solely from substantially all the variable bits of said first round segment of data, the second variable segment having a first derivation from a most of the bits of a first particular round segment of data, where said linear combining is selected from a group consisting of direct linear combination, indirect linear combination,

variably rotating said first round segment of data by a number of variable bits dependent on at least a portion of the n-bit block of data, and

bit-moving a second particular round segment of data having a second derivation from selected from one of the first, second, third, and fourth round segments of data by a predetermined bit-moving operation selected from the group consisting of circular bit-rotation by non-zero numbers of bits, logical bit-shifts by non-zero numbers of bits, nonidentity bit-permutation, where there are some output bits of the bit-moving operation which can affect the n-bit round output.

31. The method of claim 30 wherein each of said rounds receives n-bit round output, and modifies at least x different round segments to provide n-bit round output, and where at least x said round segments are rotated by the variable rotation function.

32. The method of claim 31 wherein the number of specified isolated bits in each round is greater than 50 percent of all the bits in said n-bit block of data, and n is a predetermined number of at least 64 bits.

33. The method of claim 31 wherein the first derivation and second derivation are derived solely from their respective input round segments, and the first particular round segment is selected from a group consisting of the second round segment, the third round segment, the fourth round segment.

34. The method of claim 31 wherein the bit-moving operation is selected from a group consisting of circular bit-rotation by non-zero numbers of bits, and mathematically equivalent use of logical bit-shifts by non-zero numbers of bits.

35. The method of claim 34 wherein the variably rotating of the first round segment is by a number of bits dependent on a portion of data from a round segment other than the first rounds segment.

36. The method of claim 35 wherein the bit-moving operation is effective fixed rotation.

37. The method of claim 35 wherein the number of specified isolated bits in each round of the block cipher is greater than 50 percent of all the bits in the n-bit data block.

38. The method of claim 36 wherein the fixed rotation is by f, where f equals log base 2 of the bit-size of a round segment.

39. The method of claim 36 wherein n=128, and in each round each primary round segment is modified with output of a linear combining of two variable segments, and each primary round segment is rotated by a data-dependent number of bits.

40. The method of claim 39 wherein x equals 2, and the first and second round segments each contain 64-bits, and the bit-moving operation is predetermined bit-rotation by 6 bits.