Regular 2 w -ary right-to-left exponentiation algorithm with very efficient DPA and FA countermeasures

With the growing demand of efficient cryptosystems, their secure implementations against various side-channel attacks and the fault attack are also requested from the practice. Several countermeasures are proposed so far, and this paper proposes a new regular 2 ^w -ary right-to-left exponentiation algorithm, which can be equipped with very efficient DPA (differential power attack) and FA (fault attack) countermeasures. Since its regular behavior clearly prevents the simple power analysis attack, the new algorithm gives a strong resistance to all the well-known major implementation attacks. This paper also gives a variant of the new algorithm for securely implementing the RSA cryptosystem with CRT (Chinese Remainder Theorem).