Side-channel analysis of the modular inversion step in the RSA key generation algorithm

SPECIAL ISSUE PAPER Side-channel analysis of the modular inversion step in the RSA key generation algorithm Alejandro Cabrera Aldaya 1, * ,† , Raudel Cuiman Márquez 1 , Alejandro J. Cabrera Sarmiento 1 and Santiago Sánchez-Solano 2 1 Instituto Superior Politécnico José A. Echeverría (CUJAE), Havana, Cuba 2 Instituto de Microelectrónica de Sevilla, IMSE-CNM (CSIC/Universidad de Sevilla), Seville, Spain SUMMARY This paper studies the security of the RSA key generation algorithm with regard to side-channel analysis and presents a novel approach that targets the simple power analysis (SPA) vulnerabilities that may exist in an implementation of the binary extended Euclidean algorithm (BEEA). The SPA vulnerabilities described, together with the properties of the values processed by the BEEA in the context of RSA key generation, represent a serious threat for an implementation of this algorithm. It is shown that an adversary can disclose the private key employing only one power trace with a success rate of 100 % –an improvement on the 25% success rate achieved by the best side-channel analysis carried out on this algorithm. Two very different BEEA implementations are analyzed, showing how the algorithm’s SPA leakages could be exploited. Also, two countermeasures are discussed that could be used to reduce those SPA leakages and prevent the recovery of the RSA private key. Copyright © 2016 John Wiley & Sons, Ltd. Received 6 May 2016; Revised 1 September 2016; Accepted 8 October 2016 KEY WORDS: side-channel analysis; SPA; binary Euclidean algorithm; RSA key generation 1. INTRODUCTION Side-channel analysis of cryptographic algorithms is a powerful technique that can seriously compromise the security of these algorithms. Since the scientific community’s early experiments with power consumption based side-channel analysis in 1999, this approach has proved to be very effective against several cryptographic algorithm implementations [1]. The observation/processing of an electronic device’s power consumption when processing secret data can leak information about that data. One of the techniques that can be employed to extract secret information is simple power analysis (SPA), which exploits the existence of visually distinguishable power consumption patterns that may reveal the sequence of operations executed by an algorithm. If this sequence of operations depends on a secret value, then the implementation is considered vulnerable to SPA. *Correspondence to: Alejandro Cabrera Aldaya, Instituto Superior Politécnico José A. Echeverría (CUJAE), Havana, Cuba. † E-mail: [email protected] Copyright © 2016 John Wiley & Sons, Ltd. INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS Int. J. Circ. Theor. Appl. (2016) Published online in Wiley Online Library (wileyonlinelibrary.com). DOI: 10.1002/cta.2283 One of the algorithms that have been targeted using this kind of side-channel analysis is the RSA key generation procedure, an algorithm commonly used in electronic devices (i.e., hardware security modules) [2] dedicated to the generation and storage of cryptographic keys. Side-channel leakages that may exist during the RSA key generation procedure have been analyzed in several published works, most of which have focused their attention on the algorithms employed to generate the secret prime numbers needed to construct an RSA key. In [3], the Joye and Pallier method proposed in [4] was analyzed to recover some bits of the secret primes, and the Coppersmith method was used to calculate the remaining ones, with an overall success rate of 0.1% [5]. In [6] and [7], the authors analyzed the leakages that could exist in different methods for checking the divisibility of a prime candidate by a prime sieve. Independent of the specific random prime number generation algorithms analyzed in these works and their intrinsic implementation details, the best success rate achieved was 25% [7]. This work presents a new side-channel analysis of the RSA key generation procedure. Instead of targeting a prime generation algorithm as in previous works, the proposed side-channel analysis, based on SPA leakages, focuses on the modular inversion operation required to generate an RSA private key. In this context, the RSA key generation procedure imposes the requirement that only one power consumption trace can be used to extract the private key. There are different approaches for computing modular inverses. Among the most popular methods are those based on the extended Euclidean algorithm [8]. In order to avoid the divisions involved in this algorithm, a binary variant of it, called binary extended Euclidean algorithm (BEEA), is often preferred because it replaces multi-precision divisions with right shift operations [9]. This change results in software implementations with very good performance [10], and it is also very suitable for hardware realizations, as the required shift operations can be implemented with minimal resources [11]. The execution flow of the BEEA is highly dependent on its inputs. This property has been studied in order to identify the side-channel leakages that could compromise a secret variable processed by this algorithm. In [12], the authors proved that if an adversary knows the specific execution flow that this algorithm follows, then the algorithm’s secret inputs can be disclosed. In that work, the execution flow was extracted using simple-branch prediction analysis, which is a kind of sidechannel analysis intrinsic to microprocessor architectures [13]. However, the existence of power-based side-channel leakages in the BEEA has not been studied in depth by the scientific community. It was previously considered [12,14] that the BEEA is vulnerable to side-channel analysis only if all the information about its execution flow is known, but in [15], a new model was introduced that is able to establish how much information can be recovered when only some information about the execution flow is known. The same study also showed that a BEEA implementation may be vulnerable to SPA and explained how the SPA leakages of a BEEA implementation can be exploited in the context of digital signature algorithm (DSA)-like signature generation [15, 16]. This paper has the following contributions with respect to [15]: in [15], the cryptographic protocol under study was ECDSA, while here the RSA key generation procedure is analyzed. This difference is important because the BEEA’s inputs in elliptic curve digital signature algorithm (ECDSA) and in RSA have different properties. These properties make that in ECDSA the number of bits that can be recovered is low in comparison with the amount that can be recovered in RSA key generation, as is formalized in Section 3. This difference implies that some analysis (not needed for ECDSA) should be performed during the processing of the power consumption traces to gather the required information as is analyzed in Sections 4 and 5. Also, in this paper, two BEEA implementations are studied allowing a more complete analysis about how the power consumption traces should be analyzed for extracting the SPA leakages that a BEEA implementation may have. On the other hand, a previously known countermeasure is proposed to be applied in a different setting with respect to its original employment without sacrificing the performance of the RSA operations. The paper is organized as follows: Section 2 introduces the RSA key generation algorithm and describes the BEEA. Section 3 presents a side-channel analysis of the BEEA, explaining how the RSA private key can be recovered employing only one power trace. Sections 4 and 5 analyze two A. CABRERA ALDAYA ET AL. Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta BEEA implementations, illustrating how the SPA vulnerabilities are present in two very different implementations of the algorithm and showing how the implementations’power consumption traces can be processed to extract the required information. Section 6 discusses two countermeasures that can be used to eliminate SPA leakages, and finally, in Section 7, some conclusions are presented. 2. RSA KEY GENERATION ALGORITHM The RSA cryptosystem employs two different keys for encryption and decryption. These are known as the public key and the private key, respectively. The public key is considered accessible to everyone, while the private key must remain secret. The RSA key generation algorithm defines how an RSA public key and the corresponding private key are created. The steps involved in generating an RSA key pair are shown in Algorithm 1. The desired key length (nlen) is the only input that this algorithm requires. This parameter defines the number of bits of the public modulus N, taking into account that an adversary must not be able to factorize it during the lifetime of the generated key. Typical values of nlen are 1024, 2048, and 4096 [16]. The first step in the RSA key generation algorithm is to generate two random, odd prime numbers, p and q. These randomly generated primes are used to compute the public modulus N(see step 2 of Algorithm 1). The generation of these numbers is subject to some constraints to avoid certain kinds of attacks [17]. However, the results presented in this work only require considering that pand qshould have about nlen/2 bits, as is the case in practice to avoid some factorization attacks [17]. The parameter ϕ(N) (calculated at step 3 of Algorithm 1) corresponds to Euler’s totient function and is only used during the key generation process, but its confidentiality must be guaranteed because if it is known, the private key could be disclosed using step 5. However, there are three facts about ϕ(N) that are very useful in this work and that can be known in advance: 1. The bit-length of ϕ(N) is equal to the bit-length of N(nlen). 2. Its two least significant bits are zero. 3. Nand ϕ(N) share roughly half of their bits (the most significant ones). The first two facts can easily be deduced considering that pand qare two prime numbers of several hundreds of bits (i.e., nlen/2). This means that the product of (p1) and (q1) will produce a number divisible by four and with the same bit-length as N=pq (i.e., nlen). According to the definition of ϕ(N), it can be concluded that Nis a good approximation of ϕ(N) because pand qin (1) have about the half of the number of bits of Nand ϕ(N). ϕNðÞ¼N–pþq–1ðÞ (1) SCA OF THE MODULAR INVERSION STEP IN THE RSA KEY GENERATION ALGORITHM Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta Considering that pand qhave the same bit-length, it can be concluded that the number of bits that Nand ϕ(N) have in common is about nlen/2, where the exact number depends on a carry propagation. Therefore, these numbers will share their nlen/2 10 most significant bits with high probability. The public exponent eshould be selected from the interval (1, ϕ(N)) and must be relatively prime to ϕ(N). For performance reasons, eis often fixed to a prime number with a low Hamming weight. For example, e=2 16 + 1 is a typical value found in many implementations that offers a good trade-off between performance and security [17, 18]. For this reason, this value of eis used to present the results of this work, although the same results can also be generalized to other values of e. The last step of the RSA key generation algorithm aims in obtaining the private exponent d,a parameter equal to the modular inverse of emodulo ϕ(N). This step is the target of the proposed attack, particularly when the modular inverse is computed using the binary extended Euclidean algorithm or another algorithm based on it, as is common in practice due to its good performance. This algorithm is described in the following section, with particular attention to some of its more interesting properties. 2.1. Binary extended Euclidean algorithm The binary greatest common divisor algorithm proposed by Stein in 1967 is commonly known as the binary Euclidean algorithm [9]. This algorithm can be extended (to what is known as BEEA) to obtain integers xand ysuch that ax +by =gcd(a,b), while at the same time computing the greatest common divisor of aand b(i.e., gcd(a,b)). When gcd(a,b) = 1, the value obtained for xcorresponds to the multiplicative inverse of amodulo b. The BEEA is very useful for generating RSA keys because eand ϕ(N) must be relative primes. This means that the greatest common divisor of eand ϕ(N) must be calculated to ensure the fulfillment of this requirement; and, additionally, the multiplicative inverse of emodulo ϕ(N) also has to be computed. One of the BEEA’s properties is that it is able to compute these quantities at the same time, offering very good performance [8,11]. In this paper, the classic variant of the BEEA was employed as it allows results to be generalized to other less common variants such as those described in [8]. Algorithm 2 shows the procedure to compute the private exponent dand the greatest common divisor of eand ϕ(N) employing the BEEA. In this algorithm, some steps of the original description of the BEEA (cf. [8]) used to ensure that at least one of the variables uor vis odd before step 7 were excluded. This was possible because ϕ(N) is an even integer and, because gcd(e,ϕ(N)) = 1 must hold, ecan never be even; it is therefore always selected to be an odd number (e.g., e=2 16 + 1), ensuring that at the first execution of step 7 of Algorithm 2, uis always odd. A specific notation was used in this paper to describe certain properties of the BEEA. The term u-loop refers to the loop responsible for dividing variable uby two (steps 8 to 15 of Algorithm 2). Likewise, the term v-loop refers to the loop that divides v. The term x-loop is used to refer to either of the aforementioned two loops (where the ‘x’can be ‘u’or ‘v’). Another important component of Algorithm 2, here denominated the sub-step, is associated with the subtraction operations executed between steps 24 and 31 of Algorithm 2. Using this notation, it is possible to state certain facts about the BEEA. Fact 1: During the first iteration, the only x-loop that is executed is the v-loop because at the start of the algorithm, uis initialized to e, which is an odd number, while v, initialized as ϕ(N), is always an even number, as highlighted in the previous section. Fact 2: At any iteration, one and only one x-loop is executed because these loops ensure that the variables uand vare odd numbers before the execution of the sub-step. This means that when the sub-step is executed, one of its subtractions (at step 25 or at step 29) ensures that only one of variables uor vwill be an even number. A. CABRERA ALDAYA ET AL. Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta For the sake of notation uniformity, the variables used to represent the BEEA leakages in [12] and [15] were reutilized in this study. Equivalently to their definition in [12], these variables can be defined using the x-loop and sub-step notation as follows: SHIFTS[i]=the number of times that an x loop is executed at iteration i. SUBS i ½¼′u′:if u≥vat step 24 ′v′:if u<vat step 24  SCA OF THE MODULAR INVERSION STEP IN THE RSA KEY GENERATION ALGORITHM Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta 3. SIDE-CHANNEL ANALYSIS OF THE BEEA In [12], a side-channel analysis of the BEEA was presented. It concluded that the algorithm’s inputs can be fully recovered when the adversary is able to collect the SHIFTS[i] and SUBS[i] for all iterations. Recently, in [15], the authors proved that, knowing only the SHIFTS[i], some SUBS[i] can be recovered, and a certain number of bits of one of the BEEA inputs can be expressed as a function of the other one. With regard to power-based side-channel analysis, the latter approach is very interesting because, as commented in [15], it seems very difficult to extract the SUBS[i] directly from a power trace but much easier to extract the SHIFTS[i] if the sub-step can be distinguished. Each iteration of the BEEA can be segmented into a series of x-loop iterations followed by a substep. This means that the SHIFTS[i] are related to the time elapsed between two consecutive sub-steps. Consequently, if the sub-step procedure can be distinguished in a power trace, then an adversary should be able to extract the SHIFTS[i]. Figure 1 shows an example of an execution flow of the BEEA where a capital ‘L’is used to represent an x-loop iteration and a capital ‘S’is used to label the sub-step. From this execution flow, it is possible to extract some SHIFTS[i] counting the number of ‘L’between each consecutive pair of ‘S’. Therefore, the first six SHIFTS[i] are as follows: 5, 2, 1, 2, 1, and 5. If the power consumption of a BEEA implementation can be segmented like the sequence of Figure 1, then it is possible to extract the SHIFTS[i] employing SPA techniques. Sections 4 and 5 describe two different BEEA implementations and analyze their power traces, showing how the SHIFTS[i] can be extracted from a power trace for each hardware platform. In this paper, the power consumption is the source of the leakage, but the analysis of the side-channel vulnerabilities of the BEEA when it is used during an RSA key generation can be applied to any scenario where the SHIFTS[i] can be extracted. The rest of this section presents the rationale for recovering all bits of an RSA private key during its generation, considering that an adversary is able to obtain the required SHIFTS[i] using similar methods to those described in Sections 4 and 5. According to the findings in [15], the higher the number of iterations for which the corresponding SHIFTS[i] and SUBS[i] are known, the higher the number of bits that can be recovered. More formally, when for the first Titerations the SHIFTS[i] are known and the first T2SUBS[i] are known too, then it is possible to express the ∑T i¼1SHIFTS i½þ1 least significant bits of one of the BEEA inputs (i.e., the secret input) as a function of the other input (i.e., the known input). This model for analyzing the side-channel leakages of the BEEA can be applied in the context of RSA key generation because the value to be inverted (e) is known by the adversary. This means that some bits of ϕ(N) can be expressed as a function of the public exponent e, the recovered SHIFTS[i], and the corresponding SUBS[i]. In an SPA context, the recovery of the SUBS[i] seems difficult because the operations executed and the data processed on the two branches of the sub-step are the same, and are therefore likely to be indistinguishable in a power trace. The difference between the branches is in the order of the operands (see Algorithm 2), so differentiating between them is difficult employing SPA techniques. On the other hand, analyzing the BEEA’s inputs during the generation of the private exponent, it is observed that eand ϕ(N) have very different bit-lengths. That is, when eis equal to 2 16 + 1, it has only 17 bits, while ϕ(N) has the same bit-length as N(usually more than 1024 bits). This means that the value of uat the start of the algorithm is equal to a 17-bit value, while v(initialized to ϕ(N)) stores a much higher value. This difference implies that the result of the comparison at step 24 of Algorithm 2 (which determines the values of SUBS[i]) can be predicted with absolute certainty during several iterations because vwill have more bits than uduring those iterations. This means that for those iterations, the corresponding SUBS[i] can be inferred by an adversary Figure 1. Example of a binary extended Euclidean algorithm execution flow. A. CABRERA ALDAYA ET AL. Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta (i.e., SUBS[i]=‘v’as v≫u). This property has devastating results on the security of a vulnerable BEEA implementation because, as is formalized below, the number of SUBS[i] that can be inferred is sufficient to disclose the value of ϕ(N). The exact number of iterations for which it can be concluded, with absolute certainty, that SUBS[i]=‘v’, depends on the number of bits that vloses at every iteration. At the ith iteration, v loses SHIFTS[i] bits through the right shifts in the v-loop. This means that the number of iterations for which SUBS[i]=‘v’is closely related to the SHIFTS[i]. In fact, it is very likely that it is the only reason, because the other step of the BEEA that may reduce the bit-length of voccurs at the sub-step, but there, uis subtracted from v, so it is very unlikely that vloses a bit at this subtraction while vhas a much higher number of bits than u. The formal modeling of this behavior is not covered in this paper because, as will be shown later, the number of iterations for which it is needed to know with absolute certainty that SUBS[i]=‘v’indicates that the bit-length of vwill be very different from the bit-length of u. So, considering only the effect of the SHIFTS[i] on the number of iterations for which it can be concluded that SUBS[i]=‘v’, it is clear to see that v, initialized to ϕ(N), has to be divided by two Ltimes (2) to store a value of the same bit-length of u. L¼log2ϕNðÞ–log2eðÞ (2) This indicates that the minimum number of iterations for which it can be concluded that SUBS[i]=‘v’with absolute certainty is defined by the minimum value of Tthat satisfies ∑T i¼1SHIFTS i½þ1≥L. Considering the results in [15], the Lleast significant bits of ϕ(N) can be recovered if the SHIFTS[i] and SUBS[i] are known for the first Titerations, and taking into account that in this case Lonly differs by 17 from the bit-length of ϕ(N), then ϕ(N) can be almost fully recovered using this method as is shown in Figure 2. In this figure, ϕ(N) and Nare represented as nlen bits numbers showing that they have in common half of their most significant bits (shaded area). The method described earlier makes it possible to recover all bits of ϕ(N) except the log 2 (e) most significant ones. When eis equal to 2 16 + 1, as is common, only the 17 most significant bits of ϕ(N) still need to be recovered. However, as mentioned in Section 2, Nand ϕ(N) share approximately half of their most significant bits, so the remaining 17 most significant bits (MSBs) of ϕ(N) are already known from the knowledge of the public parameter N.Onceϕ(N) is completely disclosed, the recovery of the private exponent (d) is immediate because it is known that the latter is the multiplicative inverse of the public exponent emodulo ϕ(N). The number of iterations, T, for which it is needed to know the SHIFTS[i] depends only on the bitlength of ϕ(N). Taking into account that, with high probability, Nand ϕ(N) have their nlen/2 10 most significant bits in common, only nlen/2 + 10 bits of ϕ(N) are unknown. This means that the minimum value of Tthat satisfies (3) corresponds to the number of iterations for which the SHIFTS[i] should be extracted from a power trace to recover the remainder bits of ϕ(N). ∑T i¼1SHIFTS i½þ1≥nlen 2þ10 (3) At each iteration iof the BEEA, the corresponding SHIFTS[i] is at least one (Section 2). Also, considering that the probability of SHIFTS[i]=k is defined by 1/2 (k1) [8], there is a 50% chance that uis divided by at least two at each iteration. This means that, on average, the first T=nlen/4 + 5 SHIFTS[i] should be sufficient to fulfill (3). This leads to the conclusion that for Figure 2. Similarity between Nand ϕ(N). SCA OF THE MODULAR INVERSION STEP IN THE RSA KEY GENERATION ALGORITHM Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta RSA-2048 and RSA-4096, an average of 517 and 1029 SHIFTS[i], respectively, need to be extracted from a power trace for recovering the unknown bits of ϕ(N). With regard to side-channel analysis, the bit-length difference between ϕ(N) and ehas devastating results for the security of an RSA key generation implementation that employs the BEEA. The procedure described in this section shows that an adversary only needs to be able to extract the SHIFTS[i] to recover the private key. This renders ineffective the countermeasure proposed in [14] against an SPA attack against the BEEA designed to enforce the indistinguishability of the sub-step branches to avoid the recovery of the SUBS[i],because the attack presented here obtains the required SUBS[i] analytically, instead of employing SPA-based techniques. The following section highlights the application of the attack when other values of the public exponent, e, are used, while in Sections 4 and 5, two commonly used cryptographic implementation platforms are analyzed in order to show the feasibility for extracting the SHIFTS[i] from a power trace. 3.1. Analysis for NIST standardized values of e As shown in the previous section, the value of e(i.e., 2 16 + 1) commonly used to speed up the RSA encryption and RSA signature verification procedures represents a serious threat when confronted by an SPA-capable adversary. Consequently, in order to reduce the number of bits of ϕ(N) leaked from an SPA-vulnerable BEEA implementation, eshould be selected of about the same bit-length of N. However, some standards, such as NIST FIPS-186-4, restrict the selection of eto the range 2 16 <e<2 256 [16]. This means that the maximum acceptable bit-length for ein this standard is 256. Therefore, using the side-channel leakage and the method explained previously, the 256 most significant bits of ϕ(N) will remain unrecovered. However, taking into consideration that the minimum security strength currently allowed is 2048 bits [19], then ϕ(N) and Nshare at least about their 1024 most significant bits, so the full recovery of ϕ(N) is still possible. This shows that, even with the highest value of ecompliant with the NIST standard, ϕ(N) can be fully recovered and the private key fully disclosed during the RSA key generation procedure if an SPA-vulnerable BEEA implementation is used. 4. HARDWARE BINARY EXTENDED EUCLIDEAN ALGORITHM TARGET In this section, a hardware implementation of the BEEA is analyzed, and some methods are presented for identifying the meaningful patterns that allow the recovery of the SHIFTS[i].The hardware platform targeted corresponds to a third-party field-programmable gate array (FPGA) implementation of the BEEA that follows the steps of Algorithm 2. This implementation employs three embedded RAM memories (BRAMs) for storing the BEEA variables. Each variable is stored as an array of 32-bit words. This BRAM arrangement reduces latency by allowing the parallel execution of some steps of the BEEA. For example, it is known that the BEEA variables are arranged in these BRAMs in such a manner that the three subtractions at the sub-step stage can be executed in parallel, while in the v-loop implementation, the steps of the branches resulting from step 18 of Algorithm 2 are executed concurrently just after the division by two operation of the variable v. Also, at steps 22 and 23 of Algorithm 2, the divisions by two are interleaved with the addition and subtraction operations. This property is important because it could result in a different power consumption pattern with respect to the division by two and addition/subtraction ones. 4.1. Simple power analysis to a FPGA binary extended Euclidean algorithm implementation The SAKURA-G board (Morita Tech Co., Ltd, Taipei, Taiwan) is one of the most commonly used platforms for evaluating the side-channel resistance of FPGA cryptographic algorithm implementations [20]. The BEEA core netlist was implemented for the Spartan 6 LX75 FPGA present on this board. Power consumption traces were acquired by means of the SAKURA-G on-board amplifier output [20]. The traces were captured using a Tektronix DPO3034 oscilloscope (Tektronix, Inc., Beaverton, OR, USA) with the target implementation operating at 6 MHz [21]. Two channels of the scope were A. CABRERA ALDAYA ET AL. Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta employed: one to capture the trigger signal and the other to obtain the traces. The sample rate was 250 MSps and the bandwidth was limited to 20 MHz, as this results in better looking traces. A portion of a power trace captured using this measurement setup is shown in Figure 3. This trace corresponds to the target implementation’s power consumption just at the beginning of the first iteration of the BEEA. This means that power consumption of the initialization phase (steps 1 to 6 of Algorithm 2) is not shown but, it would have a similar shape for different values of ϕ(N), therefore, it is not relevant in the context of an SPA. The power trace in Figure 3 has to be analyzed to extract the SHIFTS[i] needed to recover the remainder bits of ϕ(N),as described in Section 3. As a SHIFTS[i] corresponds to the number of times an x-loop is executed at iteration i, it is important to identify each BEEA’s iteration in the power trace. Identification of the sub-step procedure makes it possible to segment the BEEA power trace into iterations; because the SHIFTS[i] are related to the time elapsed between two consecutive sub-steps, they can therefore then be recovered. Analyzing the power trace shown in Figure 3, it can be concluded that it is composed by a concatenation of a few power consumption patterns. These patterns are marked in the figure as D1, D2,AD, and SS. The correspondence of these patterns with the multi-precision operations (microoperations) present in the BEEA could be directly established if it were possible to measure the power consumption of the BEEA implementation while it processes a known value of ϕ(N). However, even if an adversary is unable to do this, there are alternative methods for establishing the correspondence. In this work, it is assumed that the adversary cannot control the BEEA inputs. This implies that the power consumption patterns must be identified using general facts about the processed values and the BEEA. This approach provides a more general description of the algorithm’s SPA vulnerabilities. For example, if the adversary is able to trigger the execution of an RSA key generation implementation several times, a new pair of prime numbers pand qwill be generated at each execution, and a new, random ϕ(N) will consequently be processed by the BEEA core. Comparing a few of these traces, it is possible to note that the sequence D1-AD-D1-D2 always appear at the start of the power trace. To identify which power consumption pattern corresponds to each of the BEEA micro-operations, some facts about this algorithm (presented in Section 2.1), together with known information about ϕ(N), will be used. Taking into account that the one and only x-loop executed at the first iteration is the v-loop and that, as shown in Section 2, ϕ(N) is always divisible by four, then the v-loop will be executed at least twice during the first iteration of the BEEA (i.e., SHIFTS[1] ≥2). This leads to the conclusion that the observable sequence of patterns D1-AD-D1-D2 should correspond to the steps of BEEA that are executed during the first two iterations of the first v-loop. The reason that makes this sequence of patterns always appears at the start of the BEEA is that the sequence of steps of Algorithm 2 that are executed during the first two iterations of the first v-loop only depends on the evenness of the variables involved (v,C,D,e, and ϕ(N)), which are the same for every value of ϕ(N) during the first two iterations of the first v-loop. More specifically, at the start of the first iteration of the v-loop, variables C and D are equal to zero and one, respectively, meaning that the BEEA will branch to steps 22 and 23 of Algorithm 2. So, C will subsequently be updated according to (4): Figure 3. FPGA binary extended Euclidean algorithm implementation partial power trace. SCA OF THE MODULAR INVERSION STEP IN THE RSA KEY GENERATION ALGORITHM Copyright © 2016 John Wiley & Sons, Ltd. Int. J. Circ. Theor. Appl. 2016 DOI: 10.1002/cta