Embedded Public-key Cryptosystems Via Enhanced Montgomery Multiplication

The Montgomery multiplication algorithm is one of the most efficient techniques used to speed up the modular multiplications required during exponentiation processes in public-key cryptography. In view of the expanding demand of embedded security services, this paper tackles the problem of efficiently supporting Montgomery´s method on inexpensive digital circuitry and focuses on the finely integrated product scanning (FIPS) variant of Montgomery´s multiplication. The proposed approach improves on the basic FIPS formulation by removing sources of inefficiencies, and boosts the exploitation of the computing resources in digital hardware. Experimental tests on different, commercial DSP devices demonstrate the benefits of the enhanced algorithm implementation and confirm both the method effectiveness in increasing efficiency and its general validity.