JP2016009114A - Data processing apparatus and decryption processing method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To verify a fault attach countermeasure against a discretionary public key e in a time equal to one session of exponential remainder.SOLUTION: In an exponential remainder arithmetic expressed by Y=XmodN, calculation is made of C0=XmodN, C1=XmodN, and T=XmodN, where d' represents the 2's complement of d and n represents the number of bits of d, determination is made as to whether a remainder where N is a divisor for the product of the value of C0 and the value of C1 matches the value of T, and, when it matches, the value of C1 is made to be Y, and, when it does not match, an error is assumed. This exponential remainder arithmetic is applied to an exponential remainder arithmetic in the cases where RSA decoding is performed using a Chinese remainder theorem.

Description

  The present invention relates to a measure against a fault attack (FA) against the Chinese remainder theorem (CRT) of RSA (Rivest Shamir Adleman), which is one of public key cryptosystems. The present invention relates to a technology effective when applied to a security function-equipped product and a security function-equipped system represented by IOT (Internet of Things).

  In RSA, the Chinese remainder theorem is used to perform the decryption process at high speed. On the other hand, various attack methods for revealing secret information such as a key while executing an encryption algorithm such as RSA have been proposed. A powerful attack is a fault attack. In this method, an error is generated in some way during execution of the calculation, and the key information is specified from the calculation result at this time and the calculation result when the operation is performed correctly.

<RSA>
RSA means that the public key is e, n, the secret key is f, the plaintext is Z, and the ciphertext is X, the following formula X = Z ^e modM,
Encrypt with Also, the following equation Z = X ^f modM,
Decrypt with.

Here, if the secret prime numbers are p and q, the following relation 1 = e × fmod {(p−1) (q−1)},
M = p × q,
Holds.

<Chinese surplus theorem>
When the Chinese remainder theorem is used for the decoding process, the following calculation formula Dp = fmod (p−1),
Dq = fmod (q−1),
Xp = X ^Dp modp,
Xq = X ^Dq modq,
w = (Xp−Xq) × q ⁻¹ modp,
Z = w × q + Xq,
The plaintext Z can be obtained by

<Fault Attack>
Fault attack is the encryption of noise and power to the power supply and clock, and laser irradiation to the circuit, and the secret value such as the key is revealed by comparing the output value when the failure state occurs with the correct value. It is an attack technique.

<Fault attack against the Chinese remainder theorem>
In the fault attack for the Chinese remainder theorem, as shown below, a fault condition is caused at the time of execution of a modular multiplication operation for obtaining Xp or Xq. For example, as illustrated in FIG. 6, the failure state is caused in accordance with the execution timing of the remainder calculation for which Xp is to be obtained. From the calculation result Z ′ that causes an error due to the failure state and the correct calculation result Z, the following calculation formula ZZ ′ = (w−w ′) × q,
q = gcd {pq, (w−w ′) × q} = gcd (M, Z−Z ′),
Q is obtained as the greatest common divisor between the known value M and the output value difference ZZ ′. Since p and f can be obtained from q, the secret key f is revealed to the attacker.

<Fault attack countermeasures>
For example, there is a technique described in Patent Document 1 as a countermeasure against an attack technique that analyzes physical information such as power consumption and illegally reveals the secret key f. Also, there is a technique described in Patent Document 2 as a countermeasure against an attack caused by analysis of power consumption or failure injection. However, none of the countermeasures against the fault attack focusing on the decoding algorithm based on the Chinese remainder theorem is considered. The inventor examined the following measures.

  As a first countermeasure, Xp and Xq are calculated twice, and if it is confirmed that the same value is obtained twice, the value of Z is output. That is, if the result does not match after the verification, it is considered that the attack has been received, and the value of Z is not output. In this method, it is necessary to perform the power-residue calculation relating to Xp and Xq four times.

The second measure is to re-encrypt the result Z calculated using the Chinese remainder theorem (X = Z ^e modM) and output Z if it can be confirmed that the value is the same as the input X. Z is not output. Since e = 65537 is often used, in this case, the calculation time for re-encryption is not long, and the calculation time is not practical.

JP 2014-81426 A JP 2010-277085 A

  The inventor examined the first countermeasure and the second countermeasure for the countermeasure against the fault attack. In the first countermeasure, the power-residue calculation relating to Xp and Xq needs to be performed four times, and the calculation time increases to a degree that cannot be ignored. As a second countermeasure, when an arbitrary value e is used to increase the encryption strength, if the value of e increases, it is assumed that the calculation processing time becomes too long to be practically used.

  The above and other problems and novel features will become apparent from the description of the specification and the accompanying drawings.

  An outline of representative ones of the embodiments disclosed in the present application will be briefly described as follows.

That is, in the modular exponentiation operation represented by Y = X ^d mod N, when d's two's complement is d 'and n is the number of bits of d, C0 = X ^d' mod N, C1 = X ^d mod N and T = X ² ^ ⁿ mod N is calculated, and it is determined whether or not the remainder modulo N matches the value of T with respect to the product of the value of C 0 and the value of C 1. Is set to Y, and if they do not match, an error is processed. The power-residue calculation applies RSA decoding processing to a power-residue calculation when the Chinese remainder theorem is used. In this specification, the power multiplier “ ² ^ ⁿ ” in the above “X ² ^ ⁿ ” means “2 ⁿ ”. That is, in this specification, the symbol ^ may be used as a power symbol for convenience.

  The effects obtained by the representative ones of the embodiments disclosed in the present application will be briefly described as follows.

  That is, whether or not an error has been injected at the power-residue calculation timing in the Chinese remainder theorem process applied to the RSA decryption process, even when an arbitrary public key e is used for encryption, Therefore, it is possible to detect through the original power-residue operation for decryption without adding a power-residue operation for encryption or an encryption operation only for verification.

FIG. 1 shows the function of the power-residue operation in a data processing apparatus including a computing unit 2 that can execute a power-residue operation to counter a fault attack on the Chinese remainder theorem of RSA, which is one of public key cryptography. It is explanatory drawing illustrated by the logic description. FIG. 2 is a flowchart illustrating a specific calculation process for the logical description of FIG. FIG. 3 is an explanatory diagram showing a processing example of steps S2 to S9 in FIG. 2 in the case where d = 101110001 ₂ and n = 8 in binary notation. FIG. 4 is a block diagram showing a configuration for realizing the function of the arithmetic unit by the program processing of the processor as a specific example of the data processing apparatus. FIG. 5 is a block diagram showing a configuration for realizing the function of an arithmetic unit with dedicated hardware as another specific example of the data processing apparatus. FIG. 6 is an explanatory diagram exemplifying a fault attack that causes a failure state when performing a modular remainder operation for obtaining Xp or Xq in the process of the national remainder theorem. FIG. 7 is an explanatory diagram exemplifying a logical description of a power-residue operation by a normal binary method. FIG. 8 is a flowchart illustrating an operation processing flow for realizing the logical description of FIG. FIG. 9 is an explanatory diagram showing a processing example of the logical description of the modular exponentiation operation of FIG. 7 in the case where binary notation and d = 1011001 ₂ and n = 8 are taken as an example.

1. First, an outline of an embodiment disclosed in the present application will be described. Reference numerals in the drawings referred to with parentheses in the outline description of the embodiments merely exemplify what are included in the concept of the components to which the reference numerals are attached.

[1] <Data processing device capable of calculating remainder to counter a fault attack>
The data processing device (1) has a computing unit (2) that performs RSA decoding using the Chinese remainder theorem. In the modular exponentiation operation to be expressed by Y = X ^d mod N, the arithmetic unit sets C ^′ = X ^{d ′} mod N, C 1 = X ^d mod N, and d ′ as the two's complement of d and n as the number of bits of d. T = X ² ^ ⁿ mod ^N is calculated (S2 to S9), and it is determined whether or not the remainder modulo N matches the value of T with respect to the product of the value of C0 and the value of C1 (S10). , S11), if they match, the value of C1 is set to Y (S12), and if they do not match, an error is determined (S13).

  According to this, whether or not an error is injected at the timing of exponentiation operation in the process of the Chinese remainder theorem applied to the decryption process of RSA, even when an arbitrary public key e is used for encryption Thus, it is possible to detect through a power residue operation for decryption without adding a power residue operation only for verification or an encryption operation for only verification. Therefore, it is possible to prevent the decoding using the incorrect result of the modular multiplication that should respond to the injected fault as it is, and it is possible to contribute to the shortening of the arithmetic processing time. In other words, the calculation processing time for preventing unauthorized disclosure of the secret key due to the fault attack is reduced.

[2] <Error response when a fault attack is detected>
In item 1, the error processing is processing that returns a value other than the value of C1.

  According to this, not only the fault attack itself focusing on the decryption algorithm based on the Chinese remainder theorem is invalidated but also the unauthorized access person cannot recognize it.

[3] <Function of the arithmetic unit is realized by processor program processing>
In Item 1, the arithmetic unit includes a work memory (4), a processor (3) that performs program processing using the work memory, and a program memory (5) that stores an operation program of the processor.

  According to this, it is possible to provide flexibility in realizing the function of the arithmetic unit.

[4] <Achievement of calculator functions with dedicated hardware>
In item 1, the arithmetic unit performs arithmetic control of power residue calculation to be expressed by Y = X ^d mod N and power residue operation to perform an operation based on a predetermined operation command issued from a processor (13) that performs program processing. Circuit.

  According to this, it can contribute to the further speed-up of the decoding process by an arithmetic unit.

[5] <Remainder calculation method to counter a fault attack>
The decoding processing method is a method of performing RSA decoding by data processing using the Chinese remainder theorem, and the data processing includes two exponentiation remainder operations. In each power-residue operation represented by Y = X ^d mod N, d's two's complement is d ', n is the number of bits of d, C0 = X ^d' mod N, C1 = X ^d mod N, and T = X ² ^ ⁿ modN is calculated (S2 to S9), and it is determined whether or not the remainder modulo N matches the value of T with respect to the product of the value of C0 and the value of C1 (S10, S11). If they match, the value of C1 is set to Y (S12), and if they do not match, an error is set (S13).

  According to this, whether or not an error is injected at the timing of exponentiation operation in the process of the Chinese remainder theorem applied to the decryption process of RSA, even when an arbitrary public key e is used for encryption Thus, it is possible to detect through a power residue operation for decryption without adding a power residue operation only for verification or an encryption operation for only verification. Therefore, it is possible to prevent the decoding using the incorrect result of the modular multiplication that should respond to the injected fault as it is, and it is possible to contribute to the shortening of the arithmetic processing time. In other words, the calculation processing time for preventing unauthorized disclosure of the secret key due to the fault attack is reduced.

[6] <Error response when a fault attack is detected>
In item 5, the error processing is processing that returns a value other than the value of C1.

  According to this, not only the fault attack itself focusing on the decryption algorithm based on the Chinese remainder theorem is invalidated but also the unauthorized access person cannot recognize it.

[7] <Data processing apparatus capable of calculating remainder to counter a fault attack>
The data processing device (1) has a computing unit (2) that decrypts the ciphertext X by RSA encryption into plaintext Z using the secret keys f, p, and q. The arithmetic processing by the computing unit includes a first process for obtaining Xp = X ^Dp modp using a remainder Dp obtained by dividing f by p−1, and Xq = X ^Dq using a remainder Dq obtained by dividing f by q−1. a second process of obtaining a mod q, and a third process by using the inverse element ^{q -1} q-modulo value and p Xp-Xq, seek w = (Xp-Xq) × q -1 modp, 4th process which calculates | requires plaintext Z by wxq + Xp. When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is d ′ as the 2's complement of d, and n is the number of bits of d. C0 = X ^{d ′} mod ^N , C 1 = X ^d mod ^N and T = X ² ^ ⁿ mod ^N are calculated (S2 to S9), and N is modulo the product of the value of C0 and the value of C1. It is determined whether or not the remainder to be matched with the value of T (S10, S11). If they match, the value of C1 is set to Y (S12), and if they do not match, an error is set (S13).

  According to this, whether or not an error is injected at the timing of exponentiation operation in the process of the Chinese remainder theorem applied to the decryption process of RSA, even when an arbitrary public key e is used for encryption Thus, it is possible to detect through a power residue operation for decryption without adding a power residue operation only for verification or an encryption operation for only verification. Therefore, it is possible to prevent the decoding using the incorrect result of the modular multiplication that should respond to the injected fault as it is, and it is possible to contribute to the shortening of the arithmetic processing time. In other words, the calculation processing time for preventing unauthorized disclosure of the secret key due to the fault attack is reduced.

[8] <Error response when a fault attack is detected>
In item 7, the error processing is processing that returns a value other than the value of C1.

  According to this, not only the fault attack itself focusing on the decryption algorithm based on the Chinese remainder theorem is invalidated but also the unauthorized access person cannot recognize it.

[9] <Achievement unit functions realized by processor program processing>
In item 7, the computing unit includes a work memory (4), a processor (3) that performs program processing using the work memory, and a program memory (5) that stores an operation program of the processor.

  According to this, it is possible to provide flexibility in realizing the function of the arithmetic unit.

[10] <Achievement of calculator functions with dedicated hardware>
In Item 7, the arithmetic unit is a modular arithmetic circuit that should perform arithmetic control and arithmetic operations of the first to fourth processes based on a predetermined arithmetic command issued from a processor (13) that performs program processing.

  According to this, it can contribute to the further speed-up of the decoding process by an arithmetic unit.

[11] <Remainder calculation method to counter a fault attack>
The decryption method is a method of decrypting plaintext Z by giving ciphertext X by RSA encryption together with secret keys f, p and q to the data processing device, and using the remainder Dp obtained by dividing f by p−1, Xp = X ^Dp modp first process, fq divided by q-1 is used as a second process to calculate Xq = X ^Dq modq, and the inverse of q modulo Xp-Xq and p using the original ^{q -1,} and a third process of obtaining a w = (Xp-Xq) × q -1 modp, and a fourth process of obtaining a plaintext Z by w × q + Xp. When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is d ′ as the 2's complement of d, and n is the number of bits of d. C0 = X ^{d ′} mod ^N , C 1 = X ^d mod ^N and T = X ² ^ ⁿ mod ^N are calculated (S2 to S9), and N is modulo the product of the value of C0 and the value of C1. It is determined whether or not the remainder to be matched with the value of T (S10, S11). If they match, the value of C1 is set to Y (S12), and if they do not match, an error is set (S13).

  According to this, whether or not an error is injected at the timing of exponentiation operation in the process of the Chinese remainder theorem applied to the decryption process of RSA, even when an arbitrary public key e is used for encryption Thus, it is possible to detect through a power residue operation for decryption without adding a power residue operation only for verification or an encryption operation for only verification. Therefore, it is possible to prevent the decoding using the incorrect result of the modular multiplication that should respond to the injected fault as it is, and it is possible to contribute to the shortening of the arithmetic processing time. In other words, the calculation processing time for preventing unauthorized disclosure of the secret key due to the fault attack is reduced.

[12] <Error response when a fault attack is detected>
In item 11, the error processing is processing that returns a value other than the value of C1.

  According to this, not only the fault attack itself focusing on the decryption algorithm based on the Chinese remainder theorem is invalidated but also the unauthorized access person cannot recognize it.

[13] <Data processing apparatus capable of calculating remainder to counter a fault attack>
The data processing device (1) has a computing unit (2) that decrypts the ciphertext X by RSA encryption into plaintext Z using the secret keys f, p, and q. The arithmetic processing by the computing unit includes a first process for obtaining Xp = X ^Dp modp using a remainder Dp obtained by dividing f by p−1, and Xq = X ^Dq using a remainder Dq obtained by dividing f by q−1. a second process of obtaining a mod q, and a third process by using the inverse element ^{q -1} q-modulo value and p Xp-Xq, seek w = (Xp-Xq) × q -1 modp, 4th process which calculates | requires plaintext Z by wxq + Xp. When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is as follows:
Processing to initially set X in the T register (S1);
A process of rewriting the T register with a remainder modulo N with respect to the square of the value of the T register each time the bits of d are referred to (S5),
Until the bit of d referred to becomes 1 for the first time, the process of rewriting the C0 register and the C1 register with the value of the T register every time the bit of d is referred (S4),
Once the referenced d bit is set to 1, the C1 register is rewritten with a remainder modulo N for the product of the value of the C1 register and the value of the T register each time 1 of the d bit is referenced ( S8) a process of rewriting the C0 register with a remainder modulo N for the product of the value of the C0 register and the value of the T register each time 0 of the bit of d is referred to (S7), and all bits of d When the reference is made, it is determined whether or not the remainder modulo N with respect to the product of the value of the C0 register and the value of the C1 register matches the value of the T register (S10, S11). And register value Y (S12), and if they do not match, an error (S13) is included.

  According to this, whether or not an error is injected at the timing of exponentiation operation in the process of the Chinese remainder theorem applied to the decryption process of RSA, even when an arbitrary public key e is used for encryption Thus, it is possible to detect through a power residue operation for decryption without adding a power residue operation only for verification or an encryption operation for only verification. Therefore, it is possible to prevent the decoding using the incorrect result of the modular multiplication that should respond to the injected fault as it is, and it is possible to contribute to the shortening of the arithmetic processing time. In other words, the calculation processing time for preventing unauthorized disclosure of the secret key due to the fault attack is reduced.

[14] <Error response when a fault attack is detected>
In item 13, the error processing is processing that returns a value other than the value of the C1 register.

  According to this, not only the fault attack itself focusing on the decryption algorithm based on the Chinese remainder theorem is invalidated but also the unauthorized access person cannot recognize it.

[15] <Actual unit functions are realized by processor program processing>
In item 13, the computing unit (2) includes a work memory (4) that is made available as the T register, the C0 register, and the C1 register and is used as a storage area for the value d, and the work memory. A processor (3) that performs program processing using the program and a program memory (5) that stores an operation program of the processor.

  According to this, it is possible to provide flexibility in realizing the function of the arithmetic unit.

[16] <Achievement of calculator functions with dedicated hardware>
In item 13, the arithmetic unit is a modular exponentiation operation circuit that performs an operation based on a predetermined operation command, and includes a command register (20), a parameter register (22, 23), a control circuit (21), and an operation circuit (24 ). The command register is written with the predetermined operation command from the program processing device. The parameter register is assigned to the T register, the C0 register, and the C1 register, and has a setting area for the value d. The control circuit refers to a predetermined operation command written in the command register and a value d set in the parameter register, and uses the T register, the C0 register, and the C1 register to transmit the operation circuit to the operation circuit. Calculations in the first process to the fourth process are executed.

  According to this, it can contribute to the further speed-up of the decoding process by an arithmetic unit.

[17] <Remainder calculation method to counter a fault attack>
The decryption method is a method of decrypting plaintext Z by giving ciphertext X by RSA encryption together with secret keys f, p and q to the data processing device, and using the remainder Dp obtained by dividing f by p−1, Xp = X ^Dp modp first process, fq divided by q-1 is used as a second process to calculate Xq = X ^Dq modq, and the inverse of q modulo Xp-Xq and p using the original ^{q -1,} and a third process of obtaining a w = (Xp-Xq) × q -1 modp, and a fourth process of obtaining a plaintext Z by w × q + Xp. When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is as follows:
Processing to initially set X in the T register (S1);
A process of rewriting the T register with a remainder modulo N with respect to the square of the value of the T register each time the bits of d are referred to (S5),
Until the bit of d referred to becomes 1 for the first time, the process of rewriting the C0 register and the C1 register with the value of the T register every time the bit of d is referred (S4),
Once the referenced d bit is set to 1, the C1 register is rewritten with a remainder modulo N for the product of the value of the C1 register and the value of the T register each time 1 of the d bit is referenced ( S8) every time the bit 0 of d is referenced, the C0 register is rewritten with a remainder modulo N with respect to the product of the value of the C0 register and the value of the T register (S7), and all bits of d When the reference is made, it is determined whether or not the remainder modulo N with respect to the product of the value of the C0 register and the value of the C1 register matches the value of the T register (S10, S11). And register value Y (S12), and if they do not match, an error (S13) is included.

  According to this, whether or not an error is injected at the timing of exponentiation operation in the process of the Chinese remainder theorem applied to the decryption process of RSA, even when an arbitrary public key e is used for encryption Thus, it is possible to detect through a power residue operation for decryption without adding a power residue operation only for verification or an encryption operation for only verification. Therefore, it is possible to prevent the decoding using the incorrect result of the modular multiplication that should respond to the injected fault as it is, and it is possible to contribute to the shortening of the arithmetic processing time. In other words, the calculation processing time for preventing unauthorized disclosure of the secret key due to the fault attack is reduced.

[18] <Error response when a fault attack is detected>
In item 17, the error processing is processing that returns a value other than the value of the C1 register.

  According to this, not only the fault attack itself focusing on the decryption algorithm based on the Chinese remainder theorem is invalidated but also the unauthorized access person cannot recognize it.

2. Details of Embodiments Embodiments will be further described in detail.

<Operational Unit that Performs RSA Decoding Processing Using Chinese Remainder Theorem>
FIG. 1 illustrates a security function-installed product represented by an IC card, an in-vehicle microcomputer system, an IOT, and the like and a data processing apparatus 1 applied to a security function-installed system. This data processing device includes a computing unit 2 that enables a power-residue operation to counter a fault attack on the Chinese remainder theorem of RSA, which is one of public key cryptography. In FIG. 1, the function of such a power-residue operation in the arithmetic unit 2 is exemplified by a logical description.

  Here, RSA and the Chinese remainder theorem are as described above, and the following explanation is based on them. The data processing device 1 performs a calculation process of decrypting the ciphertext X and obtaining a plain Z according to a predetermined algorithm to which the RSA and the Chinese remainder theorem are applied. It goes without saying that the arithmetic processing for encrypting the plaintext Z to obtain the ciphertext X may be supported.

When the public key is e, n, the secret key is f, the plaintext is Z, and the ciphertext is X, the decryption operation processing in RSA is the following arithmetic expression Z = X ^f modM
It is realized by. Here, if the secret prime numbers are p and q, the following relation 1 = e × fmod {(p−1) (q−1)},
M = p × q,
Holds. In consideration of this relationship, when the Chinese remainder theorem is used for the calculation processing of the decoding, the following calculation formula Dp = fmod (p−1),
Dq = fmod (q−1),
Xp = X ^Dp modp ... 1st process,
Xq = X ^Dq modq ... 2nd process,
w = (Xp−Xq) × q ⁻¹ modp ... the third process,
Z = w × q + Xq ... 4th process,
The plaintext Z can be obtained by

The logical description shown in the calculator 2 of FIG. 1 does not return the calculation result of the first process or the second process when a fault attack is performed by error injection on the first process or the second process. It is for making. In the logical description of FIG. 1, the power-residue arithmetic expressions of both the first process and the second process are shown as Y = X ^d mod N for convenience. That is, in the case of the first process Xp = X ^Dp modp, Xp = Y, Dp = d, and p = N. In the case of the second process Xq = X ^Dq modq, Xp = Y, Dq = d, and q = N. In FIG. 1, the symbol * means multiplication. k = 0 to n−1 means a bit number from the lower side of d having an n-bit length.

The logical description shown in the computing unit 2 in FIG. 1 shows that when the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d modN, the process for realizing this expression is When the two's complement is d ′ and n is the number of bits of d, C0 = X ^{d ′} modN,
C1 = X ^d mod N,
T = X ² ^ ⁿ mod ^N ,
To determine whether or not the remainder modulo N matches the value of T with respect to the product of the value of C0 and the value of C1, and if it matches, the value of C1 is set to Y. If there is an error, it means processing to be an error. This process will be specifically described below.

<Calculation method of Y = X ^d mod N>
FIG. 2 illustrates a specific operation processing flow for the logical description of FIG. In order to perform a calculation process of Y = X ^d modN, a T register, a C0 register, a C1 register, a k register, and a d register are prepared. 2, the T register, the C0 register, the C1 register, the k register, and the d register are simply illustrated as T, C0, C1, k, and d together with the symbol ←. The k register takes the values of bit numbers 0 to n−1 from the lower side of the value d set in the d register. Intermediate values T, C0, and C1 are temporarily held in the T register, the C0 register, and the C1 register.

  First, the value N is set in the N register, the ciphertext X is initialized in the T register, the initial value 0 is set in the k register, and the value d is set in the d register (S1).

  Next, it is determined whether or not the bit number value d [k] = 1 set in the k register has already occurred (S2). (S3), that is, whether d [k] = 1 has occurred for the first time this time (S2 = No, S3 = No), or whether d [k] = 1 has not yet occurred (S2 = No, S3 = Yes) is determined. Even if d [k] = 1 has not yet occurred, and when d [k] = 1 occurs for the first time, the register T is rewritten with the operation result of T * TmodN, and the value of the register k is set to k + 1. Update (S5). When d [k] = 1 occurs for the first time, the value of T at that time is initialized in the register C0, and the value of T at that time is initialized in the register C1 (S4).

  If the bit number value d [k] = 1 set in the k register in step S2 has already occurred (S2 = Yes), if d [k] = 0 this time (S6 = Yes), The register C0 is rewritten with the calculation result of C0 * TmodN (S7). If d [k] = 1 is present (S6 = No), the register C1 is rewritten with the calculation result of C1 * TmodN (S8). Following step S7 and S8, the process of step S5 is performed.

  After step S5, it is determined whether or not the logical value determination of each bit of the value d has been completed up to the most significant bit (k <n-1) (S9), and the above processes S2 to S8 are repeated until the most significant bit is reached. .

Steps S2 to S8 can be positioned as a modification of the binary method for the power-residue calculation. In the normal binary method, as illustrated in the logical description of FIG. 7 and the operation processing flow of FIG. 8, when the value of each bit of d is 1, both intermediate values C and T are updated, and in the case of 0, Only the value of T is updated, and the last remaining value in C becomes Y of the calculation result. As an example, in binary notation, d = 10111001 ₂ and n = 8, FIG. 9 shows powers related to intermediate value C and powers related to T corresponding to the value d [k] of each bit of k = 0 to 7. For example, when k = 4 (d [k] = 1), the power related to the intermediate value C is X ⁹ + X ¹⁶ = X ²⁵ .

The processing of steps S2 to S9 in FIG. 2 for the normal binary method updates both the intermediate values C1 and T when the value of each bit of d is 1, and updates the intermediate values C0 and T when 0. Update both. The former corresponds to the power-residue operation C1 = X ^d modN for the power exponent d, and the latter corresponds to the power-residue operation C0 = X ^{d ′} modN for the two's complement d ′ of ^d . In particular, since the bit of the complement d ′ related to the bit whose value d is first set to the value 1 has the value 1, when the bit first becomes the value 1, only C1 as shown in step S4. In addition, the value of the register T is also set to C0.

As an example of the processing of S2 to S9, FIG. 3 shows the case where d = 1011001 ₂ and n = 8 in binary notation as in FIG. Figure 3 also convenience C0, C1, and illustrates a power only for each T, then exponential value of the T is k is X ² times every advancing one. The power value related to C0 is the product of the previous value when d [k] = 1, and the product of the power value related to C0 immediately before and the power value related to T when d [k] = 0. The power value related to C1 is the product of the previous value when d [k] = 0, and the product of the power value related to C1 just before and the power value related to T when d [k] = 1. Since d and d ′ are in a complement relationship, the product of the power value related to C0 and the power value related to C1 is equal to the power value related to T for each k.

When the processing of steps S2 to S9 is completed while sequentially referring to all bits of d, the C0 register is rewritten with a remainder modulo N for the product of the value of the C0 register and the value of the C1 register (S10). , C0 register value is matched with T register value (S11). If no error is positively injected by laser irradiation or the like during the power-residue calculation process represented by Y = X ^d mod N, the value of the C0 register matches the value of the T register in the determination of step S11. According to the example of FIG. 3, X ⁷¹ × X ¹⁸⁵ = X ²⁵⁶ .

  If the determination in step S11 is coincident, Y = C1 is output as the calculation result (S12). If they do not match, error processing is performed (S13).

In this way, when the d bits become 1 for the first time, the same value as T is written to the registers C0 and C1, and when each bit of d is 0, the register values C0 and T In the case of 1, the register values C1 and T are updated. Assuming that d ′ is the 2's complement of d, C0 = X ^{d ′} mod ^N , C 1 = X ^d mod ^N , T = X ² ^ ⁿ mod ^N , and C 0 × C 1 mod N = X ^{(d + d ′)} mod ^N = X ² ^ ⁿ Since modN = T, if T and C0 × C1modN have the same value, C1 is output as the calculation result Y. Otherwise, it is regarded that an attack has occurred and error processing is performed. As error processing, Y is not output, or any value other than C1 is output.

  According to this arithmetic processing method, an arbitrary public key e is used for encryption as to whether or not an error has been injected at the power-residue arithmetic timing in the process of the Chinese remainder theorem applied to the RSA decryption process. Even in this case, the detection can be performed through the original exponentiation remainder operation for decryption without adding the exponentiation remainder operation only for the verification or the encryption operation for the verification only. Therefore, it is possible to prevent the decoding using the incorrect result of the modular multiplication that should respond to the injected fault as it is, and it is possible to contribute to the shortening of the arithmetic processing time. In other words, for any public key e, it is possible to perform a countermeasure against a fault attack in a time equivalent to one exponentiation residue, and to shorten the calculation processing time to prevent unauthorized disclosure of the secret key due to the fault attack Is realized.

<Specific examples of data processing apparatus>
FIG. 4 shows a specific example of the data processing apparatus 1. The data processing device 1 shown in FIG. 4 is configured to realize the function of the computing unit 2 by program processing of the processor. The computing unit 2 includes, for example, a work memory 4, a processor 3 that performs program processing using the work memory 4, and a program memory 5 that stores an operation program of the processor 3. The processor 3 includes at least a central processing unit, decodes instructions sequentially fetched from the program memory 5, and executes control of the arithmetic sequence of the above-described decoding processing of RSA and arithmetic processing using the Chinese remainder theorem. At this time, the work memory 4 is used as a storage area for the T register, C0 register, C1 register, N register and d register, and other work areas, and is accessed and used by the processor 3. In addition, the data processing apparatus 1 includes an external interface circuit 6 and an accelerator 7. Needless to say, the processor 3 may include other circuit units such as a cache memory, an address conversion buffer, and a floating point arithmetic unit in addition to the central processing unit.

  The data processing apparatus 1 can be configured as a single LSI on one semiconductor substrate by a CMOS integrated circuit manufacturing technique or the like. Alternatively, it is also possible to configure a system by mounting a plurality of semiconductor devices on a multi-chip semiconductor integrated circuit module composed of a plurality of semiconductor chips or a circuit board. The computing unit 2 can also be configured as a multichip by a plurality of semiconductor devices.

  By realizing the function of the computing unit 2 by the program processing of the processor 3, it is possible to provide flexibility in realizing the function of the computing unit 2.

  FIG. 5 shows another specific example of the data processing apparatus 1. The data processing device 1 shown in FIG. 5 is configured to realize the function of the computing unit 2 with dedicated hardware. The computing unit 2 constitutes a modular exponentiation operation circuit that should perform an operation based on a predetermined operation command. The arithmetic unit 2 constituting the power-residue arithmetic circuit includes a command register 20, parameter registers 22 and 23, a control circuit 21, and an arithmetic circuit 24. A predetermined arithmetic command is written to the command register 20 from the processor 13 as a program processing device. The processor 13 fetches and executes a program stored in the program memory 15. The parameter register 23 is assigned to the T register, C0 register, C1 register, and N register. The parameter register 22 is a setting area for the value d. The arithmetic circuit 24 includes an arithmetic logic arithmetic circuit, a multiplication circuit, and the like. The control circuit 21 uses the T register, the C0 register, the C1 register, and the N register by referring to a predetermined operation command written in the command register 20 and the value d set in the parameter register 22, and the Chinese The arithmetic circuit 24 is caused to execute the arithmetic processing of the above-described decoding processing of the RSA using the remainder theorem. In addition, the data processing apparatus 1 includes an external interface circuit 16 and an accelerator 17. Needless to say, the processor 3 may include other circuit units such as a cache memory, an address conversion buffer, and a floating point arithmetic unit in addition to the central processing unit.

  The data processing apparatus 1 of FIG. 5 can be configured as a single LSI on a single semiconductor substrate by a CMOS integrated circuit manufacturing technique or the like. The computing unit 2 constituting the power-residue computing circuit can be regarded as one accelerator. The data processing apparatus 1 of FIG. 5 can be configured as a system by mounting a plurality of semiconductor devices on a multi-chip semiconductor integrated circuit module composed of a plurality of semiconductor chips or a circuit board. The computing unit 2 can also be configured as a multichip by a plurality of semiconductor devices.

  According to this, it is possible to contribute to further speeding up of the decoding process by using the arithmetic unit 2 that is made into dedicated hardware.

  It goes without saying that the present invention is not limited to the above-described embodiment, and various modifications can be made without departing from the scope of the invention.

  For example, it is not limited to the method of developing this based on the right binary method as a binary method for performing the power-residue operation while determining the logical value of the bit of d, but also applied to the method of developing this based on the left binary method It goes without saying that it is possible.

  Moreover, the processing flow of FIG. 2 is an example, and it cannot be overemphasized that it can change suitably in the detail.

DESCRIPTION OF SYMBOLS 1 Data processor 2 Operation unit 3 Processor 4 Work memory 5 Program memory 13 Processor 15 Program memory 16 External interface circuit 17 Accelerator 20 Command register 22, 23 Parameter register 24 Operation circuit

Claims (18)

It has a computing unit that performs RSA decoding using the Chinese remainder theorem,
The arithmetic unit is a modular multiplication operation that should be expressed as Y = X ^d modN.
Let d 'be the two's complement of d, and let n be the number of bits of d.
C0 = X ^{d ′} mod N,
C1 = X ^d mod ^N , and T = X ² ^ ⁿ mod ^N ( ² ^ ⁿ means 2 ⁿ ),
It is determined whether or not the remainder modulo N matches the value of T with respect to the product of the value of C0 and the value of C1, and if they match, the value of C1 is set to Y, and if they do not match, an error is indicated. A data processing apparatus that performs processing.   The data processing apparatus according to claim 1, wherein the error processing is processing that returns a value other than the value of C1.   2. The data processing apparatus according to claim 1, wherein the computing unit includes a work memory, a processor that performs program processing using the work memory, and a program memory that stores an operation program of the processor. 2. The arithmetic unit according to claim 1, wherein the arithmetic unit is a modular arithmetic circuit to perform arithmetic control and arithmetic operation of a modular exponentiation expressed by Y = X ^d mod N based on a predetermined arithmetic command issued from a processor that performs program processing. A data processing device. A decoding processing method for performing RSA decoding by data processing using the Chinese remainder theorem,
The data processing includes two power-residue operations,
In each power-residue calculation represented by Y = X ^d mod N,
d's complement of d is d ', n is the number of bits of d,
C0 = X ^{d ′} mod N,
C1 = X ^d mod ^N and T = X ² ^ ⁿ mod ^N ,
It is determined whether or not the remainder modulo N matches the value of T with respect to the product of the value of C0 and the value of C1, and if they match, the value of C1 is set to Y, and if they do not match, an error is indicated. A decoding processing method for performing the processing.   6. The decoding processing method according to claim 5, wherein the error processing is processing for returning a value other than the value of C1. An arithmetic unit that decrypts the ciphertext X by the RSA cipher into plaintext Z using the secret keys f, p, and q;
The arithmetic processing by the arithmetic unit is as follows:
a first process for obtaining Xp = X ^Dp modp using a remainder Dp obtained by dividing f by p−1;
a second process for obtaining Xq = X ^Dq modq using a remainder Dq obtained by dividing f by q−1;
A third process for calculating w = (Xp−Xq) × q ⁻¹ modp using the value of Xp−Xq and the inverse q ^{−1 of} q modulo p;
a fourth process for obtaining plaintext Z by w × q + Xp,
When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is d ′ as the 2's complement of d, and n is the number of bits of d. And when
C0 = X ^{d ′} mod N,
C1 = X ^d mod ^N and T = X ² ^ ⁿ mod ^N ,
It is determined whether or not the remainder modulo N matches the value of T with respect to the product of the value of C0 and the value of C1, and if they match, the value of C1 is set to Y, and if they do not match, an error is indicated. A data processing device including processing to perform.   8. The data processing apparatus according to claim 7, wherein the process to be an error is a process of returning a value other than the value of C1.   8. The data processing device according to claim 7, wherein the computing unit includes a work memory, a processor that performs program processing using the work memory, and a program memory that stores an operation program of the processor.   8. The data processing according to claim 7, wherein the arithmetic unit is a modular arithmetic circuit that should perform arithmetic control and arithmetic operations of the first to fourth processes based on a predetermined arithmetic command issued from a processor that performs program processing. apparatus. A decryption method for decrypting plaintext Z by giving ciphertext X by RSA cipher together with secret keys f, p and q to a data processing device,
a first process for obtaining Xp = X ^Dp modp using a remainder Dp obtained by dividing f by p−1;
a second process for obtaining Xq = X ^Dq modq using a remainder Dq obtained by dividing f by q−1;
A third process for calculating w = (Xp−Xq) × q ⁻¹ modp using the value of Xp−Xq and the inverse q ^{−1 of} q modulo p;
a fourth process for obtaining plaintext Z by w × q + Xp,
When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is d ′ as the 2's complement of d, and n is the number of bits of d. And when
C0 = X ^{d ′} mod N,
C1 = X ^d mod ^N and T = X ² ^ ⁿ mod ^N ,
It is determined whether or not the remainder modulo N matches the value of T with respect to the product of the value of C0 and the value of C1, and if they match, the value of C1 is set to Y, and if they do not match, an error is indicated. A decoding processing method.   12. The decoding processing method according to claim 11, wherein the process to be an error is a process of returning a value other than the value of C1. An arithmetic unit that decrypts the ciphertext X by the RSA cipher into plaintext Z using the secret keys f, p, and q;
The arithmetic processing by the arithmetic unit is as follows:
a first process for obtaining Xp = X ^Dp modp using a remainder Dp obtained by dividing f by p−1;
a second process for obtaining Xq = X ^Dq modq using a remainder Dq obtained by dividing f by q−1;
A third process for calculating w = (Xp−Xq) × q ⁻¹ modp using the value of Xp−Xq and the inverse q ^{−1 of} q modulo p;
a fourth process for obtaining plaintext Z by w × q + Xp,
When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is as follows:
Processing to initialize X in the T register;
a process of sequentially referring to the bits of d and rewriting the T register with a remainder modulo N with respect to the square of the value of the T register each time it is referred to;
Until the bit of d referred to becomes 1 for the first time, each time the bit of d is referenced, the process of rewriting the C0 register and the C1 register with the value of the T register,
Once the referenced d bit is set to 1, the C1 register is rewritten with a remainder modulo N for the product of the value of the C1 register and the value of the T register each time 1 of the d bit is referenced. A process of rewriting the C0 register with a remainder modulo N for the product of the value of the C0 register and the value of the T register each time 0 of the bit of d is referenced, and when all bits of d are referenced, the C0 register It is determined whether or not the remainder modulo N for the product of the value of C1 and the value of the C1 register matches the value of the T register. A data processing apparatus including processing to be an error.   14. The data processing device according to claim 13, wherein the error processing is processing for returning a value other than the value of the C1 register. In Claim 13, the computing unit is:
A work memory that is made available as the T register, the C0 register, and the C1 register and is used as a storage area for the value d;
A processor that performs program processing using the work memory;
A data processing apparatus including a program memory for storing an operation program of the processor. The arithmetic unit according to claim 13, wherein the arithmetic unit is a modular arithmetic circuit to perform an operation based on a predetermined operation command, and includes a command register, a parameter register, a control circuit, and an arithmetic circuit.
The command register is written with the predetermined operation command from the program processing device,
The parameter register is assigned to the T register, the C0 register, and the C1 register, and has a setting area for the value d,
The control circuit refers to a predetermined operation command written in the command register and a value d set in the parameter register, and uses the T register, the C0 register, and the C1 register to transmit the operation circuit to the operation circuit. A data processing apparatus that executes calculations of a first process to a fourth process. A decryption method for decrypting plaintext Z by giving ciphertext X by RSA cipher together with secret keys f, p and q to a data processing device,
a first process for obtaining Xp = X ^Dp modp using a remainder Dp obtained by dividing f by p−1;
a second process for obtaining Xq = X ^Dq modq using a remainder Dq obtained by dividing f by q−1;
A third process for calculating w = (Xp−Xq) × q ⁻¹ modp using the value of Xp−Xq and the inverse q ^{−1 of} q modulo p;
a fourth process for obtaining plaintext Z by w × q + Xp,
When the power-residue arithmetic expression of both the first process and the second process is expressed as Y = X ^d mod N, the process for realizing this expression is as follows:
Processing to initialize X in the T register;
a process of sequentially referring to the bits of d and rewriting the T register with a remainder modulo N with respect to the square of the value of the T register each time it is referred to;
Until the bit of d referred to becomes 1 for the first time, each time the bit of d is referenced, the process of rewriting the C0 register and the C1 register with the value of the T register,
Once the referenced d bit is set to 1, the C1 register is rewritten with a remainder modulo N for the product of the value of the C1 register and the value of the T register each time 1 of the d bit is referenced. A process of rewriting the C0 register with a remainder modulo N for the product of the value of the C0 register and the value of the T register each time 0 of the bit of d is referenced, and when all bits of d are referenced, the C0 register It is determined whether or not the remainder modulo N for the product of the value of C1 and the value of the C1 register matches the value of the T register. A decryption processing method including processing to be an error.   18. The decoding processing method according to claim 17, wherein the process to be an error is a process of returning a value other than the value of the C1 register.

Images