Self-randomized exponentiation algorithms

Exponentiation is a central process in many public-key cryptosystems such as RSA and DH. This paper introduces the concept of self-randomized exponentiation as an efficient means for preventing DPA-type attacks. Self-randomized exponentiation features several interesting properties: it is fully generic in the sense that it is not restricted to a particular exponentiation algorithm, it is parameterizable: a parameter allows to choose the best trade-off between security and performance; it can be combined with most other counter-measures; it is space-efficient as only an additional long-integer register is required; it is flexible in the sense that it does not rely on certain group properties; it does not require the prior knowledge of the order of the group in which the exponentiation is performed. All these advantages make our method particularly well suited to secure implementations of the RSA cryptosystem in standard mode, on constrained devices like smart cards.