Extended key preparing apparatus, extended key preparing method, recording medium and computer program

• US 6,956,951 B2
• Filed: 03/20/2001
• Issued: 10/18/2005
• Est. Priority Date: 07/13/2000
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Ito, Koichi, Takenaka, Masahiko, Yanami, Hitoshi, Shimoyama, Takeshi, Torii, Naoya, Yajima, Jun, Yokoyama, Kazuhiro
• Primary Examiner(s): Smithers, Matthew
• Assistant Examiner(s): FIELDS, COURTNEY D
• Application Number:
  US09/811,551
• Publication Number:
  US 20020006196A1
• Time in Patent Office: 1,673 Days
• Field of Search: 380/277, 380/46, 380/42, 380/29
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• 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

Intermediate data a_i, b_i, c_i, and d_i are prepared by an intermediate data preparing equipment 4 from a cryptographic key through a nonlinear type function operation and the like, an extended key preparing equipment 5 selects a [X_r], b [Y_r], c [Z_r], and d [W_r] corresponding to the number of stages r from the intermediate data, and rearranges the data as well as conducts that of bit operation to prepare extended keys, whereby an extended key preparing apparatus by which an extended key required in the case where common key cryptosystem is applied can be safely prepared at a high speed, a process for preparing such an extended key, and a recording medium used therefor are provided.

Claims

1. An extended key preparing apparatus wherein extended keys are prepared in common key cryptosystem from a cryptographic key input, comprising:

a dividing unit which divides a bit string of said cryptographic key into a plurality of bit groups, each bit group having a predetermined bit length;

an intermediate data preparing unit which prepares a plurality of intermediate data groups from the bit groups by a predetermined operation with different constant for each bit group, each intermediate data group having first intermediate data;

a selecting unit which selects one item of the first intermediate data for each of the intermediate data groups depending on a number of stages of extended keys to determine second intermediate data; and

an extended key preparing unit which prepares the extended keys having a bit length longer than the bit string of said cryptographic key by converting irreversibly the second intermediate data, wherein said intermediate data preparing unit is provided with a nonlinear type operating unit for effecting a nonlinear type operation with respect to each bit group to prepare the intermediate data groups.

2. An extended key preparing apparatus according to claim 1, wherein said dividing unit divides the bit string of said cryptographic key into eight of the bit groups, the predetermined bit length is 32 bits, and said nonlinear type operating unit separates each bit group into 6, 5, 5, 5, 5, and 6 bits to transpose the same into other data, respectively, and the data after transposition are subjected to nonlinear type operation by the use of a determinant.

3. An extended key preparing apparatus according to claim 1, wherein said intermediate data preparing unit is provided with:

an addition unit which adds a first constant to an even-numbered bit group that has been subjected to the nonlinear type operation to obtain a first result;

a multiplication unit which multiplies by a second constant an odd-numbered bit group which has been subjected to the nonlinear type operation to obtain a second result, wherein the odd number is the even number plus one; and

an exclusive OR operating unit which effects exclusive OR operation of the first result and the second result.

4. An extended key preparing apparatus according to claim 3, comprising further a preparing unit for preparing the intermediate data group by nonlinearly operating on a result of said exclusive OR operation.

5. An extended key preparing apparatus according to claim 4, wherein said addition unit and said multiplication unit repeat a plurality of times additions and multiplications by the use of the number i of different constants, respectively, to prepare the number i of data in every bit group;

said exclusive OR operating unit repeats i times operations for acquiring exclusive OR of the even-numbered bit group and the odd-numbered bit group which have been operated by the use of the same constants; and

said preparing unit prepare the number i of items of the first intermediate data in every bit group.

6. An extended key preparing apparatus according to claim 5, wherein said selecting unit selects one item of the first intermediate data corresponding to said number of stages of an extended key among the number i of items of the first intermediate data contained in the respective intermediate data groups which have been prepared by said intermediate data preparing unit.

7. An extended key preparing apparatus according to claim 1, wherein said extended key preparing unit is provided with:

a rearrangement unit which rearranges the second intermediate data to obtain a rearranged intermediate data; and

an irreversible conversion unit which converts irreversibly the rearranged intermediate data.

8. An extended key preparing apparatus according to claim 7, wherein the second intermediate data includes four items represented by four elements X, Y, Z, and W, respectively,

said rearrangement unit rearranges the four items, and

said irreversible converting unit prepares a first data by adding the element Y to a data obtained by shifting cyclically the element X leftwards by 1 bit;

prepares a second data determined by sifting cyclically the data leftwards by further 1 bit, which data has been obtained by subtracting the element W from a data obtained by shifting cyclically the element Z leftwards by 1 bit; and

performs an exclusive OR operation on said first data and said second data.

9. An extended key preparing apparatus according to claim 1, wherein said dividing unit divides a cryptographic key of 128 bits, 192 bits, or 256 bits into eight groups of 32 bits.

10. An extended key preparing method wherein extended keys are prepared in common key cryptosystem from a cryptographic key input, comprising:

dividing a bit string of said cryptographic key into a plurality of bit groups, each bit group having a predetermined bit length;

preparing a plurality of intermediate data groups from the bit groups by effecting a nonlinear type operation with different constant for each bit group, each intermediate data group having a first intermediate data;

selecting one item of the first intermediate data for each of the intermediate data groups depending on a number of stages of extended keys to determine second intermediate data; and

preparing the extended keys having a bit length longer than the bit string of said cryptographic key by converting irreversibly the second intermediate data.

11. An extended key preparing method according to claim 10, wherein said dividing includes dividing the bit string of said cryptographic key into eight of the bit groups, the predetermined bit length is 32 bits, and

said effecting of the nonlinear type operation includes separating each bit group into 6, 5, 5, 5, 5, and 6 bits to transpose the same into other data, respectively, and the data after transposition are subjected to a nonlinear type operation by the use of a determinant.

12. An extended key preparing method according to claim 10, wherein said preparing of the plurality of intermediate data groups includes

adding a first constant to an even-numbered bit group that has been subjected to the nonlinear type operation to obtain a first result;

multiplying by a second constant an odd-numbered bit group which has been subjected to the nonlinear type operation to obtain a second result, wherein the odd number is the even number plus one; and

effecting an exclusive OR operation of the first result and the second result.

13. An extended key preparing method according to claim 12, further comprising preparing the intermediate data group by nonlinearly operating on a result of said exclusive OR operation.

14. An extended key preparing method according to claim 13, wherein said adding and said multiplying includes repeating a plurality of times additions and multiplications by the use of the number i of different constants, respectively, to prepare the number i of data in every bit group;

said effecting of the exclusive OR operation includes repeating i times operations for acquiring exclusive OR of the even-numbered bit group and the odd-numbered bit group which have been operated by the use of the same constants; and

said preparing of the intermediate data group by nonlinearly operating includes preparing the number i of intermediate data in every bit group.

15. An extended key preparing method according to claim 14, wherein said selecting includes selecting one item of the first intermediate data corresponding to said number of stages of an extended key among the number i of items of the first intermediate data contained in the respective intermediate data groups which have been prepared by said intermediate data preparing step.

16. An extended key preparing method according to claim 10, wherein said preparing of the extended keys includes

rearranging the second intermediate data to obtain a rearranged intermediate data;

and

converting irreversibly the rearranged intermediate data.

17. An extended key preparing method according to claim 16, wherein the second intermediate data includes four items represented by four elements X, Y, Z, and W, respectively,

said rearranging includes rearranging the four items, and

said converting includes

preparing a first data by adding the element Y to a data obtained by shifting cyclically the element X leftwards by 1 bit;

prepares a second data determined by sifting cyclically the data leftwards by further 1 bit, which data has been obtained by subtracting the element W from a data obtained by shifting cyclically the element Z leftwards by 1 bit; and

performing an exclusive OR operation on said first data and said second data.

18. An extended key preparing method according to claim 10, wherein said dividing step divides a cryptographic key of 128 bits, 192 bits, or 256 bits into eight groups of 32 bits.

19. A computer readable recording medium wherein an extended key preparing program in which extended keys are prepared in common key cryptosystem from a cryptographic key input is to be recorded, the program comprising program code means which when executed perform:

dividing a bit string of said cryptographic key into a plurality of bit groups, each bit group having a predetermined bit length;

preparing a plurality of intermediate data groups from the bit groups by effecting a nonlinear type operation with different constant for each bit group, each intermediate data group having a first intermediate data;

one item of the first intermediate data for each of the intermediate data groups depending on a number of stages of extended keys to determine second intermediate data; and

preparing the extended keys having a bit length longer than the bit string of said cryptographic key by converting irreversibly the second intermediate data.

20. An extended key preparing program in which extended keys are prepared in common key cryptosystem from a cryptographic key input, the program comprising program code means which when executed perform:

dividing a bit string of said cryptographic key into a plurality of bit groups, each bit group having a predetermined bit length;

preparing a plurality of intermediate data groups from the bit group by effecting a nonlinear type operation with different constant for each bit group, each intermediate data group having first intermediate data;

one item of the intermediate data for each of the intermediate data groups depending on a number of stages of extended keys to determine second intermediate data; and

preparing the extended keys having a bit length longer than the bit string of said cryptographic key by converting irreversibly the second intermediate data.

21. An extended key preparing apparatus wherein extended keys are prepared in common key cryptosystem from a cryptographic key input, comprising:

a dividing unit which divides binary digit string of said cryptographic key into a plurality of elements each composed of a predetermined bit length;

an intermediate data preparing unit which prepares a plurality of intermediate data by applying a plurality of times an operation wherein a predetermined constant is used to the respective elements divided by said dividing unit, said intermediate data preparing unit being provided with a nonlinear type operating unit for effecting nonlinear type operation with respect to the respective elements divided by said dividing unit, said nonlinear type operating unit performing nonlinear type operation in such a manner that when said cryptographic key is divided into eight elements of 32 bits by said dividing unit, said nonlinear type operating unit separates said elements into 6, 5, 5, 5, 5, and 6 bits to transpose the same into other data, respectively, and the data after transposition are subjected to nonlinear type operation by the use of a determinant

a selecting unit which selects a plurality of intermediate data corresponding to the number of stages of extended keys from the plurality of the intermediate data prepared by said intermediate data preparing unit; and

an extended key preparing unit which prepares the extended keys corresponding to said number of stages by converting irreversibly the plurality of the intermediate data selected by said selecting unit.

22. An extended key preparing method wherein extended keys are prepared in common key cryptosystem from a cryptographic key input, comprising the steps of,

dividing binary digit string of said cryptographic key into a plurality of elements each composed of a predetermined bit length;

preparing a plurality of intermediate data by applying the plurality of times an operation wherein a predetermined constant is used to the respective elements divided by said dividing step, said preparing involving a nonlinear type operating step for effecting nonlinear type operation with respect to the respective elements divided by said dividing step, said nonlinear type operating step performing a nonlinear type operation in such a manner that when said cryptographic key is divided into eight elements of 32 bits by said dividing step, said nonlinear type operating step separates said elements into 6, 5, 5, 5, 5, and 6 bits to transpose the same into other data, respectively, and the data after transposition are subjected to nonlinear type operation by the use of a determinant;

selecting a plurality of intermediate data corresponding to the number of stages of extended keys from the plurality of the intermediate data prepared by said intermediate data preparing step; and

preparing the extended keys corresponding to said number of stages by converting irreversibly the plurality of the intermediate data selected by said selecting step.