Fast and Parallel Modular Multiplication without Borrow for ECC on ARM-NEON

Fast reduction is a powerful modular reduction method for many ECC curves using NIST-style prime modulus. Based on fast reduction, existing vectorized modular multiplication schemes (such as MR and SMCOS) were constructed in succession. However, these schemes are only applicable to those NIST-style primes with just subtraction items. The vector design on fast reduction for ones with addition items (including certain well-known curves, NIST P-256 and SM2, etc.) rarely holds in practice because of the possible borrow situation. In this work, we fill this gap and propose a pipelined and vectorized fast reduction that, with the aid of pre-processing and post-processing, eliminates all potential borrow during the reduction. Based on the proposed reduction, we successfully construct a vectorized modular multiplication, namely Borrowless, which works with all NIST-style primes, including the ones with addition items. Using NIST P-256, SM2, and NIST P-224 curves as case studies, on the 32-bit ARM NEON platform, we demonstrate the effectiveness of Borrowless and its significant performance advantage over existing vector designs (e.g., CICOS and MR) and widely-used algorithm libraries (e.g., OpenSSL and GMP).