Search

Abstract: 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. [Copyright &y& Elsevier]

Modular exponentiation is a basic operation in various applications, such as cryptography. Generally, the performance of this operation has a tremendous impact on the efficiency of the whole application. Therefore, many researchers have devoted special interest to providing smart methods and efficient implementations for modular exponentiation. One of these methods is the sliding-window method, which pre- processes the exponent into zero and non-zero partitions. Zero partitions allow for a reduction of the number of modular multiplications required in the exponentiation process. In this paper, we devise a novel hardware for computing modular exponentiation using the sliding-window method. The partitioning strategy used allows variable-length non-zero partitions, which increases the average number of zero partitions and so decreases that of non-zero partitions. It performs the partitioning process in parallel with the pre-computation step of the exponent so no overhead is introduced. The implementation is efficient when compared against related existing hardware implementations. [ABSTRACT FROM AUTHOR]

Abstract: 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. In this paper, we propose two efficient hardware implementations for computing modular exponentiations, which are based on the m-ary method. The m-ary method includes a power pre-computation step. The first design ignores the exponent and pre-computes all possible powers while the second takes advantage of the formation of the exponent to compute only those powers that are really necessary for the rest of the computation. As it can be expected, the implementation of the first architecture, compared with that of the second one, requires more time to complete an exponentiation. In compensation, however, the first should require less hardware area than the second. We provide a comparison of these two implementations using the performance factor, which takes into account both space and time requirements. [Copyright &y& Elsevier]

Abstract: Most of cryptographic systems are based on modular exponentiation, wherein the operands are considerably large. Generally, modular exponentiation is implemented using a chain of modular multiplications. One way of improving the throughput of a cryptographic system implementation is reducing the number of the required modular multiplications. Given the exponent, finding the minimal number of multiplications that are necessary to reach the exponentiation results is a hard problem. We take advantage of an evolutionary stochastic process, commonly called genetic algorithms, to compute minimal addition chains, allow us to reduce drastically the number of the required modular multiplications. In this paper, we investigate two different ways to implement modular exponentiation based on the evolved addition chain: the first approach consists of implementing all the exponentiation operation on hardware and the second approach combines software and hardware. While the first approach attempts to optimise the encryption/decryption throughput regardless of the cost of system implementation, the second attempts to reach a balance between the throughput and the cost of the implementation. [Copyright &y& Elsevier]

Generally speaking, public-key cryptographic systems consist of raising elements of some group such as GF(2n), Z/NZ or elliptic curves, to large powers and reducing the result modulo some given element. Such operation is often called modular exponentiation and is performed using modular multiplications repeatedly. The practicality of a given cryptographic system depends heavily on how fast modular exponentiations are performed. Consequently, it also depends on how efficiently modular multiplications are done as these are at the base of the computation. This problem has received much attention over the years. Software as well as hardware efficient implementation were proposed. However, the results are scattered through the literature. In this paper we survey most known and recent methods for efficient modular multiplication, investigating and examining their strengths and weaknesses. For each method presented, we provide an adequate hardware implementation. [ABSTRACT FROM AUTHOR]

In this paper, genetic programming is used as an alternative means to automatically generate secure and minimal hardware designs of public-key cryptosystems such as the RSA cryptosystem. We evolve optimal hardware circuits for modular exponentiation, which is a cornerstone operation in many public-key cryptographic system. The evolved circuits minimize both space (i.e. required gate number) and time (i.e. encryption and decryption time). The evolved designs are shielded against side-channel leakage and hence secure. The structure of the cryptographic circuit is random and so the private key cannot be deduced using known attacks. We compare our results against existing well-known designs, which were produced by human designers based on the binary method. [ABSTRACT FROM AUTHOR]