Title :
Speeding Up Big-Numbers Squaring
Author :
Gueron, Shay ; Krasnov, Vlad
Author_Institution :
Dept. of Math., Univ. of Haifa, Haifa, Israel
Abstract :
This paper deals with optimizations for big-numbers (multi-precision) squaring, and their efficient implementation on x86-64 platforms. Such optimizations have various usages, and a most prominent one is RSA acceleration, where big-numbers squaring consumes a significant portion of the computations. We introduce an algorithm for big-numbers squaring, that reduces the number of single precision add-with-carry operations, and trades several additions with a single left shift operation. When measured on the 2nd Generation Intel® Core™ processor, for 512-bit operands, our algorithm is roughly 1.4 times faster than the implementation of GMP library 5.0.2. For 1024-bit operands, our implementation is 1.2 times faster than that of the GMP library 5.0.2. Our optimization is used in a recently posted Open SSL patch [4] for accelerating modular exponentiation for RSA.
Keywords :
coprocessors; digital arithmetic; instruction sets; optimisation; public domain software; public key cryptography; reduced instruction set computing; 2nd Generation Intel® CoreTM processor; OpenSSL patch; RSA; big number squaring; bit operand; modular exponentiation; optimization; x86-64 platform; Acceleration; Algorithm design and analysis; Cryptography; Educational institutions; Libraries; Optimization; Vectors; RSA; multi-precision arithmetic;
Conference_Titel :
Information Technology: New Generations (ITNG), 2012 Ninth International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4673-0798-7
DOI :
10.1109/ITNG.2012.61
