Compact implementation of modular multiplication for special modulus on MSP430X. (English) Zbl 1433.94093

Seo, Hwajeong; An, Kyuhwang; Kwon, Hyeokdong; Hu, Zhi

Lee, Kwangsu (ed.), Information security and cryptology – ICISC 2018. 21st international conference, Seoul, South Korea, November 28–30, 2018. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11396, 55-66 (2019).

Summary: For the pre/post-quantum public key cryptography (PKC), such as elliptic curve cryptography (ECC) and supersingular isogeny Diffie-Hellman key exchange (SIDH), modular multiplication is the most expensive operation among basic arithmetic of these cryptographic schemes. For this reason, the execution timing of such cryptographic schemes in an implementation level, which may highly determine the service availability for the low-end microprocessors (e.g., 8-bit AVR and 16-bit MSP430X), is mainly relied on the efficiency of modular multiplication on the target processors.{
}In this paper, we present new optimal modular multiplication techniques based on interleaved Montgomery multiplication on 16-bit MSP430X microprocessors, where the multiplication part is performed in a hardware multiplier and the reduction part is performed in a basic arithmetic logic unit (ALU) with optimal modular multiplication routine, respectively. This approach is effective for special modulus of NIST curves, SM2 curves, and SIDH. In order to demonstrate the superiority of proposed Montgomery multiplication, we applied the proposed method to the NIST P-256 curve, of which the implementation improves the previous modular multiplication and squaring operations by 39% and 37.1% on 16-bit MSP430X microprocessors, respectively. Moreover, secure countermeasures against timing attack and simple power analysis is also applied to the scalar multiplication of NIST P-256, which achieves the 9,285,578 clock cycles and only requires 0.575 s (@16 MHz). The proposed Montgomery multiplication has broad applications to other cryptographic schemes and microprocessors.
For the entire collection see [Zbl 1407.68039].

MSC:

94A60

Cryptography

Keywords:

Montgomery multiplication; public key cryptography; MSP430X; software implementation

Software:

MSP430X