Abstract: Generalised Mersenne Numbers (GMNs) were defined by Solinas in 1999 and feature in the NIST (FIPS 186-2) and SECG standards for use in elliptic curve cryptography. Their form is such that modular reduction is extremely efficient, thus making them an attractive choice for modular multiplication implementation. However, the issue of residue multiplication efficiency seems to have been overlooked. Asymptotically, using a cyclic rather than a linear convolution, residue multiplication modulo a Mersenne number is twice as fast as integer multiplication; this property does not hold for prime GMNs, unless they are of Mersenne's form. In this work we exploit an alternative generalisation of Mersenne numbers for which an analogue of the above property --- and hence the same efficiency ratio --- holds, even at bitlengths for which schoolbook multiplication is optimal, while also maintaining very efficient reduction. Moreover, our proposed primes are abundant at any bitlength, whereas GMNs are extremely rare. Our multiplication and reduction algorithms can also be easily parallelised, making our arithmetic particularly suitable for hardware implementation. Furthermore, the field representation we propose also naturally protects against side-channel attacks, including timing attacks, simple power analysis and differential power analysis, which is essential in many cryptographic scenarios, in constrast to GMNs.
Recommendations
- scientific article; zbMATH DE number 175750
- Selected Areas in Cryptography
- Some properties of generalized Mersenne numbers
- On generalized Mersenne numbers, their interpretations and matrix generators
- On generalized Mersenne hybrid numbers
- On generalized Mersenne prime
- Generalized New Mersenne Number Transforms
- Generalized Mersenne numbers of the form cx²
- Mersenne Numbers
Cites work
- A Heuristic Asymptotic Formula Concerning the Distribution of Prime Numbers
- A method for obtaining digital signatures and public-key cryptosystems
- A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems
- Advances in Cryptology - EUROCRYPT 2004
- Advances in Elliptic Curve Cryptography
- Algorithms and Computation
- Cryptographic Hardware and Embedded Systems - CHES 2004
- Discrete Weighted Transforms and Large-Integer Arithmetic
- Distribution of generalized Fermat prime numbers
- Efficient techniques for high-speed elliptic curve cryptography
- Elliptic Curves and Primality Proving
- Endomorphisms for faster elliptic curve cryptography on a large class of curves
- Factoring integers with elliptic curves
- Factoring Repunits
- Faster Addition and Doubling on Elliptic Curves
- Generalized Repunit Primes
- High-speed high-security signatures
- scientific article; zbMATH DE number 1617927 (Why is no real title available?)
- scientific article; zbMATH DE number 1617931 (Why is no real title available?)
- scientific article; zbMATH DE number 5485460 (Why is no real title available?)
- scientific article; zbMATH DE number 176559 (Why is no real title available?)
- scientific article; zbMATH DE number 1349933 (Why is no real title available?)
- scientific article; zbMATH DE number 475430 (Why is no real title available?)
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- scientific article; zbMATH DE number 1500484 (Why is no real title available?)
- scientific article; zbMATH DE number 1504802 (Why is no real title available?)
- scientific article; zbMATH DE number 1504805 (Why is no real title available?)
- scientific article; zbMATH DE number 1504818 (Why is no real title available?)
- scientific article; zbMATH DE number 1557039 (Why is no real title available?)
- scientific article; zbMATH DE number 1759301 (Why is no real title available?)
- scientific article; zbMATH DE number 954401 (Why is no real title available?)
- scientific article; zbMATH DE number 2114384 (Why is no real title available?)
- scientific article; zbMATH DE number 1418307 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- Modular Multiplication Without Trial Division
- Public Key Cryptography - PKC 2006
- Selected Areas in Cryptography
- Some Primes of the Form (a n - 1)/(a - 1)
- Structure of parallel multipliers for a class of fields GF(2^ m)
- Sur certaines hypothèses concernant les nombres premiers
- Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems
- Topics in Cryptology – CT-RSA 2004
Cited in
(10)- A new algorithm for residue multiplication modulo \(2^{521}-1\)
- scientific article; zbMATH DE number 175750 (Why is no real title available?)
- scientific article; zbMATH DE number 2086877 (Why is no real title available?)
- On generalized Mersenne prime
- Routine controversies : Mathematical challenges in Mersenne's correspondence
- Selected Areas in Cryptography
- Selected Areas in Cryptography
- scientific article; zbMATH DE number 7653018 (Why is no real title available?)
- Faster integer multiplication using short lattice vectors
- Missing a trick: Karatsuba variations
This page was built for publication: Generalised Mersenne numbers revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326517)
