nach oben

Journal of Cryptographic Engineering

Erschienen in:

22.02.2017 | Special Issue on Montgomery Arithmetic

Spectral arithmetic in Montgomery modular multiplication

verfasst von: Wangchen Dai, Ray C. C. Cheung

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 3/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Modular multiplication is considered to be the most computation-intensive operation for cryptographic algorithms involving large operands, such as RSA and Diffie–Hellman. Their key sizes have been increased significantly in recent decades to provide sufficient cryptographic strength. Thus, large integer modular multiplication algorithm with high efficiency is in demand. Montgomery modular multiplication (MMM) integrated by the spectral arithmetic can be a suitable solution. This is because MMM eliminates the time-consuming trail division, while the spectral arithmetic can speed up the integer multiplications from quadratic time to linearithmic time. This survey paper introduces the development of spectral-based MMM, as well as its two important properties: high parallelism and low complexity. Besides, different algorithms are explored to demonstrate how each of them benefits the modular multiplication. Moreover, we also compare these algorithms in terms of digit-level complexity and provide general ideas about algorithm selection when implementing modular multiplication with 1024-bit operand size and above.

Vorheriger Artikel Montgomery inversion

Nächster Artikel Montgomery curves and their arithmetic

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Chen, D.D., Yao, G.X., Cheung, R.C.C., Pao, D., Koç, Ç.K.: Parameter space for the architecture of FFT-based Montgomery modular multiplication. IEEE Trans. Comput. 65(1), 147–160 (2016)MathSciNetCrossRef

Pöppelmann, T., Güneysu, T.: Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware. In: International Conference on Cryptology and Information Security in Latin America. Springer, pp. 139–158 (2012)

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, pp. 1–23 (2010)

Güneysu, T., Lyubashevsky, V., Pöppelmann, T.: Practical lattice-based cryptography: a signature scheme for embedded systems. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer, pp. 530–547 (2012)

Cao, X., Moore, C., ONeill, M., Hanley, N., OSullivan, E.: High-speed fully homomorphic encryption over the integers. In: International Conference on Financial Cryptography and Data Security. Springer, pp. 169–180 (2014)

Van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, pp. 24–43 (2010)

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

Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Conference on the Theory and Application of Cryptographic Techniques. Springer, pp. 311–323 (1986)

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRef

10.

Rivest, R.L.: A description of a single-chip implementation of the RSA Cipher. Lambda, vol. 1, no. Fourth Quarter, pp. 14–18 (1980)

11.

Barker, E., Barker, W., Burr, W., Polk, W., Smid, M., Gallagher, P.D., et al.: NIST special publication 800-57 recommendation for key management—part 1: general (2012)

12.

Knuth, D.E.: Fundamental algorithms: the art of computer programming (1973)

13.

Karatsuba, A., Ofman, Y.: Multiplication of multidigit numbers on automata. In: Soviet Physics Doklady, vol. 7, p. 595 (1963)

14.

Cook, S.A., Aanderaa, S.O.: On the minimum computation time of functions. Transactions of the American Mathematical Society, pp. 291–314 (1969)MathSciNetCrossRef

15.

Schönhage, A., Strassen, V.: Schnelle multiplikation großer zahlen. Computing 7(3–4), 281–292 (1971)MathSciNetCrossRef

16.

Fürer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979–1005 (2009)MathSciNetCrossRef

17.

Harvey, D., Van Der Hoeven, J., Lecerf, G.: Even faster integer multiplication. J. Complex. 36(10), 1–30 (2016)MathSciNetCrossRef

18.

Covanov, S., Thomé, E.: Fast arithmetic for faster integer multiplication (2015). ArXiv preprint arXiv:1502.02800

19.

Walter, C.D.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35(21), 1831–1832 (1999)CrossRef

20.

McLaughlin Jr., P.: New frameworks for Montgomery modular multiplication method. Math. Comput. 73(246), 899–906 (2004)MathSciNetCrossRef

21.

Phatak, D.S., Goff, T.: Fast modular reduction for large wordlengths via one linear and one cyclic convolution. In: Computer Arithmetic, 2005. ARITH-17 2005. 17th IEEE Symposium on. IEEE, pp. 179–186 (2005)

22.

Saldamlı, G., Koç, Ç.K.: Spectral modular exponentiation. In: Computer Arithmetic, 2007. ARITH’07. 18th IEEE Symposium on. IEEE, pp. 123–132 (2007)

23.

David, J.P., Kalach, K., Tittley, N.: Hardware complexity of modular multiplication and exponentiation. IEEE Trans. Comput. 56(10), 1308–1319 (2007)MathSciNetCrossRef

24.

Dai, W., Chen, D., Cheung, R.C.C., Koç, Ç.K.: Area-time efficient architecture of FFT-based Montgomery multiplication. IEEE Trans. Comput. 66(3), 375–388 (2017)MathSciNetCrossRef

25.

Nussbaumer, H.J.: Fast Fourier transform and convolution algorithms. Springer, Berlin (1982)CrossRef

26.

Pollard, J.M.: The fast Fourier transform in a finite field. Math. Comput. 25(114), 365–374 (1971)MathSciNetCrossRef

27.

Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90), 297–301 (1965)MathSciNetCrossRef

28.

Crandall, R., Fagin, B.: Discrete weighted transforms and large-integer arithmetic. Math. Comput. 62(205), 305–324 (1994)MathSciNetCrossRef

29.

Bernstein, D.J.: Multidigit multiplication for mathematicians. Adv. Appl. Math. 1–19 (2001)

30.

Granlund, T.: The GMP development team: the GNU multiple precision arithmetic library 6.1.0 edn. (2015)

31.

Saldamlı, G.: Spectral Modular Arithmetic. PhD Thesis (2005)

32.

Koç, Ç.K., Acar, T., Kaliski, B.S.: Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro 16(3), 26–33 (1996)CrossRef

33.

Smart, N., Babbage, S., Catalano, D., Cid, C., Weger, B.D., Dunkelman, O., Ward, M.: ECRYPT II yearly report on algorithms and keysizes (2011–2012). European Network of Excellence in Cryptology (ECRYPT II), Sept (2012)

34.

Zimmermann, R.: Efficient VLSI implementation of modulo (\(2^n\pm 1\)) addition and multiplication. In: Computer Arithmetic, 1999. Proceedings. 14th IEEE Symposium on. IEEE, pp. 158–167 (1999)

35.

Huang, M., Gaj, K., El-Ghazawi, T.: New hardware architectures for Montgomery modular multiplication algorithm. IEEE Trans. Comput. 60(7), 923–936 (2011)MathSciNetCrossRef

36.

Giorgi, P., Imbert, L., Izard, T.: Parallel modular multiplication on multi-core processors. In: Computer Arithmetic (ARITH), 2013 21st IEEE Symposium on. IEEE, pp. 135–142 (2013)

37.

Vetterli, M., Nussbaumer, H.J., et al.: Simple FFT and DCT algorithms with reduced number of operations. Signal Process. 6(4), 267–278 (1984)MathSciNetCrossRef

38.

Martens, J.B.: Recursive cyclotomic factorization new algorithm for calculating the discrete fourier transform. IEEE Trans. Acoust Speech Signal Process. 32(4), 750–761 (1984)MathSciNetCrossRef

39.

Duhamel, P., Hollmann, H.: Split-radix FFT algorithm. Electron. Lett. 20(1), 14–16 (1984)CrossRef

40.

Solinas, J.A.: Generalized Mersenne Numbers. Citeseer, Bielefeld (1999)

41.

Emmart, N., Weems, C.C.: High precision integer multiplication with a gpu using strassen’s algorithm with multiple FFT sizes. Parallel Process. Lett. 21(03), 359–375 (2011)MathSciNetCrossRef

42.

Wang, W., Huang, X.: A novel fast modular multiplier architecture for 8192-bit RSA cryposystem. In: High Performance Extreme Computing Conference (HPEC), 2013 IEEE. IEEE, pp. 1–5 (2013)

43.

Kumar, V., Selvakumar, D., Sobha, P.: Area and frequency optimized 1024 point radix-2 FFT processor on FPGA. In: VLSI Systems, Architecture, Technology and Applications (VLSI-SATA), 2015 International Conference on. IEEE, pp. 1–6 (2015)

44.

Doröz, Y., Öztürk, E., Sunar, B.: Accelerating fully homomorphic encryption in hardware. IEEE Trans. Comput. 64(6), 1509–1521 (2015)MathSciNetMATH

45.

Pöppelmann, T., Naehrig, M., Putnam, A., Macias, A.: Accelerating homomorphic evaluation on reconfigurable hardware. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer, pp. 143–163 (2015)

46.

Cao, X., Moore, C., Neill, M.O., Sullivan, E.O., Hanley, N.: Optimised multiplication architectures for accelerating fully homomorphic encryption

Titel: Spectral arithmetic in Montgomery modular multiplication
verfasst von: Wangchen Dai
Ray C. C. Cheung
Publikationsdatum: 22.02.2017
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Cryptographic Engineering / Ausgabe 3/2018
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-017-0151-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2018

Montgomery inversion

Montgomery curves and their arithmetic

Special issue in honor of Peter Lawrence Montgomery

Montgomery reduction within the context of residue number system arithmetic

Karatsuba-like formulae and their associated techniques

The Montgomery ladder on binary elliptic curves