Algorithm 1. Chinese Remainder Theorem
Input: p, q, d, n and C
1: C
p
C
d (modp1)
(mod p), and C
q
C
d (modq1)
(mod q);
2: u q(q
1
(mod p)), and
v
p(p
1
(mod q));
3: M CRT
p,q?n
(C
p
, C
q
) u C
p
+
v
C
q
(mod n);
4: Return M.
RSA decryption with CRT produces a factor four times faster than normal modular exponentiation, such as left-to-right
square and multiplication, making it essential for competitive RSA implementations. RSA-CRT is not vulnerable to Kocher’s
original timing attack. However, once the factorization of n is revealed, it is easy to obtain the private key d by computing
d e
1
(mod /(n)) because RSA-CRT uses the factor of n.
2.2.3. Montgomery Multiplication
The Sliding Windows Exponentiation (SWE) algorithm performs a modular multiplication at every step. MM, discovered
by Montgomery [15] in 1985, is the most efficient algorithm for the computation of modular multiplications during modular
exponentiation. It uses addition and division by powers of 2, which can be accomplished by shifting the operand to the right
when calculating the result. The efficiency of the algorithm is very high because it eliminates time-consuming integer divi-
sions. MM is used to calculate
Z abR
1
ðmod nÞ ð1Þ
where R is a constant power of 2, R > n, and R
1
is the inverse of R in module n. To use this algorithm, a conversion to and
from the n-residue format is required. Hence, using this algorithm for repeated multiplications on the same residue is more
attractive, just like modular exponentiations. To use MM, all variables must first be converted into Montgomery form, which
transforms number a into aR (mod n). Thus, a and b can be multiplied as aR bR = cR
2
. The fast Montgomery reduction algo-
rithm is then used to compute cR
2
R
1
= cR (mod n). The result is also in Montgomery form, and thus can be directly used in
subsequent Montgomery operations. At the end of the exponentiation algorithm, the output is converted back into standard
form by multiplying it by R
1
(mod n). Algorithm 2 shows the steps of the MM Algorithm. The conditional subtraction S n is
called ‘‘extra reduction’’ [15].
Algorithm 2. MM Algorithm
Input: X, Y, S =MM(X, Y)=XYR
1
(mod n)
1: S =0;
2: for i =0ton 1 do;
3: if X
i
is 1 then;
4: S = S + Y;
5: end if
6: if S is an odd number then
7: S = S + N;
8: end if
9: Shift right the binary form of S with one position
10: end for
11: if S P n then
12: S = S n
13: end if
2.3. Statistical tool of two-sample unpooled t-test
Statistical tools are used in the improved algorithm discussed in the present study. The most important tool is the two-
sample unpooled t-test. The output value of the t-test is used for decision-making on the key bits during the data analysis
phase of the timing attack.
Two-sample unpooled t-test [21] aims to analyze the means of samples from two independent populations. The null
hypothesis (H
0
) states that there are no differences exist between the means of different groups, suggesting that the in-
tra-group variance should be equal to the inter-group variance. The alternative hypothesis (H
1
) states that any of the group
is different from the others [20]. The t-test aims to test the rejection region.
H
0
:¼
l
1
l
2
¼ d; H
1
:¼
l
1
l
2
– d ð2Þ
466 C. Chen et al. / Information Sciences 232 (2013) 464–474