Spectral methods have been widely used in various fields of engineering and applied mathematics. In the field of computer arithmetic: data compression, polynomial multiplication and the spectral integer multiplication of Sch&uml / onhage and Strassen are among the most important successful utilization. Recent advancements in technology report the spectral methods may also be beneficial for modular operations heavily used in public key cryptosystems. In this study, we evaluate the use of spectral methods in modular multiplication. We carefully compare their timing performances with respect to the full return algorithms. Based on our evaluation, we introduce new approaches for spectral modular multiplication for polynomials and exhibit standard reduction versions of the spectral modular multiplication algorithm for polynomials eliminating the overhead of Montgomery&rsquo / s method. Moreover, merging the bipartite method and standard approach, we introduce the bipartite spectral modular multiplication to improve the hardware performance of spectral modular multiplication for polynomials. Finally, we introduce Karatsuba combined bipartite method for polynomials and its spectral version.

A new class of moduli called the low-weight polynomial form integers (LWPFIs) is introduced. LWPFIs are expressed in a low-weight, monic polynomial form, <em>p</em> = <em>f</em>(<em>t</em>). While the generalized Mersenne numbers (GMNs) proposed by Solinas allow only powers of two for <em>t</em>, LWPFIs allow any positive integers. In our first proposal of LWPFIs, we limit the coefficients of <em>f</em>(<em>t</em>) to be 0 and ±1, but later we extend LWPFIs to allow any integer of less than <em>t</em> for the coefficients of <em>f</em>(<em>t</em>). Modular multiplication using LWPFIs is performed in two phases: 1) polynomial multiplication in Z[<em>t</em>]/<em>f</em>(<em>t</em>) and 2) coefficient reduction. We present an efficient coefficient reduction algorithm based on a division algorithm derived from the Barrett reduction algorithm. We also show a coefficient reduction algorithm based on the Montgomery reduction algorithm. We give analysis and experimental results on modular multiplication using LWPFIs. <br /><br /> New three, four and five-way squaring formulae based on the Toom-Cook multiplication algorithm are presented. All previously known squaring algorithms are symmetric in the sense that the point-wise multiplication step involves only squarings. However, our squaring algorithms are asymmetric and use at least one multiplication in the point-wise multiplication step. Since squaring can be performed faster than multiplication, our asymmetric squaring algorithms are not expected to be faster than other symmetric squaring algorithms for large operand sizes. However, our algorithms have much less overhead and do not require any nontrivial divisions. Hence, for moderately small and medium size operands, our algorithms can potentially be faster than other squaring algorithms. Experimental results confirm that one of our three-way squaring algorithms outperforms the squaring function in GNU multiprecision library (GMP) v4. 2. 1 for certain range of input size. Moreover, for degree-two squaring in Z[<em>x</em>], our algorithms are much faster than any other squaring algorithms for small operands. <br /><br /> We present a side channel attack on XTR cryptosystems. We analyze the statistical behavior of simultaneous XTR double exponentiation algorithm and determine what information to gather to reconstruct the two input exponents. Our analysis and experimental results show that it takes <em>U</em>^{1. 25} tries, where <em>U</em> = max(<em>a</em>,<em>b</em>) on average to find the correct exponent pair (<em>a</em>,<em>b</em>). Using this result, we conclude that an adversary is expected to make <em>U</em>^{0. 625} tries on average until he/she finds the correct secret key used in XTR single exponentiation algorithm, which is based on the simultaneous XTR double exponentiation algorithm.

A new class of moduli called the low-weight polynomial form integers (LWPFIs) is introduced. LWPFIs are expressed in a low-weight, monic polynomial form, <em>p</em> = <em>f</em>(<em>t</em>). While the generalized Mersenne numbers (GMNs) proposed by Solinas allow only powers of two for <em>t</em>, LWPFIs allow any positive integers. In our first proposal of LWPFIs, we limit the coefficients of <em>f</em>(<em>t</em>) to be 0 and ±1, but later we extend LWPFIs to allow any integer of less than <em>t</em> for the coefficients of <em>f</em>(<em>t</em>). Modular multiplication using LWPFIs is performed in two phases: 1) polynomial multiplication in Z[<em>t</em>]/<em>f</em>(<em>t</em>) and 2) coefficient reduction. We present an efficient coefficient reduction algorithm based on a division algorithm derived from the Barrett reduction algorithm. We also show a coefficient reduction algorithm based on the Montgomery reduction algorithm. We give analysis and experimental results on modular multiplication using LWPFIs. <br /><br /> New three, four and five-way squaring formulae based on the Toom-Cook multiplication algorithm are presented. All previously known squaring algorithms are symmetric in the sense that the point-wise multiplication step involves only squarings. However, our squaring algorithms are asymmetric and use at least one multiplication in the point-wise multiplication step. Since squaring can be performed faster than multiplication, our asymmetric squaring algorithms are not expected to be faster than other symmetric squaring algorithms for large operand sizes. However, our algorithms have much less overhead and do not require any nontrivial divisions. Hence, for moderately small and medium size operands, our algorithms can potentially be faster than other squaring algorithms. Experimental results confirm that one of our three-way squaring algorithms outperforms the squaring function in GNU multiprecision library (GMP) v4. 2. 1 for certain range of input size. Moreover, for degree-two squaring in Z[<em>x</em>], our algorithms are much faster than any other squaring algorithms for small operands. <br /><br /> We present a side channel attack on XTR cryptosystems. We analyze the statistical behavior of simultaneous XTR double exponentiation algorithm and determine what information to gather to reconstruct the two input exponents. Our analysis and experimental results show that it takes <em>U</em>^{1. 25} tries, where <em>U</em> = max(<em>a</em>,<em>b</em>) on average to find the correct exponent pair (<em>a</em>,<em>b</em>). Using this result, we conclude that an adversary is expected to make <em>U</em>^{0. 625} tries on average until he/she finds the correct secret key used in XTR single exponentiation algorithm, which is based on the simultaneous XTR double exponentiation algorithm.

The aim of this dissertation is to improve computational efficiency of modular exponentiation-based public-key cryptosystems. The operational speed of these public-key cryptosystems is largely determined by the modular exponentiation operation of the form A = ge mod m where g is the base, e is the exponent and m is the modulus. The required modular exponentiation is computed by a series of modular multiplications. Optimized algorithms are required for various platforms, especially for lower-end platforms. These require the algorithms to be efficient and consume as little resources as possible. In these dissertation algorithms for integer multiplication, modular reduction and modular exponentiation, was developed and implemented in software, as required for public-key cryptography. A detailed analysis of these algorithms is given, as well as exact measurement of the computational speed achieved by each algorithm. This research shows that a total speed improvement of 13% can be achieved on existing modular exponentiation based public-key cryptosystems, in particular for the RSA cryptosystem. Three novel approaches are also presented for improving the decryption speed efficiency of the RSA algorithm. These methods focus on the selection of the decryption exponent by careful consideration of the difference between the two primes p and q. The resulting reduction of the decryption exponent improves the decryption speed by approximately 45%. / Dissertation (MEng (Electronics))--University of Pretoria, 2006. / Electrical, Electronic and Computer Engineering / unrestricted