Skip to main content
placeholder image

Efficient modular exponentiation based on multiple multiplications by a common operand

Conference Paper


Download full-text (Open Access)

Abstract


  • The main operation in RSA encryption/decryption is the modular exponentiation, which involves a long sequence of modular squarings and multiplications. In this paper, we propose to improve modular multiplications AB, AC which have a common operand. To reach this goal we modify the Montgomery modular multiplication in order to share common computations in AB and AC. We extend this idea to reduce the cost of multiple modular multiplications AB1,...,ABl by the same operand A. We then take advantage of these improvements in the Montgomery-ladder and SPA resistant m-ary exponentiation algorithms. The complexity analysis shows that for an RSA modulus of size 2048 bits, the proposed improvements reduce the number of word operations (ADD and MUL) by 14% for the Montgomery-ladder and by 5%-8% for the m-ary exponentiations. Our implementations show a speed-up by 8%-14% for the Montgomery-ladder and by 1%-8% for the m-ary exponentiations for modulus of size 1024, 2048 and 4048 bits.

UOW Authors


  •   Negre, Christophe (external author)
  •   Plantard, Thomas
  •   Robert, Jean-Marc (external author)

Publication Date


  • 2015

Citation


  • Negre, C., Plantard, T. & Robert, J. (2015). Efficient modular exponentiation based on multiple multiplications by a common operand. In J. Muller, A. Tisserand & J. Villalba (Eds.), Proceedings of the 2015 IEEE Symposium on Computer Arithmetic (ARITH 22) (pp. 144-151). Piscataway, New Jersey, United States: IEEE.

Scopus Eid


  • 2-s2.0-84952330957

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=6049&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/5022

Start Page


  • 144

End Page


  • 151

Place Of Publication


  • http://arith22.gforge.inria.fr/

Abstract


  • The main operation in RSA encryption/decryption is the modular exponentiation, which involves a long sequence of modular squarings and multiplications. In this paper, we propose to improve modular multiplications AB, AC which have a common operand. To reach this goal we modify the Montgomery modular multiplication in order to share common computations in AB and AC. We extend this idea to reduce the cost of multiple modular multiplications AB1,...,ABl by the same operand A. We then take advantage of these improvements in the Montgomery-ladder and SPA resistant m-ary exponentiation algorithms. The complexity analysis shows that for an RSA modulus of size 2048 bits, the proposed improvements reduce the number of word operations (ADD and MUL) by 14% for the Montgomery-ladder and by 5%-8% for the m-ary exponentiations. Our implementations show a speed-up by 8%-14% for the Montgomery-ladder and by 1%-8% for the m-ary exponentiations for modulus of size 1024, 2048 and 4048 bits.

UOW Authors


  •   Negre, Christophe (external author)
  •   Plantard, Thomas
  •   Robert, Jean-Marc (external author)

Publication Date


  • 2015

Citation


  • Negre, C., Plantard, T. & Robert, J. (2015). Efficient modular exponentiation based on multiple multiplications by a common operand. In J. Muller, A. Tisserand & J. Villalba (Eds.), Proceedings of the 2015 IEEE Symposium on Computer Arithmetic (ARITH 22) (pp. 144-151). Piscataway, New Jersey, United States: IEEE.

Scopus Eid


  • 2-s2.0-84952330957

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=6049&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/5022

Start Page


  • 144

End Page


  • 151

Place Of Publication


  • http://arith22.gforge.inria.fr/