Fault and simple power attack resistant RSA using Montgomery modular multiplication

Side channel attacks and more specifically fault, simple power attacks, constitute a pragmatic, potent mean of braking a cryptographic algorithm like RSA. For this reason, many researchers have proposed modifications on the arithmetic operation functions required for RSA in order to thwart those attacks. However, these modifications are applied on theoretic - algorithmic level and do not necessary result in high performance RSA designs. This paper constitute the first complete attempt for an efficient design approach on a fault and simple power attack resistant RSA based on the well known, for its high performance, Montgomery multiplication algorithm. To achieve this, a fault and simple power attack resistant modular exponentiation algorithm is proposed that is based on the Montgomery modular multiplication. In order to optimize this algorithm´s performance we also propose a modified version of Montgomery modular multiplication algorithm that employs value precomputation and carry save logic in all input, output and intermediate values. We introduce a hardware architecture based on the proposed Montgomery modular multiplication algorithm and use it as a building block for the design of a fault and simple power attack resistant modular exponentiation unit. This unit is optimized by taking advantage of the inherit parallelism in the proposed fault and simple power attack resistant modular exponentiation algorithm. Realizing the proposed unit in FPGA technology very advantageous results are found when compared against other well known designs even though our design bears an extra computation cost due to its fault and simple power attack resistance characteristic.