Timing attack against implementation of a parallel algorithm for modular exponentiation

We describe a parallel algorithm for modular exponentiation y ≡ x^k mod n. Then we discuss timing attacks against an implementation of the proposed parallel algorithm for modular exponentiation. When we have two processors, which perform modular exponentiation, an exponent k is scattered into two partial exponents k⁽⁰⁾ and k⁽¹⁾, where k⁽⁰⁾ and k⁽¹⁾ are derived by bitwise AND operation from k such that k⁽⁰⁾ = k ∧ (0101⋯01)₂ and k⁽¹⁾ = k ∧(1010 ⋯10)₂. Two partial modular exponentiations y₀ ≡ x^k(0) mod n and y₁ ≡ x^k(1) mod n are performed in parallel using two processors. Then we can obtain y by computing y ≡ y₀y₁ mod n. In general, the hamming weight of k⁽⁰⁾ and k⁽¹⁾ are smaller than that of k. Thus fast computation of modular exponentiation y ≡ x^k mod n can be achieved. Moreover we show a timing attack against an implementation of this algorithm. We perform a software simulation of the attack and analyze security of the parallel implementation.