Efficient implementation of modular multiplication on FPGAs based on sign detection
Ahmad Abdelfattah, Ayman Mohammad Bahaa-Eldin, Hossam Mahmoud Ahmad Fahmy · 2009
All public key cryptosystems, though being highly secure, have a common drawback: They require heavy computational effort. This is due to the reliance on modular multiplication of large operands (1024 bits or higher). The same problem arises in data encryption/decryption and digital signature schemes. Examples of such cryptosystems are RSA, DSA, and ECC. Now considering embedded platforms for applications of smart cards and smart tokens, the overall time performance of the cipher system becomes very slow. This refers to the limited computational power of the embedded processors. This paper introduces an enhanced architecture for computing the modular multiplication of two large numbers X and Y modulo a given modulus M. The proposed design can act as a co-processor for embedded general purpose CPUs. The proposed design is compared with three previous architectures depending on carry save adders and look up tables. Look up tables should be loaded with a set of pre-computed values. Our proposed architecture uses the same carry save addition, but replaces both look up tables and pre-computations with an enhanced version of sign detection techniques. The proposed architecture supports higher frequencies than other architectures. It also has a better overall absolute time for a single operation.