Cryptology ePrint Archive: Report 2015/465

Efficient Arithmetic on ARM-NEON and Its Application for High-Speed RSA Implementation

Hwajeong Seo and Zhe Liu and Johann Groschadl and Howon Kim

Abstract: Advanced modern processors support Single Instruction Multiple Data (SIMD) instructions (e.g. Intel-AVX, ARM-NEON) and a massive body of research on vector-parallel implementations of modular arithmetic, which are crucial components for modern public-key cryptography ranging from RSA, ElGamal, DSA and ECC, have been conducted. In this paper, we introduce a novel Double Operand Scanning (DOS) method to speed-up multi-precision squaring with non-redundant representations on SIMD architecture. The DOS technique partly doubles the operands and computes the squaring operation without Read-After-Write (RAW) dependencies between source and destination variables. Furthermore, we presented Karatsuba Cascade Operand Scanning (KCOS) multiplication and Karatsuba Double Operand Scanning (KDOS) squaring by adopting additive and subtractive Karatsuba's methods, respectively. The proposed multiplication and squaring methods are compatible with separated Montgomery algorithms and these are highly efficient for RSA crypto system. Finally, our proposed multiplication/squaring, separated Montgomery multiplication/squaring and RSA encryption outperform the best-known results by 22/41\%, 25/33\% and 30\% on the Cortex-A15 platform.

Category / Keywords: implementation / Public-key cryptography, Modular arithmetic, SIMD-level parallelism, Vector instructions, ARM-NEON, RSA

Date: received 15 May 2015, last revised 19 May 2015

Contact author: hwajeong84 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150520:011856 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]