Paper 2015/465

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

Hwajeong Seo, Zhe Liu, 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Public-key cryptographyModular arithmeticSIMD-level parallelismVector instructionsARM-NEONRSA
Contact author(s)
hwajeong84 @ gmail com
History
2015-05-20: last of 3 revisions
2015-05-17: received
See all versions
Short URL
https://ia.cr/2015/465
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/465,
      author = {Hwajeong Seo and Zhe Liu and Johann Groschadl and Howon Kim},
      title = {Efficient Arithmetic on ARM-NEON and Its Application for High-Speed RSA Implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2015/465},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/465}},
      url = {https://eprint.iacr.org/2015/465}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.