Tripartite modular multiplication

详细信息    查看全文

• 作者：Kazuo Sakiyama^a ; ^b ; ^{saki@ice.uec.ac.jp"" rel=""nofollow} ; Miroslav Knež ; ević ; ^a ; ^{miroslav.knezevic@esat.kuleuven.be"" rel=""nofollow} ; Junfeng Fan^a ; ^{junfeng.fan@esat.kuleuven.be"" rel=""nofollow} ; Bart Preneel^a ; ^{bart.preneel@esat.kuleuven.be"" rel=""nofollow} ; Ingrid Verbauwhede^a ; ^{ingrid.verbauwhede@esat.kuleuven.be"" rel=""nofollow} [Author vitae]
• 关键词：Modular multiplication ; Barrett reduction ; Karatsuba multiplication ; Montgomery reduction ; Public-key cryptography
• 刊名：Integration, the VLSI Journal
• 出版年：2011
• 出版时间：September 2011
• 年：2011
• 卷：44
• 期：4
• 页码：259-269
• 全文大小：804 K

文摘

This paper presents a new modular multiplication algorithm that allows one to implement modular multiplications efficiently. It proposes a systematic approach for maximizing a level of parallelism when performing a modular multiplication. The proposed algorithm effectively integrates three different existing algorithms, a classical modular multiplication based on Barrett reduction, the modular multiplication with Montgomery reduction and the Karatsuba multiplication algorithms in order to reduce the computational complexity and increase the potential of parallel processing. The algorithm is suitable for both hardware implementations and software implementations in a multiprocessor environment. To show the effectiveness of the proposed algorithm, we implement several hardware modular multipliers and compare the area and performance results. We show that a modular multiplier using the proposed algorithm achieves a higher speed comparing to the modular multipliers based on the previously proposed algorithms.