Top

Journal of Cryptographic Engineering

Published in:

06-01-2020 | Regular Paper

Efficient modular operations using the adapted modular number system

Authors: Laurent-Stéphane Didier, Fangan-Yssouf Dosso, Pascal Véron

Published in: Journal of Cryptographic Engineering | Issue 2/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The adapted modular number system (AMNS) is an integer number system which aims to speed up arithmetic operations modulo a prime p. Such a system is defined by a tuple \((p, n, \gamma , \rho , E)\), where p, n, \(\gamma \) and \(\rho \) are integers and \(E\in \mathbb {Z}[X]\). In El Mrabet and Gama (in: WAIFI, lecture notes in computer science, Springer, 2012) conditions required to build AMNS with \(E(X)=X^n + 1\) are provided. In this paper, we generalise their approach and provide a method to generate multiple AMNS for a given prime p with \(E(X)=X^n-\lambda \) and \(\lambda \in \mathbb {Z}{\setminus }\{0\}\). Moreover, we propose a complete set of algorithms without conditional branching to perform arithmetic and conversion operations in the AMNS, using a Montgomery-like method described in Negre and Plantard (in: Information security and privacy, 13th Australasian conference, ACISP 2008, Wollongong, Australia, 2008). We show that our implementation outperforms GNU MP and OpenSSL libraries. Finally, we highlight some properties of the AMNS which state that it could lead to a helpful countermeasure against some side-channel attacks.

previous article Faster modular arithmetic for isogeny-based crypto on embedded devices

next article Applications of machine learning techniques in side-channel attacks: a survey

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Abarzúa, R., Valencia, C., López, J.: Survey for performance and security problems of passive side-channel attacks countermeasures in ECC. Cryptology ePrint Archive, Report 2019/010 (2019)

Antão, S., Bajard, J.C., Sousa, L.: RNS based elliptic curve point multiplication for massive parallel architectures. Comput. J. 55(5), 629–647 (2012)CrossRef

Bajard, J.C., Duquesne, S., Ercegovac, M.: Combining leak-resistant arithmetic for elliptic curves defined over \(f_p\). Publications Mathématiques de Besançon. Algrèbre et Théorie des Nombres, pp. 67–87 (2013). ISSN: 1958-7236

Bajard, J.C., Eynard, J., Hasan, A., Zucca, V.: A full RNS variant of fv like somewhat homomorphic encryption schemes. In: SAC 2016, Selected Areas in Cryptography. St. John’s, Newfoundland and Labrador, Canada (2016)

Bajard, J.C., Imbert, L.: A full RNS implementation of RSA. IEEE Trans. Comput. 53(6), 769–774 (2004)CrossRef

Bajard, J.C., Imbert, L., Liardet, P.Y., Teglia, Y.: Leak resistant arithmetic. In: Workshop on Cryptographic Hardware and Embedded Systems CHES 2004. Cambridge (Boston), USA. Lecture Notes in Computer Science, pp. 62–75. Springer (2004)

Bajard, J.C., Imbert, L., Plantard, T.: Modular number systems: beyond the Mersenne family. In: 11th International Workshop, Selected Areas in Cryptography, SAC 2004, Waterloo, Canada, pp. 159–169 (2004)

Bajard, J.C., Imbert, L., Plantard, T.: Arithmetic operations in the polynomial modular number system. In: 17th IEEE Symposium on Computer Arithmetic (ARITH-17) 2005, Cape Cod, MA, USA, pp. 206–213 (2005). Extended (complete) version: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00109201/document. Accessed 2 Jan 2020

Baldi, M.: QC-LDPC Code-Based Cryptography. SpringerBriefs in Electrical and Computer Engineering. Springer, Berlin (2014)

10.

Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Odlyzko, A.M. (ed.) Advances in Cryptology—CRYPTO’86, pp. 311–323. Springer, Berlin (1987)

11.

Didier, L.S., Dosso, F.Y., El Mrabet, N., Marrez, J., Véron, P.: Randomization of arithmetic over polynomial modular number system. In: 26th IEEE International Symposium on Computer Arithmetic, vol. 1, pp. 199–206. Kyoto, Japan (2019). https://doi.org/10.1109/ARITH.2019.00048

12.

El Mrabet, N., Gama, N.: Efficient multiplication over extension fields. In: WAIFI. Lecture Notes in Computer Science, vol. 7369, pp. 136–151. Springer (2012)

13.

El Mrabet, N., Nègre, C.: Finite field multiplication combining AMNS and DFT approach for pairing cryptography. In: ACISP. Lecture Notes in Computer Science, vol. 5594, pp. 422–436. Springer (2009)

14.

Garner, H.L.: The residue number system. IRE Trans. Electr. Comput. EL 8(6), 140–147 (1959)CrossRef

15.

Gathen, J.V.Z., Hartlieb, S.: Factoring modular polynomials. J. Symb. Comput. 26(5), 583–606 (1998)MathSciNetCrossRef

16.

Goubin, L.: A refined power-analysis attack on elliptic curve cryptosystems. In: International Workshop on Public Key Cryptography, pp. 199–211. Springer (2003)

17.

Granlund, T., et al.: GNU multiple precision arithmetic library 6.1.2 (2016). https://gmplib.org/. Accessed 2 Jan 2020

18.

Horner, W.G.: A new method of solving numerical equations of all orders, by continuous approximation. Philos. Trans. R. Soc. Lond. 109, 308–335 (1819)

19.

Johnston, A.M.: A generalized qth root algorithm. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA’99, Society for Industrial and Applied Mathematics, pp. 929–930 (1999)

20.

Joye, M., Tymen, C.: Protections against differential analysis for elliptic curve cryptography—an algebraic approach. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2001, pp. 377–390. Springer, Berlin (2001)

21.

Kocher, P.C.: Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) Advances in Cryptology—CRYPTO’96, pp. 104–113. Springer, Berlin (1996)

22.

Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: CRYPTO. Lecture Notes in Computer Science, vol. 1666, pp. 388–397. Springer (1999)

23.

Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534 (1982)MathSciNetCrossRef

24.

Mishra, B.: Algorithmic Algebra. Springer, Berlin (1993)CrossRef

25.

Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)MathSciNetCrossRef

26.

Negre, C., Plantard, T.: Efficient modular arithmetic in adapted modular number system using Lagrange representation. In: Information Security and Privacy, 13th Australasian Conference, ACISP 2008, Wollongong, Australia, pp. 463–477 (2008)

27.

Plantard, T.: Arithmétique modulaire pour la cryptographie. Ph.D. thesis, Montpellier 2 University, France (2005)

28.

Project, T.O.: Openssl (1999). https://www.openssl.org/. Accessed 2 Jan 2020

29.

Shoup, V., et al.: NTL: a library for doing number theory (1990). https://www.shoup.net/ntl/. Accessed 2 Jan 2020

30.

Solinas, J., Fu, D.E.: Elliptic curve groups modulo a prime (ECP Groups) for IKE and IKEv2. RFC 5903 (2010). https://doi.org/10.17487/RFC5903. https://rfc-editor.org/rfc/rfc5903.txt. Accessed 2 Jan 2020

31.

Stein, W., et al.: Sagemath (2005). http://www.sagemath.org/index.html. Accessed 2 Jan 2020

Title: Efficient modular operations using the adapted modular number system
Authors: Laurent-Stéphane Didier
Fangan-Yssouf Dosso
Pascal Véron
Publication date: 06-01-2020
Publisher: Springer Berlin Heidelberg
Published in: Journal of Cryptographic Engineering / Issue 2/2020
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-019-00221-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2020

Deep learning for side-channel analysis and introduction to ASCAD database

Applications of machine learning techniques in side-channel attacks: a survey

A differential fault attack on the WG family of stream ciphers

Faster modular arithmetic for isogeny-based crypto on embedded devices

Premium Partner