Patent Publication Number: US-8111827-B2

Title: Cryptographic processing apparatus and cryptographic processing method

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2009-7249 filed on Jan. 16, 2009, the entire contents of which are incorporated herein by reference. 
     FIELD 
     The embodiment(s) described herein relate to a cryptographic processing apparatus and a cryptographic processing method. 
     BACKGROUND 
     Various cipher algorithms are utilized as fundamental technologies of security systems. Generally, cipher algorithms are classified into two groups, namely, public key cryptosystems and common key cryptosystems. The public key cryptosystems use different keys for encryption and decryption. The public key cryptosystems keep a key for decrypting ciphertext called a secret key as secret information only for a receiver, instead of making a key for encryption called a public key publicly available, to thereby ensure high security. The common key cryptosystems, on the other hand, use the same key for encryption and decryption called a common key. The common key cryptosystems keep a common key as information unknown to any third party other than the sender and receiver to thereby ensure high security. 
     The cipher algorithms of the common key cryptosystems have the advantages of high processing speed and compact packaging over the cipher algorithms of the public key cryptosystems. Therefore, the encryption function is added to compact devices such as mobile phones or integrated-circuit (IC) cards using the cipher algorithms of the common key cryptosystems. Furthermore, due to the high processing speed and real-time encryption/decryption of information, the cipher algorithms of the common key cryptosystems are also used for broadcasting or information communication in communication fields. 
     The cipher algorithms of the common key cryptosystems are classified into two types, namely, stream ciphers and block ciphers. Now, the block ciphers are widely used in terms of security. The block ciphers divide plaintext into blocks each having a certain bit length, and encrypt the plaintext block by block. The bit length of each block which is the unit of encryption is called “block length”. 
     There are many block ciphers of the common key cryptosystems with various types of block sizes such as 64-bit, 128-bit and others. Typical cipher algorithms include DES (Data Encryption Standard), AES (Advanced Encryption Standard), SC2000, MISTY1, MISTY2, KASUMI, and CAMELLIA. Such cipher algorithms of the common key cryptosystems are implemented by software or hardware. 
     One of the cipher algorithms of the common key cryptosystems, MISTY1, will now be described. MISTY1 is described in, for example, Specification of MISTY1 (&lt;http://www.cryptrec.go.jp/cryptrec — 03_spec_cypherlist_files/PDF/05 — 02jspec.pdf&gt;). MISTY1 is a cipher algorithm with a common key size of 128 bits and a block length of 64 bits. That is, MISTY1 generates 64-bit ciphertext from 64-bit plaintext using a 128-bit common key. In the following, a description will be given of a round processing part of MISTY1. 
       FIGS. 10A and 10B  are circuit diagrams illustrating an example configuration of a MISTY1 round processing part.  FIG. 10A  illustrates a round processing part for use in the decryption process.  FIG. 10B  illustrates a round processing part for use in the encryption process. 
     The round processing part of MISTY1 illustrated in  FIGS. 10A and 10B  performs processing where the number of rounds n is 8. In Specification of MISTY1 mentioned above, 8 rounds are recommended. The round processing part of MISTY1 has a Feistel structure with eight FO functions FO 1 , FO 2 , FO 3 , FO 4 , FO 5 , FO 6 , FO 7 , and FO 8  and ten FL functions FL 1 , FL 2 , FL 3 , FL 4 , FL 5 , FL 6 , FL 7 , FL 8 , FL 9 , and FL 10  or ten FL −1  functions FL 1   −1 , FL 2   −1 , FL 3   −1 , FL 4   −1 , FL 5   −1 , FL 6   −1 , FL 7   −1 , FL 8   −1 , FL 9   −1 , and FL 10   −1 . In the encryption process of MISTY1, 64-bit plaintext P is input and 64-bit ciphertext C is output. In the decryption process, 64-bit ciphertext C is input and 64-bit plaintext P is output. 
     In the following, a description will be given of the FL functions and the FL −1  functions. 
       FIG. 11A  is a circuit diagram illustrating an example configuration of an FL function.  FIG. 11B  is a circuit diagram illustrating an example configuration of an FL −1  function. The FL function includes an AND gate  1   a  in the first stage and an OR gate  2   a  in the second stage. Conversely to the FL function, the FL −1  function includes an OR gate  2   b  in the first stage and an AND gate  1   b  in the second stage. 
     32-bit input data to the FL function and the FL −1  function is divided into two data segments of 16 bits each, and each data segment is transformed using an XOR gate, an AND gate, and an OR gate. In  FIGS. 11A and 11B , KL ij  (1≦i≦8, 1≦j≦2) represents 16-bit data at the j-th position from the left of KL i , where KL i  denotes an extended key. In MISTY1, extended-key processing is performed to generate a 256-bit extended key KL i  from a 128-bit secret key K. The details of the generation of an extended key are described in Specification of MISTY1 mentioned above. 
     In the FL function, the bit string of the upper 16 bits of the 32-bit input and the upper 16 bits KL i1  of the extended key are input to the AND gate  1   a . The bit string of the lower 16 bits of the 32-bit input and the output of the AND gate  1   a  are input to an XOR gate  3   a . The output of the XOR gate  3   a  and the lower 16 bits KL i2  of the extended key are input to the OR gate  2   a . The bit string of the upper 16 bits of the 32-bit input and the output of the OR gate  2   a  are input to an XOR gate  3   b . The output of the XOR gate  3   b  corresponds to the upper 16 bits of a 32-bit output of the FL function, and the output of the XOR gate  3   a  corresponds to the lower 16 bits of the 32-bit output of the FL function. 
     In the FL −1  function, the bit string of the lower 16 bits of the 32-bit input and the lower 16 bits KL i2  of the extended key are input to the OR gate  2   b . The bit string of the upper 16 bits of the 32-bit input and the output of the OR gate  2   b  are input to an XOR gate  3   c . The output of the XOR gate  3   c  and the upper 16 bits KL i1  of the extended key are input to the AND gate  1   b . The bit string of the lower 16 bits of the 32-bit input and the output of the AND gate  1   b  are input to an XOR gate  3   d . The output of the XOR gate  3   c  corresponds to the upper 16 bits of a 32-bit output of the FL −1  function, and the output of the XOR gate  3   d  corresponds to the lower 16 bits of the 32-bit output of the FL −1  function. 
     A method for implementing an FL function and an FL −1  function in a first typical example will now be described. 
     In a hardware implementation supporting both the encryption process and the decryption process, it is necessary to implement an FL function and an FL −1  function.  FIG. 12  is a circuit diagram illustrating an implementation method in the first typical example. In the first typical example, an FL function  6  and an FL −1  function  7  can be switched using a selector  5  depending on the encryption process or the decryption process. 
     A method for implementing an FL function and an FL −1  function in a second typical example will now be described. 
     A compact implementation method for implementing an FL function and an FL −1  function has been available. Such an implementation method is described in, for example, Japanese Patent No. 4128395.  FIG. 13  is a circuit diagram illustrating an implementation method in the second typical example. In the second typical example, a single AND gate  1   c  and a single OR gate  2   c  are used for implementation. In the second typical example, therefore, an AND gate and an OR gate, which are common parts between the two functions, are shared and the functions are merged into a single function. 
     In  FIG. 13 , the bit string of the lower 16 bits of a 32-bit input and the output of the AND gate  1   c  are input to an XOR gate  3   e . The bit string of the upper 16 bits of the 32-bit input and the output of the OR gate  2   c  are input to an XOR gate  3   f . The bit string of the upper 16 bits of the 32-bit input and the output of the XOR gate  3   f  are input to a selector  5   a . The bit string of the lower 16 bits of the 32-bit input and the output of the XOR gate  3   e  are input to a selector  5   b . The output of the selector  5   a  and the upper 16 bits KL i1  of an extended key are input to the AND gate  1   c . The output of the selector  5   b  and the lower 16 bits KL i2  of the extended key are input to the OR gate  2   c . The output of the XOR gate  3   f  corresponds to the upper 16 bits of a 32-bit output of the circuit illustrated in  FIG. 13 , and the output of the XOR gate  3   e  corresponds to the lower 16 bits of the 32-bit output of the circuit illustrated in  FIG. 13 . 
     When each of the selectors  5   a  and  5   b  selects the upper signal, the circuit illustrated in  FIG. 13  serves as an FL function. When the lower signals are selected, the circuit serves as an FL −1  function. This technique allows a significant reduction in circuit size. A related technique is disclosed in Dai Yamamoto, et al., “A Very Compact Hardware Implementation of the MISTY1 Block Cipher”, CHES 2008, LNCS 5154, pp. 315-330, 2008, or Akashi Satoh and Sumio Morioka, “Small and High-Speed Hardware Architectures for the 3GPP Standard Cipher KASUMI”, Information Security Conference 2002, LNCS 2433, pp. 48-62, 2002. 
     SUMMARY 
     According to an aspect of the present invention, there is provided a cryptographic processing apparatus and method for performing arithmetic operation on an FL function and an FL −1  function in a cryptographic process. The cryptographic processing apparatus includes a first arithmetic gate configured to receive a first input bit string and a first extended key bit string, the first input bit string being an upper N-bit string in a 2N-bit input of the cryptographic processing apparatus, where the first extended key bit string is based on one of an upper N-bit string and a lower N-bit string of an extended key, the first arithmetic gate is one of an AND gate and an OR gate. 
     According to an embodiment, a cryptographic processing apparatus includes a first XOR gate configured to receive an output of the first arithmetic gate and a second input bit string, the second input bit string being a lower N-bit string in the 2N-bit input of the cryptographic processing apparatus; a second arithmetic gate configured to receive an output of the first XOR gate and a second extended key bit string, the second extended key bit string being based on the other of the upper N-bit string and the lower N-bit string of the extended key, the second arithmetic gate being a gate different from the first arithmetic gate and the other of the AND gate and the OR gate; a second XOR gate configured to receive an output of the second arithmetic gate and the first input bit string; a third arithmetic gate configured to receive an output of the second XOR gate and the first extended key bit string, the third arithmetic gate being a same gate as the first arithmetic gate and the one of the AND gate and the OR gate; and a third XOR gate configured to receive an output of the third arithmetic gate and an output of the first XOR gate. 
     Additional objects and advantages of the invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The object and advantageous of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       These and/or other aspects and advantages will become apparent and more readily appreciated from the following description of the embodiments, taken in conjunction with the accompanying drawings of which: 
         FIG. 1  is a circuit diagram illustrating an example configuration of a merge function according to a first example. 
         FIG. 2  is a circuit diagram illustrating an example configuration of a merge function according to a second example. 
         FIG. 3  is a circuit diagram illustrating an example configuration of a merge function according to a third example. 
         FIG. 4  is a circuit diagram illustrating an example configuration of a merge function according to a fourth example. 
         FIG. 5  is a circuit diagram illustrating an example configuration of a merge function according to a fifth example. 
         FIG. 6  is a circuit diagram illustrating an example configuration of a merge function according to a sixth example. 
         FIG. 7  is a circuit diagram illustrating an example configuration of a merge function according to a seventh example. 
         FIG. 8  is a table illustrating exemplary circuit sizes according to embodiment(s). 
         FIG. 9  is a table illustrating exemplary delay times according to embodiment(s). 
         FIG. 10A  is a circuit diagram illustrating an example configuration of a round processing part for performing decryption according to MISTY1. 
         FIG. 10B  is a circuit diagram illustrating an example configuration of a round processing part for performing encryption according to MISTY1. 
         FIG. 11A  is a circuit diagram illustrating an example configuration of an FL function. 
         FIG. 11B  is a circuit diagram illustrating an example configuration of an FL −1  function. 
         FIG. 12  is a circuit diagram illustrating an implementation method in a first typical example. 
         FIG. 13  is a circuit diagram illustrating an implementation method in a second typical example. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Reference will now be made in detail to the embodiments, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below to explain the present invention by referring to the figures. 
     However, the second typical example has a serious problem in that a feedback loop is formed in a combinational circuit. Regardless of which function the circuit illustrated in  FIG. 13  serves as, no registers are included in a path and a loop structure is formed only in a combinational circuit. In this structure, it is difficult to perform logic synthesis which is an operation for conversion from a hardware description language into a circuit structure. Even if it is possible to perform logic synthesis, there is a risk that a circuit generated after the conversion may be an oscillator circuit. Therefore, in terms of reliability, it is difficult to commercialize a circuit having the feedback loop structure described above into a product. 
     Thus, when the features of the FL function and the FL −1  function are merged to produce a single function, it is not easy to achieve a reduction in circuit size without forming a feedback loop in a circuit configuration. Conventionally, therefore, in many developments pertaining to MISTY1 and KASUMI, as in the first typical example, the FL function and the FL −1  function are independently implemented. 
     The present technique has been carried out in order to overcome the problems or difficulties described above and others existing in typical systems, and provides a cryptographic processing apparatus for realizing a merge function including an FL function and an FL −1  function using a circuit having no feedback loop. 
     An embodiment of the present technique will be described hereinafter with reference to the drawings. 
     The present technique provides a compact hardware implementation in common key cryptosystems that employ an FL function and an FL −1  function, such as MISTY1, MISTY2, KASUMI, and CAMELLIA, by using a new function obtained by efficiently merging the FL function and the FL −1  function into a single function. The present technique is useful for producing compact common key cipher hardware. 
     In the following, a merge function obtained by merging an FL function and an FL −1  function into a single function will be described in the context of MISTY1 by way of example. The basic concept of application to MISTY2, KASUMI, CAMELLIA, and the like is similar to that for MISTY1. While particular applications are discussed herein, the present invention is not limited to implementation with any specific methodology, technique or specific algorithm related to cryptography. 
       FIG. 1  is a circuit diagram illustrating an example configuration of a merge function according to a first example. As described above, an FL function is configured using a circuit having a two-stage structure in which an AND gate is provided in the first stage and an OR gate is provided in the second stage. Conversely, an FL −1  function is configured using a function having a two-stage structure in which an OR gate is provided in the first stage and an AND gate is provided in the second stage. In contrast, the merge function according to the first example is configured using a circuit having a three-stage structure. More specifically, the merge function according to the first example is configured using a circuit including a first arithmetic gate corresponding to an AND gate  11   a  in the first stage, a second arithmetic gate corresponding to an OR gate  12  in the second stage, and a third arithmetic gate corresponding to an AND gate  11   b  in the third stage. In the circuit illustrated in  FIG. 1 , only the OR gate  12  is common to the two functions. 
     A 32-bit input of the circuit illustrated in  FIG. 1  is divided into a first input bit string corresponding to the input upper bit string of the upper 16 bits and a second input bit string corresponding to the input lower bit string of the lower 16 bits. Here, N=16. 
     In the circuit illustrated in  FIG. 1 , the input upper bit string and a first extended key bit string KL i1  corresponding to the upper 16 bits of an extended key are input to the AND gate  11   a . The input lower bit string and the output of the AND gate  11   a  are input to a first XOR gate corresponding to an XOR gate  13   a . The output of the XOR gate  13   a  and the input lower bit string are input to a first selector corresponding to a selector  14   a.    
     In the circuit illustrated in  FIG. 1 , the output of the selector  14   a  and a second extended key bit string KL i2  corresponding to the lower 16 bits of the extended key are input to the OR gate  12 . The input upper bit string and the output of the OR gate  12  are input to a second XOR gate corresponding to an XOR gate  13   b.    
     In the circuit illustrated in  FIG. 1 , the output of the XOR gate  13   b  and KL i1  are input to the AND gate  11   b . The output of the selector  14   a  and the output of the AND gate  11   b  are input to a third XOR gate corresponding to an XOR gate  13   c . The output of the XOR gate  13   c  and the output of the selector  14   a  are input to a second selector corresponding to a selector  14   b.    
     The output of the XOR gate  13   b  corresponds to the upper 16 bits of a 32-bit output of the circuit illustrated in  FIG. 1 . The output of the selector  14   b  corresponds to the lower 16 bits of the 32-bit output of the circuit. 
     In the circuit illustrated in  FIG. 1 , each of the selectors  14   a  and  14   b  selects and outputs one of the two inputs in accordance with a selection signal sel. Upon receipt of a selection signal corresponding to the FL function, the selector  14   a  selects the output of the XOR gate  13   a , and the selector  14   b  selects the output of the selector  14   a . Accordingly, the circuit illustrated in  FIG. 1  serves as an FL function. Upon receipt of a selection signal corresponding to the FL −1  function, the selector  14   a  selects the input lower bit string, and the selector  14   b  selects the output of the XOR gate  13   c . Accordingly, the circuit illustrated in  FIG. 1  serves as an FL −1  function. 
     Thus, only the OR gate  12 , rather than both an AND gate and an OR gate, is used as a common part, thereby avoiding the formation of a feedback loop. 
     In the circuit illustrated in  FIG. 1 , furthermore, the FL function and the FL −1  function are merged into a single function, leading to saving of and thereby the circuit size corresponding to a 16-bit AND gate and a 16-bit XOR gate, that is, 56 gates, can be removed. Therefore, the first typical example requires a circuit size of about 336 gates for 0.18-micrometer process while the first example requires a circuit size of about 280 gates. 
     In order to further reduce the circuit size in the first example, the selectors in the first example are equivalently transformed into AND gates. 
       FIG. 2  is a circuit diagram illustrating an example configuration of a merge function according to a second example. In  FIG. 2 , the same reference numerals as those in  FIG. 1  represent the same portions as or equivalent portions to those illustrated in  FIG. 1 , and will not be described here. In the circuit illustrated in  FIG. 2 , the selectors  14   a  and  14   b  in the circuit illustrated in  FIG. 1  are moved to the input side of the XOR gates  13   a  and  13   c  to obtain a third selector corresponding to a selector  15   a  and a fourth selector corresponding to a selector  15   b , respectively. Therefore, the selectors  15   a  and  15   b  can select the output signals of the AND gates  11   a  and  11   b , respectively, or 0 signal of 16 bits. 
     In the circuit illustrated in  FIG. 2 , upon receipt of a selection signal corresponding to the FL function, the selector  15   a  selects the output of the AND gate  11   a , and the selector  15   b  selects the 0 signal. Accordingly, the circuit illustrated in  FIG. 2  serves as an FL function. In the circuit illustrated in  FIG. 2 , upon receipt of a selection signal corresponding to the FL −1  function, the selector  15   a  selects the 0 signal, and the selector  15   b  selects the output of the AND gate  11   b . Accordingly, the circuit illustrated in  FIG. 2  serves as an FL −1  function. 
       FIG. 3  is a circuit diagram illustrating an example configuration of a merge function according to a third example. In  FIG. 3 , the same reference numerals as those in  FIG. 2  represent the same portions as or equivalent portions to those illustrated in  FIG. 2 , and will not be described here. In the circuit illustrated in  FIG. 3 , the selectors  15   a  and  15   b  in the circuit illustrated in  FIG. 2  are equivalently transformed into a first AND gate corresponding to an AND gate  16   a  and a second AND gate corresponding to an AND gate  16   b , respectively. In the circuit illustrated in  FIG. 2 , the selection signals sel for the selectors are 1-bit signals, whereas in the circuit illustrated in  FIG. 3 , selection signals sel are 16-bit expanded signals. 
     In the circuit illustrated in  FIG. 3 , the AND gate  16   a  performs an AND operation between the output of the AND gate  11   a  and the selection signal sel. The AND gate  16   b  performs an AND operation between the output of the AND gate  11   b  and the negation of the selection signal sel. 
     Thus, the transformation of selectors into AND gates allows the circuit illustrated in  FIG. 3  to further reduce the circuit size as compared with the circuit illustrated in  FIG. 1 . 
     The merging of the FL function and the FL −1  function into a single function may cause an extension of the critical path, leading to a reduction in processing speed. 
     It is assumed here that a 2-1 NAND gate has a delay d. When an AND gate, an OR gate, an XOR gate, and a selector are configured using only NAND gates, the delays of the individual gates are 2d, 2d, 3d, and 3d, respectively. 
     The delay of the critical path in the first typical example illustrated in  FIG. 12  is given by the sum of the delay of FL or FL −1  and the delay of the selector that selects FL or FL −1 . Here, the delay of FL or FL −1  is given by (first stage: AND-XOR)+(second stage: OR-XOR) for FL or (first stage: OR-XOR)+(second stage: AND-XOR) for FL −1 . Therefore, the delay of FL or FL −1  is given by (2d+3d)+(2d+3d)=10d. Further, the delay of the selector that selects FL or FL −1  is 3d. Therefore, the critical path in the first typical example has a delay of 13d. 
     In contrast, the delay of the critical path in the third example illustrated in  FIG. 2  is given by (first stage: AND-sel-XOR)+(second stage: OR-XOR)+(third stage: AND-sel-XOR)=(2d+3d+3d)+(2d+3d)+(2d+3d+3d)=21d. This is because while the FL function and the FL −1  function are in parallel in the first typical example illustrated in  FIG. 12 , the FL function and the FL −1  function are in tandem in the third example illustrated in  FIG. 3 . In the following, in order to overcome the inconvenience described above, the AND gates equivalently transformed in the third example are removed from the critical path. 
       FIG. 4  is a circuit diagram illustrating an example configuration of a merge function according to a fourth example. In  FIG. 4 , the same reference numerals as those in  FIG. 3  represent the same portions as or equivalent portions to those illustrated in  FIG. 3 , and will not be described here. In the circuit illustrated in  FIG. 4 , the AND gates  16   a  and  16   b  in the circuit illustrated in  FIG. 3  are removed from the critical path and are replaced by a third AND gate corresponding to an AND gate  17   a  and a fourth AND gate corresponding to an AND gate  17   b , respectively. 
     In the circuit illustrated in  FIG. 4 , the AND gate  17   a  performs an AND operation between a selection signal sel and KL i1 . The AND gate  17   b  performs an AND operation between the negation of the selection signal sel and KL i1 . 
     In MISTY1, a path for generating an extended key KL ij  is not a critical path. This is because there are a large number of known implementations capable of generating KL ij  in a cycle preceding the processing cycle of the FL function. The application of those implementations to MISTY1 can prevent the effect of the delay time for generating the extended key KL ij  on the delay time of the FL function. With the consideration of the nature of MISTY1, the AND gates  16   a  and  16   b  illustrated in  FIG. 3  can be moved to the positions of the AND gates  17   a  and  17   b  illustrated in  FIG. 4 . Therefore, the delay of the critical path in the circuit illustrated in  FIG. 4  can be reduced by an amount corresponding to two AND gates, as compared with that in the circuit illustrated in  FIG. 3 . That is, the delay of the critical path in the circuit illustrated in  FIG. 4  is given by (first stage: AND-XOR)+(second stage: OR-XOR)+(third stage: AND-XOR)=(2d+3d)+(2d+3d)+(2d+3d)=15d. 
       FIG. 5  is a circuit diagram illustrating an example configuration of a merge function according to a fifth example. In  FIG. 5 , the same reference numerals as those in  FIG. 1  represent the same portions as or equivalent portions to those illustrated in  FIG. 1 , and will not be described here. The fifth example has a basic configuration and advantages similar to those in the first example illustrated in  FIG. 1 , but is different in the arrangement of OR gates and an AND gate. In the circuit illustrated in  FIG. 1 , an OR gate is common to the FL function and the FL −1  function, whereas in the circuit illustrated in  FIG. 5 , an AND gate is common to the FL function and the FL −1  function. More specifically, the circuit illustrated in  FIG. 5  is configured using a circuit including a first arithmetic gate corresponding to an OR gate  21   a  in the first stage, a second arithmetic gate corresponding to an AND gate  22  in the second stage, and a third arithmetic gate corresponding to an OR gate  21   b  in the third stage. In the circuit illustrated in  FIG. 5 , only the AND gate  22  is common to the two functions. 
     In the circuit illustrated in  FIG. 5 , the output of the OR gate  21   a  is connected to the input of the XOR gate  13   a . The output of the AND gate  22  is connected to the input of the XOR gate  13   b . The output of the OR gate  21   b  is connected to the input of the XOR gate  13   c . In the fifth example and the following sixth and seventh examples, a first extended key bit string corresponds to the input of an OR gate based on KL i2 , and a second extended key bit string corresponds to the input of an AND gate based on KL i1 . 
       FIG. 6  is a circuit diagram illustrating an example configuration of a merge function according to the sixth example. In  FIG. 6 , the same reference numerals as those in  FIG. 5  represent the same portions as or equivalent portions to those illustrated in  FIG. 5 , and will not be described here. In the circuit illustrated in  FIG. 6 , the selectors  14   a  and  14   b  in the circuit illustrated in  FIG. 5  are moved to the input side of the XOR gates  13   a  and  13   c  to obtain selectors  15   a  and  15   b , respectively. The sixth example has a basic configuration and advantages similar to those of the second example, but is different in the arrangement of OR gates and an AND gate. 
       FIG. 7  is a circuit diagram illustrating an example configuration of a merge function according to the seventh example. In  FIG. 7 , the same reference numerals as those in  FIG. 6  represent the same portions as or equivalent portions to those illustrated in  FIG. 6 , and will not be described here. In the circuit illustrated in  FIG. 7 , the selectors  15   a  and  15   b  in the circuit illustrated in  FIG. 6  are equivalently transformed into AND gates  16   a  and  16   b , respectively. The seventh example has a basic configuration and advantages similar to those in the third example, but is different in the arrangement of OR gates and an AND gate. 
     As least some of the advantages of the examples described above are described below in detail. 
       FIG. 8  is a table illustrating exemplary circuit sizes of the circuits according to the respective examples. The table illustrated in  FIG. 8  provides exemplary circuit sizes in the first to seventh examples and the first and second typical examples. In the table illustrated in  FIG. 8 , #1-bit MUX represents the number of selectors having a width of 1 bit. #1-bit AND/OR represents the number of AND gates and OR gates having a width of 1 bit. #1-bit XOR represents the number of XOR gates having a width of 1 bit. Gate Count represents the circuit size concerning the FL function and the FL −1  function. In the first typical example, the circuit size is as large as 336 gates. This is because the FL function and the FL −1  function are independently provided, and a selector for switching between the functions is also required. The second typical example allows a small circuit size; however, due to the use of the feedback loop structure, the implementation cannot be commercialized into a product. The first and second examples allow a reduction in circuit size as compared with the first typical example, but have small advantages. This is because the circuit sizes of the selectors are the same. The third and fourth examples allow a reduction in circuit size up to 200 gates by equivalently transforming the selectors in the first example into AND gates. 
     Accordingly, it can be expected that, when the first typical example and the fourth example are compared, the circuit size concerning the FL function and the FL −1  function is reduced from 336 gates to 200 gates, that is, by about 40%. 
     The overall circuit size of a typical compact MISTY1 hardware implementation is about 4000 gates for 0.18-micrometer process according to Yamamoto et al. in the paper mentioned above. The application of the fourth example to this typical technique allows a reduction in circuit size by about 3.5%. 
     Further, the overall circuit size of a typical compact KASUMI hardware implementation is about 3400 gates for 0.13-micrometer process according to Satoh and Morioka in the paper mentioned above. The application of the fourth example to this typical technique allows a reduction in circuit size by up to 4%. 
       FIG. 9  is a table illustrating exemplary delay times in the respective examples. The table illustrated in  FIG. 9  provides exemplary delay times in the first to seventh examples and the first and second typical examples. In the table illustrated in  FIG. 9 , AND/OR represents the number of AND gates and OR gates in the merge function. XOR represents a number of XOR gates in a merge function. 2-1MUX represents the number of selectors in the merge function. Delay represents the delay time of the merge function. In the first typical example, the delay time is 13d. In the first example, in contrast, the delay time is larger and is 21d. This is because, as described previously, the merge function has a three-stage structure, and additional selectors are generated within the merge function. In the third example, the equivalent transformation of the selectors into AND gates allows a reduction in delay time by 2d but the delay time is still larger than that in the first typical example. In the fourth example, the removal of the two AND gates from the critical path results in a delay time of 15d. Therefore, the delay time in the fourth example is substantially equivalent to that in the first typical example, i.e., 13d. 
     According to the first or fifth example, one of an AND gate and an OR gate, rather than both an AND gate and an OR gate, is used as a common module to merge the functions, thereby avoiding the formation of a feedback loop. 
     According to the second, third, fourth, sixth, or seventh example, the selectors, which may cause the increase in circuit size and the extension of the critical path, are equivalently transformed into AND gates, thereby reducing the circuit size. Further, the AND gates are removed from the critical path, thereby reducing the critical path. While the configurations and structures of the embodiment(s) herein are described using specific examples, the present invention is not limited to particulars of any of the examples. 
     The embodiments can be implemented in computing hardware (computing apparatus) and/or software, such as (in a non-limiting example) any computer that can store, retrieve, process and/or output data and/or communicate with other computers. The results produced can be displayed on a display of the computing hardware. A program/software implementing the embodiments may be recorded on computer-readable media comprising computer-readable recording media. The program/software implementing the embodiments may also be transmitted over transmission communication media. Examples of the computer-readable recording media include a magnetic recording apparatus, an optical disk, a magneto-optical disk, and/or a semiconductor memory (for example, RAM, ROM, etc.). Examples of the magnetic recording apparatus include a hard disk device (HDD), a flexible disk (FD), and a magnetic tape (MT). Examples of the optical disk include a DVD (Digital Versatile Disc), a DVD-RAM, a CD-ROM (Compact Disc-Read Only Memory), and a CD-R (Recordable)/RW. An example of communication media includes a carrier-wave signal. 
     Further, according to an aspect of the embodiments, any combinations of the described features, functions and/or operations can be provided. 
     All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiment of the present invention has been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention, the scope of which is defined in the claims and their equivalents.