Efficient and Constant Time Modular Reduction With Generalized Mersenne Primes
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 ef...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10788683/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 <inline-formula> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula> bit overflow may occur in the result such that <inline-formula> <tex-math notation="LaTeX">$\delta \ll n$ </tex-math></inline-formula>. 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 <inline-formula> <tex-math notation="LaTeX">$p\geq 2^{n}/(1+2^{-\delta +1})$ </tex-math></inline-formula>. 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. |
|---|---|
| ISSN: | 2169-3536 |