IEEE Access · 2020 · 29 citations · 14 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureCryptographyParallel ComputingCryptographic ImplementationData ParallelismHardware AccelerationModular ArithmeticParallel ArchitecturesParallel Computer ArchitectureCache AttacksExponentiation AlgorithmsInteger MultiplicationModular Arithmetic AlgorithmsModular MultiplicationModular Reduction AlgorithmsMulti-core ComputingResidue Number Systems
This paper reports a constant-time CPU and GPU software implementation of the RSA exponentiation by using algorithms that offer a first-line defense against timing and cache attacks. In the case of GPU platforms the modular arithmetic layer was implemented using the Residue Number System (RNS) representation. We also present a CPU implementation of an RNS-based arithmetic that takes advantage of the parallelism provided by the Advanced Vector Extensions 2 (AVX2) instructions. Moreover, we carefully analyze the performance of two popular RNS modular reduction algorithms when implemented on many- and multi-core platforms. In the case of CPU platforms we also report that a combination of the schoolbook and Karatsuba algorithms for integer multiplication along with Montgomery reduction, yields our fastest modular multiplication procedure. In comparison with previous literature, our software library achieves faster timings for the computation of the RSA exponentiation using 1024-, 2048- and 3072-bit private keys.
14
A Survey of General‐Purpose Computation on Graphics Hardware
John D. Owens, David Luebke, Naga K. Govindaraju et al. · Computer Graphics Forum · 2007 · 2K citations
Modular Multiplication Without Trial Division
Peter L. Montgomery · Mathematics of Computation · 1985 · 1.1K citations · Full text
Multiplication of Multidigit Numbers on Automata
Anatolij A. Karatsuba, Yu. Ofman · Soviet physics. Doklady · 1963 · 794 citations
David Adrian, Karthikeyan Bhargavan, Zakir Durumeric et al. · 2015 · 334 citations · Full text