Skip to main content
placeholder image

Efficient regular modular exponentiation using multiplicative half-size splitting

Journal Article


Abstract


  • In this paper, we consider efficient RSA modular exponentiations xKmodN which are regular and constant time. We first review the multiplicative splitting of an integer x modulo N into two half-size integers. We then take advantage of this splitting to modify the square-and-multiply exponentiation as a regular sequence of squarings always followed by a multiplication by a half-size integer. The proposed method requires around 16 % less word operations compared to Montgomery-ladder, square-always and square-and-multiply-always exponentiations. These theoretical results are validated by our implementation results which show an improvement by more than 12 % compared approaches which are both regular and constant time.

Publication Date


  • 2017

Citation


  • Negre, C. & Plantard, T. (2017). Efficient regular modular exponentiation using multiplicative half-size splitting. Journal of Cryptographic Engineering, 7 (3), 245-253.

Scopus Eid


  • 2-s2.0-85027721051

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers1/695

Number Of Pages


  • 8

Start Page


  • 245

End Page


  • 253

Volume


  • 7

Issue


  • 3

Place Of Publication


  • Germany

Abstract


  • In this paper, we consider efficient RSA modular exponentiations xKmodN which are regular and constant time. We first review the multiplicative splitting of an integer x modulo N into two half-size integers. We then take advantage of this splitting to modify the square-and-multiply exponentiation as a regular sequence of squarings always followed by a multiplication by a half-size integer. The proposed method requires around 16 % less word operations compared to Montgomery-ladder, square-always and square-and-multiply-always exponentiations. These theoretical results are validated by our implementation results which show an improvement by more than 12 % compared approaches which are both regular and constant time.

Publication Date


  • 2017

Citation


  • Negre, C. & Plantard, T. (2017). Efficient regular modular exponentiation using multiplicative half-size splitting. Journal of Cryptographic Engineering, 7 (3), 245-253.

Scopus Eid


  • 2-s2.0-85027721051

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers1/695

Number Of Pages


  • 8

Start Page


  • 245

End Page


  • 253

Volume


  • 7

Issue


  • 3

Place Of Publication


  • Germany