RSA signature algorithms using the Chinese remainder theorem (CRT-RSA) are approximately four-times faster than straightforward implementations of an RSA cryptosystem. However, the CRT-RSA is known to be vulnerable to fault attacks; even one execution of the algorithm is sufficient to reveal the secret keys. Over the past few years, several countermeasures against CRT-RSA fault attacks have tended to involve additional exponentiations or inversions, and in most cases, they are also vulnerable to new variants of fault attacks. In this paper, we review how Shamir’s countermeasure can be broken by fault attacks and improve the countermeasure to prevent future fault attacks, with the added benefit of low additional costs. In our experiment, we use the side-channel analysis resistance framework system, a fault injection testing and verification system, which enables us to inject a fault into the right position, even to within 1 μs. We also explain how to find the exact timing of the target operation using an Atmega128 software board. The RSA algorithm has been used as an important cryptographic tool for authentication, signature generation, and verification. This is based on the presumed difficulty of factoring large integers—that is, the factoring problem. Despite the reliability of RSA, however, improvements in its performance remain a challenging research topic owing to its large size modulus. One solution is to adopt the Chinese remainder theorem (CRT) to RSA, which provides approximately a four-fold increase in performance. Additional savings in memory space is also possible owing to the reduced size of the modulus. These are the main reasons why CRT has been used with RSA (CRT-RSA) in smart cards with limited resources. However, injecting a fault (or faults), such as a clock glitch, power glitch, or light, during the computation of CRT-RSA and observing its faulty output gives the attacker information about secret keys [1] ; such attacks are known as fault attacks. In contrast to power analysis attacks or brute force attacks against cryptographic algorithms, fault attacks require only one (or a few) fault injections and post-processing algorithms to find the secret keys. Among various fault attacks, some are practical, while others are only theoretically possible. Researchers have also studied countermeasures against fault attacks. As expected, the simplest way is to re-compute the signature and compare the two outputs, but this is not an efficient method. A challenging research topic is how to provide a secure and computationally efficient CRT-RSA algorithm. However, practical and secure solutions are hard to find; most of the countermeasures involve additional exponentiations or inversions [2] – [7] , and the majority of those are themselves also susceptible to fault attacks [4] , [8] – [11] . We revisit Shamir’s countermeasure and show what types of fault attacks can be applied to this algorithm in practice. We then propose an improved countermeasure against fault attacks without involving additional heavyweight operations such as exponentiations or inversions. The remainder of this paper is organized as follows: we first introduce some basic concepts, including Shamir’s countermeasure, and then look at fault attacks that can be practically applied to Shamir’s countermeasure in section II. We next propose a new CRT-RSA algorithm in section III, and then we demonstrate its security against fault attacks in section IV. We describe the experiments used to verify the security of the proposed countermeasure and show the experimental results in section V. Finally, we conclude the paper in section VI. In this section, we introduce some basic concepts and notations that will be used throughout the paper and briefly explain the RSA algorithm. Also included in the explanation is the CRT, which is used to speed up RSA. RSA, which is named after its inventors, Rivest, Shamir and Adleman, is the first public-key cryptosystem known to be suitable for both digital signatures and encryption. The details of the parameters, including the public and private key pairs, are as follows: The two numbers e and d , are called public and private exponents, respectively, and a public key is a pair of ( N, e ); a private key is ( N, d ). The factors p and q , may be destroyed or kept secret. It is currently intractable to find the private key d from the public key ( N, e ). If it is possible to factorize N into p and q , one can obtain the private key d . For this reason, the security of the RSA algorithm is based on the difficulty of factoring large numbers. Algorithm 1 shows the process used for making digital signatures using RSA. Exponentiations and modulo computations are the main operations used in the algorithm and are sometimes too heavyweight to be used in resource-limited devices.           Algorithm 1: RSA digital signing Input: message msg, private key (N, d). Output: signature S = m^d mod N. 1    begin 2             Create a message digest to be sent. 3             Represent the digest as an integer m, 0 ＜ m ＜ N–1. 4             S ← m^d mod N. 5             Return S. 6    end For better computation speed and efficiency, RSA can use the CRT. CRT-RSA provides approximately a four-fold faster computation than directly computing S = m^d mod ( p · q ). The additional benefit is that the two modular exponentiations in CRT-RSA use smaller exponents and smaller moduli, thereby reducing resource consumption. The following explains the basic concept of CRT. Suppose n ₁ , n ₂ , … , n _k are positive integers that are pairwise coprime. Then, for any given set of integers a ₁ , a ₂ , …, a _k , there exists an integer x satisfying the following simultaneous congruences: In addition, all solutions x are congruent modulo to the product N = n ₁ × n ₂ ×…× n_k . Thus, x ≡ y (mod n_i ), for 1 < i < k , if and only if, x ≡ y (mod N ). This theorem provides a way to improve the performance of RSA. Unlike RSA, CRT-RSA uses p and q , and three additional secrets d_p , d_q , and i_q —where d_p and d_q are known as CRT exponents and i_q as a CRT coefficient. These values are obtained by computing the following: Given the quintuple ( p, q, d_p, d_q, i_q ), CRT-RSA can be represented as shown in Algorithm 2.           Algorithm 2: CRT-RSA Input: message digest m, private key p, q, d_p, d_q, i_q. Output: signature S. 1      begin 2           S_p ← m^dp mod p. 3           S_q ← m^dq mod q. 4           Combine two S_p and S_q using Garner’s recombination algorithm as follows:                   S = (((S_p – S_q) mod p)· i_q mod p) · q + S_q. 5           Return S. 6      end We note that Gauss’ recombination, described below, consumes more memory space than Garner’s recombination Owing to the reduced size of the modulus, CRT-RSA provides two noticeable enhancements: a faster computation speed, and less required memory space. As a cryptographic algorithm, however, CRT-RSA has a critical drawback as it is known to be susceptible to a simple fault attack called a Bellcore attack, which reveals the secret prime factors by inserting a single fault. Simply speaking, fault attacks refer to malicious behaviors used to change the normal executions of a chip by inducing an exploitable fault. In doing so, an attacker can then obtain useful information that will assist them in the revealing of secrets from such hardware devices. A Bellcore attack [12] , the most well-known fault attack on CRT-RSA, enables an attacker to reveal the secret prime factors by inducing a single fault on a chip. Suppose that by some event, a fault occurs only during the computation of S_p . We let Ŝ_p and Ŝ denote a faulty S_p and a faulty signature, respectively. We then know the following: which gives us gcd (( S − Ŝ ) mod N , N ) ⇔ gcd (( m − Ŝ^e ) mod N , N ) = q . Thus, the attacker can easily factorize N . There are a variety of countermeasures for protecting against a Bellcore attack. In the next section, we introduce Shamir’s countermeasure [13] and several fault attacks that can be practically applied to this countermeasure. To protect against the fault attack described in the previous section, Shamir proposed a CRT-RSA algorithm, shown in Algorithm 3. Unlike recently published CRT-RSA countermeasures, this countermeasure requires d as an input. Thus, this can be a burden for the overall computation.            Algorithm 3: Shamir’s countermeasure Input: message digest m, private key p, q, d, i_q. Output: signature S = m^d mod N. 1     begin 2          Generate a random prime r. 3          S_pr ← m^{d mod φ(p·r)} mod p·r. 4          S_qr ← m^{d mod φ(q·r)} mod q·r. 5          if S_pr≢S_qr mod r then 6              Return error. 7          end 8          S_p ← S_pr mod p and S_q ← S_qr mod q. 9          Recombine S_p and S_q as explained previously. 10        Return S. 11     end Since p, q , and r are prime numbers, we know that provided that faults are never injected. As it is, noting Ŝ_pr as the faulty value of S_pr and | r | as the bit size of r , we have the following: Based on this probability, if any fault is injected during the computation of S_pr or S_qr , an error message must be returned with a probability of about 1 − (2 ^−(|r|−1) ln 2). However, this countermeasure has several drawbacks. First, a fault induced while p (or q ) is accessed to compute p · r (or q · r , respectively) is not detected. This is based on the assumption that p is likely to be reloaded when needed owing to the limited amount of registers in smart cards. With a faulty p (or a faulty q ), a Bellcore attack reveals the secrets. Second, the computations below are not protected This reveals the same security hole of the straightforward CRT-RSA on a Bellcore attack. Similarly, the recombination of S_p and S_q is never protected; and as a result, it is possible to inject a fault to i_q without being noticed. Let î_q denote a faulty value of i_q , we then have the following: and This enables an attacker to perform a Bellcore attack. We do not take into account an attack on the security comparison. For these kinds of attacks, the attacker has to disturb two precise parts of the computation to bypass the checking procedure: a) a temporary value or an operation to be disturbed and b) the coherence test to bypass. The latter will be possible if the attacker modifies the zero flag of the status register so as to bypass the security comparison. However, it is strongly assumed that sensitive registers are unprotected by redundancy mechanisms such as hardwired checksums or error-correcting codes. In addition, we set aside zero-value attacks in which the attacker is supposed to set one of the target buffers to zero during the execution of the exponentiation. To the best of our knowledge, it is not possible in practice to set a large buffer to zero [14] . Thus far, several variants of Shamir’s countermeasure have been proposed. In most cases, they tend to involve additional exponentiations or inversions; thus, resulting in performance degradation. Furthermore, most of them are still susceptible to fault attacks. In this section, we propose a new CRT-RSA algorithm withstandable to fault attacks. Our algorithm, based on Shamir’s countermeasure, performs additional security-purpose operations; thus, making up for the vulnerabilities of Shamir’s countermeasure. From the practical standpoint of smart cards, it is a noticeable aspect that our algorithm does not need additional exponentiations or inversions from Shamir’s algorithm, which results in acceptable performance and resource requirement. We exclusively focus on how to offer a fault-infective CRT-RSA [15] , thereby preventing a Bellcore attack. To that end, an error induced by a fault attack must lead to a fault-infective CRT computation on both S_p and S_q , or on the overall computation of S . Consequently, any kind of fault is expected to result in In particular, we aim to use a special purpose fault-infective computation on a secret modulus such that a fault induced while a secret prime is being loaded spreads throughout the other secret primes. For this purpose, we constructed a modulus chaining where all of the secret primes are tangled up together. This modulus chaining consists of two main concepts: PUSH and POP. In Algorithm 4, PUSH is a procedure adding input values to the target variable sum, where the addition is performed by XORing. In Algorithm 5, POP, on the other hand, outputs the value of a specific variable as follows. Given sum = α ⊕ β ⊕ γ , for example, [POP α ] performs the following: What is important here is that [POP α ] does not load α from memory but instead loads β and γ , and then it computes value_α from sum . In addition, [POP α ] updates sum = value_α ⊕ β ⊕ γ . These contribute to the following facts. First, if any fault is induced while β or γ is accessed, or while T_sum is computed, it results in a faulty and consequently produces faulty sûm and faulty . Consequently, subsequent POPs performed on this faulty sûm result in faulty outputs. Moreover, we verify the integrity of sum in the later part of the algorithm so that the faulty sûm returns an error code. Second, injecting faults while value_α or sum is computed has the same result as the previous case. This has an influence on not only value_α but also on the subsequent outputs of POPs. Owing to these properties, the attacker is unable to succeed in a Bellcore attack if faults are injected while PUSHs or POPs are executed. The details of the proposed algorithm are represented in Algorithm 6.             Algorithm 4: PUSH x, y, ⋯. Input: variable x, y, ⋯. 1     begin 2          sum ← x⊕y⊕ ⋯. 3          W ← W ⋃ {x, y, ⋯}. 4     end             Algorithm 5: POP x Input: variable x, Output: the value of x. 1     begin 2          T ← W− {x}. 3          T_sum ← ${\displaystyle \underset{t\in T}{\oplus }t}.$ 4          value_x ← sum⊕T_sum. 5          sum ← T_sum⊕value_x. 6          return value_x. 7     end             Algorithm 6: Proposed algorithm Input: message digest m, private key p, q, d, i_q. Output: signature S = m^d mod N. 1     begin 2          Generate a random prime r. 3          [PUSH p, q, and r]. 4          d_pr ← d mod φ ([POPp]·[POPr]). 5          d_qr ← d mod φ ([POPq]·[POPr]). 6          $\overline{p}$ ← ([POPp]·[POPr]). 7          $\overline{q}$ ← ([POPq]·[POPr]). 8          S_pr ← m^dpr mod $\overline{p}$ . 9          S_qr ← m^dqr mod $\overline{q}$ . 10         if S_pr≢S_qr mod [POPr] then 11               Return error. 12          end 13          S_p ← S_pr mod [POPp] 14          S_q ← S_qr mod [POPq] 15          S ← (((S_p ← S_q) mod p) · i_q mod p) · q + S_q. 16          if (S≢S_pr mod [POPp]) or 17          (S≢S_qr mod [POPq]) then 18               Return error. 19          end 20          check ← sum ${\displaystyle \underset{w\in W}{\oplus }w}.$ 21          if check≠0 then 22               Return error. 23          end 24          Return S. 25     end On the assumption that each prime used in the algorithm is reloaded every time—owing to the limited number of registers in smart cards—we perform PUSH p , q , and r in the beginning and obtain the value of each prime through POP instead of accessing the primes directly. As previously pointed out, Shamir’s countermeasure does not protect computations from obtaining S_p , S_q , or the CRT recombination. For this reason, we check the congruence relations on S , S_pr , and p as well as on S , S_qr and q after finishing the CRT recombination. The value of check must be confirmed as an integrity check to make sure the POPs have been performed without disturbance by faults. Based on Shamir’s countermeasure, we place the following additional operations in the algorithm. It is worth noting that PUSH consists of two XORs, POP, and four XORs. Hence, PUSH/POP impose 54 XORs in total. It is also important to note that no inversions or exponentiations are additionally used from Shamir’s countermeasure. Table 1 compares the computational cost of previous countermeasures and our own countermeasure for CRT-RSA, where k is the bit length of secret primes, and l is the bit length of a random prime. Our CRT-RSA algorithm requires two exponentiations of a ( k + l )-bit modulus with a ( k + l )-bit exponent, one CRT recombination with two multiplications of two k -bit numbers and two multiplications of k -bit and l -bit numbers. Therefore, the final time complexity of CRT-RSA with our countermeasure is 2( k + l ) ³ + 2 k ² + 2 kl , excluding the cost for extra operations (that is, addition and logical operations). We note that our CRT-RSA has almost the same level of complexity with Shamir’s countermeasure; the additional operations stated earlier do not impose a noticeable increase in the computational cost. We now analyze the security of the proposed algorithm against the fault attacks described in section II. Our analysis does not include all kinds of fault attacks like permanent faults, where some parameters may be permanently corrupted or damaged by some serious environmental factors. The first type of fault is induced while a prime is accessed. As shown in Algorithm 4, there are three primes in the algorithm: p , q , and r . They are loaded at PUSH or POP, except for the CRT recombination. If a fault is injected while a specific prime, say p for example, is accessed, then the following analysis shows the reason why the algorithm is resistant to a fault attack: except for the recombination, p is loaded at PUSH ( p, q, r ), POP q , and POP r . Let denote a faulty p . If a fault is injected during the execution of PUSH, we then have sûm = ⊕ q ⊕ r . The faulty sûm has dependency upon subsequent POPs as follows: (We omit the case of disturbing access to q or r , because it causes a similar result). This shows that a fault injection leads to a fault-infective computation because the faulty sum propagates through the subsequent POPs. For this reason, sum must be intact for an attacker to succeed. It is also possible to inject faults while accessing primes in the execution of POPs. More specifically, fault injection, making the faulty T_sum , outputs the faulty sûm , which results in a faulty infective computation (see line 5 in Algorithm 5). The primes can also be accessed at the CRT recombination. To protect the recombination from fault attacks, we place a security comparison right after the recombination. Thus, if a fault makes a faulty , for example, another fault should be injected during the computation of S_pr mod [POP p ] such that Ŝ ≢ S_pr mod [POP p ] becomes false, which enables an attacker to pass the security comparison. However, the probability for an attacker to succeed in injecting faults at two precise parts of the computation is negligible [14] . The second type of fault is those that could be injected in a transient manner during any computation. Our algorithm performs a total of three security comparisons. The first is to detect either a faulty S_pr or S_qr . To that end, S_pr ≡ S_qr mod [POP r ] is checked at line 10 in Algorithm 6. Since we have Pr [ Ŝ_pr ≡ S_qr mod r] ≈ 2 ^{−( |r| −1)} ln 2, the bit length of r determines the security level of the algorithm. The second is to mainly detect faults that are possibly injected during the computation of S_p ← S_pr mod [POP p ] and S_q ← S_pr mod [POP q ] or during the CRT recombination. Since the bit length of p and q is |S|/2, faulty outputs are unlikely to pass this comparison. The last one, is to verify the integrity of sum , which might be distorted during the last execution of POP; [POP q ]. For this purpose, all primes are newly loaded from the storage and XORed with sum ; the result must be 0 if all operations have been normally performed without faults. Consistency checks at lines 10 and 16, and the use of POP and PUSH to guarantee the integrity of p , q and r , are closely correlated with each other so that they verify that no error occurred during the computation of S_p or S_q and the CRT recombination. In this section, we first describe our fault-injection setup. We then detail the experiment we performed and present the results. We first show the vulnerabilities of Shamir’s countermeasure and show the security of our proposed CRT-RSA against fault attacks using the SCARF system. For injecting faults and analyzing the response during the execution of CRT-RSA, we need a parameter-controlling PC, an experimental board for fault injection, and an oscilloscope. Specifically, implementing CRT-RSA on a software board is more recommendable than porting on a smart card, because we have to insert an additional trigger for injecting a fault during a specific period. Figure 1 shows the hardware setup that we use to inject faults into an Atmega 128 software board. We implemented both Shamir’s countermeasure and our proposed algorithm on an Atmega 128 microcontroller that can operate within the standardized smart card communication specification [19] . The setup consists of a fault-injection control system, named SCARF, our board containing an Atmega 128 microcontroller, a field programmable gate array (FPGA), a triggercontroller, and more. SCARF sends a command including operating parameters to the microcontroller, which in turn forwards the fault parameters to the FPGA. The FPGA then controls the operating environment of the on-board algorithm. The parameters we can handle include the clock cycle and power supply. To inject a fault during the execution of CRT-RSA, we change one of these parameters into abnormal values. Basically, the parameters consist of timing information and fault types. Timing information specifies an offset, synchronizing duration with the control devices and fault injection duration, as shown in Fig. 2 . Fault types can be given by an abnormal clock cycle ( Fig. 3 ), power supply ( Fig. 4 ), or a combination of the two ( Fig. 5 ). In our experiments, we use an abnormal power supply as a fault. The Atmega 128 [20] is a high-performance, low-power AVR 8-bit microcontroller, providing an advanced RISC architecture with 133 instructions and up to a 16 MIPS throughput at 16 MHz. It contains 128 KB of in-system reprogrammable flash, 4 KB of EEPROM/internal SRAM, and up to 64 KB of optional external memory space. Its operating voltages are from 4.5 V to 5.5 V. It may not be acceptable for an 8-bit processor to execute CRT-RSA with a modulus size of more than 1,024 bits. Owing to this fact, we implement both Shamir’s countermeasure and our algorithm with | p | = | q | = 32 bits, which is reasonable for an Atmega 128. More specifically, the public exponent and secret primes we used are: Both Shamir’s countermeasure and our algorithm are designed to return an error code in the presence of faults. However, if faults are injected without being detected, a meaningful output will be returned; thus, enabling a Bellcore attack. In the following experiments, we intentionally injected faults at the vulnerable points where Shamir’s countermeasure is susceptible and injected the same type of faults on the proposed scheme. The results show that Shamir’s countermeasure returns a faulty signature, while our algorithm returns a meaningless error code; 0x00. Experiment 1 (Shamir’s countermeasure): We initiate communication between the Atmega 128 software board and the SCARF system, introduced previously, as defined in the ISO/IEC 7816-4 standard, which specifies the organization, security, and commands for an interchange. Shamir’s countermeasure is executed at the command from SCARF, and this command also defines the fault parameters, which include timing information and fault types. It is not possible to extract a trigger signal from a smart card, and for this reason, we used a software board. We set trigger signals generated when particular operations begin so that we can find a part of the specific operation(s) in the waveform of CRT-RSA ( Fig. 6 ). The SCARF system provided us with a user interface controlling the fault-injection timing in the unit of μs. After finding the exact position of the target operations using the trigger signal, we can inject a fault at the right position. We note that a fault-injection environment should support parameters in the unit of μs, and we therefore inject a fault at a fairly lightweight operation such as the loading of a secret prime. We reduce the 3.3 V power supply to 2.2 V, while (a) the secret primes are being loaded and (b) the operations including the CRT recombination are being performed. We ran procedure (a) 100 times and attack procedure (b) 500 times, trying to inject faults into various points of operations. We set the trigger signals for (a) and (b), and adjusted the timing for a fault injection using the SCARF system, the results of which are shown in Fig. 7 . We noticed that a fault injection is not always successful; a software board (or a smart card) often totally crashes or sometimes a fault injection has no effect. As a result, we only succeeded in injecting 60 faults out of a total of 600 ((a) 4 times and (b) 56 times); the faulty outputs are shown in Fig. 8 . The SCARF system first runs the algorithm without faults and stores its original output. Every time faults are injected into the algorithm, the system compares the output of the algorithm to the original output and shows faulty bytes in red if they are different from the original output. By using one of any fault signature shown in Fig. 8 , the attacker can reveal the secret primes p and q , and compute then d , because the public exponent e is known. Experiment 2 (The proposed algorithm): In this experiment, we testify the security of our algorithm. As in Experiment 1, we gave the same type of fault at every point where Shamir’s countermeasure fails to protect from faults. For a stronger verification of the security of the proposed algorithm, more faults are injected than had been for Experiment 1. We intensively injected faults when loading secret primes and operations around where the CRT recombination is executed. As pointed out previously, fault injection does not show a fixed success rate even though basic operations are the same. In this experiment, the microcontroller crashed more often than in the previous experiment, and more faults failed to be injected. As a result, only 21 of 1,000 faults are successfully injected and are represented in red in Fig. 9 ((a) 5 times and (b) 16 times). As designed for protection against fault attacks, all faulty signatures return an error code 0x00 without exception. Needless to say, error code 0x00 does not enable a Bellcore attack. The Bellcore attack on CRT-RSA reveals the secret prime factors by introducing a single fault on a chip. Although Shamir’s software countermeasure has attracted a lot of attention, several drawbacks—from a security point of view—have limited its widespread use. Many later countermeasures have depended on additional exponentiations and inversions to detect fault attacks, resulting in severe performance degradation. In this paper, we improved Shamir’s countermeasure to protect against a Bellcore attack with low additional costs. Unlike previous fault injection experiments, our experiment environment, the SCARF system, enables us to inject a fault into the right position, even in the unit of ㎲. We implemented Shamir’s countermeasure, as well as our own countermeasure, on an Atmega 128 software board and generated trigger signals when specific operations began. The exact time of the target operations could be calculated using these trigger signals, and we were able to inject faults wherever we wanted—even at the loading of the secret primes. Our security analysis and experiments demonstrate that the proposed countermeasure provides reliable security. skwnag@etri.re.kr Seungkwang Lee received his BS in computer science and electronic engineering from Handong University, Pohang, Rep. of Korea in 2009, and his MS degree in computer science from Pohang University of Science and Technology (POSTECH) Pohang, Rep. of Korea in 2011. He is currently working as a researcher with ETRI, Daejeon, Rep. of Korea. His research interests include side-channel attacks, fault attacks, and software/hardware implementation. Corresponding Author  dhchoi@etri.re.kr Dooho Choi received his BS degree in mathematics from Sungkyunkwan University, Seoul, Rep. of Korea in 1994 and his MS and PhD in mathematics from Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Rep. of Korea in 1996 and 2002, respectively. Since Jan. 2002, he has been a senior researcher in Electronics and Telecommunications Research Institute (ETRI), Daejeon, Rep. of Korea. His current research interests are side-channel analysis and its resistant crypto design, security technologies of RFID and wireless sensor networks, lightweight cryptographic protocol/module design, and cryptography based on non-commutativity. He was the editor of the ITU-T Rec. X.1171. choiyj@etri.re.kr Yongje Choi received his BSEE and MS from Chonnam National University, Gwangju, Rep. of Korea, in 1996 and 1999, respectively. He is currently a senior member of technical staff at the Electronics and Telecommunications Research Institute (ETRI), Daejeon, Rep. of Korea. His research interests include VLSI design, crypto processor design, side-channel analysis, and information security.