The Polynomial Modular Number System (PMNS) and the Residue Number System (RNS) are integer number systems which aim to speed up modular arithmetic. Their parallel properties make them suitable for the implementation of cryptographic applications on modern processors with SIMD instructions. In this work, we will show the implementation choices made for the modular multiplication in both systems and compare their implementation performances for several sizes of moduli. We target the Intel 64-bit sequential instruction set and the Intel AVX-512 vector instruction set. This instruction set allows significant speed-ups up to 1 621 bit size moduli, while the vectorized PMNS implementation is up to 2.5 times faster than the vectorized RNS, though the vectorized RNS becomes slightly better for 3 251 bits, due to the difficulty to find a PMNS with a suitable parameter$n$. The vectorized RNS implementations reach performance levels close the state-of-the-art GMP library, while the retired instruction counts are lower for sizes between 401 and 3 251 bits.

Presents the front cover, title page, cover page, or splash screen of the proceedings record.

The Polynomial Modular Number System (PMNS) is an integer number system designed to speed up arithmetic operations modulo a prime p. Such a system is defined by a tuple B = (p, n, γ, ρ, E) where E ε Z[X] and E(γ) = 0 mod p. In a PMNS, an element a of Z/pZ is represented by a polynomial A such that: A(γ) = a mod p, deg A <; n ||A||∞ <; p. In [6], the authors mentioned that PMNS can be highly redundant but they didn't really take advantage of this possibility. In this paper we use, for the first time, the redundancy of PMNS to protect algorithms against Side Channel Attacks (SCA). More precisely, we focus on elliptic curve cryptography. We show how to randomize the modular multiplication in order to be safe against existing SCA and we demonstrate the resistance of our construction. We describe the generation of a PMNS while guaranteeing, for all elements of Z/pZ, the minimum number of distinct representations we want. We also show how to reach all these representations.

In this paper, we improved the method proposed in [1] which was designed to detect errors in the elliptic curve scalar multiplication algorithm (ECSM). The algorithm we propose is SPA-secure and safe against recent data and instruction cache timing attacks.