Ic card

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to an IC card that encrypts or decrypts data in accordance with an external command.

【0002】

[Conventional technology]

IC cards have been attracting attention in recent years as a new information storage medium to replace magnetic cards. In particular, an IC card with a built-in CPU not only functions as an information storage medium, but also has an information processing function and can realize high security, so it is expected to be used in various fields of the highly information-oriented society. ing. Generally, an IC card has a built-in non-volatile memory such as EEPROM, and information is stored as a file in this EEPROM. Access to the EEPROM is performed by giving a command to the IC card from the outside and interpreting and executing the command by the built-in CPU. Predetermined access conditions are set for each file in advance, and the CPU accesses the file only when the command argument satisfies the access conditions. As a result, the IC card prevents an unauthorized third party from tampering with or stealing the EEPROM data.

【0003】

Further, in the IC card system, when data is transmitted / received between the IC card and the reader / writer, the data is encrypted. This is to prevent the contents from being stolen even if a third party illegally acquires the communication signal between the reader / writer and the IC card. FIG. 8 is a diagram showing the transmission of information from an external device such as a reader / writer to an IC card. The external device acquires the ciphertext X by applying a predetermined encryption process to the plaintext A, and transmits it to the IC card. The IC card decrypts the ciphertext X by performing a decryption process corresponding to the encryption process used by the external device. When the decryption process is completed, the IC card edits the response information indicating that the process is completed and sends it to the external device. In addition, the external device receives the response information and ends a series of processes.

【0004】

Plaintext encryption is usually performed by calculating a mathematical formula with the plaintext and predetermined key information as variables. Typical examples of such encryption methods currently proposed include, for example, RLRivest, A. Shamir, and LMAdleman. "A method for obtaining digital signatures and public-key cryptosystems" (Communications of the ACM, Vol. 21, No.2: pp.120-126, Feb., 1978) There is an RSA cryptosystem discussed. RSA encryption is a so-called asymmetric key encryption method in which the key information used when encrypting plaintext and the key information used when decrypting ciphertext are different. Of the two types of asymmetric key information, one is used as a private key that is secretly stored in the EEPROM of an IC card to a third party, and the other is used as a public key that is widely disclosed to a third party.

【0005】

The RSA encryption decryption process is performed using the formula "A = X".^Y(mod N) is executed. Here, A is plaintext, X is ciphertext, Y is private key, and N is public key. As is clear from the above equation, in RSA cryptography, the decryption process is performed by calculating the power remainder. Therefore, the amount of calculation is usually very large. For this reason, when executing RSA cryptography, a calculation algorithm for reducing the calculation of the power remainder is usually used. As a calculation algorithm for reducing the amount of calculation of the power remainder, for example, "the binary calculation method of the power" is known (DEKnuth. The Art of Computer Progaramming, volume 2, Seminumerical Algorithms. Addison-Wesley, 2nd edition, 1981. ,reference).

【0006】

A calculation algorithm called the Montgomery method, which applies this "binary calculation method of power" and enables the remainder calculation to be performed with a small amount of calculation, is used for the calculation of the RSA cipher (PL Montgomery. ModularMultiplication without). Trial Division , Mathematics of Computation, Vol.44, No.170, pp.519-521, Apr., 1985). In the Montgomery method, the power remainder calculation "A = X" is performed by the algorithm shown in Fig. 9.^Y(mod N) "is executed.

【0007】

First, four values N, X, Y and R are entered (S902). Here, X satisfies the relationship of 0 <X <N with respect to N. In addition, the private key Y is displayed in binary notation as Y = e._je_j-1 E₂e₁It shall be expressed as. However, e_iMeans the numerical value of the i-th bit. R is R = 2 using the number of bits j in Y^jIt is a numerical value defined as. Next, from the entered number, Montgomery remainder A^*, B^*Is required (S904). The Montgomery remainder is "a" so that it has a one-to-one correspondence with the remainder "a (modn)" modulo n.^*A value defined as "= ar (mod n)". However, n is an integer of k-bits, 2^k-1n <2^k, R = 2^k, Gcd (r, n) = 1.

【0008】

Next, the Montgomery product is calculated for each bit of the exponent Y (S906 ~ S912). That is, when the exponent Y is composed of j bits, the calculation of the Montgomery product of S910 is repeated j times. The Montgomery product is "MonPro (a)^*, B^*) = a^*b b^*r^-1(mod n) "is the product defined. FIG. 10 is a flow chart showing the processing contents of the Montgomery product. The Montgomery product contains two arithmetic operations, S1002 and S1006. The arithmetic processing of S1002 is always performed for each bit of the exponent Y regardless of whether it is 1 or 0. On the other hand, the arithmetic processing of S1006 is executed only for one of the bits constituting the exponent Y. When the iterative calculation of the Montgomery product (S906 to S912) in Fig. 9 finishes for all the bits that make up the exponent Y, then A^*The Montgomery product for and 1 is performed (S914). As a result, the plaintext A obtained by decrypting the ciphertext X is acquired, and a series of decryption processes are completed.

【0009】

[Problems to be Solved by the Invention]

As explained above, in the conventional IC card decoding process, 1 is set and 1 is not set for each bit digit of the index Y displayed in binary. The content is different. That is, in the processing in FIG. 10, if the corresponding bit is 1, only two steps of S1002 and S1006 are calculated, and if the corresponding bit is 0, only one step of S1002 is calculated. Therefore, the time required for the decoding process depends on the number of bits of 1 in the exponent of the power, and increases as the number of bits of 1 increases.

【0010】

For this reason, the third party obtains the time required for the decryption process by the IC card from the time from when the command for ordering the decryption of the ciphertext is sent to the IC card until the response is returned. It was possible to estimate the ratio of 1 bit and 0 bit in the exponent (secret key) Y of the power remainder calculation from the obtained time. That is, the conventional IC card has a problem that the content of the private key Y is decrypted from the time when the response is transmitted, and the security of the IC card may be impaired.

【0011】

Therefore, an object of the present invention is to provide an IC card in which the content of the key information used in the encryption process or the decryption process is not inferred from the time when the response information to the command from the outside is transmitted.

【0012】

[Means for solving problems]

In order to solve the above problem, the invention according to claim 1 includes a CPU and a memory accessible to the CPU, and performs data encryption processing using key information stored in the memory according to an external instruction. Alternatively, the IC card that performs the decryption process and transmits the response information related to the result to the outside has a delay means for delaying the transmission of the response information, and the encryption process or the decryption process is being executed or executed. By executing the delay means before and after, the correlation between the content of the key information and the time when the response information is transmitted is lost.

【0013】

The invention according to claim 2 is the IC card according to claim 1, wherein the delay means is an arithmetic process substantially unrelated to the encryption process or the decryption process, which is executed by the CPU for a random period of time. It is characterized by being. The "substantially irrelevant process" means a process capable of normally executing an encryption process or a decryption process without performing the process. In addition, "execution at random time" means to execute a process that requires a certain amount of time a random number of times, or to execute a process whose execution time is randomly determined each time, once or twice or more. It means to execute.

【0014】

The invention according to claim 3 has the timekeeping means for notifying the passage of a predetermined time in the IC card according to claim 1, and the delay means is the encryption until the CPU receives the notification from the timekeeping means. It is characterized in that the start or continuation of the conversion process or the decoding process is interrupted. The invention according to claim 4 is the IC card according to any one of claims 1 to 3, wherein the delay means performs the encryption process or decryption regardless of the bit configuration of the key information. It is characterized in that the time required for processing is constant.

【0015】

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, embodiments according to the present invention will be described in more detail with reference to the drawings and the like. (First Embodiment) The first embodiment according to the present invention is an IC card capable of encrypting plaintext or decrypting ciphertext using RSA, which is an encryption method of an asymmetric key method. is there. In the present embodiment, the encryption processing or decryption processing by RSA is performed according to the calculation algorithm by the Montgomery method shown in FIG. FIG. 1 is a diagram showing a configuration of an IC card according to the present embodiment. As shown in FIG. 1, the IC card 10 includes ROM12 which is a read-only memory, RAM14 which is a volatile memory, EEPROM16 which is a non-volatile memory which can be rewritten at any time, CPU18 which accesses these memories, and a timer module 20. It has. The timer module is a time measuring device that operates independently of the operation of the CPU 18 and notifies the CPU 18 by interrupting when the instructed time elapses.

【0016】

In addition, the IC card 10 is provided with an I / O line for exchanging electric signals and the like with a reader / writer (not shown). When the IC card is inserted into the reader / writer, the contacts of the reader / writer are connected to this I / O line, and electrical signals are sent and received. The CPU18 is given a command via the above I / O line. A command is information sent from a reader / writer to an IC card to cause the IC card to perform a predetermined operation. When a command is given, the CPU 18 processes the command by executing the program stored in the ROM 12 or the EEPROM 16.

【0017】

FIG. 2 is a diagram showing the format of the RSA_CALC command, which is one of the commands used in this embodiment. The RSA_CALC command is a command that causes the IC card 10 to decrypt the ciphertext and return the plaintext obtained as a result as a response. The first 5 bytes of the RSA_CALC command are CLA, which indicates the class of the command, INS, which indicates the type, parameters P1 and P2 of the command, and LC, which indicates the length (number of bytes) of the subsequent DATA. The DATA after the 6th byte is the ciphertext X to be decrypted. The 1-byte data LE following DATA is the expected value of the response. In the present embodiment, the LE value is set so that all the encrypted or decrypted data is returned as a response up to a maximum of 256 bytes.

【0018】

FIG. 3 is a flow chart showing the operation of the IC card 10 when the RSA_CALC command is executed. When the RSA_CALC command is received, the ciphertext X is first obtained from the DATA of RSA_CALC, and the public key N, the private key Y, and the constant R stored at the predetermined address of the EEPROM are read (S302). Next, from the above numerical values obtained, Montgomery remainder A^*And B^*Is calculated (S304). Furthermore, the counter i is set to the number of digits (bits) j of the private key Y displayed in binary (S306). Next, it is determined whether the counter i is greater than 0 (S308).

【0019】

As a result of the judgment of S308, if the counter i is greater than 0, it means that some of the bits constituting the private key Y have not yet been calculated for the Montgomery product. In this case, CPU 18 performs the calculation of the Montgomery product for the bit of the digit indicated by the counter i at that time (S310). In S310, the same processing as described in S910 of FIG. 9 is performed. Further, the CPU 18 starts the processing of S310 and at the same time calls the timer module 20 at a predetermined time (S312). Here, the predetermined time means a time equal to or longer than the time required to execute the Montgomery product of S310 for the bit in which 1 is set. As a result, the timer module 20 counts the predetermined time in parallel with the CPU 18 executing the processing of the S310.

【0020】

After finishing the processing in S310, CPU18 waits until there is an interrupt from timer module 20 (S314). When there is an interrupt, CPU18 decrements counter i by 1 (S316), and then repeats the processing from S308 to S316. On the other hand, in S308, when the counter i does not satisfy the condition "i> 0", it means that the Montgomery product has been calculated for all the bits constituting the private key Y. In this case, CPU18 is A, which is shown in S318 next.^*Perform a calculation of the Montgomery product for and 1 and get the plaintext A. Furthermore, CPU18 edits the response information indicating that the RSA_CALC command was processed normally, and sends this to the reader / writer (S320).

【0021】

As described above, in the IC card of the present embodiment, when executing the Montgomery product of S310 in order to perform the decryption processing of the ciphertext, a certain time is measured by calling the timer module at the same time, and the time is measured. Until a certain period of time elapses, even if the calculation of the Montgomery product is completed, the next process is not executed. As a result, in the present embodiment, the calculation time of the decryption process is always constant regardless of the bit configuration of the private key Y, and the time from when the IC card 10 receives the RSA_CALC command to when the response is returned is also It is constant regardless of the contents of the private key. Therefore, in the present embodiment, the bit configuration of the private key is not estimated from the time when the response is transmitted, and it is possible to provide an IC card with extremely high security.

【0022】

(Second Embodiment) Next, the second embodiment according to the present invention will be described. In the following description, parts that perform the same functions as those in the first embodiment are designated by the same reference numerals, and duplicate description will be omitted as appropriate. FIG. 4 is a diagram showing the configuration of the IC card 30 of the present embodiment. The IC card 30 is different from the IC card 10 of the first embodiment in that it does not have the timer module 20 but has the coprocessor 32, and causes the coprocessor 32 to perform the calculation of the Montgomery product. Further, the IC card 30 decrypts the ciphertext X by transmitting the RSA_CALC command from the reader / writer like the IC card 10, and sends a response to that effect to the reader / writer when the command processing is completed. The decryption process is performed based on the RSA cipher as in the first embodiment, and the calculation of the RSA cipher is executed according to the algorithm of the Montgomery method.

【0023】

FIG. 5 is a flow chart showing the operation of the IC card 30 when the RSA_CALC command is executed. In FIG. 5, S502 to S508 are the same as the contents of S302 to S308 in FIG. 3, and there is no difference in operation between the IC card 30 and the IC card 10. When the counter i satisfies the condition of "i> 0" in S508, CPU18 is A to coprocessor 32.^*, B^*, N and R values and the value of the corresponding bit of the private key Y are passed. A^*The coprocessor 32, which has been passed a value such as, performs the calculation of the Montgomery product shown in FIG. In this embodiment, the decoding process can be performed at a higher speed by causing the coprocessor to execute the calculation of the Montgomery product in this way.

【0024】

On the other hand, while the coprocessor 32 calculates the Montgomery product, the CPU 18 performs a loop calculation with contents unrelated to the decoding process a predetermined number of times (S512). Here, the predetermined number of times means a sufficient number of times that the time required for the CPU 18 to process the S512 is equal to or longer than the maximum time required for the coprocessor 32 to process the S510. When the loop calculation of S512 is completed, CPU18 decrements counter i by 1, and then repeats the processing from S508 to S514. The repetition of the processing from S508 to S514 is continued until the condition of "i> 0" is not satisfied in S508, that is, the processing of S510 is performed for all the bits constituting the private key Y. On the other hand, when the condition "i> 0" is no longer satisfied in S508, the same processing as in S318 and S320 in FIG. 3 is executed (S516, S518), and a series of decoding processing is completed.

【0025】

(Third Embodiment) Next, the third embodiment according to the present invention will be described. FIG. 6 is a diagram showing the configuration of the IC card 40 of the present embodiment. The IC card 40 is different from the IC card 10 of the first embodiment and the IC card 30 of the second embodiment in that it has neither a timer module 20 nor a coprocessor 32.

【0026】

FIG. 7 is a flow chart showing the operation of the IC card 40 when the RSA_CALC command is executed. The operation of the IC card 40 when executing the RSA_CALC command is the same as the operation of the IC card 10 shown in FIG. 3 from S702 to S708 from S302 to S708. When the counter i satisfies the condition "i> 0" in S708, the CPU 18 executes the calculation of the Montgomery product shown in FIG. 10 (S710). When the calculation of the Montgomery product is completed, the CPU 18 generates a random number (S712) and executes a predetermined loop calculation as many times as the number of times corresponding to the acquired random number (S714). The predetermined loop calculation is a calculation of contents irrelevant to the decoding process, similar to the loop calculation in S512 of FIG.

【0027】

When the loop calculation of S714 is completed, the CPU 18 decrements the counter i by 1, and then continues the processing from S708 to S716 until the calculation of the Montgomery product is performed for all the bits constituting the private key Y. Furthermore, when all the processes from S708 to S714 are completed, the same processes as S318 and S320 in FIG. 3 are executed (S718 and S720), and a series of decoding processes are completed.

【0028】

As described above, in the present embodiment, the loop calculation is executed after the calculation of the Montgomery product in S710. Therefore, at the end of the decoding process and at the time of transmitting the response in S720, there is a delay by the time when the loop calculation is performed. Moreover, since the number of times the loop calculation is executed is randomly determined by a random number, the length of the delay time is uncertain. Therefore, in the present embodiment, there is no correlation between the time when the response is transmitted and the calculation time of the Montogomery product performed in S710, and the private key is observed by observing the time when the response is transmitted by a third party. It is impossible to predict the bit configuration of Y.

【0029】

(Other Embodiments) The present invention is not limited to the above embodiments. The above embodiment is an example, and any one having substantially the same configuration as the technical idea described in the claims of the present invention and exhibiting the same effect and effect is the present invention. It is included in the technical scope of the invention.

【0030】

For example, in the above embodiment, a case where a ciphertext is given to the IC card from the outside and the plaintext is decrypted has been described as an example. However, this gives a plaintext to the IC card from the outside and encrypts the plaintext. It may be that. Further, in the above embodiment, the IC card using the RSA encryption has been described, but this does not mean that the technical scope of the present invention is limited at all. The technical idea of the present embodiment is broadly applicable to an IC card that performs encryption or decryption processing using key information, and the time required for the encryption or decryption processing depends on the bit configuration of the key information. Applicable. Further, in the above embodiment, a process for delaying the end of the decoding process and the transmission of the response signal during or after the execution of the decoding process is performed. However, this type of delay process is a decoding process. It may be executed before the execution of.

【0031】

[Effect of the invention]

As described in detail above, according to the present invention, when the response information is transmitted, there is no correlation with the content of the key information, so that the content of the key information can be inferred by a third party and the security of the IC card can be improved. There is no danger of being harmed.

[Simple explanation of drawings]

[Figure 1]

It is a figure which shows the structure of the IC card 10 which is 1st Embodiment of this invention.

[Figure 2]

It is a figure which shows the format of the RSA_CALC command.

[Fig. 3]

It is a flow chart which shows the operation of IC card 10 when the RSA_CALC command is executed.

[Fig. 4]

It is a figure which shows the structure of the IC card 30 which is 2nd Embodiment of this invention.

[Fig. 5]

It is a flow chart which shows the operation of the IC card 30 when the RSA_CALC command is executed.

[Fig. 6]

It is a figure which shows the structure of the IC card 40 which is the 3rd Embodiment of this invention.

[Fig. 7]

It is a flow chart which shows the operation of the IC card 40 when the RSA_CALC command is executed.

[Fig. 8]

It is explanatory drawing which shows the state at the time of transmitting information from an external device such as a reader / writer to an IC card.

[Fig. 9]

It is a figure which shows the algorithm of the calculation of the power remainder by the Montgomery method.

[Fig. 10]

It is a flow chart which shows the processing content of a Montgomery product.

[Explanation of symbols]

10 IC card 12 ROM 14 RAM 16 EEPROM 18 CPU 20 timer module 32 coprocessor