JP2008224830A - Tamper resistant power calculation method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a tamper-proof exponentiation operation method wherein an exponentiation operation method of Brickell etc. is provided with resistance to side channel analysis. <P>SOLUTION: An exponentiation operation method having resistance to side channel analysis is provided. The exponentiation operation often used in encryption algorithm frequently becomes a target of side channel analysis, and is required to have resistance to it. In this method, the exponent parts are rearranged prior to the operation so that the operation columns become constant when exponentiation operation is performed. Thus, the exponents as secret information can be prevented from being estimated from power consumption waveforms or processing time. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

The present invention relates to a tamper-resistant power calculation method having resistance to analysis of secret information inside a cryptographic processor by side channel analysis.

With the development of computer networks in recent years, services involving money transfer, such as online shopping, have been expanded. On the other hand, an increase in so-called network crimes due to eavesdropping and falsification of computerized information and information leakage have become major social problems.

Cryptographic technology plays a major role in solving these problems. Examples include information encryption and an authentication system using digital signature technology, which have been introduced in various situations. In this way, encryption technology has become indispensable for today's network society.

However, attack (decryption) techniques for cryptographic techniques are also becoming more sophisticated. Among them, there is a side channel analysis that measures the processing time and power consumption of a processor that executes cryptographic processing (hereinafter also referred to as “cryptographic processor”), and analyzes the secret information inside the cryptographic processor from these characteristics. It has become a real threat. As typical side channel analysis, timing analysis and power analysis are known.

Here is an example of side channel analysis for the RSA method. The RSA method is the most widely used public key encryption method. In RSA encryption and digital signature verification processing, the power-residue calculation M ^E mod N (the remainder of M divided by E) is calculated. Here, M is the target message, and E and N are public keys. In addition, in the RSA system decryption and digital signature generation processing, the power-residue calculation C ^D mod N is also calculated. Here, C is the target message, N is the public key, and D is the secret key.

When implementing power-residue calculation using the binary method, the operation sequence of the power-residue as a whole differs depending on whether each bit value is 0 or 1 when the secret key D is expressed in binary. There is. Non-Patent Document 1 introduces a technique for determining such a difference in the operation sequence from the processing time of the power-residue calculation.

  On the other hand, Non-Patent Document 2 introduces a method for determining from power consumption. If the difference between the operation sequences can be discriminated, it can be discriminated whether each bit of D is 0 or 1, and therefore all the bits of the secret key D can be determined.

An example is given for side channel analysis of the ECDSA method, which is a kind of elliptic curve cryptosystem. The ECDSA method is composed of a point calculation on an elliptic curve and an integer calculation. ECDSA digital signature processing
Find the remainder r obtained by dividing the x coordinate of kP by z,
s = k ^-1 (M + xr) mod z
To create a signature (r, s). Where P is a point on the elliptic curve, z is the order of the point on the elliptic curve, k is a random number selected from integers less than z, M is the message of interest, and x is the signer's private key. Since the attacker knows information other than x and k, if k is known, the secret key x can be obtained from the expression s.

The operation kP for adding the point P k times is a power operation and is usually called scalar multiplication. When scalar multiplication is implemented by the binary method, the value of k can be estimated in the same way as the power-residue calculation in the RSA method.

Various techniques for preventing these attacks have been devised. The underlying idea is roughly divided into two types: making the processing sequence constant regardless of secret information, and randomizing the input data to randomize the data being processed by the cryptographic processor. it can.

According to the former, for example, as described in the attack technique for the RSA method, the value of D cannot be discriminated because the same operation sequence is obtained even if the value of each bit of the secret key D is 0 or 1. Such a method is introduced in Non-Patent Document 3.

  The latter is a technique for preventing side channel analysis by making the processing time and power consumption characteristics of the cryptographic processor irrelevant to the secret information inside the cryptographic processor. Non-Patent Document 4 is known as an efficient power calculation method. This technique is as follows.

Consider a scalar multiplication kP of a point P on an elliptic curve. Here, k is 160 bits, and 40 blocks divided by 4 bits are k ₃₉ , k ₃₈ ,..., K ₁ , k _{0 in} order from the MSB side. Assume that a 40-point pre-calculation table for calculating TBL [i] = 2 ^{16 × i} P for i = 0, 1, 2,.
JF Dhem et al., A Practical Implementation of the Timing Attack (Proceedings of CARDIS '98, Lecture Notes in Computer Science 1820, pp.167-182, Springer-Verlag, 1998) TS Messerges et al., Investigation of Power Analysis Attacks on Smartcards (Proceedings of USENIX Workshop on Smartcard Technology '99) JS Coron, Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems (Proceedings of Cryptographic Hardware and Embedded Systems '99, Lecture Notes in Computer Science 1717, pp.292-302, Springer-Verlat, 1999) EF Brickell et al., Fast Exponentiation with Precomputation (Proceedings of EUROCRYPT '92, Lecture Notes in Computer Science 658, pp.200-207, Springer-Verlag, 1993)

Such defensive techniques based on ideas have been proposed for various algorithms for power operations. However, the current situation is that it is not possible to avoid an increase in processing time and an increase in necessary memory by applying a defense technique. This is a problem of the overall defense method against side channel analysis.

Therefore, if a defensive technique for side-channel analysis is devised for the power calculation method that is as efficient as possible, it is expected that it can be processed within the allowable time set for using the cryptographic processor even if the processing time increases. The

The scalar multiplication method of Brickell et al. Shown in Non-Patent Document 4 is shown as a flowchart in FIG. First, in steps 901 and 902, areas A and B for storing intermediate results are initialized as virtual points O called infinity points on the elliptic curve, respectively. Steps 903 to 909 are a loop process in which d is decreased by 1 from 15 to 1. Steps 904 to 907 are a loop process in which i is decreased by 1 from 39 to 0. In step 905, it is checked whether k _i = d. If it is established, B and TBL [i] are added and a point on the elliptic curve stored in B is added (step 906). If it is not established, nothing is done, that is, step 906 is not performed and the routine proceeds to step 907. When the i loop is completed in step 907, the process proceeds to step 908. In step 908, A and B are added and stored in A. When step 909 is finished, A = kP and scalar multiplication is calculated. In this calculation, scalar multiplication can be executed by adding up to 55 points on the elliptic curve.

However, this method has a problem that it is vulnerable to side channel analysis. This is because the number of loops for checking whether k _i = d before the operation B ← B + TBL [i] is determined depending on k, which causes a difference in the processing sequence of the cryptographic processor. Therefore, if the number of loops can be determined by side channel analysis, the value of each k _i can be determined, and thus the value of k is exposed.

It is an object of the present invention to provide a tamper-resistant power calculation method in which the power calculation method of Brickell et al. Has resistance to side channel analysis.

An invention corresponding to claim 1 is a method of calculating a power-residue c = m ^k mod N that appears during cryptographic processing using an information processing device, wherein the n-bit integer data k is converted to LSB ( Least Significant Bit (Least Significant Bit) is divided into s blocks (s is the smallest integer greater than or equal to n / w) in order from w bits, and the MSB (Most Significant Bit, most significant bit) of the data k When the block to be included is less than w bits, the MSB side is padded with 0 to make the block w bits, and the data k divided into the blocks is expressed as k _s−1 , k _s−2 ,. ₁ , k ₀ , when each block is viewed as a w-bit integer and rearranged in descending order, means for storing the corresponding subscripts in that order, and when storing the subscripts, the k To the subscript corresponding to the place where the size changes when the are sorted in descending order in w-bit blocks And means for adding, i = 1, 2, ... , means for holding the pre-calculated table TBL consisting s pieces of data ^{TBL [i] = m wi mod} N to s, 2 two intermediate variables A, B Means for initializing to 1, means for initializing the loop counter d to s-1, and referring to the stored subscripts in order, and if the subscript is not marked, B × TBL [d] mod N Calculating and storing in B, and when there is a mark on the subscript, means for calculating B × A mod N and storing in A and subtracting 1 from d. It is.

The invention corresponding to claim 2 is characterized in that the two intermediate variables A and B are TBL [s], TBL [s + 1] or TBL [s + 1], TBL [s], respectively. Item 2. The tamper-resistant power calculation method according to Item 1.

The invention corresponding to claim 3 is a method of calculating scalar multiplication Q = kP of a point on an elliptic curve appearing during encryption processing using an information processing device, wherein the n-bit integer data k is A means for dividing the LSB (Least Significant Bit, least significant bit) sequentially into s blocks of w bits (where s is the smallest integer greater than or equal to n / w), and the MSB (Most Significant Bit, most significant bit) of the data k ) Includes a means for padding 0 to the MSB side to make the block w bits when the block including w is less than w bits, and the data k divided into the blocks is k _s-1 , k _s-2 ,. , k ₁ , k ₀ , when each block is viewed as a w-bit integer and rearranged in descending order, means for storing the corresponding subscripts in that order, and when storing the subscripts, Corresponds to the place where the size changes when k is rearranged in the order of w bits. A means for adding a mark to a subscript, means for holding a precalculation table TBL consisting of s pieces of data TBL [i] = w ⁱ P for i = 1, 2, ..., s, and two intermediate variables A means for initializing A and B to 1, a means for initializing the loop counter d to s-1, and referring to the stored subscripts in order, and if the subscript is not marked, B × TBL [ d] means to calculate mod N and store it in B, and if there is a mark on the subscript, B × A mod N is calculated and stored in A and subtracts 1 from d. This is a tamper-power calculation method.

The invention corresponding to claim 4 is characterized in that the two intermediate variables A and B are TBL [s], TBL [s + 1] or TBL [s + 1], TBL [s], respectively. Item 4. The tamper-resistant power calculation method according to Item 3.

(Function)
In the invention corresponding to claim 1, by taking the above-described means, when performing the power-residue calculation by the method of Brickell et al. An operation sequence for performing multiplication can be made constant. Therefore, the analysis of k can be made difficult from the power consumption waveform of the calculation or the processing time.

In the invention corresponding to claim 2, in the invention corresponding to claim 1, B ← B + TBL [i] and A ← A by making the storage position of the intermediate variables A and B the same position as the pre-calculation table Since the calculation of + B can be TBL for both input and output, analysis of k can be made more difficult from the power consumption waveform or processing time.

 In the invention corresponding to claim 3, by performing the above-described means, when performing the scalar multiplication of the points on the elliptic curve by the method of Brickell et al., The values of k blocks are aligned first. This makes it possible to make the calculation sequence for adding points on the elliptic curve constant. Therefore, the analysis of k can be made difficult from the power consumption waveform of the calculation or the processing time.

The invention corresponding to claim 4 is the invention corresponding to claim 3, wherein B ← B + TBL [i] and A ← A by making the storage positions of the intermediate variables A and B the same as the pre-calculation table Since the calculation of + B can be TBL for both input and output, analysis of k can be made more difficult from the power consumption waveform or processing time.

As described above, according to the present invention, it is possible to provide a tamper resistant power calculation method that makes the power index difficult from the analysis by the power analysis or the timing analysis when the power calculation is performed by the method of Brickell et al.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.

(First embodiment)
FIG. 1 is a schematic diagram showing the configuration of an apparatus that implements a tamper-resistant modular multiplication method according to the first embodiment of the present invention. This tamper-proof modular exponentiation apparatus 101 is configured as a power modular multiplication operation unit of a computer such as an IC card, and performs power modular multiplication using hardware or software. Specifically, it comprises a control unit 102, a ROM (read only memory) 103, a RAM (random access memory) 104, a pre-calculation table 105, and a remainder multiplication unit 106.

The ROM 103 stores parameters necessary for performing the power-residue calculation. For example, when m and N are fixed values, they are m and N. When implemented in software, it may also store programs that perform power-residue calculations using the method of Brickell et al. The RAM 104 stores temporary data such as intermediate results of power-residue calculations. The pre-calculation table 105 stores TBL [] consisting of TBL [i] = m ^wi mod N. The pre-calculation table 105 may be included in the ROM 102. The modular multiplication unit 106 receives the input values x and y from the ROM 103 or RAM 104 or the pre-calculation table 105 under the control of the control unit 102, performs modular multiplication z = a × b mod N, and returns the result z to the RAM 104. .

FIG. 2 and FIG. 3 are flowcharts for realizing the tamper-resistant modular multiplication method according to the first embodiment of the present invention. Although this flowchart will be described here as being executed by the tamper-resistant modular exponentiation apparatus shown in FIG. 1, it is not limited thereto.

In Fig. 2 and Fig. 3, since 1024 bits are generally used in today's power-modulo method, n is 1024 bits, w is 8 bits, s is s = n / w = Although the case of 128 is shown, it is of course easy to generalize.

The first embodiment of the present invention will be described with reference to FIGS.

First, k is assumed to be divided into 128 blocks of 8 bits each, and these are k ₁₂₇ , k ₁₂₆ ,..., K ₁ , k ₀ from the MSB side. Although not shown in FIG. 2, this is a step performed before or at step 201. Since n is 1024 bits, there is no need to pad the block containing the MSB with 0. However, if necessary, 0 is padded to the MSB side of the k to make the block w bits. .

In step 201, k ₁₂₇ ,..., K ₀ are rearranged in descending order, and the subscripts corresponding thereto are stored in area F. FIG. 3 is a flowchart describing step 201 in detail. Here, FIG. 3 corresponding to step 201 will be described.

In step 301, an area F for storing subscripts is initialized to zero. Steps 302 to 309 are loop processes in which d is decreased by 1 from 255 (= 2 ^w −1) to d = 0. Steps 303 to 306 are loop processes in which i is decreased by 1 from 127 (= s−1) to i = 0. Here, i may be increased by 1 from 0 to 127. In step 304, it is checked whether k _i = d. When it is established, i is concatenated as 1-byte data to the area F in which the subscript is stored (step 305). If it does not hold, do nothing, that is, skip step 305 and proceed to step 306. After the i loop of step 306 is completed, the process proceeds to step 307 and checks whether i> 0. When established, the area F is marked to change the value of d. Here, one byte of 0x80 (128 in decimal) is used as the mark (step 308). If it does not hold, do nothing, that is, skip step 308 and go to step 309. When the d loop of step 309 is finished, this flowchart is finished.

Therefore, the flowchart returns to FIG. In steps 202 and 203, the intermediate results A and B are set to 1. Steps 204 to 208 are loop processes in which i is increased by 1 from 0 to 382 (= (2 ^w -1) + s-1). In step 205, it is checked whether the i-th element F [i] of F is 0x80. If true, B × A mod N is executed and stored in A (step 206), and the process proceeds to step 208. If not, B × TBL [F [i]] mod N is executed and stored in B (step 207). When finished in step 208, A stores m ^k mod N. This is because, in the present embodiment, in the method of Brickell et al., Only k _i = d is determined at the beginning of the process, and the execution order of the remainder multiplication is the same as the method of Brickell et al. Further, in the method of Brickell et al., The loop of d is not performed at d = 0, but in this embodiment (FIG. 3), the case of d = 0 is also performed. However, when i = 0 in step 307, 0x80 is not connected to F, and therefore the calculation in FIG. 2 corresponding to d = 0 is performed only in step 207 and not in step 206. Therefore, since the operation corresponding to d = 0 does not affect the final result A, the same final result as the method of Brickell et al. Can be obtained.

As described above, according to the present invention, only one modular multiplication is executed for each loop in the loop from step 204 to 208, so that the value of k can be estimated from the power consumption waveform and the processing time. Can be difficult.

Further, step 201 and step 202 need not be executed in succession, and after executing step 201 and storing F, it is also possible to execute step 202 and subsequent steps after performing another process. This makes it difficult to analyze the relationship between the process in step 201 (FIG. 3) and the process in step 202 and subsequent steps.

(Second embodiment)
The second embodiment makes analysis more difficult by storing A and B storing intermediate results in the same array as the pre-calculation table TBL in the first embodiment.

FIG. 4 is a flowchart for realizing the tamper-resistant modular multiplication method according to the second embodiment of the present invention. Although this flowchart is described here as being executed by the tamper-resistant modular exponentiation apparatus shown in FIG. 1, it is not limited thereto.

In the second embodiment, the precalculation table 105 needs to be writable. Therefore, it is assumed that the data is stored in the RAM 104 prior to the calculation.

In Fig. 4, 1024 bits are generally used in today's method of power-based cryptography, so n is 1024 bits, w is 8 bits, and s is s = n / w = 128 Although cases are shown, it is of course easy to generalize.

A second embodiment of the present invention will be described with reference to FIGS.

First, k is assumed to be divided into 128 blocks of 8 bits each, and these are k ₁₂₇ , k ₁₂₆ ,..., K ₁ , k ₀ from the MSB side. Although not shown in FIG. 4, this is a step performed before or at step 401. Also, since n is considered to be 1024 bits, there is no need to pad the block containing the MSB with 0. However, if necessary, 0 is padded to the MSB side of k to make the block w bits. .

In step 401, k ₁₂₇ ,..., K ₀ are rearranged in descending order, and the subscripts corresponding thereto are stored in area F. The flowchart describing the step 401 in detail is FIG. 3 as in the first embodiment, and the flow is as described in the first embodiment. In steps 402 and 403, TBL [128] and TBL [129] are selected from the pre-calculation table as areas for storing intermediate results, and each is set to 1. Steps 404 to 406 are loop processes in which i is increased by 1 from 0 to 382 (= (2 ^w -1) + s-1). In step 405, TBL [129- (F [i] >> 7)] <-TBL [129] × TBL [F [i]] mod N is executed. In this calculation, when F [i] = 0x80, TBL [128] ← TBL [129] x TBL [128] mod N, and A = TBL [128], B = TBL [129] This corresponds to step 206 in FIG. When F [i] is less than 0x80, TBL [129] ← TBL [129] × TBL [F [i]] mod N, corresponding to step 207 in FIG. 2 when B = TBL [129] . Therefore, the flowchart of FIG. 4 has the same calculation flow as that of FIG. 2, and when finished, m ^k mod N is stored in TBL [128].

As described above, according to the present invention, the power-residue calculation is calculated in a constant calculation sequence without branching in the loop from step 404 to step 406. Therefore, the value k is calculated from the power consumption waveform and the processing time. It can be difficult to guess.

Also, step 401 and step 402 do not need to be executed in succession. After step 401 is executed and F is stored, another process is performed and then step 402 and the subsequent steps are executed. Similar to the first embodiment, it is more difficult to analyze the relationship between the process 3) and the processes after step 402.

(Third embodiment)
FIG. 5 is a schematic diagram showing a configuration of an apparatus for carrying out a tamper-resistant modular multiplication method according to the third embodiment of the present invention. The tamper-resistant modular multiplication unit 501 is configured as a power modular calculation unit of a computer such as an IC card, and performs power modular multiplication using hardware or software. Specifically, it comprises a control unit 502, a ROM (read only memory) 503, a RAM (random access memory) 504, a pre-calculation table 505, and an addition unit 506 for points on an elliptic curve.

The ROM 503 stores parameters necessary for performing the power-residue calculation. For example, it is an elliptic curve parameter. When implemented in software, it may store programs that perform scalar multiplication of points on elliptic curves using the method of Brickell et al. The RAM 504 stores temporary data such as intermediate results of power-residue calculations. Pre-calculation table 505 stores the TBL [] consisting _{TBL [i] = w i P} . The pre-calculation table 505 may be included in the ROM 502. The point addition unit 506 on the elliptic curve receives the input values x and y from the ROM 503 or RAM 504 or the pre-calculation table 505 under the control of the control unit 502, and adds the points on the elliptic curve z = a + b And return the result z to the RAM 504.

FIG. 6 and FIG. 7 are flowcharts for realizing a tamper-resistant power calculation (scalar multiplication on an elliptic curve) method according to the third embodiment of the present invention. Although this flowchart is described here as being executed by the tamper-resistant modular exponentiation apparatus shown in FIG. 5, it is not limited thereto.

In Fig. 6 and Fig. 7, the key length of today's elliptic curve cryptosystem is generally 160 bits, so n is 160 bits, w is 4 bits, and s is s = n / w = 40 Of course, it is easy to generalize.

The first embodiment of the present invention will be described with reference to FIGS.

First, k is assumed to be divided into 40 blocks of 4 bits, and these are k ₃₉ , k ₃₈ ,..., K ₁ , k ₀ from the MSB side. Although not shown in FIG. 6, this is a step performed before or at step 601. In addition, since n is considered to be 160 bits, it is not necessary to pad the block including the MSB with 0, but if necessary, 0 is padded to the MSB side of k to make the block w bits. .

In step 601, k ₃₉ ,..., K ₀ are rearranged in descending order, and the subscripts corresponding thereto are stored in the region F. FIG. 7 is a flowchart describing step 601 in detail. Here, FIG. 7 corresponding to step 601 will be described.

In step 701, an area F for storing subscripts is initialized to zero. Steps 702 to 709 are a loop process in which d is reduced by 1 from 15 (= 2 ^w −1) to d = 0. Steps 703 to 706 are loop processing in which i is decreased by 1 from 39 (= s−1) to i = 0. Here, i may be increased by 1 from 0 to 39. In step 704, it is checked whether k _i = d. When it is established, i is concatenated as 1-byte data to the area F storing the subscript (step 705). If it does not hold, do nothing, that is, skip step 705 and proceed to step 706. After the i loop in step 706 is completed, the process proceeds to step 707, where it is checked whether i> 0. When established, the area F is marked to change the value of d. Here, one byte of 0x80 (128 in decimal) is used as the mark (step 708). If it does not hold, do nothing, that is, skip step 708 and go to step 709. When the d loop of step 709 is finished, this flowchart is finished.

Therefore, the flow returns to the flowchart of FIG. In steps 602 and 603, the intermediate results A and B are set as the infinity point O on the elliptic curve, respectively. Steps 604 to 608 are loop processes in which i is increased by 1 from 0 to 54 (= (2 ^w -1) + s-1). In step 605, it is checked whether the i-th element F [i] of F is 0x80. If true, B + A is executed and stored in A (step 606), and the process proceeds to step 608. If not, B + TBL [F [i]] is executed and stored in B (step 607). When finished in step 608, kP is stored in A. This is because, in the present embodiment, in the method of Brickell et al., Whether k _i = d is only determined at the beginning of the processing, and the execution order of the remainder multiplication is the same as the method of Brickell et al. Further, in the method of Brickell et al., The loop of d is not performed at d = 0, but in this embodiment (FIG. 7), the case of d = 0 is also performed. However, when i = 0 in step 707, 0x80 is not connected to F, and therefore the calculation in FIG. 6 corresponding to d = 0 is performed only in step 607 and not in step 606. Therefore, since the operation corresponding to d = 0 does not affect the final result A, the same final result as the method of Brickell et al. Can be obtained.

As described above, according to the present invention, only the addition of the points on the elliptic curve is executed once for each loop in the loop from step 604 to 608, so that the value of k is calculated from the power consumption waveform and the processing time. Can be difficult to guess.

Further, step 601 and step 602 do not need to be executed in succession. After executing step 601 and storing F, it is also possible to execute step 602 and subsequent steps after performing another process. This makes it difficult to analyze the relationship between the processing in step 601 (FIG. 7) and the processing in step 602 and subsequent steps.

(Fourth embodiment)
In the fourth embodiment, in the third embodiment, A and B storing intermediate results are stored in the same array as the pre-calculation table TBL, thereby making analysis more difficult.

FIG. 8 is a flowchart for realizing the tamper-resistant modular multiplication method according to the third embodiment of the present invention. Although this flowchart will be described here as being executed by the tamper-resistant modular exponentiation apparatus shown in FIG. 5, it is not limited thereto.

In the fourth embodiment, the precalculation table 505 needs to be writable. Therefore, it is assumed that the data is stored in the RAM 504 prior to calculation.

Figure 8 shows that the key length of today's elliptic curve cryptosystem is generally 160 bits, so n is 160 bits, w is 4 bits, and s is s = n / w = 40. Of course, it is easy to generalize.

A fourth embodiment of the present invention will be described with reference to FIGS.

First, k is assumed to be divided into 40 blocks of 4 bits, and these are k ₃₉ , k ₃₈ ,..., K ₁ , k ₀ from the MSB side. Although not shown in FIG. 8, this is a step performed before or at step 801. In addition, since n is considered to be 160 bits, it is not necessary to pad the block including the MSB with 0, but if necessary, 0 is padded to the MSB side of k to make the block w bits. .

In step 801, k ₃₉ ,..., K ₀ are rearranged in descending order, and the subscripts corresponding thereto are stored in area F. The flowchart describing the details of step 801 is FIG. 7 as in the third embodiment, and the flow is as described in the third embodiment. In steps 802 and 803, TBL [40] and TBL [41] are selected from the pre-calculation table as areas for storing intermediate results, and each is set as an infinite point O on the elliptic curve. Steps 804 to 806 are loop processes in which i is increased by 1 from 0 to 54 (= (2 ^w -1) + s-1). In step 805, TBL [41- (F [i] >> 7)] <-TBL [41] + TBL [F [i]] is executed. In this calculation, TBL [41] ← TBL [41] + TBL [40] when F [i] = 0x80, and in Fig. 6 when A = TBL [40] and B = TBL [41] Corresponds to step 606. When F [i] is less than 0x80, TBL [41] ← TBL [41] + TBL [F [i]], which corresponds to step 607 in FIG. 6 when B = TBL [41]. Therefore, the flowchart of FIG. 8 has the same calculation flow as that of FIG. 6, and kP is stored in TBL [40] when the calculation is completed.

As described above, according to the present invention, since the addition of points on the elliptic curve is calculated in a constant calculation sequence without branching in the loop from step 804 to 806, k is calculated from the power consumption waveform and the processing time. Can be difficult to guess.

Further, step 801 and step 802 do not need to be executed in succession. After step 801 is executed and F is stored, another process is performed, and then step 802 and the subsequent steps are executed. Similar to the third embodiment, it is more difficult to analyze the relationship between the process 7) and the processes in and after step 802.

Tamper-resistant modular multiplication device according to first and second embodiments of the present invention Tamper-resistant modular multiplication method according to the first embodiment of the present invention K encoding method according to first and second embodiments of the present invention Tamper-resistant modular multiplication method according to the second embodiment of the present invention Tamper resistant color multiplication apparatus according to third and fourth embodiments of the present invention Tamper resistant scalar multiplication method according to the third embodiment of the present invention K encoding method according to third and fourth embodiments of the present invention Tamper resistant scalar multiplication method according to the third embodiment of the present invention Power calculation method by Brickell et al.

Explanation of symbols

101 ... Tamper-resistant modular multiplication device
102 ... Control unit
103 ... ROM
104 ... Random access memory
105 ... Pre-calculation table
106: Remainder multiplication unit
201 ... First step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
202 ... Second step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
203 ... Third step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
204 ... Fourth step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
205 ... Fifth step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
206 ... Sixth step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
207 ... Seventh step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
208: Eighth step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
301. First step of k encoding method according to first and second embodiments of the present invention
302 ... Second step of k encoding method according to first and second embodiments of the present invention
303 ... the third step of the encoding method of k according to the first and second embodiments of the present invention
304 ... Fourth step of k encoding method according to first and second embodiments of the present invention
305 ... Fifth step of k encoding method according to first and second embodiments of the present invention
306: Sixth step of k encoding method according to first and second embodiments of the present invention
307: Seventh step of k encoding method according to first and second embodiments of the present invention
308: Eighth step of the encoding method of k according to the first and second embodiments of the present invention
309 ... Ninth step of k encoding method according to first and second embodiments of the present invention
401: First step of tamper-resistant modular multiplication method according to first embodiment of the present invention
402 ... Second step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
403 ... Third step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
404 ... Fourth step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention.
405 ... Fifth step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
406 ... Sixth step of the tamper-resistant modular multiplication method according to the first embodiment of the present invention
501 ... Tamper resistant color multiplication device
502 ... Control unit
503 ... ROM
504… Random access memory
505 ... Pre-calculation table
506 ... Point addition unit on elliptic curve
601... First step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
602 ... Second step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
603 ... Third step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
604 ... Fourth step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
605: Fifth step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
606 ... Sixth step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
607 ... Seventh step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
608 ... Eighth step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
701: First step of k encoding method according to third and fourth embodiments of the present invention
702 ... Second step of k encoding method according to third and fourth embodiments of the present invention
703 ... Third step of k encoding method according to third and fourth embodiments of the present invention
704 ... Fourth step of k encoding method according to third and fourth embodiments of the present invention
705 ... Fifth step of k encoding method according to third and fourth embodiments of the present invention
706 ... Sixth step of k encoding method according to third and fourth embodiments of the present invention
707 ... Seventh step of k encoding method according to third and fourth embodiments of the present invention
708: Eighth step of the k encoding method according to the third and fourth embodiments of the present invention.
709 ... Ninth step of k encoding method according to third and fourth embodiments of the present invention
801 ... First step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
802: Second step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
803 ... Third step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
804 ... Fourth step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
805 ... Fifth step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
806: Sixth step of the tamper-resistant modular multiplication method according to the third embodiment of the present invention
901 ... First step of power calculation method by Brickell et al.
902… The second step of the power calculation method by Brickell et al.
903… The third step of the power calculation method by Brickell et al.
904… The fourth step of the power calculation method by Brickell et al.
905 ... Fifth step of power calculation method by Brickell et al.
906… Brickell et al. 6th step
907 ... Seventh step of power calculation method by Brickell et al.
908… Eighth step of power calculation method by Brickell et al.
909 ... Ninth step of power calculation method by Brickell et al.

Claims (4)

A method of calculating a power-residue c = m ^k mod N that appears during cryptographic processing using an information processing device,
means for dividing n-bit integer data k into L blocks (L is the smallest integer of n / w or more) in order of w bits from LSB (Least Significant Bit),
Means for padding the MSB side with 0 when the block containing the MSB (Most Significant Bit) of the data k is less than w bits to make the block w bits;
When the data k divided into the blocks is k _s−1 , k _s−2 ,..., K ₁ , k ₀ , this corresponds to the case where each block is rearranged in the descending order as an integer of w bits. Means for storing the subscripts in that order;
Means for adding a mark to a subscript corresponding to a portion that changes in size when the k is rearranged in a large order in a w-bit block when storing the subscript;
means for holding a precomputed table TBL consisting of s data TBL [i] = m ^wi mod N for i = 1, 2, ..., s;
Means to initialize two intermediate variables A and B to 1,
Means for initializing the loop counter d to s-1;
The stored subscripts are referred to in order. If the subscript is not marked, B × TBL [d] mod N is calculated and stored in B. If the subscript is marked, B × A mod N Means for calculating and storing in A and subtracting 1 from d. 2. The tamper-resistant power calculation method according to claim 1, wherein the two intermediate variables A and B are TBL [s], TBL [s + 1] or TBL [s + 1], TBL [s], respectively. . A method of calculating a scalar multiplication Q = kP of points on an elliptic curve appearing during cryptographic processing using an information processing device,
Means for dividing the n-bit integer data k into L blocks (L is the smallest integer of n / w or more) in order of w bits in order from LSB (Least Significant Bit, least significant bit);
Means for padding the MSB side with 0 when the block containing the MSB (Most Significant Bit) of the data k is less than w bits to make the block w bits;
When the data k divided into the blocks is k _s−1 , k _s−2 ,..., K ₁ , k ₀ , this corresponds to the case where each block is rearranged in the descending order as an integer of w bits. Means for storing the subscripts in that order;
Means for adding a mark to a subscript corresponding to a portion that changes in size when the k is rearranged in a large order in a w-bit block when storing the subscript;
means for holding a pre-calculation table TBL composed of s pieces of data TBL [i] = w ⁱ P for i = 1, 2, ..., s;
Means to initialize two intermediate variables A and B to 1,
Means for initializing the loop counter d to s-1;
The stored subscripts are referred to in order. If the subscript is not marked, B × TBL [d] mod N is calculated and stored in B. If the subscript is marked, B × A mod N Means for calculating and storing in A, and subtracting 1 from d. 4. The tamper-resistant power calculation method according to claim 3, wherein the two intermediate variables A and B are TBL [s], TBL [s + 1] or TBL [s + 1], TBL [s], respectively. .