Efficient architectures for modular exponentiation using Montgomery powering ladder
Yiruo He, Huapeng Wu · 2011
Side channel attacks have been considered as serious threats to certain public-key cryptosystems, such like RSA and elliptic curve system. For modular exponentiation for RSA and scalar multiplication for elliptic curve cryptosystems, Montgomery powering ladder has been shown to be a good choice for counter-measures against side-channel attacks. In this paper, two efficient architectures for modular exponentiation respectively using Montgomery powering ladder algorithm and m-ary powering ladder method are proposed. The first one is a straightforward and efficient implementation of the Montgomery powering ladder algorithm, in which the multiplication and squaring are performed in parallel during each clock cycle. A novel-designed two-by-two cross-point switch is used to select each ladder step. By parallelizing the Montgomery powering ladder using loop unrolling technique so that the number of loops is reduced by half, a second efficient architecture is proposed that requires only half number of clock cycles compared to the first one. The second proposed architecture realizes the m-ary Montgomery powering ladder for the case that the radix equals to 4.