Paper 2012/140

Highly-Parallel Montgomery Multiplication for Multi-core General-Purpose Microprocessors

Selcuk Baktir and Erkay Savas

Abstract

Popular public key algorithms such as RSA and Diffie-Hellman key exchange, and more advanced cryptographic schemes such as Paillier's and Damgård-Jurik's algorithms (with applications in private information retrieval), require efficient modular multiplication with large integers of size at least 1024 bits. Montgomery multiplication algorithm has proven successful for modular multiplication of large integers. While general purpose multi-core processors have become the mainstream on desktop as well as portable computers, utilization of their computing resources have been largely overlooked when it comes to performing computationally intensive cryptographic operations. In this work, we propose a new parallel Montgomery multiplication algorithm which exhibits up to 39% better performance than the known best serial Montgomery multiplication variant for the bit-lengths of 2048 or larger. Furthermore, for bit-lengths of 4096 or larger, the proposed algorithm exhibits better performance utilizing multiple cores available. It achieves speedups of up to 81%, 3.37 times and 4.87 times for the used general-purpose microprocessors with 2, 4 and 6 cores, respectively. To our knowledge, this is the first work that shows with actual implementation results that Montgomery multiplication can be practically parallelized on general-purpose multi-core processors.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Montgomery multiplicationRSAmulti-core architecturesgeneral-purpose microprocessorsparallel algorithms
Contact author(s)
selcuk baktir @ bahcesehir edu tr
History
2012-03-22: received
Short URL
https://ia.cr/2012/140
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/140,
      author = {Selcuk Baktir and Erkay Savas},
      title = {Highly-Parallel Montgomery Multiplication for Multi-core General-Purpose Microprocessors},
      howpublished = {Cryptology ePrint Archive, Paper 2012/140},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/140}},
      url = {https://eprint.iacr.org/2012/140}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.