Abstract
We present a new algorithm for residue multiplication modulo the Mersenne prime \(p=2^{521}-1\) based on the Toeplitz matrix-vector product. For this modulus, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of Granger and Scott presented in Public Key Cryptography (PKC) 2015. We have implemented three versions of our algorithm to provide an extensive comparison — according to the best of our knowledge — with respect to the well-known algorithms and to show the robustness of our algorithm for this 521-bit Mersenne prime modulus. Each version is having less number of operations than its counterpart. On our machine, Intel Pentium CPU G2010 @ 2.80 GHz machine with gcc 5.3.1 compiler, we find that for each version of our algorithm modulus p is more efficient than modulus 2p. Hence, by using Granger and Scott code, constant-time variable-base scalar multiplication, for modulus p we find 1, 251, 502 clock cycles for P-521 (NIST and SECG curve) and 1, 055, 105 cycles for E-521 (Edwards curve). While, on the same machine the clock cycles counts of Granger-Scott code (modulus 2p) for P-521 and E-521 are 1, 332, 165 and 1, 148, 871 respectively.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
- 4.
- 5.
References
Bernstein, D.J., Chuengsatiansup, C., Lange, T.: Curve41417: Karatsuba revisited. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 316–334. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44709-3_18
Bodrato, M.: Towards optimal toom-cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 116–133. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73074-3_10
Certicom Research. SEC 2: recommended elliptic curve domain parameters. In: Proceeding of Standards for Efficient Cryptography, Version 2.0, 27 January 2010
Fan, H., Hasan, M.A.: A new approach to subquadratic space complexity parallel multipliers for extended binary fields. IEEE Trans. Comput. 56(2), 224–233 (2007)
FIPS PUB 186-4: Federal information processing standards publication. Digital Signature Standard (DSS), Information Technology Laboratory, National Institute of Standards and Technology (NIST), Gaithersburg, MD 20899-8900, July 2013
Granger, R., Scott, M.: Faster ECC over \(\mathbb{F}_{2^{521}-1}\). In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 539–553. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46447-2_24
Paoloni, G.: How to benchmark code execution times on Intel IA-32 and IA-64 instruction set architectures, p. 123. Intel Corporation, September 2010
Weimerskirch, A., Paar, C.: Generalizations of the Karatsuba algorithm for efficient implementations. In: IACR Cryptology ePrint Archive 2006, p. 224 (2006)
Acknowledgments
We are very thankful to Michael Scott for answering our questions related to implementation. This work is supported by TÜBİTAK under Grant No. BIDEB-114C052 and EEEAG-115R289.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Ali, S., Cenk, M. (2017). A New Algorithm for Residue Multiplication Modulo \(2^{521}-1\) . In: Hong, S., Park, J. (eds) Information Security and Cryptology – ICISC 2016. ICISC 2016. Lecture Notes in Computer Science(), vol 10157. Springer, Cham. https://doi.org/10.1007/978-3-319-53177-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-53177-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53176-2
Online ISBN: 978-3-319-53177-9
eBook Packages: Computer ScienceComputer Science (R0)