KR100431286B1 - Method for preventing the CRT-based fault attack and apparatus thereof - Google Patents

Abstract

The present invention discloses a method and apparatus for responding to a Chinese remainder theorem (CRT) based error attack.

The present invention is a minority About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption or digital signature generation of RSA public key password Operation method If an error occurs in the operation stage associated with one prime factor in, the error By using the widely used CRT (Chinese Restoration Theorem) to improve efficiency, it can spread to errors in the computational stages associated with other prime factors. It is effective to withstand CRT error attacks that can occur in the calculation of. Since the calculation method according to the present invention does not change the structure of the modular calculation engine, which is the core used in the existing RSA system, it is fully compatible with the existing system. There is no comparison operation that determines safety, which increases confidence in safety, and if there is an error for one argument, the error is propagated to the other arguments. You can safely defend against CRT errors by disabling the factorization of.

Description

Method for preventing the CRT-based fault attack and apparatus thereof

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to the field of security, and more particularly, to a method and an apparatus corresponding to a CRT-based error attack, and in particular to a CRT-based error attack on an RSA cryptosystem.

To date, cryptographers have developed secure cryptographic algorithms only for mathematical cryptographic attacks. Recently, in the encryption / decryption model of data, a physical method of attack is possible with side-channel information such as power consumption, execution time, malfunction, and electromagnetic radiation.

A cryptographic attack is possible using information on the public channel and information leaked to the side channel. Such an attack is called a side channel attack or a side channel attack. This is the first parallax attack proposed by Paul Kocher in 1996 as a side channel attack, and this attack method is to find out the secret key by analyzing the execution time information of the cryptographic operation on the side channel.

In addition to parallax attacks, error attacks that inject errors into cryptographic operations and attack them, and power analysis attacks that attack information consumption on power dissipated through hardware during the time of cryptographic operations are proposed. Until these side channel attacks were proposed, cryptographic algorithms and protocols were recognized to be safe only on the mathematical basis. However, in practice, since side channel attacks presented successful attack methods and experimental results, it is no longer possible to implement cryptographic algorithms and protocols. You must consider whether you are safe from side channel attacks.

The present invention deals with error attacks on the Chinese Remainder Theorem (CRT) based RSA cryptosystem. In particular, the countermeasure according to the present invention, which analyzes the countermeasure recently proposed by Shamir and improves it, will be described in detail.

In RSA public key (signature verification key) cryptography, a secret key operation (in case of RSA encryption, a secret key operation is involved in decryption, and in RSA digital signature technique, a secret key operation is required for signature generation). In order to reduce the amount of computation required, there are many methods to apply CRT to secret key operation.

Hereinafter, an error attack method known as a side channel attack for an RSA public key cryptosystem, which is a representative public key cryptosystem, will be described.

Fault cryptanalysis

In 1996, Bellcore's D. Boneh et al. Reported in the paper "New threat model breaks crypto codes: a new 'Potential serious problem' was reported," hardware fault cryptanalysis, a new attack on RSA public key cryptography. For the first time, a fault analysis or fault attack was introduced. The error attack method is classified into an active side channel attack method, unlike a parallax attack method and a power attack method that take only information such as execution time and power consumption of a cryptographic algorithm without active manipulation of an attack target. This is because it presupposes a situation in which an attacker can intentionally inject an error into the cryptographic device that is being attacked.

Hereinafter, the error attack methods for the RSA public key cryptosystem are classified into two cases according to the presence or absence of the CRT method.

-How to attack errors on RSA cryptosystems

Error attacks against RSA cryptosystems that do not use CRT were first proposed by Boneh, DeMillo, and Lipton. This error attack method is called a register error attack.

Bao et al. And Joye et al., Respectively, proposed transient attacks using RSA cryptosystems. In addition, Yen et al. Proposed an error attack using safe-error.

Hereinafter, an error attack method for the CRT-based RSA cryptosystem will be described.

-Method of Generating RSA Signature Using CRT

decimal About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption or digital signature generation of RSA public key password Briefly explaining the method using the CRT as follows. For convenience Is called the signature for message m. CRT based How to calculate the following steps.

The signer uses p and q to generate the following equation:

, here

, here

, here ego .

here Can be calculated in advance.

In the above case, the improvement of the calculation speed when the CRT is used is as follows.

if If this is an integer with a size of k bits, Is implemented using the square-and-multiply algorithm, the total execution time is Proportional to On the other hand, if you use the CRT and implement the modular power with the square-and-multiply algorithm, each modulus The execution time of the power against Is proportional to the total signature generation and requires two modular powers. Proportional to Therefore, signature generation of RSA using CRT is theoretically performed four times faster than signature generation of RSA without CRT.

-Error attack on CRT based RSA cryptosystem

Boneh et al. In the signature generation process of Equation 1 If either is not the correct value, an attacker with two signatures (one exact signature and one wrong signature) for the same message It is proposed that the attack to decompose In this case, the error attack of the CRT-based RSA cryptosystem requires two signatures, one for the plain text message and one for the plain text message.

Later, Lenstra et al. Proposed a method in which an attacker who had only one error signature could launch an error attack. In this way, this shows that even an attacker with a single error signature can do so. This is a more realistic and powerful attack because it has fewer constraints than the first error attack proposed by Boneh et al.

The error attack on CRT-based RSA public key cryptosystem proposed by Boneh et al. And Lenstra et al. Is not limited to the cause of error. In other words, The error in the calculation of the error may be due to one hardware error, one due to multiple causes, or one due to a bug in the software. Since it is assumed that only error is generated, the error attack on CRT-based RSA public key cryptography is classified as the most powerful and common attack among various error attacks.

Conventional methods for defending against such an attack method require a large amount of computation, and there is no way to verify whether an error is generated in the case of a system having a permanent defect.

In addition, in the case of avoiding errors, the method of dealing with errors is likely to increase the probability that there is an undetectable error. In addition, the conventional methods are vulnerable to a hardware error attack, and there is a problem that it is difficult to flexibly expand in an implementation to cope.

The prior art also requires the use of one or more comparison operations (or similar operations). However, there may be an error in the comparison operation itself, and the result of the error may be passed to the attacker, and there is a possibility that the signature required for authentication is leaked.

Reference documents for techniques related to the present invention are as follows. The details of the techniques described in the following references are not described separately.

F. Bao, R. H. Deng, Y. Han, A. Jeng, A.D. Narasimbalu, and T. Ngair, "Breaking public key cryptosystems on tamper resistant devices in the presence of transient faults," In Pre-proceedings of the 1997 Security Protocols Workshop, Paris, France, 1997.

Bellcore Press Release, "New threat model breaks crypto codes," Sept. 1996 or D. Boneh, R. A. DeMillo, and R.J. Lipton, "On the importance of checking cryptographic protocols for faults," In Advances in Cryptology-EUROCRYPT '97, LNCS 1233, PP. 37-51, Springer-Verlag, 1997.

-E. Biham and A. Shamir, "Differential Fault Analysis of Secret Key Cryptosystems," in Proceedings of Advances in Cryptology-CRYPTO '97, pp. 513-525, Springer-Verlag, 1997.

-M. Joye, J.-J. Quisquater, F. Bao, and R.H. Deng, "RSA-type signatures in the presence of transient faults," In Cryptography and Coding, LNCS 1355, pp. 109-121, Springer-Verlag, Berlin, 1997.

-J. Keley, B. Schneier, D. Wagner, and C. Hall, "Side Channel Cryptanalysis of Product Cipher," in Proceedings of ESORICS '98, pp. 97-110, Springer- Verlag, Septemper 1998.

P. Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems," in Proceedings of Advances in Cryptology-CRYPTO '96, pp. 104-113, Springer-Verlag, 1996.

-P. Kocher, J. Jaffe, and B. Jun, "Introduction to Differential Power Analysis and Related Attacks," http://www.cryptography.com/dpa/technical, 1998.

-W. Schindler. "A Timing Attack against RSA with the Chinese Remainder Theorem," in Cryptographic Hardware and Embedded Systems-CHES2000, vol. 1965 of LNCS, pages 109-124. Springer-Verlag, August 2000.

A. Shamir, "How to check modular exponentiation," presented at the rump session of EUROCRYPT '97, Konstanz, Germany, 11-15th May 1997.

A. Shamir, "Method and apparatus for protecting public key schemes from timing and fault attacks," United States Patent 5991415, Novemeber 23, 1999.

-S.M. Yen and M. Joye, "Checking before output may not be enough against faults-based cryptanalysis," IEEE Trans. on Computers, vol. 49, no. 9, pp. 967-970, Sept. 2000.

Technical problem to be solved by the present invention, in order to solve the above problems, do not perform a calculation, such as a comparison operation, if an error occurs in the operation associated with one argument affects the operation associated with the other argument Error in It is to provide a method and device for safely responding to CRT errors in CRT-based cryptographic systems because it prevents the prime factor of.

1 illustrates a flow of a method corresponding to a sequential CRT based error attack on an RSA cryptosystem according to the present invention.

Figure 2 illustrates the flow of a method for responding to a parallel CRT based error attack on the RSA cryptosystem in accordance with the present invention.

Minority by this invention for solving the said technical problem About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation To counter this sequentially computed error attack against the Chinese Remnant Theorem (CRT) -based cipher system,

(a) intermediate parameters , (here silver Small integer to satisfy), , And for a given message m, Calculating each;

(b) , ,

Sequentially calculating; And

(c) using the Chinese remainder theorem Wow

After calculating each of

The signature value s Comprising the step of calculating the signature value characterized in that it comprises.

Minority by this invention for solving the said technical problem About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation This parallel countermeasure is a way to counter error attacks against the CRT-based RSC system.

(a) intermediate parameters, (here silver Small integer to satisfy), , And for a given message m, Calculating each;

(b) , Calculating each; And

(c) using the Chinese remainder theorem Wow

After calculating, the signature value To Comprising the step of calculating the signature value characterized in that it comprises.

Minority by this invention for solving the said another technical problem About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation The devices that respond to this sequentially computed error attack against the Chinese Remnant Theorem (CRT) -based encryption system,

Intermediate parameter , (here silver Small integer to satisfy), , And for a given message m, Means for calculating each;

, ,

Means for sequentially calculating; And

Chinese rest using theorem Wow After calculating each of

The signature value s It characterized in that it comprises a means for calculating the signature value by calculating.

Minority by this invention for solving the said another technical problem About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation In a device that responds to an error attack on the Chinese Remnant Theorem (CRT) -based Cryptographic System computed in parallel,

Intermediate parameters, Where r is Small integer to satisfy), , And for a given message m, Means for calculating each;

Means for calculating each; And

Chinese rest using theorem Wow

After calculating, the signature value To It characterized in that it comprises a means for calculating the signature value by calculating.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

The conventional countermeasures for the error attack method for the CRT-based RSA cryptosystem will be described. In particular, Shamir's error attack countermeasure of US Patent # 5991415 will be briefly described, and the error attack countermeasure according to the present invention will be described.

First, the existing CRT-based RSA error attack countermeasures are briefly described.

Among the known error attack countermeasures, the countermeasures against the error attack on the CRT-based RSA cryptosystem are roughly classified as follows.

1. CRT Error Attack and Since the error is generated only for one of the two methods, the simplest attack prevention method uses two values for signature generation. and It is a way to check if it is right. These methods and These two methods are used to check whether an error has occurred through a double operation or a verification function, which is very inefficient because the encryption operation itself requires a large amount of computation. Also, for systems with permanent defects, there is no way to verify that an error has been generated, so these countermeasures are not appropriate.

2. The second countermeasure is back to the original message through signature verification on the signature value. It is a method of determining whether there is an error by restoring to If you use, it takes a lot of operation and is inappropriate.

As mentioned above, the CRT-based RSA signature error attack is known to be a general and strong attack because it is based on the premise that fewer constraints of the CRT-based error attack occur. The attack countermeasures of 1 and 2 are methods for checking the occurrence of an error through a checking procedure, which are less efficient due to a large amount of calculation, and the inspection process itself may be the target of another error attack, and the hardware may be permanent. If it is caused by a defect, there is a disadvantage that countermeasures are impossible.

Shamir proposed a countermeasure to cope with the above CRT error attack at Eurocrypt'97Rump Session, which is registered as a patent (US Patent # 5991415). The advantage of Shamir's response is that it can withstand CRT-based parallax attacks.

Despite these advantages, the problems with the error countermeasures proposed by Shamir are as follows. This method generates a random number r and uses it, where the probability of an error that is theoretically undetectable is As many exist. That is, since r is a random number, the length can be varied. However, if a large r is selected, the probability of an undetectable error is reduced. However, since the modular operation must be performed on a larger number, the operation efficiency is reduced. On the contrary, selecting a small r increases the efficiency of the operation relatively, but safety may be threatened because there is a probability that there is an undetectable error. In order to provide sufficient safety, the number of bits of r must be at least 32 bits.

And countermeasures with a checking procedure are vulnerable to hardware failure attacks. Countermeasures through checking procedures, such as Shamir's countermeasures, are inherently weak against hardware error attacks and are difficult to scale up when new error attacks are proposed. (The checking procedure here is from 1. and Is computed twice, the signature is verified in 2, the plain text message is compared to the original message, or in Shamir's countermeasures. Refers to the process of checking.)

To overcome this problem of Shamir's error countermeasures, the present invention uses a new error response method that does not rely on a checking procedure. The present invention is directed to CRT-based computational methods that are safe against error attacks. When designing a security method according to the present invention to withstand such a CRT-based error attack is the most important is as follows.

1. There should be no inspection process for error response.

2. Signature At creation time If an error occurs in the It's designed to affect. sure The same is true when an error occurs. This is not a checking process, but a fault infective if a fault is injected and an attackable factor (i.e., a factor that enables factoring) will fail, making the actual attack impossible. .

At this time, the characteristics as described above can be defined as fault infective CRT computation.

According to the present invention for solving the above technical problem, a method for responding to an error attack of the Chinese CRT based RSA encryption system, the verification of the signature on the plain text using the Chinese residual theorem In operations involving a single argument between given arguments that return a value In the event that there is a risk of attack on the cryptographic system due to an error that can enable the prime factorization of, the error associated with the argument causes an error for another argument, thereby preventing the verification value from being obtained. do.

The method according to the invention embodied therein is described below.

1 illustrates a flow of a method corresponding to an error attack of a sequential CRT based RSA cryptosystem according to the present invention.

Use additional parameters in addition to those used in the RSA algorithm.

decimal About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption or digital signature generation of RSA public key password Calculate

After that, according to the present invention, a method for responding to an error attack of a sequential Chinese Restoration Theorem (RST) based RSA encryption system is as follows.

Intermediate parameters, (here silver Small integer to satisfy), Calculate and for a given m, Calculate each (step 100).

Where gcd (a, b) represents the greatest common divisor of a, b, Function represents the Euler totient function for n.

And , , Calculate sequentially (step 110).

After that , By calculating each

To obtain the signature s (step 120).

In the above method, several additional parameters can be used for signing. When verifying that the signing is performed properly, verification is performed as follows.

In step 100 of FIG.

In this relationship

Because of

therefore

ego,

to be.

In this case, there is no check procedure for error response. Also signed At creation time If an error occurs in Will cause an error. Even if information about one argument is leaked and there is room for an attacker to attack, an error for the other argument will occur, preventing the attacker from attacking the formula.

2 illustrates a flow of a method corresponding to an error attack of a parallel CRT based RSA cryptosystem according to the present invention.

As in the case of FIG. 1, the method of FIG. 2 uses additional parameters in addition to those used in the RSA algorithm.

decimal For open modulus n = p · q and (At this time Secret operation for decryption or digital signature generation of RSA public key password using public key e and secret key d satisfying Precalculate And the intermediate parameter, Where r is Small integer to satisfy), Calculate and for a given m, Calculate each (step 200).

Are calculated respectively (step 210), , To calculate the signature value s by calculating each (step 220). That is, the signature value s

Calculate the signature value.

As in the above case, there is no check process for error response. In addition, even if information about one argument is leaked and there is room for attackers to attack, errors related to other arguments may occur, preventing the attacker from attacking the formula.

The methods according to the invention do not use key dependent checking or comparison operations compared to the prior art. Conventional techniques must use one or more comparison operations (or similar operations). However, there may be an error in the comparison operation itself, and the result of that error may be passed to the attacker.

The following is a description for the case where the secret prime factor is leaked due to improper CRT recombination due to a hardware error, for example.

If Wow All assume that there are no errors.

One possible CRT recombination is calculated as follows.

At this time Is calculated in advance and stored. The above method is called Gauss algorithm. At this time It is necessary to store two precomputed values each having a length of a predetermined bit.

In step 1 120 of the first method of the present invention, Even if one of the values of is incorrect due to a hardware error (caused by an attacker or EEPROM error), the following relationship holds:

therefore Is calculated and stored in advance, even if there is an error that could be caused by an attacker or an EEPROM error. Neither p nor q.

Garner's algorithm, a well-known and improved CRT recombination method, is calculated as follows.

Unfortunately, If there is an error in, the following result is obtained in step 120 of the first method of FIG. 1 proposed according to the present invention.

The synthetic number n can be calculated and factored as

In fact, the above hardware error attack on CRT recombination is general and can be applied to Shamir's proposal of the original CRT acceleration and also to the second method of FIG. 2 according to the present invention. However, the original Garner's algorithm is preferably modified as follows to avoid the hardware error decryption mentioned above.

At this time Is preferably calculated first and stored in advance. At this time, in the case of [Equation 4], it is necessary to store two values calculated in advance, but in the case of [Equation 9], only one value calculated in advance may be stored. Therefore, while reducing the storage capacity, the number of values to be calculated in advance is advantageous in terms of calculation time.

The modification proposed above requires slightly more calculations than the original one of Equation 1 or Equation 4. However, even if the value of X` is not correct due to a hardware error, it can be easily confirmed that CRT recombination is still safe even under the above-mentioned attack.

Wow Gauss's algorithm and the modified Garner's algorithm are also error-converting properties. I If the value of is not correct and the value of X is not correct, it is expressed as follows.

therefore Wow If there is no error (or if both values are incorrect), then n Is not factored. Careful selection of the process of CRT recombination will help prevent CRT-based hardware error attacks.

The following describes an improved method according to the present invention for parallax attack resistance.

Shamir's method can defend against parallax decryption by a binary search approach.

In the method of FIGS. 1 and 2 according to the invention Binary search parallax decryption is possible for operations.

if a <q Assume that the operation on takes very little time. To observe the parallax statistic and approximate the value of p, the attacker deliberately uses a relatively large number And a relatively small number Can be supplied repeatedly.

A method for improving the two security methods according to the present invention to counter the two parallax decryption will be described.

To combat binary search attacks against modulo p (or modulo q), select any integer R = k · p where k is any integer. Then for the CRT calculation (or The original process for obtaining the parameters is preferably modified as follows.

At this time R was pre-masked and used. Because of this, it is not necessary to post-mask later. In order to calculate, an arbitrary integer R is chosen to be k · q.

(or Select an arbitrary integer R = k 占 p (k is any integer) to counter binary search attacks against the. Then, the original procedure for calculating k _p (or k _q ) is preferably modified as follows.

R was masked beforehand, Since k is later masked and used. In order to calculate, an arbitrary integer R is chosen to be k · q.

Any integer R (>> p, q) is modulo p or If appended to message m prior to the operation, (the attacker intentionally And a relatively small number By supplying modulo p or The timing characteristic for whether or not was run is not accessible by the attacker.

With the same property to repel the previous search parallax cryptography for finding p (or q), the technique proposed above has less overhead than Shamir's method in terms of implementation. Shamir's method requires extended modulus, which is inconvenient to implement or complicated for most existing processors. However, the proposal does not require any expansion modulus at all.

Hardware error attacks against RSA used with CRT can be applied even if only one error result is available to the attacker. It is very different from other physical attacks and requires a well-developed response. This is important because the RSA used with the CRT is adopted globally, from small devices (eg smart cards) to numerous applications based on large servers. However, the methods according to the invention give satisfactory results.

All previous crypto solutions require removing the error result (to prevent it being accessed by attackers) or disabling this error result. In some cases, these requirements are difficult to implement with very high reliability. However, two security methods according to the present invention provide satisfactory results.

Those skilled in the art will appreciate that the present invention can be implemented in a modified form without departing from the essential features of the present invention. Therefore, the disclosed embodiments should be considered in descriptive sense only and not for purposes of limitation. Examples included in the above description are introduced for the understanding of the present invention, and these examples do not limit the spirit and scope of the present invention.

In addition to the above examples, it will be apparent to those skilled in the art that various embodiments of the present invention are possible. The scope of the present invention is shown not in the above description but in the claims, and all differences within the scope will be construed as being included in the present invention.

In addition, it can be easily understood by those skilled in the art that each of the above steps according to the present invention can be variously implemented in software using a general programming technique or in hardware including a programming element such as a PLD. It can be.

And all the steps of the present invention can also be embodied as computer readable code on a computer readable recording medium. The computer-readable recording medium includes all kinds of recording devices in which data that can be read by a computer system is stored. Examples of computer-readable recording media include ROM, RAM, CD-ROM, CD-RW, magnetic tape, floppy disks, HDDs, optical disks, magneto-optical storage devices, and carrier wave (eg, Internet It also includes the implementation in the form of). The computer readable recording medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion.

The present invention is a minority About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption or digital signature generation of RSA public key password Operation method If an error occurs in the operation stage associated with one prime factor in, the error By using the widely used CRT (Chinese Restoration Theorem) to improve efficiency, it can spread to errors in the computational stages associated with other prime factors. It is effective to withstand CRT error attacks that can occur in the calculation of. Since the calculation method according to the present invention does not change the structure of the modular calculation engine, which is the core used in the existing RSA system, it is fully compatible with the existing system. There is no comparison operation that determines safety, which increases confidence in safety, and if there is an error for one argument, the error is propagated to the other arguments. You can safely defend against CRT errors by disabling the factorization of.

Claims (8)

delete decimal About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation In this method of countering an error attack against the sequentially calculated Chinese Remnant Theorem (CRT) -based encryption system, (a) intermediate parameters , (here silver Small integer to satisfy), , And for a given message m, Calculating each; (b) , , Sequentially calculating; And (c) using the Chinese remainder theorem Wow After calculating each of The signature value s And calculating the signature value to calculate the signature value of the Chinese password. decimal About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation In this method of countering the error attack against the Chinese Remnant Theorem (CRT) based on the Cryptographic System, which is calculated in parallel, (a) intermediate parameters, Where r is Small integer to satisfy), , And for a given message m, Calculating each; (b) Calculating each; And (c) using the Chinese remainder theorem Wow After calculating, the signature value To And calculating the signature value to calculate the signature value of the Chinese password. The method according to claim 2 or 3, In the recombination of CRT defined as, before calculating step (c) And store the pre-calculated and then use the same to perform the calculation of step (c). The method of claim 2 or 3, wherein in response to the parallax attack, in step (a), When R = k ㆍ p (k is any integer), The value of Responding to the Chinese remaining theorem-based error attack on the RS password system, characterized in that obtained. The method of claim 2 or 3, wherein in response to the parallax attack, in step (a), When R = k q (k is an arbitrary integer), The value of Responding to the Chinese remaining theorem-based error attack on the RS password system, characterized in that obtained. decimal About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation In the device corresponding to the error attack against the sequentially calculated CRT-based RS encryption system, Intermediate parameter , (here silver Small integer to satisfy), , And for a given message m, Means for calculating each; , , Means for sequentially calculating; And Chinese rest using theorem Wow After calculating each of The signature value s And a means for obtaining a signature value by calculating a value of the device. decimal About Modulus and (At this time Public key satisfying And secret key Secret operation for decryption of RSA public key cryptography or digital signature generation In a device that responds to an error attack on the Chinese Remnant Theorem (CRT) -based Cryptographic System computed in parallel, Intermediate parameters, Where r is Small integer to satisfy), , And for a given message m, Means for calculating each; Means for calculating each; And Chinese rest using theorem Wow After calculating, the signature value To And a means for obtaining a signature value by calculating a value of the device.