Cryptography Reference
In-Depth Information
Algorithm 1. Montgomery ladder [9]
Require: n , d =( d t− 1 ,...,d 0 ) 2 , m ∈ Z n
Ensure: m d mod n
Algorithm 2. Protected ladder [8]
Require: d =( d t− 1 ,...,d 0 ) 2 , m ∈ Z n
Ensure: m d mod n
r = rand () Z n ; R 2 = r 1 mod n
R 0 = r
R 1 = r · m mod n
for i = t − 1 downto 0 do
R d i = R 0 · R 1 mod n
R d i = R d i mod n
R 2 = R 2 mod n
end for
return R 0 · R 2 mod n
R 0 =1
R 1 = m
for i = t − 1 downto 0 do
R d i = R 0 · R 1 mod n
R d i = R d i mod n
end for
return R 0
already processed (Leading) bits. The remaining (Trailing) bits are denoted by
d T . The intermediates after processing the bit d i are
( m 2 ·d L mod n, m 2 ·d L +1 mod n )for d i =0
( m 2 ·d L +1 mod n, m 2 ·d L +2 mod n )for d i =1 .
( R 0 ,R 1 )=
R R 0
A basic property of the Montgomery ladder is that the quotient
is constant.
This property is important for our attack. In a correct execution of the RSA
algorithm this quotient equals m .
In order to achieve further side-channel resistance, Fumaroli and Vigilant sug-
gested a blinded version [8]. Their proposal is depicted in Algorithm 2. It includes
a random mask r , which is a factor of both intermediates, R 0 and R 1 . Hence, r is
squared in each step in both variables. As a consequence, the result includes the
factor r 2 t . By squaring the inverse of r in every iteration we get r 2 t
at the end
of the algorithm. Thus the result can be unblinded by calculating R 0 ·
R 2 mod n .
To counteract fault attacks, they suggested to include a checksum which is
updated at the end of every iteration. If one or more iterations (key bits) are
skipped due to a fault attack, the checksum is invalid at the end of the algorithm.
This prevents an adversary from tampering with the loop counter. However, this
checksum cannot detect our attack. Therefore, it is not included in Algorithm 2.
Finally, we use the Jacobi symbol for the attack on the blinded Montgomery
ladder. The Jacobi symbol is a generalization of the Legendre symbol for com-
posite moduli and is defined as
c
k
= c
p 1
α 1 c
p 2
α 2
c
p k
α k
where k = p α 1 p α 2
p α k
k
···
···
2
with p denoting the Legendre symbol for primes p
c
p
=
0if c =0 (mod p )
+1 if c
x s.t. x 2 = c
=0 (mod p )and
(mod p )
1otherwise .
 
Search WWH ::




Custom Search