JPH118616A - Ic card having provision against attack taking advantage of failure - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enhance the security against attach taking advantage of a failure of the IC card that conducts signature generating processing at a high speed by using the Chinese remainder theorem. SOLUTION: The power remainder calculation generating a digital signature M is processed at a high speed with the Chinese remainder theorem by using a prime factor to modulus (n), and an error check code for data generated in the calculation process of the Chinese remainder theorem together with the data themselves are calculated and stored simultaneously. In the case of the digital signature M, the error check code of the data is again calculated, the stored error check code is collated to detect an error of the data and an error status is returned when the error is detected.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an IC card equipped with a coprocessor having an encryption / decryption function of RSA public key cryptosystem and capable of processing a modular exponentiation calculation at a high speed. Gives a physical stimulus from the IC
The present invention relates to an IC card in which an error is intentionally generated with respect to a calculation result of a card, and a countermeasure against a failure use attack in which secret information is analyzed by using the error.

[0002]

2. Description of the Related Art In a public key cryptosystem, a pair of an encryption key and a decryption key are different, and the encryption key is made public and the decryption key is kept secret. This has the advantage that only one kind of decryption key for oneself needs to be stored. In addition, the sender signs with the private key that only he knows, the receiver checks the signature with the public key, and confirms that the sender of the transmitted message is not a fake, Authentication communication (digital signature communication) in which the receiver can confirm whether or not tampering has occurred is possible. The RSA public key cryptosystem is known as a representative example of the public key cryptosystem having such an authentication communication function.

In the RSA public key cryptosystem, an encryption key is a set of (e, n), a decryption key is a set of (d, n), e and n (random numbers) are public keys, and d is a secret key. It is. The public key is
Any two different prime factors p and q are selected, the product n = pq is calculated, e is generated from n, and the secret key d is generated from the generated public key. The creation of a digital signature by the RSA encryption is performed by modular exponentiation using a secret key exponent d. A method of reducing the amount of computation using prime factors p and q of the modulus n of modular exponentiation and performing high-speed processing is known. (JJ Quisquater and C. Couvreur, "Fast Decipher
ment Algorithm forRSA Public-Key Cryptosystem ", Ele
ctronics Letters Volume.18 (1982) No.21, pp.905-90
7).

An IC card equipped with a coprocessor that performs high-speed modular exponentiation calculation at a high speed and that creates a digital signature by RSA encryption at a high speed will be described. As shown in FIG. 5, the reader / writer 1 and the IC card 2 can communicate with each other. When a message C is given from the reader / writer 1 to the IC card 2 together with a command name for creating a digital signature, the IC The card generates a digital signature M by performing modular exponentiation calculation as described later, and returns the digital signature M to the reader / writer 1 as a response.

[0005] As shown in FIG.
In addition to U2a, it has a coprocessor 2b composed of hard logic for performing modular exponentiation calculation at high speed, and executes an operation by an instruction from the CPU when creating a digital signature. The command execution procedure is stored in the ROM 2c of the IC card 2, and variables required for performing modular exponentiation are stored in the EEPROM 2d.

Next, a description will be given of high-speed digital signature processing by the IC card. Here, C: message digest to be signed d: secret key exponent M: created digital signature, M = C ^d mod n (1) modular exponentiation calculation (C ^d divided by n The remainder is M), and a digital signature M is created. Since the modulus n of the modular exponentiation calculation uses a very large value of, for example, several hundred digits in decimal, a large processing time is required if the calculation of the expression (1) is directly performed by the IC card.

Therefore, first, the signature creator himself is n = pq
Since the prime factors p and q can be known, d _p = d mod (p−1) (2) d _q = d mod (q−1) (3) a = q ⁻¹ mod p (4) is calculated and stored in the EEPROM 2d of the IC card. Here, a in equation (4) is a multiplicative inverse of q that satisfies aq≡1mod (p).

Next, in the following steps 1 to 3, a remainder calculation is performed by using p and q whose lengths are half of n instead of n, which makes it possible to calculate equation (1) as it is. Can be processed at high speed. Step _{1: C p = Cmod p,} C q = Cmod q ...... (5) Step ^{_{2: M p = C p x}} mod p, M q = C q y mod q ...... (6) Here, x = d Calculate _p , y = d _q . The calculation in step 2 is a normal RSA decoding calculation for each of p and q. Using this result, equation (1) results in the following simultaneous equation. M≡M _p (mod p) (7) M≡M _q (mod q) (8) In equation (7), M−M _p is divisible by p, and equation (8) is M−M
_It means that q is divisible by q. Step 3: from the Chinese remainder _{theorem, M = {a (M p} -M q) mod p} * q + M q digital signature M in the calculation of ... (9) is obtained.

FIG. 7 shows a processing flow for creating a digital signature M at a high speed by the above-described procedure. IC card 2
Receives a digital signature command (actually, it receives the command name and reads the command corresponding to the command name from the ROM).
D _p which is stored in the PROM, d _q, reads the a, reads the message sent with the command (step 1-2). Next, Cmo is calculated according to equation (5).
d p and C mod q are calculated to obtain C _p and C _q (steps 3 and 4). Then, using C _p , C _q , d _p , d _q , p and q, M _p is calculated by the equation (6). calculates the M _q (step 5
6). Next, a digital signature M is created by using the Chinese remainder equation using equation (9), and the created digital signature M is created.
Is returned to the reader / writer 1 as a response.

Thus, p, which is half the number of digits for n,
Since the remainder calculation is performed by q, the amount of calculation is approximately 1/4 compared to the calculation of the equation (1), and the processing can be speeded up.

By the way, in a failure attack, a physical stimulus (heat, pressure, radiation, voltage, etc.) is externally applied to an IC card for creating a digital signature.
An error is intentionally generated in a part of the bit pattern on the memory or the register of the C card. For example, in the intermediate calculation of the Step 2 (6), intentionally generate an error, misleading either the value of M _p or M _q. Here, M
Assuming that the calculation result of _p is incorrect, it is set to M _p ', and M
It is assumed that _q is correctly obtained. Since the signature M obtained by applying M _p ′ and M _q to the equation (9) is also incorrect, it is _defined as M ′.

At this time, using the data C to be signed and the value of the published modulus n, secretly by gcd ((M ′) ^e −C, n) (gcd: greatest common divisor) (10) The prime factor q of n to be kept is found (Marc Joye and Jean-Jacques Quisquater; "Attacks
on system using Chinese remaindering "November 1
1,1996 This paper is http://www.dice.ucl.ac.be/crypto/
techreports.html). because,
M is correct that when ^{M e ≡C (mod n) ......} (11) is satisfied, but not satisfied because there is an error in M _p '. And 'So ^{_{≡C p x (mod p) (}} x = d p), (M' M p ^{a) e ≡C (mod q) ......} (12). That is, the greatest common divisor of (M ') ^e- C and n (= pq) is q. Thus, if q is known, p is also known, and as a result, all secret information is known.

[0013]

As described above, since secret information is analyzed by a failure attack, it is necessary to confirm whether or not the digital signature M calculated using the Chinese remainder theorem is correct. To confirm, it was necessary to verify the created digital signature by the signature creator himself. That is, using the public key e of the signature creator, Me ^e C (mod
It was necessary to verify n).

By the way, in the case of an IC card equipped with a coprocessor for performing the modular exponentiation calculation at high speed, the size of the integer to be subjected to the modular exponentiation calculation by the coprocessor is limited in hardware. As described above, the prime factors p and q of the modulus n of the modular exponentiation are used in the creation of a digital signature for high-speed processing. Therefore, when the sizes of p and q are taken to the limit that can be handled by the coprocessor, p, The product n of q exceeds the limit that can be handled by the coprocessor.
Verification of the signature is performed by using only e and n to calculate Me ^e C (modn) by a coprocessor, but this operation cannot be performed. On the other hand, verification by software processing using CPU instructions requires much more time than signature processing itself. Can't do it. For this reason, if the size of n exceeds the limit that can be handled by the coprocessor, it is common to not verify the created signature, resulting in a failure use attack.

The present invention has been made to solve the above-mentioned problem. When a message creator himself / herself creates a digital signature using an RSA private key, the message creator performs a high-speed signature creation process using the Chinese remainder theorem. The purpose is to increase the security against failure-based attacks that attempt to obtain confidential information by causing an IC card to make a calculation error in the middle result of the Chinese Remainder Theorem and create an erroneous digital signature. Things.

[0016]

According to the present invention, a co-processor is mounted, and a modular exponentiation calculation for generating a digital signature is performed at high speed by a Chinese remainder theorem using a prime factor of a public key n of an RSA public key cryptosystem. In the IC card, the error detection code for the data is simultaneously calculated and stored together with the data generated in the calculation process according to the Chinese remainder theorem. Calculate the error detection code again,
It is characterized in that it is collated with the stored error detection code. The present invention also provides a digital signature created and output as a response on the condition that no error is detected in the verification of the error detection code, and an error status on the condition that the error is detected in the verification of the error detection code. The method is characterized in that a word is output and the processing is terminated.

[0017]

Embodiments of the present invention will be described below. FIGS. 1 and 2 are diagrams for explaining an IC card in which a countermeasure against a failure use attack according to the present invention is taken, and FIGS. 3 and 4 are diagrams for explaining a digital signature creation processing flow of the present invention. The present invention is the same as the conventional one in that the digital signature of the expression (1) is performed by the processing shown in the expressions (2) to (9) using the IC card described in FIGS. Therefore, the following description will be made with reference to these equations, and the description of the already-defined variables and the like will be omitted as appropriate. As described above, in the failure use attack, (2) to
An external physical stimulus (heat, pressure, radiation,
By applying a voltage or the like, an error is intentionally generated in a part of the bit pattern on the memory or the register of the IC card.

Therefore, C _p = C mod p, C _q in equations (5) and (6) in steps 1 and 2 during the creation of a digital signature using the Chinese Remainder Theorem.
_{= Cmodq, M p = C p} x mod p (x = d p), M q =
After calculating each of C _q ^y mod q (y = d _q ), an error detection code is calculated for each, and stored in a memory or a register at the same time as C _p , C _q , M _p , and M _q. .

C _p , C _q , M _p , M
when calculating a digital signature used in the equation (9) using _q, again C _p, C _q, calculates an error detecting code of M _p, M _q, and the error detection code has been stored previously Collate. After checking that no bit error has occurred in C _p , C _q , M _p , and M _q , C _p , C _q ,
_Mp and _Mq are used. As a result of the comparison, C _p , C _q ,
If a bit error has occurred in M _p and M _q , an error status word is returned to the reader / writer, and the process is terminated. In this way, an erroneous digital signature will not be returned as a response even if a failure use attack is received.

FIG. 1 shows a CRC (Cycl) as an error detection code.
ic Redundancy Check) code. FIG. 1 shows C _p calculated by equations (5) and (6),
This shows a state in which C _q , M _p , and M _q are stored in a memory or a register as a bit pattern. At the same time, these CRC codes are generated and written. When writing data to an IC card, an error check code is usually added.
A CRC code based on the TT standard is used. C
The RC code is generated by performing a logical operation of a predetermined algorithm based on data to be written, and is written together with the data. For example, a CRC code based on the ISO-CCITT standard specifies that data to be written has a predetermined value, for example, "100010000000100" in binary.
001 ”is defined as the remainder when divided by the 17-bit number.

Each of the generated C _p , C _q , M _p , M
CRC code X for _{q (C p), X (} C q), X
(M _p ) and X (M _q ) are stored simultaneously. And
At the stage of creating a digital signature, the CRC code X
( _Cp ) ', X ( _Cq )', X ( _Mp ) ', X
(M _q ) ′ is calculated and compared with the previously stored CRC codes X (C _p ), X (C _q ), X (M _p ), and X (M _q ). After checking that no bit error has occurred in C _p , C _q , M _p , M _q , C _p , C _p
Create a digital signature M using _q , M _p , M _q . If a bit error has occurred in C _p , C _q , M _p , and M _q , an error status word is returned, and the processing is terminated.

FIG. 2 shows an example in which a parity code is used as an error detection code. FIG. 2 shows a state in which C _p , C _q , M _p , and M _q calculated by the equations (5) and (6) are stored in a memory or a register as a bit pattern, and at the same time, C _p , C _q , M _An exclusive OR is calculated for each byte of _p and _Mq for each bit, and the horizontal parity P
( _Cp ), P ( _Cq ), P ( _Mp ), and P ( _Mq ) are calculated and stored at the same time. Then, at the stage of creating the digital signature, the horizontal parity P (C _p ) ′, P (C
_q ) ', P (M _p )', P (M _q ) 'and calculate the previously stored horizontal parities P (C _p ), P (C _q ), P (C _q )
(M _p ) and P (M _q ). As a result of the comparison, C _p ,
C _q, M _p, confirm that the bit error has not occurred in the M _q, to create a digital signature M using _{C p, C q, M p} , M q. If a bit error has occurred in C _p , C _q , M _p , and M _q , an error status word is returned, and the processing is terminated.

Next, the flow of the digital signature creation processing according to the present invention will be described with reference to FIGS. When the IC card receives the digital signature command, the IC card uses d _p , d _q , a
As well as the message sent with the command (steps 11 to 12). Then
(5) with determining the C _p by calculating the Cmod p using equation calculates and stores the C _p of CRC code X (C _p) (step 13). Similarly, with determining the C _q by calculating the Cmod q, calculates and stores the CRC code X (C _q) of C _q (step 14). Further, (6) with computing the M _p, M _q in formula, M _p, M _q of CRC code X (M _p), and stores each calculate the X (M _q) (step 15, 16). Next, at the stage of creating a digital signature, CRC codes of C _p , C _q , M _p , and M _q are calculated again, and the stored CRC code X
_{(C p), X (C} q), X (M p), X (M q) and matching each (step 17-20).

In this comparison, as shown in FIG. 4, the stored CRC code X (Y) is compared with the calculated CRC code T of Y, and if both match, the process ends normally. If it ends abnormally. Regardless of the abnormal termination at any of steps 17 to 20 in FIG. 3, an error status word is returned to the reader / writer at that point, and the processing is terminated. If all of steps 17 to 20 are completed normally, a digital signature is created and returned as a response (steps 21 and 22).

[0025]

As described above, according to the present invention, even when the size of n exceeds the limit that can be handled by the coprocessor, the created signature can be verified in a short time, so that a failure use attack can be prevented. Even if received, the possibility of returning an incorrect digital signature as a response can be reduced. Although there is no possibility that an error occurs in the error detection code itself or an error in a range exceeding the error detection capability of the error detection code due to a failure use attack,
In most cases, it is possible to detect that a failure use attack has been received.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating an example in which a CRC code is used as an error detection code.

FIG. 2 is a diagram illustrating an example in which a parity check is used as an error detection code.

FIG. 3 is a diagram illustrating a digital signature creation processing flow according to the present invention.

FIG. 4 is a diagram illustrating a CRC matching process.

FIG. 5 is a diagram illustrating communication between a reader / writer and an IC card.

FIG. 6 is an explanatory diagram of an IC card.

FIG. 7 is an explanatory diagram of a conventional digital signature creation processing flow.

[Explanation of symbols]

1 ... reader / writer, 2 ... IC card, 2a ... CPU,
2b: Coprocessor, 2c: ROM, 2d: EEPRO
M.

──────────────────────────────────────────────────の Continued on the front page (51) Int.Cl. ⁶ Identification code FI H04L 9/32 H04L 9/00 673E

Claims (2)

[Claims] 1. An IC card equipped with a coprocessor and processing a modular exponentiation calculation for generating a digital signature of an RSA public key cryptosystem at high speed by a Chinese remainder theorem using a prime factor of a public key n. At the same time, along with the data generated in the calculation process by the Chinese remainder theorem, an error detection code for the data is calculated and stored at the same time, and when the digital signature is created,
An IC card for failure use attack, wherein the error detection code of the data is calculated again and collated with the stored error detection code. 2. The IC card according to claim 1, wherein a digital signature is created and output as a response on condition that no error is detected by the error detection code collation, and the error is detected by the error detection code collation. An IC card which outputs an error status word on condition that the processing is terminated.