Timing Attacks against a Parallelized RSA Implementation (特集:プライバシを保護するコンピュータセキュリティ技術)

概要

論文の詳細を見る
We discuss timing attacks against RSA using the parallel modular exponentiation. We describe a parallel algorithm for the modular exponentiation y Ξ x^d mod n. Then timing attacks against the parallel implementation are demonstrated. When we have two processors, which perform the modular exponentiation, an exponent d is scattered into two partial exponents d^<(0)> and d^<(1)> where d^<(0)> and d^<(1)> are derived by bitwise AND operation from d such that d^<(0)> = dΛ(0101・・・01)_2 and d^<(1)> = dΛ(1010・・・10)_2. Two partial modular exponentiations y_0 Ξ x^d^<(0)> mod n and y_1 = x^d^<(1)> mod n are performed in parallel using two processors. Then we can obtain y by computing y Ξ y_0y_1 mod n. In general, the hamming weights of d^<(0)> and d^<(1)> are smaller than that of d. Thus a fast computation of the modular exponentiation y Ξ x^d mod n can be achieved. We describe a timing attack against RSA with and without the Chinese Remainder Theorem (CRT) using the parallel modular exponentiation. Both the secret exponents d_p = d mod p - 1 and d_q = d mod q - 1, where n = pq, are scattered into two partial exponents, respectively. We show that timing attacks are still applicable to that case.
2004-08-15