Imported: 10 Mar '17 | Published: 27 Nov '08

USPTO - Utility Patents

According to an aspect of the present invention, there is provided a non-linear data converter including: first to fourth converters that each performs a respective converting process on an input bit string to output respective output bit string; a generator that generates a random number bit string; and a selector that selects any one of the output bit strings from the first to fourth converters based on the random number bit string. Each of the converting processes is equivalent to performing a first mask process, a non-linear conversion predetermined for an encoding or a decoding and a second mask process.

The entire disclosure of Japanese Patent Application No. 2007-137842 filed on May 24, 2007 including specification, claims, drawings and abstract is incorporated herein by reference in its entirety.

1. Field of the Invention

An aspect of the present invention relates to a non-linear data converter, an encoder and a decoder.

2. Description of the Related Art

An encoder or a decoder by a common key encoding system such as a DES (Data Encryption Standard) is mounted on an IC card or the like and widely used. It is very important to protect a secret key from an illegal access.

For instance, as disclosed in JP-A-2000-66585 showing a counter measure to an illegal access such as a DPA (Differential Power Analysis) for estimating a secret key from a consumed electric power during the operation of an encoder or a decoder, a method is reported that a predetermined mask value and a mask value obtained by inverting bits thereof are selected at random for each encoding operation or decoding operation to perform a mask process.

However, in JP-A-2000-66585, a resistance to a high-order DPA for estimating the secret key from a consumed electric power at a plurality of timings is not considered.

According to an aspect of the present invention, there is provided a non-linear data converter including: a first converter that performs a first process on an input bit string to output a first output bit string, the first process equivalent to performing: a mask process using a first mask, a non-linear conversion predetermined for performing an encoding or a decoding, and a mask process using a second mask; a second converter that performs a second process on the input bit string to output a second output bit string, the second process equivalent to performing: the mask process using the first mask, the non-linear conversion, and a mask process using an inverted second mask; a third converter that performs a third process on the input bit string to output a third output bit string, the third process equivalent to performing: a mask process using an inverted first mask, the non-linear conversion, and the mask process using the second mask; a fourth converter that performs a fourth process on the input bit string to output a fourth output bit string, the fourth process equivalent to performing: the mask process using the inverted first mask, the non-linear conversion, and the mask process using the inverted second mask; a generator that generates a random number bit string; and a selector that selects any one of the first to fourth output bit strings based on the random number bit string.

According to anther aspect of the present invention, there is provided a non-linear data converter including: a first converter that performs a first process on an input bit string to output a first output bit string, the first process equivalent to performing: a mask process using a first mask, a non-linear conversion predetermined for performing an encoding or a decoding, and a mask process using a second mask; a first inverter that inverts the first output bit string to output a second output bit string; a second converter that performs a second process on the input bit string to output a third output bit string, the second process equivalent to performing: a mask process using an inverted first mask, the non-linear conversion, and the mask process using the second mask; a second inverter that inverts the third output bit string to output a fourth output bit string; a generator that generates a random number bit string; and a selector that selects any one of the first to fourth output bit strings based on the random number bit string.

According to still anther aspect of the present invention, there is provided an encoder including: a key scheduler that generates a j-th enlarged key from a secret key, j being an integer larger than 1 and smaller than z, z being an integer larger than 2; a random number generator that generates a j-th random number bit string; a mask generator that generates a j-th first mask and a j-th second mask based on the j-th random number bit string, a predetermined first mask and a predetermined second mask; a pre-processor that outputs a first bit string based on an input plaintext block; a j-th function calculator that performs an encoding calculation to a j-th bit string to output a (j+1)-th bit string; and a post-processor that outputs a ciphertext block based on a (Z+1)-th bit string; wherein the j-th function calculator includes: a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing: a mask process using the j-th first mask, a non-linear conversion predetermined for performing an encoding, and a mask process using the j-th second mask; a second converter that performs a second process on the j-th bit string to output a second converted bit string, the second process equivalent to performing: the mask process using the j-th first mask, the non-linear conversion, and a mask process using an inverted j-th second mask; a third converter that performs a third process on the j-th bit string to output a third converted bit string, the third process equivalent to performing: a mask process using an inverted j-th first mask, the non-linear conversion, and the mask process using the j-th second mask; a fourth converter that performs a fourth process on the j-th bit string to output a fourth converted bit string, the fourth process equivalent to performing: the mask process using the inverted j-th first mask, the non-linear conversion, and the mask process using the inverted j-th second mask; and a selector that selects any one of the first to fourth converted bit strings based on the j-th random number bit string to output as the (j+1)-th bit string.

According to still anther aspect of the present invention, there is provided a decoder including: a key scheduler that generates a j-th enlarged key from a secret key, j being an integer larger than 1 and smaller than z, z being an integer larger than 2; a random number generator that generates a j-th random number bit string; a mask generator that generates a j-th first mask and a j-th second mask based on the j-th random number bit string, a predetermined first mask and a predetermined second mask; a pre-processor that outputs a first bit string based on an input ciphertext block; a j-th function calculator that performs a decoding calculation to a j-th bit string to output a (j+1)-th bit string; and a post-processor that outputs a decoded sentence block based on a (Z+1)-th bit string; wherein the j-th function calculator includes: a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing: a mask process using the j-th first mask, a non-linear conversion predetermined for performing an encoding, and a mask process using the j-th second mask; a second converter that performs a second process on the j-th bit string to output a second converted bit string, the second process equivalent to performing: the mask process using the j-th first mask, the non-linear conversion, and a mask process using an inverted j-th second mask; a third converter that performs a third process on the j-th bit string to output a third converted bit string, the third process equivalent to performing: a mask process using an inverted j-th first mask, the non-linear conversion, and the mask process using the j-th second mask; a fourth converter that performs a fourth process on the j-th bit string to output a fourth converted bit string, the fourth process equivalent to performing: the mask process using the inverted j-th first mask, the non-linear conversion, and the mask process using the inverted j-th second mask; and a selector that selects any one of the first to fourth converted bit strings based on the j-th random number bit string to output as the (j+1)-th bit string.

According to still anther aspect of the present invention, there is provided an encoder including: a key scheduler that generates a j-th enlarged key from a secret key, j being an integer larger than 1 and smaller than z, z being an integer larger than 2; a random number generator that generates a j-th random number bit string; a mask generator that generates a j-th first mask and a j-th second mask based on the j-th random number bit string, a predetermined first mask and a predetermined second mask; a pre-processor that outputs a first bit string based on an input plaintext block; a j-th function calculator that performs an encoding calculation to a j-th bit string to output a (j+1)-th bit string; and a post-processor that outputs a ciphertext block based on a (Z+1)-th bit string; wherein the j-th function calculator includes: a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing: a mask process using the j-th first mask, a non-linear conversion predetermined for performing an encoding process, and a mask process using the j-th second mask; a first inverter that inverts the first converted bit string to output a second converted bit string; a second converter that performs a second process on the j-th bit string to output a third converted bit string, the second process equivalent to performing: a mask process using an inverted j-th first mask, the non-linear conversion, and the mask process using the j-th second mask; a second inverter that inverts the third converted bit string to output a fourth converted bit string; and a selector that selects any one of the first to fourth converted bit strings based on the j-th random number bit string to output as the (j+1)-th bit string.

According to still anther aspect of the present invention, there is provided a decoder including: a key scheduler that generates a j-th enlarged key from a secret key, j being an integer larger than 1 and smaller than z, z being an integer larger than 2; a random number generator that generates a j-th random number bit string; a mask generator that generates a j-th first mask and a j-th second mask based on the j-th random number bit string, a predetermined first mask and a predetermined second mask; a pre-processor that outputs a first bit string based on an input ciphertext block; a j-th function calculator that performs a decoding calculation to a j-th bit string to output a (j+1)-th bit string; and a post-processor that outputs a decoded sentence block based on a (Z+1)-th bit string; wherein the j-th function calculator includes: a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing: a mask process using the j-th first mask, a non-linear conversion predetermined for performing an encoding process, and a mask process using the j-th second mask; a first inverter that inverts the first converted bit string to output a second converted bit string; a second converter that performs a second process on the j-th bit string to output a third converted bit string, the second process equivalent to performing: a mask process using an inverted j-th first mask, the non-linear conversion, and the mask process using the j-th second mask; a second inverter that inverts the third converted bit string to output a fourth converted bit string; and a selector that selects any one of the first to fourth converted bit strings based on the j-th random number bit string to output as the (j+1)-th bit string.

Embodiments will be described below.

FIG. 1 is a block diagram showing a basic structure of an encoder **5** of an encoding algorithm DES (Date Encryption Standard).

A key schedule part **20** calculates extension keys **21***a*, **21***b*, . . . , **21***p *by using key information **19** held as secret information. The extension keys **21***a*, **21***b*, . . . , **21***p *are supplied to the round functions **30***a *to **30***p *of a first round to a 16 th round. The round functions **30***a *to **30***p *respectively agitate a plaintext block **9** (64 bits) by using the extension keys **21***a*, **21***b*, . . . , **21***p*. The plaintext block **9** is permutated by an initial permutation IP **10**, then respectively agitated by the round functions **30***a *to **30***p *and finally permutated by a final permutation FP **40** to become a ciphertext block **41**.

After the plaintext block **9** is permutated by the initial permutation IP**10**, the plaintext block is divided into upper 32 bits and lower 32 bits which are input to a right side input and a left side input of the round function **30***a *of the first round. Similarly, the round function **30***a *of the first round outputs two bit strings (32 bits) respectively from a right side output and a left side output.

The two bit strings output by the round function **30***a *of the first round are input to the round function **30***b *of the second round. That is, the bit string output from the right side output of the round function **30***a *of the first round is input to the right side input of the round function **30***b *of the second round and the bit string output from the left side output of the round function **30***a *of the first round is input to the left side input of the round function **30***b *of the second round. After that, in the round functions **30***b *to **30***p *of the second round to the 16 th round, the same processes are repeated. Two bit strings as outputs of the round function **30***p *of the 16 th round whose orders are changed are concatenated together and input to the final permutation FP**40**.

FIG. 2 is a diagram showing the structure of the round function **30***a *of the first round. It is understood that the round functions **30***b *to **30***p *of the second round to the 16 th round have the same structures.

The round function **30***a *of the first round includes an extension permutation E**31**, an exclusive OR **37** that performs an exclusive OR calculation of an output of the extension permutation E**31** and the extension key **21***a*, eight S boxes (S**1**, S**2**, . . . , S**8**) **33***a *to **33***h*, a permutation P**34**, and an exclusive OR **35** for performing an exclusive OR calculation of an output of the permutation P**34** and the left side input of 32 bits of the round function **30***a *of the first round.

The right side input of 32 bits of the round function **30***a *of the first round is permutated by the extension permutation E**31** and extended to 48 bits. Then, the exclusive OR **37** performs an exclusive OR calculation of the output of 48 bits from the extension permutation E**31** and the extension key **21***a *of 48 bits. The output of 48 bits from the exclusive OR **37** is equally divided into eight bit strings at intervals of 6 bits which are respectively input to the eight S boxes (S**1**, S**2**, . . . , S**8**) **33***a *to **33***h. *

The S boxes (S**1**, S**2**, . . . , S**8**) **33***a *to **33***h *respectively non-linearly convert the input bit strings of 6 bits into bit strings of 4 bits. For instance, a table showing an input and output relation of the S box (S**1**) **33***a *of the DES is displayed in table 1.

Two bits (0 to 3: binary number) composed of a most significant bit and a least significant bit of 6 input bits designate row numbers of the S box (S**1**) **33***a *shown in table 1. The row numbers of the S box (S**1**) **33***a *shown in the Table 1 are set to 0, 1, 2 and 3 from an upper part. 4 bits (**0** to **15**: binary number) remaining by excluding the most significant bit and the least significant bit from the six input bits designate column numbers of the S box (S**1**) **33***a *shown in the Table 1. The column numbers of the S box (S**1**) **33***a *shown in the Table 1 are counted as 1, 1, 2, 3, . . . , 15 from a left end.

Assuming that the bit string input to the S box (S**1**) **33***a *is 011011, the row number is 1 (01/b: binary) and the column number is 13 (1101/b), so that an output value 5 is obtained. Accordingly, the output of the S box (S**1**) **33***a *is 0101. The S box (S**1**) **33***a *includes six input lines (one corresponds to 1 bit) and four output lines (one corresponds to 1 bit) and is formed with a suitable combination of wiring and logical elements (NAND, NOR or the like) for connecting the input lines to the output lines so that the input and output relation shown in the table 1 is obtained.

32 bits obtained by sequentially concatenating the bit strings (4 bit8) respectively output from the S boxes (S**1**, S**2**, . . . , S**8**) including the output bit string of the S box (S**1**) **33***a *to the output bit string of the S box (S**8**) **33***h *are permutated by the permutation P**34**. Then, the exclusive OR **35** performs an exclusive OR calculation of the output of 32 bits from the permutation P**34** and the left side input of 32 bits of the round function **30***a *of the first round. The calculated result of the exclusive OR **35** becomes the right side output of 32 bits from the round function **30***a *of the first round. The left side output of the round function **30***a *of the first round is the same as the right side input.

FIG. 3 is a block diagram showing an encoder **100** according to a first embodiment. The encoder **100** according to the first embodiment includes an initial permutation part (IP) **105** for performing an initial permutation of an externally input plaintext block of 64 bits, exclusive ORs **130**A and **130**B for performing an exclusive OR calculation of a bit string output by the initial permutation part **105** and mask values rmsk_{0 }and lmsk_{0}, exclusive ORs **130***a *to **130***h *for performing an exclusive OR calculation for a mask process or a mask removing process, a selector **110**L for selecting a left side input of 32 bits of a round function from any one of an output of the exclusive OR **130**A, an output of the exclusive OR **130***h *and an output of the exclusive OR **130***b*, a selector **110**R for selecting the right side input of 32 bits of the round function from any one of an output of the exclusive OR **130**B, an output of the exclusive OR **130***h *and an output of the exclusive OR **130***b*, registers **120**L and **120**R for storing outputs of 32 bits from the selectors **110**L and **110**R, an exclusive OR **130***z *for performing an exclusive OR calculation of an output of the exclusive OR **130***d *and an extension key rkey_{j}, a random number generating part **145** for generating a random number bit string for each round function, an extension permutation part (E) **150**, a permutation part (P) **160**, exclusive ORs **130**C and **130**D for performing an exclusive OR calculation of two outputs of the round function of a 16 th round and below described mask values rmsk_{16 }and lmsk_{16 }and a final permutation part (FP) **165** for performing a final permutation to a received bit string to output a ciphertext block of 64 bits to an external part.

The encoder **100** according to the first embodiment includes four respectively different modified S boxes **141***a *to **144***a *(first group of modified S boxes **140***a*) that are formed in accordance with a non-linear converting system of the S box (S**1**) **33***a *of a DES and a selector **110***a *for selecting one of outputs of the four modified S boxes **141***a *to **144***a *of the first group of modified S boxes.

Although eight groups of the four modified S boxes **141***a *to **144***a *are provided as similarly to FIG. 2, the boxes are omitted form FIG. 3 due to a limitation in the sheet size. It is understood that there are the first group of modified S boxes **140***a *including the four respectively different modified S boxes to the eighth group of modified S boxes which are respectively formed in accordance with the non-linear converting system. It is understood that there are selectors **110***a *to **110***h *for respectively selecting the outputs of the first group of modified S boxes **140***a *to the eighth group of modified S boxes **140***h. *

The initial permutation **105**, the selectors **110**L and **110**R, the registers **120**L and **120**R, the exclusive ORs **130**A to **130**D, **130***a *to **130***h *and **130***z*, the first group of modified S boxes **140***a *to the eighth group of modified S boxes **140***h *(in this case, a second group of modified S boxes **140***b *to the eighth group of modified S boxes **140***h *are not shown), the extension permutation part **150**, the permutation part **160** and the final permutation part **165** operate synchronously with a clock signal.

The random number generating part **145** generates two random number bit strings of 8 bits (lmptn_{j}, rmptn_{j}) (j=1, 2, . . . , 16) respectively for the calculation of the round functions (from the first round to the 16 th round).

Mask values (rmsk_{j}, lmsk_{j}) of 32 bits and a mask value (ermsk_{j}) of 48 bits are mask values generated in accordance with the random number bit strings (lmptn_{j}, rmptn_{j}) and a mask value a (it cannot be externally detected) of 4 bits that is predetermined in the encoder **100**. In a below-description, a designates a bit string of 4 bits obtained by inverting a for each bit, a designates a bit string of 6 bits shown by 0a0| and a designates a bit string shown by 1a1. shows a bit concatenation.

The mask values of (lmsk_{j}, rmsk_{j}) of 32 bits are generated by extending each of the bits of the random number bit strings (lmptn_{j}, rmptn_{j}) of 8 bits to 4 bits. For instance, when the random number bit string (lmptn_{j}) is 11010100, the mask value (lmsk_{j}) of 32 bits is aaaaaaaa (a is 4 bits). When the random number bit string (rmptn_{j}) is 01011010, the mask value (rmsk_{j}) of 32 bits is aaaaaaaa.

The mask value (ermsk_{j}) of 48 bits is generated by extending each of the bits of the random number bit string (rmptn_{j}) of 8 bits to 6 bits. When the random number bit string (rmptn_{j}) is 01011010, the mask value of (ermsk_{j}) of 48 bits is 0a01a10a01a11a10a01a10a0.

FIG. 4 is a block diagram showing equivalent circuits of the modified S boxes (S**1**_{00}, S**1**_{01}, S**1**_{10}, S**1**_{11}) **141***a *to **144***a *provided in the first group of modified boxes **140***a *in a right side. It is understood that the equivalent circuits are the same as those provided in the second group of modified S boxes **140***b *to the eighth group of modified S boxes **140***h *that are not shown in the drawing.

When a bit string x of 6 bits is input to the S boxes (Si) **33***a *to **33***h *(i=1, 2, . . . , 8) of the DES, the S boxes output bit strings Si(x) of 4 bits. That is, when the bit string of 6 bits is input to the first modified S boxes (S**1**_{00}, S**1**_{01}, S**1**_{10}, S**1**_{11}) **141***a *to **144***a *to the eighth modified S boxes (S**8**_{00}, S**8**_{01}, S**8**_{10}, S**8**_{11}) **141***h *to **144***h*, the first to eighth modified S boxes output bit strings of 4 bits Si_{00}(x) Si_{01}(x), Si_{10}(x) and Si_{11}(x) (i=1, 2, . . . , 8).

An input and output relation of the first to eighth modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) **141***a *to **144***h *will be shown below. A sign + shows an exclusive OR calculation hereinafter.

Namely, the first to eighth modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) **141***a *to **144***h *are designed on the basis of a converting table led from the input and output relation so that the first to eighth modified S boxes generate the bit strings of 4 bits from the bit strings of 6 bits to calculate as Si_{00}(x)=Si(x+a)+a, Si_{01}(x)=Si(x+a)+a, Si_{10 }(x)=Si(x+a)+a, Si_{11}(x)=Si(x+a)+a (i=1, 2, . . . , 8).

An operation of the encoder **100** according to the first embodiment will be described for each clock cycle by referring to FIG. 3.

Initially, the random number generating part **145** generates the random number bit strings (rmptn_{o}, lmptn_{o}). The initial permutation part **105** divides the externally input plaintext block of 64 bits into the upper 32 bits and the lower 32 bits and output the divided plaintext blocks. The exclusive OR **130**A performs the exclusive OR calculation of the output upper 32 bits and the mask value (rmsk_{0}) calculated from the random number bit string (rmptn_{0}). The exclusive OR **130**B performs the exclusive OR calculation of the output lower 32 bits and the mask value (lmsk_{0}) calculated from the random number bit string (lmptn_{0}). The calculated results are respectively stored in the registers **120**L and **120**R through the selectors **110**L and **110**R. Since the random number bit strings (rmptn_{o}, lmptn_{o}) are used in the round function of the first round (a second clock cycle), these random number bit strings are stored. [Second to 16 th clock cycles (round function of j th round, j=1, 2, . . . , 15)]

The random number generating part **145** generates the random number bit strings (rmptn_{j}, lmptn_{j}). The exclusive OR **130***a *performs the exclusive OR calculation of the bit string of 32 bits stored in the register **120**R and the mask value (rmsk_{j}) calculated from the random number bit string (rmptn_{j}). The next exclusive OR **130***b *performs the exclusive OR calculation of an output of the exclusive OR **130***a *and a mask value (lmsk_{j1}). The calculated result thereof is output to the selectors **110**R and **110**L and the extension permutation part E**150**, permutated in the extension permutation part E**150** and extended to a bit string of 48 bits. The output of the exclusive OR **130***b *is a left output (a bit string of 32 bits) of the round function of a j th round).

The exclusive OR **130***c *performs the exclusive OR calculation of E(rmsk_{j}) obtained by performing an extension permutation (E) to the mask value (rmsk_{j}) and the mask value (ermsk_{j}). The exclusive OR **130***d *performs the exclusive OR calculation of the bit string of 48 bits output by the extension permutation part (E) **150** and the output of the exclusive OR **103***c*. The exclusive OR **130***z *performs the exclusive OR calculation of the calculated result of the exclusive OR **130***d *and an extension key (a round key: rkey_{j}) input to the round function of the j th round. The bit string of 48 bits obtained in such a way is divided into 8 bit strings (a first bit string to an eighth bit string) respectively composed of 6 bits

Then, the first bit string is input to the first group of modified S boxes **140***a *(modified S boxes **141***a *to **144***a*) to perform the non-linear conversion explained in FIG. 4. The second bit string to the eighth bit string are also input to the second group of modified S boxes **140***b *to the eighth group of modified S boxes **140***h *that are not shown in the drawing to perform the non-linear conversion explained in FIG. 4.

Selectors **110***a *to **110***h *(selectors **110***b *to **110***h *are not shown in the drawing) determine, for each of the round functions, from which of the modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}), an output is selected on the basis of an i th bit of the random number bit strings lmptn_{j} and rmptn_{j} respectively for the first group of modified S boxes **140***a *to the eighth group of modified S boxes **140***h. *

When the random number bit string of the round function of the j th round is rmptn_{j}=11010100, lmptn_{j}=01011010, since first bits of rmptn_{j} and lmptn_{j} are 1 and 0, the selector **110***a *selects an output of the modified S box (Sl_{10}) **143***a* from the first group of modified S boxes **140***a*. Outputs of modified S boxes (Si_{xy}) selected by the selectors **110***a *to **110***h *are likewise determined by substituting the i th bit of rmptn_{j} for x and the i th bit of lmptn_{j} for y. It is understood that the selectors **110***b *to **110***h *of the second group of modified S boxes **140***b *to the eighth group of modified S boxes **140***h *respectively select the modified S boxes of S**2**_{11}, S**3**_{00}, S**4**_{11}, S**5**_{01}, S**6**_{10}, S**7**_{01}, and S**8**_{00}.

The bit strings of 4 bits of the first group of modified S boxes **140***a *to the eighth group of modified S boxes **140***h *selected by the selectors **110***b *to **110***h *are sequentially concatenated together to be a bit string of 32 bits which is input to the exclusive OR **130***e. *

After that, the exclusive OR **130***e *performs the exclusive OR calculation of the concatenated bit string of 32 bits and P^{1 }(lmptn_{j}) obtained by performing an inverse calculation of a permutation (P) to the mask value (lmsk_{j}) calculated from the random number bit string (lmptn_{j}). Then, the exclusive OR **130***f *performs the exclusive OR calculation of an output of the exclusive OR **130***e *and the mask value (lmsk_{j}). The calculated result is input to the permutation part (P) **160** and permutated.

Subsequently, the exclusive OR **130***g *performs the exclusive OR calculation of the bit string of 32 bits output from the permutation part (P) **160** and the bit string of 32 bits stored in the register **120**L. The exclusive OR **130***h *performs the exclusive OR calculation of an output of the exclusive OR **130***g *and a mask value (rmsk_{j1}).

The bit string of 32 bits of the exclusive OR **130***h *obtained by performing the above-described calculation is input to the selectors **110**R and **110**L. The selector **110**R selects the output (a right side output) of the exclusive OR **130***h *and outputs to the register **120**R. The selector **110**L selects the output (a left side output) of the exclusive OR **130***b *and outputs to the register **120**L. Since the random number bit strings (rmptn_{j}, lmptn_{j}) are used for the round function of a j+1 th round, the random number bit strings are stored.

The operation of the round function of a 16 th round is the same as those of the round functions of the first to the 15 th rounds that are performed in the second to the 16 th clock cycles except the operations of the selectors **110**L and **110**R.

In the operation of the round function of the 16 th round performed in a 17 th clock cycle, the selector **110**R selects the output (the left side output) of the exclusive OR **130***b *and transmits the output to the register **120**R. The selector **110** selects the output (the right side output) of the exclusive OR **130***h *and transmits the output to the register **120**L. Since the random number bit strings (rmptn_{16}, lmptn_{16}) are used for the exclusive OR calculation (a mask process) performed immediately before the final permutation FP**165**, the random number bit strings are stored.

The exclusive OR **130**C performs the exclusive OR calculation of the bit string as the right side output of the round function of the 16 th round stored in the register **120**L and a mask value (lmsk_{16}) and transmits the calculated result to the final permutation (FP) **165**. The exclusive OR calculation is applied to the bit string stored in the register **120**R with the mask values (rmsk_{16}, lmsk_{15}) in the exclusive ORs **130***a *and **130***b*. Then, the exclusive OR **130**D performs the exclusive OR calculation of the bit string as the left side output of the round function of the 16th round that is output from the exclusive OR **130***b *and the mask value (rmsk_{16}) and transmits the calculated result to the final permutation (FP) **165**. The final permutation (FP) **165** concatenates the two bit strings received from the exclusive ORs **130**C and **130**D and permutates them to output a ciphertext block of 64 bits.

As described above, it can be considered that the encoder **100** includes the S box of the DES in which the mask process is applied to the input bit string by a or a and the mask process is applied to the output bit string by a or a to form the four kinds of modified S boxes and one of the outputs of the modified S boxes is selected at random. Thus, a resistance to a higher order DPA can be ensured.

As similar to the encoder **100**, a decoder can be constructed. Similarly, it is considered that the decoder includes the box of the DES in which the mask process is applied to the input bit string by a or a and the mask process is applied to the output bit string by a or a to form the four kinds of modified S boxes and one of the outputs of the modified S boxes is selected at random. Thus, when the ciphertext block is decoded to the plaintext block, a resistance to a higher order DPA can be also ensured.

As described above, in the first embodiment, the random number generating part **145** generates the two random number bit strings of 8 bits (lmptn_{j}, rmptn_{j}) every time the calculation of the round function of each round (the first round to the 16 th round) is performed.

As compared therewith, in a first modified example of the first embodiment, an explanation will be given to a form where a random number generating part **145** generates two random number bit strings (mptn_{0}, mptn_{1}) of 8 bits in accordance with the calculation of a round function of, for instance, a first round and generates one random number bit string (mptn_{j}) of 8 bits in the calculation of a round function of a j th round (j=2, . . . , 16).

FIG. 5 is a block diagram showing an encoder **100** according to the first modified example of the first embodiment.

The encoder **100** according to the first modified example is different from the first embodiment in a point that exclusive ORs **130***a *and **130***b *are not provided. The random number bit string (rmptn_{j}) that is generated by the random number generating part **145** of the first embodiment in the calculation of the round function of the j th round is a random number bit string (mptn_{j1}) generated by a random number generating part **145** according to the first modified embodiment in the calculation of a round function of a j1 th round. The random number bit string (lmptn_{j}) generated in the calculation of the round function of the j th round by the random number generating part **145** according to the first embodiment is a random number bit string (mptn_{j}) generated in the calculation of a round function of a j th round by the random number generating part **145** according to the first modified example.

An operation of the encoder **100** according to the first modified example is different from that of the first embodiment in view of points that the exclusive ORs **130***a *and **130***b *are not provided and the above-described random number bit strings are used as random number bit strings employed for the calculation.

In the encoder **100** according to the first modified example of the first embodiment, the reason why the exclusive ORs **130***a *and **130***b *are not provided is described below.

In the first modified example, when the calculation of the round function of the j th round is performed, a mask process and a mask removing process are performed by using the random number bit strings (mptn_{j}, mptn_{j1}) generated during the calculations of the round functions of the j th round and the j1 th round. Therefore, both mask values used when the exclusive ORs **130***a *and **130***b *perform exclusive OR calculations are (msk_{j1}), so that the exclusive ORs **130***a *and **130***b *are not necessary.

As described above, in the encoder **100** according to the first modified example of the first embodiment, since four kinds of S boxes are used, an analysis by a DPA and a higher DPA is difficult and the number of times of generations of the random number bit strings during performing an encoding calculation can be reduced to achieve a high speed calculation.

A decoder can be constructed that can reduce the number of times of generations of the random number bit strings during performing an encoding calculation and makes the analysis by the DPA and the higher order DPA difficult by using the four kinds of S boxes.

As described above, in the first embodiment, the four kinds of modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) (i=1, 2, . . . , 8) are prepared by considering the mask process to be applied to the input bit string by a or a in the S box of the DES and the mask process to be applied to the output bit string by a or a.

As compared therewith, in a second modified example, for instance, two kinds of modified S boxes (Si_{00}, Si_{10}) are prepared and two exclusive ORs are prepared for respectively inverting all bits of the outputs of the two modified S boxes (Si_{00}, Si_{10}).

FIG. 6 is a block diagram showing an encoder **100** according to the second modified example of the first embodiment.

The encoder **100** according to the second modified example is different from the first embodiment in view of points that the modified S boxes (Sl_{01}, Sl_{11}) **142***a *and **144***a *are not provided and an exclusive OR **130***x *for inverting all bits of the output of the modified S box (S**1**_{00}) **141***a *and an exclusive OR **130***y *for inverting all bits of the output of the modified S box (S**1**_{10}) **143***a *are further provided.

An operation of the encoder **100** according to the second modified example is different from that of the first embodiment in view of points that a non-linear conversion is not performed in the two modified S boxes (S**1**_{01}, S**1**_{11}), the exclusive OR **130***x *inverts all the bits of the output of the modified S box (S**1**_{00}) **141***a *and the exclusive OR **130***y *inverts all the bits of the output of the modified S box (S**1**_{11}) **144***a*, and a selector **110***a *selects anyone of outputs of the modified S box (S**1**_{00}) **141***a *as an input, the exclusive OR **130***x *regarded as the modified S box (S**1**_{01}), the modified S box (S**1**_{10}) **143***a *or the exclusive OR **130***y *regarded as the modified S box (S**1**_{11}) by using random number bit strings (lmptn_{j}, rmptn_{j}). A method that the selector **110***a *selects one from the four outputs by using the random number bit strings (lmptn_{j}, rmptn_{j}) is the same as the method described in the first embodiment.

As described above, according to the encoder **100** of the second modified example, the two kinds of the modified S boxes (for instance, S**1**_{00}, S**1**_{10}) and elements for inverting the bits of the outputs thereof are used so that an analysis by a DPA and a higher order DPA can be made to be difficult and the scale of a circuit of the encoder **100** can be reduced.

The two kinds of the modified S boxes (for instance, S**1**_{00}, S**1**_{10}) and elements for inverting the bits of the outputs thereof are used so that a decoder can be constructed in which the scale of a circuit can be reduced and an analysis by a DPA and a higher order DPA can be made to be difficult.

FIG. 7 is a block diagram showing a basic structure of an encoder **205** of an encoding algorithm AES (Advanced Encryption Standard).

A key schedule part **250** calculates extension keys **251** and **241***a *to **251***j *of, for instance, 128 bits, by using key information **249** held as secret information and supplies the extension keys **251** and **251***a *to **251***j *to a key adding part **240** and key adding parts **240***a *to **240***j *of respective rounds. For instance, a plaintext block of 128 bits is added to the extension key **251** in the key adding part **240** and agitated in round functions **200***a *to **200***j *of first to tenth rounds including the additions to the extension keys **251***a *to **251** to become a ciphertext block.

The round functions **200***a *to **200***i *of the first to the ninth rounds perform processes to input bit strings in SubBytes **210***a *to **210***i*, ShiftRows **220***a *to **220***i*, MixColumns **230***a *to **230***i *and the key adding parts **240***a *to **240***i*. In FIG. 7, only a structure of the round function **200***a *of the first round is shown. The round function **200***j *of the tenth round performs processes in a SubByte **210***j*, a ShiftRow **220***j *and the key adding part **240***j *to an input bit string.

The SubBytes **210***a *to **210***j*, the ShiftRows **220***a *to **220***j *and the MixColumns **230***a *to **230***i *divide the input bit string (128 bits) into 16 blocks at intervals of bit strings of 8 bits to process. The 16 blocks are designated hereinafter by s_{0,0}, s_{1, 0}, s_{2, 0}, s_{3, 0}, s_{0, 1}, s_{1, 1}, s_{2, 1}, s_{3, 1}, s_{0, 2}, s_{1, 2}, s_{2, 2}, s_{3, 2}, s_{0, 3}, s_{1, 3}, s_{2, 3}, s_{3, 3}.

The SubBytes **210***a *to **210***j *include 16 S boxes for performing a non-linear conversion to the input bit strings of 8 bits to output the bit strings of 8 bits. That is, in the SubBytes **210***a *to **210***j*, the 16 blocks s_{i, k} (bit strings of 8 bits) as the input bit strings are respectively converted into S(s_{i, k}) as the output bit strings.

The ShiftRows **220***a *to **22***j *convert the 16 blocks [s_{1, 0}, s_{i, 1}, s_{i, 2}, s_{i, 3}] (i=0, 1, 2, 3) into [s_{i, 0 o i}, s_{i, 1 o i}, s_{i, 2 o i}, s_{i, 3 o i}]. Symbol o shows an addition modulo four. Namely, when the 16 blocks is represented by a matrix, each row is changed.

The MixColumns **230***a *to **230***i *perform a matrix conversion of an equation 2 on GF(2^{8}) by regarding the data of 8 bits of each data block as a number of an octal extension body of GF(2^{8}) of GF(2) having an equation 1 established as a defined polynomial.

In the AES having a key length of 128 bits, in the key adding parts **240**, and **240***a *to **240***j*, the exclusive OR calculation of the input bit strings of 128 bits and the extension keys of 128 bits are performed.

FIG. 8 is a block diagram showing an encoder **300** according to a second embodiment.

The encoder **300** according to the second embodiment includes an exclusive OR **330***a *for performing a mask process before a plaintext block is input to a round function of a first round, a selector **310** for selecting the masked plaintext block and an output of the round function, a register **320** for storing the input of the round function, exclusive ORs **330***b *and **330***c *for performing exclusive OR calculations for a mask process or a mask removing process, a key adding part **350***a *for performing an exclusive OR calculation of the output of the exclusive OR **330***c *and an extension key (rkey_{k1}), a SubByte **360**, a ShiftRow **370**, a MixColumn **380**, a key adding part **350***b *of a round function of a 10 th round, an exclusive OR **330***d *for outputting a ciphertext block and a random number generating part **345** that generates a random number bit string for each round function.

The SubByte **360** includes four respectively different modified S boxes **341***a *to **344***a *(a first group of modified S boxes **340***a*) that are formed in accordance with a non-linear converting system of the S box (S**1**: not shown in the drawing) of an AES and a selector **310***a *for selecting one of outputs of the four modified S boxes **341***a *to **344***a *of the first group of modified S boxes **340***a. *

16 groups of modified S boxes **341***a *to **344***a *are provided, however, in FIG. 8, other boxes are omitted owing to the size of a sheet. Accordingly, in FIG. 8, it is understood that there are the first group of modified S boxes **340***a *including the four respectively different modified S boxes to the 16 th group of modified S boxes **340***p *which are respectively formed in accordance with the non-linear converting system. It is understood that there are selectors **310***a *to **310***p *for respectively selecting the outputs of the first group of modified S boxes **340***a *to the 16 th group of modified S boxes **340***p. *

The selectors **310** and **310***a *to **310***p*, the register **320**, the exclusive ORs **330***a *to **330***d*, the groups of modified S boxes **340***a *to **340***p*, the key adding parts **350***a *and **350***b*, the ShiftRow **370** and the MixClumn **380** operate synchronously with a clock signal.

The random number generating part **345** generates two random number bit strings of 16 bits (imptn_{k}, omptn_{k}) (k=1, 2, . . . , 10) respectively for the calculation of the round functions (from the first round to the 10 th round).

Mask values (imsk_{k}, omsk_{k}) of 128 bits are mask values generated in accordance with the random number bit strings (imptn_{k}, omptn_{k}) of 16 bits and a mask value a of 8 bits that is predetermined in the encoder **300**.

The mask values of (imsk_{k}, omsk_{k}) of 128 bits are generated by respectively extending the bits of the random number bit strings (imptn_{k}, omptn_{k}) of 16 bits to 8 bits. For instance, when the random number bit string (imptn_{k}) is 1101010011010100, the mask value (imsk_{k}) of 128 bits is set to aaaaaaaaaaaaaaaa. A method for generating the mask value (omsk_{k}) of 128 bits is the same as that for generating the mask value (imsk_{k}).

FIG. 9 is a block diagram showing equivalent circuits of the modified S boxes (S**1**_{00}, S**1**_{01}, S**1**_{10}, S**1**_{11}) **341***a *to **344***a *provided in the first group of modified S boxes **340***a *in a left side. It is understood that the S (S**1**) boxes of the AES in the equivalent circuits shown in FIG. 9 have the same structures and operations as those of the second group of modified S boxes **340***b *to the 16 th group of modified S boxes **340***p *that are not shown in the drawing.

When a bit string x of 8 bits is input to the S boxes (Si) of the AES (i=1, 2, . . . , 16, in this case, all Si are equal), the S boxes respectively output bit strings Si(x) of 8 bits. That is, when the bit string x of 8 bits is input to the modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) **341***a *to **344***a*, the modified S boxes respectively output bit strings of 8 bits Si_{00}(x) Si_{01}(x), Si_{10}(x) and Si_{11}(x).

A relation between the input x of the modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) **341***a *to **344***p *and the output Si_{00}(x), Si_{01}(x), Si_{10}(x), and Si_{11}(x) will be shown below. A sign + shows an exclusive OR calculation.

Namely, the modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) **341***a *to **344***p *are designed so that calculations of Si_{00}(x)=Si(x+a)+a, SiO_{1}(x)=Si(x+a)+a, Si_{10 }(x)=Si(x+a)+a, Si_{11 }(x)=Si(x+a)+a are performed on the basis of a converting table led from the relation between the input and the output.

The modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) **341***a *to **344***p *include eight input lines (one corresponds to 1 bit) and eight output lines (one corresponds to 1 bit) and are formed with suitable combinations of wiring and logical elements (NAND, NOR or the like) for connecting the input lines to the output lines. At this time, circuits for realizing the modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) **341***a *to **344***p *are designed not by connecting exclusive OR calculating circuits to the S box circuits of the AES, but in accordance with a new converting table led from the relation between the input and output.

An operation of the encoder **300** according to the second embodiment will be described for each clock cycle by referring to FIG. 8.

Initially, the random number generating part **345** generates the random number bit strings (imptn_{o}, omptn_{0}). The exclusive OR **330***a *performs the exclusive OR calculation of an externally received plaintext block of 128 bits and the mask value (omsk_{0}) calculated from the random number bit string (omptn_{o}). The calculated result is stored in the register **320** through the selector **310**. Since the random number bit string (omptn_{o}) is used in the round function of the first round (a second clock cycle), the random number bit string is stored in a memory that is not shown in the drawing.

[Second to 10 th Clock Cycles (Round Function of k th Round, k=1, 2, . . . , 9)

The random number generating part **345** generates the random number bit strings (imptn_{k}, omptn_{k}). The exclusive OR **330***b *performs the exclusive OR calculation of the bit string of 128 bits stored in the register **320** and the mask value (imsk_{k}). The next exclusive OR **330***c *performs the exclusive OR calculation of an output of the exclusive OR **330***b *and a mask value (omsk_{k1}) The key adding part **350***a *that receives the calculated result thereof performs the exclusive OR calculation with the extension key (rkey_{k1}).

The bit strings obtained in such a way are divided into 16 blocks respectively composed of 8 bit and input to the first group of modified S boxes to the 16 th group of modified S boxes (**340***a *to **340***p*). That is, 121 th to 128 th bits form the 16 th block.

The first group of modified S boxes **340***a *(modified S boxes **341***a *to **344***a*) performs a non-linear converting process to the input bit string to the first block. Similarly, the second to the 16 th groups of modified S boxes **340***b *to **340***p *(modified S boxes **341***b *to **344***p*, respectively) perform non-linear converting processes to the input bit strings to the second to the 16 th blocks.

Then, the selectors **310***a *to **310***p *select outputs of the modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) respectively for the first group of modified S boxes **340***a *to the 16 th group of modified S boxes **340***p *on the basis of an i th bit (i=1, 2, . . . , 16) of the random number bit strings imptn_{k}, omptn_{k}.

When the random number bit string of the round function of the k th round is imptn_{k}=1101010011010100, omptn_{k}=0101101001011010, since first bits of imptn_{k} and omptn_{k} are 1 and 0, the selector **310***a *selects an output of the modified S box (Sl_{10}) **343***a* from the first group of modified S boxes **340***a*. Outputs of modified S boxes (Si_{xy}) selected by the selectors **310***a *to **310***p *are likewise determined by substituting the i th bit of imptn_{k} for x and the i th bit of omptn_{k} for y. It is understood that the selectors **310***b *to **310***p *of the second group of modified S boxes **340***b *to the 16 th group of modified S boxes **340***p *respectively select the outputs of the modified S boxes of S**2**_{11}, S**3**_{00}, S**4**_{11}, S**5**_{01}, S**6**_{10}, S**7**_{01}, S**8**_{00}, S**9**_{10}, S**10**_{11}, S**11**_{00}, S**12**_{11}, S**13**_{00}, S**14**_{10}, S**15**_{01 }and S**16**_{00}.

The bit strings of 8 bits output from the first group of modified S boxes **340***a *to the 16 th group of modified S boxes **340***p *selected by the selectors **310***a *to **310***p *are sequentially concatenated together to be a bit string of 128 bits which is input to the ShiftRow **370**.

After that, the ShiftRow **370** performs the above-described converting process to the concatenated bit string of 128 bits. The random number bit string (omptn_{k}) is changed so as to meet a process performed in the ShiftRow **370**.

The MixColumn **380** performs a process to the output of the ShiftRow **370** so that mask values (a or a) of s_{i, k }correspond to mask values of s_{i, k}. Specifically, when the mask values corresponding to (s_{0, k}, s_{1, k}, s_{2, k}, s_{3, k}) are (a_{0,k}, a_{1, k}, a_{2, k}, a_{3, k}), the MixColumn **380** performs a process corresponding to an equation 3.

The MixColumn **380** uses the changed random number bit string (omptn_{k}) so as to meet the process performed in the ShiftRow **370**. After such a process is performed, the selector **310** selects the output of the MixColumn **380** and outputs it to the register **320**. Since the random number bit string (omptn_{k}) is used in the round function of a k+1 th round, the random number bit string (omptn_{k}) is stored.

The operations of the round functions of the first to the ninth rounds performed in the second to the tenth clock cycles and the bit string stored in the register **320** repeat the above-described operations in accordance with mask values of the rounds respectively until the process by the ShiftRow **370** is performed.

In the 11 th clock cycle, the output of the ShiftRow **370** becomes an input of the key adding part **350***b*. The key adding part **350***b *performs the exclusive OR calculation of the input bit string of 128 bits from the ShiftRow **370** and an extension key (rkey_{10}). The exclusive OR **330***d *performs the exclusive OR calculation of the calculated result of the key adding part **350***b *and a random number bit string (omptn_{10}) changed so as to meet the process performed in the ShiftRow **370** to output the ciphertext block of 128 bits.

As described above, in the encoder **300** according to the second embodiment, the mask process is considered to be applied to the input bit string and the output bit string by a or a in the S box of the AES to form the four kinds of modified S boxes and select at random which of the modified S boxes is to be used. Thus, a resistance to a higher order DPA can be ensured.

Similarly to the encoder **300** according to the second embodiment, a decoder can be constructed that includes the four kinds of modified S boxes formed by considering the mask process to be applied to the input bit string and the output bit string by a or a in the S box of the AES and selects at random which of the modified S boxes is to be used. Thus, a resistance to a higher order DPA can be also ensured.

As described above, in the second embodiment, the random number generating part **345** generates the two random number bit strings of 16 bits (imptn_{k}, omptn_{k}) every time the calculation of the round function of each round (the first round to the 10 th round) is performed.

As compared therewith, in a first modified example of the second embodiment, a random number generating part **345** generates two random number bit strings (mptn_{0}, mptn_{1}) of 16 bits in accordance with the calculation of a round function of, for instance, a first round and generates one random number bit string (mptn_{k}) of 16 bits in the calculation of a round function of a k th round (k=2, . . . , 10).

FIG. 10 is a block diagram showing an encoder **300** according to the first modified example of the second embodiment.

The encoder **300** according to the first modified example is different from the second embodiment in a point that exclusive ORs **330***b *and **330***c *are not provided. The random number bit string (imptn_{k}) that is generated by the random number generating part **345** of the second embodiment in the calculation of the round function of a k th round is a random number bit string (mptn_{k1}) generated by a random number generating part **345** according to the first modified example in the calculation of a round function of a k1 th round. The random number bit string (omptn_{k}) generated in the calculation of the round function of the k th round by the random number generating part **345** according to the second embodiment is a random number bit string (mptn_{k}) generated in the calculation of a round function of a k th round by the random number generating part **345** according to the first modified example.

An operation of the encoder **300** according to the first modified example is different from that of the second embodiment in view of points that the exclusive ORs **330***b *and **330***c *are not provided and the above-described random number bit strings are used as random number bit strings employed for the calculation.

In the encoder **300** according to the first modified example of the second embodiment, the reason why the exclusive ORs **330***b *and **330***c *are not provided is described below.

In the encoder **300** according to the first modified example of the second embodiment, when the calculation of the round function of the k th round is performed, a mask process and a mask removing process are performed by using the random number bit strings (mptn_{k}, mptn_{k1}) generated during the calculations of the round functions of the k th round and the k1 th round. Therefore, both mask values used when the exclusive ORs **330***b *and **330***c *perform exclusive OR calculations are (msk_{k1}), so that the exclusive ORs **330***b *and **330***c *are not necessary.

As described above, in the encoder **300** according to the first modified example of the second embodiment, since four kinds of S boxes are used, an analysis by a DPA and a higher DPA is difficult and the number of times of generations of the random number bit strings during performing an encoding calculation can be reduced to achieve a high speed calculation.

A decoder can be constructed that can reduce the number of times of generations of the random number bit strings during performing an encoding calculation and makes the analysis by the DPA and the higher order DPA difficult by using the four kinds of S boxes.

As described above, in the second embodiment, the four kinds of modified S boxes (Si_{00}, Si_{01}, Si_{10}, Si_{11}) (i=1, 2, . . . , 8) are prepared by considering the mask process to be applied to the input bit string by a or a in the S box of the AES and the mask process to be applied to the output bit string by a or a.

As compared therewith, in a second modified example of the second embodiment, for instance, two kinds of modified S boxes (Si_{00}, Si_{10}) are prepared and two exclusive ORs are prepared for respectively inverting all bits of the outputs of the two modified S boxes (Si_{00}, Si_{10}).

FIG. 11 is a block diagram showing an encoder **300** according to the second modified example of the second embodiment.

The encoder **300** according to the second modified example is different from the second embodiment in view of points that the modified S boxes (Sl_{01}, Sl_{11}) **342***a *and **344***a *are not provided and an exclusive OR **330***x *for inverting all bits of the output of the modified S box (S**1**_{00}) **341***a *and an exclusive OR **330***y *for inverting all bits of the output of the modified S box (S**1**_{10}) **343***a *are further provided.

An operation of the encoder **300** according to the second modified example of the second embodiment is different from that of the second embodiment in view of points that an operation (a non-linear conversion) is not performed in the modified S boxes (S**1**_{01}, S**1**_{11}), the exclusive OR **330***x *inverts all the bits of the output of the modified S box (S**1**_{00}) **341***a *and the exclusive OR **330***y *inverts all the bits of the output of the modified S box (S**1**_{10}) **343***a*, and a selector **310***a *selects any one of outputs of the modified S box (S**1**_{00}) **341***a *as an input, the exclusive OR **330***x*, the modified S box (S**1**_{10}) **343***a *or the exclusive OR **330***y *by using the random number bit strings (imptn_{k}, omptn_{k}).

As described above, according to the encoder **300** of the second modified example of the second embodiment, the two kinds of the modified S boxes (for instance, S**1**_{00}, S**1**_{10}) and elements for inverting the bits of the outputs thereof are used so that an analysis by a DPA and a higher order DPA can be made to be difficult and the scale of a circuit of the encoder **300** can be reduced.

The two kinds of the modified S boxes (for instance, S**1**_{00}, S**1**_{10}) and elements for inverting the bits of the outputs thereof are used so that a decoder can be constructed in which the scale of a circuit can be reduced and an analysis by a DPA and a higher order DPA can be made to be difficult.

The present invention is not directly limited to the above-described embodiments and components may be modified and embodied within a scope without departing from a gist thereof in the course of embodying. Further, a plurality of components disclosed in the above-described embodiments may be suitably combined together so that various inventions can be devised. For instance, some components may be deleted from all the components disclosed in the embodiments. Further, the components included in the different embodiments may be suitably combined together.

According to an aspect of the present invention, a resistance to a high-order DPA can be ensured.

a first converter that performs a first process on an input bit string to output a first output bit string, the first process equivalent to performing:

a mask process using a first mask,

a non-linear conversion predetermined for performing an encoding or a decoding, and

a mask process using a second mask;

a second converter that performs a second process on the input bit string to output a second output bit string, the second process equivalent to performing:

the mask process using the first mask,

the non-linear conversion, and

a mask process using an inverted second mask;

a third converter that performs a third process on the input bit string to output a third output bit string, the third process equivalent to performing:

a mask process using an inverted first mask,

the non-linear conversion, and

the mask process using the second mask;

a fourth converter that performs a fourth process on the input bit string to output a fourth output bit string, the fourth process equivalent to performing:

the mask process using the inverted first mask,

the non-linear conversion, and

the mask process using the inverted second mask;

a generator that generates a random number bit string; and

a selector that selects any one of the first to fourth output bit strings based on the random number bit string.

a first converter that performs a first process on an input bit string to output a first output bit string, the first process equivalent to performing:

a mask process using a first mask,

a non-linear conversion predetermined for performing an encoding or a decoding, and

a mask process using a second mask;

a second converter that performs a second process on the input bit string to output a second output bit string, the second process equivalent to performing:

the mask process using the first mask,

the non-linear conversion, and

a mask process using an inverted second mask;

a third converter that performs a third process on the input bit string to output a third output bit string, the third process equivalent to performing:

a mask process using an inverted first mask,

the non-linear conversion, and

the mask process using the second mask;

a fourth converter that performs a fourth process on the input bit string to output a fourth output bit string, the fourth process equivalent to performing:

the mask process using the inverted first mask,

the non-linear conversion, and

the mask process using the inverted second mask;

a generator that generates a random number bit string; and

a selector that selects any one of the first to fourth output bit strings based on the random number bit string.

a mask process using a first mask,

a non-linear conversion predetermined for performing an encoding or a decoding, and

a mask process using a second mask;

the mask process using the first mask,

the non-linear conversion, and

a mask process using an inverted second mask;

a mask process using an inverted first mask,

the non-linear conversion, and

the mask process using the second mask;

the mask process using the inverted first mask,

the non-linear conversion, and

the mask process using the inverted second mask;

a first converter that performs a first process on an input bit string to output a first output bit string, the first process equivalent to performing:

a mask process using a first mask,

a non-linear conversion predetermined for performing an encoding or a decoding, and

a mask process using a second mask;

a first inverter that inverts the first output bit string to output a second output bit string;

a second converter that performs a second process on the input bit string to output a third output bit string, the second process equivalent to performing:

a mask process using an inverted first mask,

the non-linear conversion, and

the mask process using the second mask;

a second inverter that inverts the third output bit string to output a fourth output bit string;

a generator that generates a random number bit string; and

a selector that selects any one of the first to fourth output bit strings based on the random number bit string.

a mask process using a first mask,

a non-linear conversion predetermined for performing an encoding or a decoding, and

a mask process using a second mask;

a first inverter that inverts the first output bit string to output a second output bit string;

a second converter that performs a second process on the input bit string to output a third output bit string, the second process equivalent to performing:

a mask process using an inverted first mask,

the non-linear conversion, and

the mask process using the second mask;

a second inverter that inverts the third output bit string to output a fourth output bit string;

a generator that generates a random number bit string; and

a mask process using a first mask,

a non-linear conversion predetermined for performing an encoding or a decoding, and

a mask process using a second mask;

a mask process using an inverted first mask,

the non-linear conversion, and

the mask process using the second mask;

a key scheduler that generates a j-th enlarged key from a secret key, j being an integer larger than 1 and smaller than z, z being an integer larger than 2;

a random number generator that generates a j-th random number bit string;

a mask generator that generates a j-th first mask and a j-th second mask based on the j-th random number bit string, a predetermined first mask and a predetermined second mask;

a pre-processor that outputs a first bit string based on an input plaintext block;

a j-th function calculator that performs an encoding calculation to a j-th bit string to output a (j+1)-th bit string; and

a post-processor that outputs a ciphertext block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding, and

a mask process using the j-th second mask;

a second converter that performs a second process on the j-th bit string to output a second converted bit string, the second process equivalent to performing:

the mask process using the j-th first mask,

the non-linear conversion, and

a mask process using an inverted j-th second mask;

a third converter that performs a third process on the j-th bit string to output a third converted bit string, the third process equivalent to performing:

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a fourth converter that performs a fourth process on the j-th bit string to output a fourth converted bit string, the fourth process equivalent to performing:

the mask process using the inverted j-th first mask,

the non-linear conversion, and

the mask process using the inverted j-th second mask; and

a selector that selects any one of the first to fourth converted bit strings based on the j-th random number bit string to output as the (j+1)-th bit string.

a key scheduler that generates a j-th enlarged key from a secret key, j being an integer larger than 1 and smaller than z, z being an integer larger than 2;

a random number generator that generates a j-th random number bit string;

a mask generator that generates a j-th first mask and a j-th second mask based on the j-th random number bit string, a predetermined first mask and a predetermined second mask;

a pre-processor that outputs a first bit string based on an input plaintext block;

a j-th function calculator that performs an encoding calculation to a j-th bit string to output a (j+1)-th bit string; and

a post-processor that outputs a ciphertext block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding, and

a mask process using the j-th second mask;

a second converter that performs a second process on the j-th bit string to output a second converted bit string, the second process equivalent to performing:

the mask process using the j-th first mask,

the non-linear conversion, and

a mask process using an inverted j-th second mask;

a third converter that performs a third process on the j-th bit string to output a third converted bit string, the third process equivalent to performing:

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a fourth converter that performs a fourth process on the j-th bit string to output a fourth converted bit string, the fourth process equivalent to performing:

the mask process using the inverted j-th first mask,

the non-linear conversion, and

the mask process using the inverted j-th second mask; and

a selector that selects any one of the first to fourth converted bit strings based on the j-th random number bit string to output as the (j+1)-th bit string.

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding, and

a mask process using the j-th second mask;

the mask process using the j-th first mask,

the non-linear conversion, and

a mask process using an inverted j-th second mask;

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

the mask process using the inverted j-th first mask,

the non-linear conversion, and

the mask process using the inverted j-th second mask; and

a key scheduler that generates a j-th enlarged key from a secret key, j being an integer larger than 1 and smaller than z, z being an integer larger than 2;

a random number generator that generates a j-th random number bit string;

a mask generator that generates a j-th first mask and a j-th second mask based on the j-th random number bit string, a predetermined first mask and a predetermined second mask;

a pre-processor that outputs a first bit string based on an input ciphertext block;

a j-th function calculator that performs a decoding calculation to a j-th bit string to output a (j+1)-th bit string; and

a post-processor that outputs a decoded sentence block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding, and

a mask process using the j-th second mask;

a second converter that performs a second process on the j-th bit string to output a second converted bit string, the second process equivalent to performing:

the mask process using the j-th first mask,

the non-linear conversion, and

a mask process using an inverted j-th second mask;

a third converter that performs a third process on the j-th bit string to output a third converted bit string, the third process equivalent to performing:

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a fourth converter that performs a fourth process on the j-th bit string to output a fourth converted bit string, the fourth process equivalent to performing:

the mask process using the inverted j-th first mask,

the non-linear conversion, and

the mask process using the inverted j-th second mask; and

a selector that selects any one of the first to fourth converted bit strings based on the j-th random number bit string to output as the (j+1)-th bit string.

a random number generator that generates a j-th random number bit string;

a pre-processor that outputs a first bit string based on an input ciphertext block;

a j-th function calculator that performs a decoding calculation to a j-th bit string to output a (j+1)-th bit string; and

a post-processor that outputs a decoded sentence block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding, and

a mask process using the j-th second mask;

the mask process using the j-th first mask,

the non-linear conversion, and

a mask process using an inverted j-th second mask;

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

the mask process using the inverted j-th first mask,

the non-linear conversion, and

the mask process using the inverted j-th second mask; and

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding, and

a mask process using the j-th second mask;

the mask process using the j-th first mask,

the non-linear conversion, and

a mask process using an inverted j-th second mask;

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

the mask process using the inverted j-th first mask,

the non-linear conversion, and

the mask process using the inverted j-th second mask; and

a random number generator that generates a j-th random number bit string;

a pre-processor that outputs a first bit string based on an input plaintext block;

a j-th function calculator that performs an encoding calculation to a j-th bit string to output a (j+1)-th bit string; and

a post-processor that outputs a ciphertext block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding process, and

a mask process using the j-th second mask;

a first inverter that inverts the first converted bit string to output a second converted bit string;

a second converter that performs a second process on the j-th bit string to output a third converted bit string, the second process equivalent to performing:

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a second inverter that inverts the third converted bit string to output a fourth converted bit string; and

a random number generator that generates a j-th random number bit string;

a pre-processor that outputs a first bit string based on an input plaintext block;

a post-processor that outputs a ciphertext block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding process, and

a mask process using the j-th second mask;

a first inverter that inverts the first converted bit string to output a second converted bit string;

a second converter that performs a second process on the j-th bit string to output a third converted bit string, the second process equivalent to performing:

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a second inverter that inverts the third converted bit string to output a fourth converted bit string; and

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding process, and

a mask process using the j-th second mask;

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a random number generator that generates a j-th random number bit string;

a pre-processor that outputs a first bit string based on an input ciphertext block;

a j-th function calculator that performs a decoding calculation to a j-th bit string to output a (j+1)-th bit string; and

a post-processor that outputs a decoded sentence block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a first converter that performs a first process on the j-th bit string to output a first converted bit string, the first process equivalent to performing:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding process, and

a mask process using the j-th second mask;

a first inverter that inverts the first converted bit string to output a second converted bit string;

a second converter that performs a second process on the j-th bit string to output a third converted bit string, the second process equivalent to performing:

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a second inverter that inverts the third converted bit string to output a fourth converted bit string; and

a random number generator that generates a j-th random number bit string;

a pre-processor that outputs a first bit string based on an input ciphertext block;

a post-processor that outputs a decoded sentence block based on a (Z+1)-th bit string;

wherein the j-th function calculator includes:

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding process, and

a mask process using the j-th second mask;

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;

a mask process using the j-th first mask,

a non-linear conversion predetermined for performing an encoding process, and

a mask process using the j-th second mask;

a mask process using an inverted j-th first mask,

the non-linear conversion, and

the mask process using the j-th second mask;