High-performance SoC-based implementation of modular exponentiation using evolutionary addition chains for efficient cryptography

Modular exponentiation is an important operation in several public-key cryptosystems. It is performed using successive modular multiplications. For the sake of efficiency, one needs to reduce the total number of required modular multiplications. This paper brings a novel idea based on the principles of ant colony optimization for finding a minimal addition chain that allows for the reduction of the number of modular multiplications required for modular exponentiations. Furthermore, we propose a hardware/software co-design of a system-on-chip implementation to efficiently compute modular exponentiations. The hardware sub-system implements the modular multiplication, which is the basic and time-consuming operation, while the software sub-system implements the search routine for the adequate operands this multiplication within previously computed products. The ant system is always in execution by an available co-processor, trying to improve the addition chain in use by the overall system. The best addition chain reached by the ant system is compared to the one used in the m-ary and sliding window methods as well as to the best addition chain evolved by genetic algorithms. We demonstrate that the ant system significantly outperforms all these methods for any exponent size. We provide a comparison of the proposed implementation with three existing ones using the performance factor, which takes into account both space and time requirements. (C) 2010 Elsevier B. V. All rights reserved.