Title of Invention: RANDOM NUMBER EXPANDING DEVICE, RANDOM NUMBER EXPANDING METHOD, AND RANDOM NUMBER EXPANDING PROGRAM Technical Field
[0001] The present invention relates to a random number expanding device, a random number expanding method and a random number expanding program that expand an M bits random number to an N bits random number, where N is larger than M. Background Art
[0002] As a basis for information security, cryptography technologies are widely used. In order to use cryptography in safety, information called secret key needs to be kept in secret except for the user. As a measure to store a secret key in safety, a method of using a computer chip is common. The secret key is written in a non-volatile memory in the chip, to which access is restricted from outside the chip. By access restriction, it is possible not to make the secret key read from outside the chip.
[0003] There has been considerable researches on attacks to retrieve a key from a computer chip. A fault attack is one of the classifications of attacks. By applying a physical stimulus to a computer, the computer may make a calculation error. There are cases when a secret key can be extracted by inducing a calculation error in a computer chip that processes encryption, and observing how a calculation error occurs in the result. Such an attack is referred to as a fault attack.
[0004] One of methods well-known as physical stimulus that provokes calculation errors is laser irradiation onto a computer chip. Non-patent literature 1 describes that by irradiating an appropriate part with a laser, it is possible to set a certain bit in a memory or a resister that stores data inside a computer chip to a logical value 0 or 1.

Such an error is referred to as a bit-set/rcset fault.
[0005] An attacker who can induce a bit-set/reset fault can retrieve secret data by
observing if a key is overwritten before and after laser irradiation.
[0006] As described in Non-patent literature 2, there are many existing
countermeasures against fault attacks. However, many of such countermeasures are
ineffective.
[0007] One of effective count ermeasures against fault attacks is a method to detect that
laser irradiation is performed by a sensor, as disclosed in Patent literature 1. However,
there are such problems that (1) a local irradiation may be overlooked, (2) the
manufacturing cost is increased by using a specific circuit, etc.
[0008] Further, another effective countermeasure against fault attacks is a method to
use random number masking. Random number masking is a technique as follows.
Let an N bits secret key k(N> exists. Here, k(N) = ki, k2, ... kjM. In random number
masking, an N bits random number r(N) is prepared. Here, r^) = rj, o, ... rN. By
taking the exclusive OR of the secret key k^) and the random number r(N), masked data
is obtained. After that, the random number r(N) and the masked data are stored in a
resister. When the secret key k V > M.
(3) r(M} represents an M bits random number, TM represents the M-th bit of r(M)-Random numbers are distinguished by <1> and <2> as with r, (M) 2nd r<2>, (uy In r, (M) and r<2>, and r<2>. The same things apply to the random number s.
(4) An exclusive OR operation is described as < +> for descriptive purposes. r](M) < + > r<2>,(M) represents an exclusive OR between the bits ofr,,{M).
[0018] *** Description of the structure ***
With reference to Fig. 1 through Fig. 16, the first embodiment will be described.
Fig. 1 is a block diagram of a basic structure of the random number expanding device 100.
The random number expanding device 100 is provided with a receiving unit 110, an expanding unit 120 and an outputting unit 130.
The receiving unit 110 receives the M bits random number i'(M)-

[0019] The expanding unit 120 expands the random number r(M) to an N bits random number S(N) by using a logical operation obtained by multiplication of one matrix of a check matrix with a size ofM^N and a generator matrix with a size of M * N, which are determined from a linear code for error correction, by a vector in a case wherein the random number r(M) is the vector with M components, in which multiplication addition is made into an exclusive OR.
That is, the expanding unit 120 expands the random number r as a random number. The outputting unit 130
5 outputs s(N) when r(M) is expanded to S(N) by the expanding unit 120. Otherwise, in a case of a truncating process as described below, the outputting unit 130 outputs a V bit random number S(V) in which at least 1 bit is removed from s(N). Here, the magnitude of each integer number is N > V > M. As will be discussed for Fig. 14, the expanding unit 120 generates the V bits random number S(y) represented by the integer number V
.0 smaller than the integer number N and larger than the integer number M, by removing at least 1 bit from the expanded random number S(N). The outputting unit 130 outputs the random number S(v>
[0022] Additionally, as will be discussed for re-masking below, the receiving unit 110 receives the third random number r<3>,(M) as the random number r,(M) and the second M bits random number r<2>, (M)- The expanding unit 120 expands the third random number r<3>, ) ^ corresponding to a random number whereto the first random number r,(M) is expanded, and an N bits random number s<2>, (N) corresponding to a
0 random number whereto the second random number r<2>, (M> is expanded. A storing unit 150 stores data masked with the random number s<)>, (N). A masking unit 140 below performs an operation of X <+> s, (N) as the data masked with the random number S,(N), and s,(N) <+> s<2>, (N) as the XOR random number expanded by the expanding unit 120. By this operation, the masking unit 140 performs re-masking to
5 convert the data masked with the random number st (NJ to data masked with the

random number s<2>, (N).
[0023] Fig. 2 is a block diagram in a case wherein the random number expanding
device 100 is further provided with the masking unit 140 and the storing unit 150.
The masking unit 140 masks data with a random number output by the outputting unit 130. The storing unit 150 stores the data masked by the masking unit 140. [0024] *** Explanation of operations ***
Fig. 3 outlines operations in the expanding unit 120 and the masking unit 140.
Fig. 4 is a flowchart of operations in the random number expanding device 100.
The operations in the random number expanding device 100 are described with reference to Fig. 2 through Fig. 4. Let the secret key k(N) be N bits, from k, to kN.
(1) The receiving unit 110 executes a step SI 1. In the step SI 1, the receiving unit 110 receives the M bits random number r(M).
(2) The expanding unit 120 executes a step S12. In the step S12, the expanding unit 120 expands the random number r(M) to the N bits random number S(N) using the logical operation obtained by multiplication of one matrix of the check matrix with the size of M x N and the generator matrix with the size of M x N, which are determined from the (N, N-M, D) linear code for error correction, by the vector in the case wherein the random number r(M) is the vector with M components. In this way, the expanding unit 120 converts the random number r(M} to the random number S(N) using an expanding function 1201. The expanding function 1201 will be discussed below,
(3) The outputting unit 130 executes a step S13. In the step S13, the outputting unit 130 outputs bit values, the number of which is not smaller than M + 1, which is larger than M bits, out of N bits of the random number S(N), as a random number.
(4) When the outputting unit 130 outputs the random number S(N> as a random number,

the masking unit 140 generates data 604 as masked secret key k{N> by taking the exclusive OR of the secret key k(N) and the random number S(N). The random number r{Mj and the data 604 are stored in a memory or a resister as the storing unit 150. According to the above operations, data masking can be performed by using a random
5 number of a desired bit number.
[0025] One of the characteristics of the random number expanding device 100 is to use a linear code technique for expanding random numbers.
Fig. 5 is a diagram illustrating operations in the expanding unit 120 that expands a random number by using the linear code technique.
.0 The expanding unit 120 expands the random number Y(M) to the random number
S(N) using the expanding function 1201. The expanding unit 120 uses the (N, N-M, D) linear code for expanding random numbers. N is a code length, N-M is an information bit length, and D is a minimum distance representing a minimum value of a hamming distance between different code words. The expanding function 1201 is defined by
5 multiplication by the check matrix 1202. The check matrix 1202 is a matrix with a size of M x N determined from the (N, N-M, D) linear code. Since the check matrix 1202 is also a generator matrix, the check matrix 1202 can be also read as the generator matrix. The check matrix 1202, or the generator matrix, has dimensions of M x N. Having the dimensions of M x N means having M rows and N columns, or may having
0 N rows and M columns. Since the check matrix 1202 is also the generator matrix, let a matrix to be used for defining the expanding function 1201 be the check matrix 1202 below. Since the check matrix 1202 has the dimensions of M * N, r(M) as input data of M bits can be output as output data S(NJ of N bits. One of the characteristics of the expanding unit 120 is to use an error correction code not for detecting a bit error, but for
5 expanding the random number r(M) as input data to the random number s^y

[0026] As an effect of expanding a random number using the check matrix 1202 of the (N, N-M, D) linear code, it is possible to improve the security against laser irradiation up to (D-l) beams. This is due to the next reason. The check matrix 1202 has N columns. When the check matrix 1202 has N rows and M columns, it suffices to transpose the check matrix 1202. By the property of the (N, N-M, D) linear code, any column of (D-l) number in the check matrix 1202 is linearly independent. Corresponding to the linear independence, any (D-l) bits, being extracted out of the random number s^) as N bits data that has been expanded by the check matrix 1202, are linearly independent. If linearly dependent A of columns exist, this means lack of random numbers. Thus, an attack is made possible by performing irradiation with A of laser beams. When the (N, N-M, D) linear code is used, since any (D-l) is linearly independent, the mentioned attack can be prevented against laser irradiation up to (D-l) beams.
[0027] Fig. 6 is a table illustrating an example that an irradiation attack with a laser toward two and more parts at the same time succeeds. By use of Fig. 6, an example will be discussed wherein an irradiation attack with a laser toward two and more parts at the same time succeeds in a case not according to the present embodiment.
Let a 2 bits secret key desired to be protected be k(2). Let each bit of the secret key k(2) be ko and kj. Let a 1 bit random number be r. An attacker knows that bits of the secret key k(2) after laser irradiation become (0, 0). A column 501 is for cases when the secret key k(2) is ko = ki; and when ko =£ ki. A column 502 is for specific bits in the cases when ko = k], and when k0 =^= kj. A column 503 indicates values of the random numbers r. A column 504 indicates masked secret keys k(2). A column 505 indicates values after laser irradiation. A column 506 indicates whether an error exists or not. A column 507 indicates error probabilities. The aim of the attacker is

to judge whether ko = ki or not. Judging whether ko - ki or not has the same effect as obtaining one bit of a key. The secret key kp) is masked using 1 bit random numbers r. Tlie masked values are in the column 504. The attacker irradiates two parts of a resister that keeps the masked values with a laser. As indicated in the column 506,
5 when k0 = ki, an error may not occur. Meanwhile, when ko =£ kj, an error inevitably occurs. Therefore, by testing if an error may occur or not, the attacker can judge whether ko = ki or not. That means success in attack. By applying the method of the present embodiment to the attack as illustrated in Fig. 6, it is possible to counter laser irradiation up to (D-l) beams.
.0 [0028] Fig. 7 illustrates an example in which the expanding unit 120 expands a random number r(§j to a random number S(i5) using the check matrix 1202.
Fig. 7 is an example when the (15, 7, 5) linear code disclosed in "Hideki Imai, 'Coding Theory,' IEICE, 1990." is used, wherein N = 15 and M = 8. Therefore, the size of the check matrix 1202 is 8 x 15. A matrix 1202-1 is a transposed matrix of the
.5 check matrix 1202. A matrix 1202-1 is a size of 15 rows and 8 columns. By multiplying the matrix 1202-1 by the random number r(g), the random number r(g) can be expanded to the 15 bits random number S(i5). The multiplication of the check matrix 1202 by a vector in a case when the random number r(S) is the vector with eight components is exclusive-OR multiplication. By masking the secret key k(is> in a
0 resister with the random number s(i5) generated by using the matrix 1202-1, it is possible to maintain the security against laser irradiation up to four beams at a time. Each component as each bit of a value 802 being a result of the exclusive-OR multiplication is exclusive OR of each bit (rj, ..., rg) of the original random number r$y That is, each bit of the random number S(i5), such as ss and so on is exclusive OR of n
5 and so on. As illustrated in Fig. 7, the expanding unit 120 generates N components

obtained by the exclusive-OR multiplication of the matrix 1202-1 with the size of M x N, by the random number r(M), as the random number s(N).
[0029] Here, the transposed matrix 1202-1 is used in Fig. 7; however, it is only for convenience. It suffices to perform a calculation so as to obtain the random number S(is) by the exclusive-OR multiplication of the check matrix 1202 with the size of 15 x 8 determined from the (15, 7, 5) linear code, by the random number r(zy That is, it suffices to obtain the random number S(NJ by multiplying the check matrix 1202 with the size of M x N determined from the (N, N-M, D) linear code, by the random number r have 1 row and M columns; otherwise, it suffices to calculate Hf x T(M} by letting the random number r(M) have M rows and 1 column.
[0030] The structures illustrated in Fig. 1 and Fig. 2, etc. may be composed of hardware, software, or may be composed of a combination of hardware and software.
Fig. 8 illustrates a case in which hardware implements the multiplication of the check matrix 1202 illustrated in Fig. 7. The expanding unit 120 is equipped with a logical operation circuit 121 that executes logical operations.
In Fig. 8, the receiving unit 110 is input terminals 111 of each XOR logical gate in an input stage, and the outputting unit 130 is output terminals 131 of each XOR logical gate in an output stage. The logical operation circuit 121 is equipped with a plurality of XOR circuits 121-1. The uppermost circuit 121a in Fig. 8 is a circuit that

calculates si bit of the random number s(i5). The second circuit 121b from above is a circuit that calculates S2 bit of the random number S(is). The undermost circuit 12 Id in Fig. 8 is a circuit that calculates S15 bit of the random number s is indicated as r.
The random number expanding device 100 in Fig. 10 is equipped with a
.5 resister 1000 that stores the random number r(M), the expanding unit 120 as a circuit to expand the random number r(M), an XOR logical gate 1003 as the masking unit 140, an XOR logical gate 1004 as the decrypting unit 160 to unmask and a resister 1005 as the storing unit 150 to store masked data. The check matrix 1202 is used for the expanding function 1201. The specific structure of the expanding unit 120 in Fig. 10
;0 is a network of XOR logical gates as illustrated in Fig. 8 in the present embodiment; however, it may be composed of a program as discussed above. Masking of N bits secret information x is performed as follows, f indicates the expanding function 1201. First, the random number r(M) stored in the resister 1000 is converted to an N bits random number f(r) by the expanding unit 120. Here, f(r) = s(N). By taking exclusive
5 OR of f(r) = S(N) and the N bits secret information x, a masked value x <-)-> f(r) is

obtained. The masked value x <+> f(rj is stored in the rcsister 1005. The output of the resister 1005 is connected to the XOR logical gate 1004. By the XOR logical gate 1004, x <+> f(r) <+> f(r) = x is established, and the secret information X before masking is decrypted. [0032] With reference to Fig. 11 and Fig. 12, re-masking will be discussed.
In a random number masking, there is a case in which change of a masking value is desired. By changing the masking value, the security may be improved. Changing of the masking value is called rc-masking. By the random number expanding device 100, re-masking can be performed effectively.
Fig. 11 illustrates operations in the expanding unit 120 and the masking unit 140 at the time of re-masking. Re-masking will be explained by the use of Fig. 11.
Let M bits random numbers be the first random number r and the second random number r<2>. Let the N bits random numbers which are expanded from r and r<2> be s and s<2>. Now, it is desired to re-mask the value x <+> f(r) that has been masked with f(r) to another masked value x <+> f(r<2>). The random number s = f(r) and the random number s<2> = f(r<2>). Further, x is secret information, r is a random number for old masking, and r<2> is a random number for new masking. First, the XOR logical gate 1100 generates r <+> r<2>.
[0033] Next, the receiving unit 110 receives r<]> <+> r<2> as the third random number r<3>,(M). The expanding unit 120 expands r<]> <+> r<2> to a random number f{r <+> r<2>). The outputting unit 130 outputs the random number f(r <+> r<2>). Since the expanding function f defined by multiplication with the check matrix 1202 is linear, f(r <+> r<2>) = f(r) <+> f(r<2>) = s <+> s<2> is established. The masking unit 140 takes the exclusive OR of the masked value x <+> f(r<(>) and the expanded random number f(r) <+> f(r<2>). In this way, the masking unit 140 obtains x <+> f(r<]>) <+>

f(r) <+> f(r<2>) = x <+> f(r<2>). Thus, the new value x <+> f(r<2>) is a result of
re-masking.
[0034] The re-masking method using the expanding function f as above has two
important advantages. First, only one expanding function f is necessary to be prepared.
Secondly, re-masking is executed without returning to the original value x not being
masked, which may improve the security.
[0035] Fig. 12 illustrates a circuit structure of the random number expanding device
100 in a case of performing re-masking, which corresponds to the block diagram of Fig.
9. Fig. 12 extends the circuit structure illustrated in Fig. 9, to which a re-masking
function is added.
In Fig. 12, a resister 1010 for a new random number r<2>, an XOR logical gate 1020 that adds the random numbers r and r<2> and a selector 1030 are added, which are new relative to Fig. 9. The XOR logical gate 1004 includes the function of the masking unit 140 as well in addition to the function of the decrypting unit 160 in Fig. 10. Byusing the circuit of Fig. 10, re-masking can be realized.
[0036] Fig. 13 is a flowchart illustrating operations in the random number expanding device 100 hi Fig. 12.
With reference to Fig. 13, the operations will be discussed.
In S21, only the random number r is sent to the XOR logical gate 1020. The output of the XOR logical gate 1020 is the random number r.
In S22, the expanding unit 120 generates s = f(r<)>), and f(r) is output from the outputting unit 130.
In S23, the XOR logical gate 1003 takes the exclusive OR of the secret information x and the f(r).
In S24, x <+> f(r) is output from the selector 1030.

In S25, x <+> f(r) is stored in the resister 1005. [0037] Next, in S31, the random number r and the random number r<2> are sent to the XOR logical gate 1020. The output of the XOR logical gate 1020 is r <+> r<2>.
In S32, the expanding unit 120 expands r <+> r<2> to f(r <+> r<2>) = f(r) i <+> f(r<2>)by the expanding function f, and the outputting unit 130 outputs f(r) <+> f(r<2>).
In S33, by the XOR logical gate 1004, f(r) <+> f(r<2>) output from the outputting unit 130 is exclusive-ORed with x <+> f(r) output from the resister 1005. Thus, from the XOR logical gate 1004, x <+> f(r) <+> f(r) <+> f(r<2>) = x <+> i ffr<2>) is output.
In S34, x <+> f(r<2>) is output from the selector 1030, and x <+> f(r<2>) is stored in the resister 1005. In this way, re-masking is completed. In order to decrypt re-masked x <+> f(r<2>), it suffices to send only the random number r<2> to the XOR logical gate 1020, expand the random number r<2> to f(r<2>) by the expanding unit 120, and XOR f(r<2>) and x <+-> f(r<2>) stored in the resister 1005 by the XOR logical gate 1004.
[0038] Fig. 14 is a diagram that describes a truncating process performed by the expanding unit 120.
With reference to Fig. 14, the truncating process will be discussed.
In what follows, N, V and M are positive integer numbers, where N > V > M. It is not always true that a (V, V-M, D) linear code exists when expansion of the random number r(M) to the random number s(v) is desired. In such a case, truncation can be performed. The truncating process will be discussed with the use of Fig. 14. It is assumed that a convenient (V, V-M, D) linear code cannot be made when expansion of the M bits random number r(M) to the V bits random number s(V) is desired. However,

it is assumed that N can be selected, where N > V, and the (N, N-M, D) linear code can be made. In this case, the check matrix 1202 of the (N, N-M, D) linear code can be used for the expanding function 1201. The output of the expanding function 1201 is N bits. That is, after expanding the random number r
[Claim 4] The random number expanding device as defined in any one of claim 1 through claim 3, wherein the expanding unit includes a logical operation circuit that

executes the logical operation.
[Claim 5] The random number expanding device as defined in claim 4, wherein the logical operation circuit includes a plurality of exclusive or circuits.
[Claim 6] The random number expanding device as defined in any one of claim 1 through claim 5, the random number expanding device further comprising:
a masking unit that masks data with a random number that is output by the outputting unit; and
a storing unit that stores the data masked by the masking unit.
[Claim 7] The random number expanding device as defined in claim 6,
wherein the receiving unit receives as the random number r(M) a third random number r<3>, (M), which is obtained by calculating an exclusive or of a first random number r,(M) of M bits and a second random number r<2>,(M) of M bits,
wherein the expanding unit expands the third random number r<3>, (M) to an XOR random number that is obtained as an exclusive or of a random number s,{N) of N bits corresponding to a random number whereto the first random number r,(M) is expanded, and a random number s<2>, (N) of N bits corresponding to a random number whereto the second random number r<2>, , (N), and
wherein the masking unit performs re-masking that converts the data masked with the random number s,(N) into data masked with the random number s<2>, (N), by an operation between the data masked with the random number s,(N) and the XOR

random number expanded by the expanding unit.
[Claim 8] The random number expanding device as defined in any one of claim 1 through claim 7, the random number expanding device farther comprising an error 5 detecting unit that detects an error included in a bit sequence, wherein the expanding unit uses at least a part of the error detecting unit when the random number r(M) is expanded to the random number S(N).
[Claim 9] A random number expanding method comprising:
) receiving a random number r(M) of M bits;
expanding the random number r{M) to a random number S(N) of N bits by a logical operation circuit using a logical operation that is obtained by a multiplication of one matrix of a check matrix with a size of M x N and a generator matrix with a size of M x N which are determined from a linear code for error correction by a vector in a
i case in which the random number r(M) is the vector having M components, the multiplication being performed through addition based on an exclusive OR; and
outputting a bit value whose number is larger than M bits out of N bits of the random number S(NJ-
I [Claim 10] A random number expanding program that makes a computer to execute:
a receiving process of a random number r(M) of M bits;
an expanding process of the random number r(M) to a random number S(N) of N bits using a logical operation that is obtained by a multiplication of one matrix of a check matrix with a size of M x N and a generator matrix with a size 6fM>^N which are determined from a linear code for error correction by a vector in a case in which the

random number r(M) is the vector having M components, the multiplication being performed through addition based on an exclusive OR; and
an outputting process of a bit value whose number is larger than M bits out of N bits of the random number S(K).

ABSTRACT
A random number expanding device (100) includes an expanding unit (120) that expands a random number r(M) to an N bits random number S(N) using a logical operation that is obtained by multiplication of one matrix of a check matrix with a size of M x N and a generator matrix with a size of M x N which are determined from an (N, N-M, D) linear code for error correction by a vector in a case in which the random number r(M) is the vector with M components, the multiplication being performed through addition based on an exclusive OR. Since the random number expanding device (100) includes the expanding unit (120), it is possible to reduce the bit numbers of random numbers to be used, and counter an irradiation attack with multiple laser beams.