Efficient regular modular exponentiation using multiplicative half-size splitting

Authors

Christophe Negre, Universite de Perpignan
Thomas Plantard, University of WollongongFollow

RIS ID

115980

Publication Details

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

Abstract

In this paper, we consider efficient RSA modular exponentiations x K mod N 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-andmultiply 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.