Efficient and Constant Time Modular Reduction With Generalized Mersenne Primes

Abstract

Many cryptographic applications require a vast number of modular multiplications with a large prime modulus. Generalized Mersennes are a class of primes commonly used in cryptography because of their special forms. When modulus is a generalized Mersenne prime, modular reductions can be calculated efficiently by several additions and subtractions thanks to their special forms. This work modifies the classical reduction algorithms for generalized Mersenne primes in the literature such that the additions and subtractions in these algorithms are performed in parallel from lower digits to higher digits, and the resulting carries and borrows are propagated together. Because calculated values can be negative, two's complement arithmetic is used in calculations. The proposed algorithms have substantial speed improvements over the classical algorithms in software. Also, because reduction modulo an n bit special prime p is performed by a series of n-bit additions and subtractions, a small delta bit overflow may occur in the result such that delta << n . Thus, a final reduction is needed after main reduction. In this work, we prove that the final reduction can be achieved by at most two subtractions where the modulus p >= 2(n)/(1+2(-delta+1)) . And, we show that this lower bound is satisfied by the special primes commonly used in cryptography including the generalized Mersenne primes in practical applications. The proposed modular reduction algorithms handle the final reduction by two subtractions in constant time to avoid timing attacks.