A New Method for Fast Integer Multiplication and its Application to Cryptography
Michael Kounavis
International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2007)
San Diego, California (USA), July 16-18, 2007
SPECTS_Summary
We describe a novel technique for multiplying big numbers. Big number multiplication is used by popular public key cryptographic algorithms like RSA and key exchange techniques like ECDH. Our multiplication routines are generalizations of the well known Karatsuba algorithm. The novelty of our approach lies on the correlation between graph properties (i.e. vertices, edges and sub-graphs) and the Karatsuba-like terms of big number multiplication routines. Our approach is unique as it is the first known to us that can generate and use one iteration Karatsuba-like multiplication formulae for any given operand size which involve the same number of scalar multiplications as the generalized recursive Karatsuba technique, proposed by Weimerskirch and Paar in [2]. We present preliminary experimental data and results from spread-sheet analysis that show that our technique can boost the performance of public key and key exchange algorithms substantially. For example for 1024-bit RSA computations our technique offers a 30% gain which increases as the key size becomes larger.