{"title":"An Efficient Architecture for Interleaved Modular Multiplication","authors":"Ahmad M. Abdel Fattah, Ayman M. Bahaa El-Din, Hossam M.A. Fahmy","country":null,"institution":"","volume":32,"journal":"International Journal of Computer and Information Engineering","pagesStart":2129,"pagesEnd":2134,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/2464","abstract":"Modular multiplication is the basic operation\r\nin most public key cryptosystems, such as RSA, DSA, ECC,\r\nand DH key exchange. Unfortunately, very large operands\r\n(in order of 1024 or 2048 bits) must be used to provide\r\nsufficient security strength. The use of such big numbers\r\ndramatically slows down the whole cipher system, especially\r\nwhen running on embedded processors.\r\nSo far, customized hardware accelerators - developed on\r\nFPGAs or ASICs - were the best choice for accelerating\r\nmodular multiplication in embedded environments. On the\r\nother hand, many algorithms have been developed to speed\r\nup such operations. Examples are the Montgomery modular\r\nmultiplication and the interleaved modular multiplication\r\nalgorithms. Combining both customized hardware with\r\nan efficient algorithm is expected to provide a much faster\r\ncipher system.\r\nThis paper introduces an enhanced architecture for computing\r\nthe modular multiplication of two large numbers X\r\nand Y modulo a given modulus M. The proposed design is\r\ncompared with three previous architectures depending on\r\ncarry save adders and look up tables. Look up tables should\r\nbe loaded with a set of pre-computed values. Our proposed\r\narchitecture uses the same carry save addition, but replaces\r\nboth look up tables and pre-computations with an enhanced\r\nversion of sign detection techniques. The proposed architecture\r\nsupports higher frequencies than other architectures.\r\nIt also has a better overall absolute time for a single operation.","references":null,"publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 32, 2009"}