Comparison of algorithms for factorization of large numbers having several distinct prime factors

• Autorzy: Kijko T. , Wroński M.

Warianty tytułu

PL

Porównanie algorytmów faktoryzacji dużych liczb posiadających kilka różnych czynników pierwszych

• Języki publikacji: EN

Abstrakty

EN

We present analysis of security of the most known assymetric algorythm RSA and its modern version MultiPrime RSA. We focused on more precisious estimations of time complexity of two factorization algorithms: Elliptic Curve Method and General Number Field Sieve. Additionally for the MultiPrime RSA algorithm we computed the maximal number of prime factors for given modulus length which does not decrease the security level.

PL

W artykule przedstawiamy analizę bezpieczeństwa powszechnie znanego algorytmu klucza publicznego RSA oraz jego następcy MultiPrime RSA. Skupiliśmy się na dokładniejszym wyznaczeniu oczekiwanego czasu faktoryzacji dużych liczb za pomocą dwóch algorytmów: Metody Krzywych Eliptycznych (ECM) i Ogólnego Sita Ciała Liczbowego (GNFS). Dodatkowo dla algorytmu MultiPrime RSA została obliczona maksymalna liczba czynników pierwszych dla danej długości modułu, która nie powoduje zmniejszenia bezpieczeństwa.

Słowa kluczowe

EN

factorization; MultiPrime RSA; ECM; GNFS; smoothness

PL

faktoryzacja; MultiPrime RSA; metoda krzywych eliptycznych; ogólne sito ciała liczbowego; B-gładkość

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 151--162
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Kijko T.

• Institute of Mathematics and Cryptology, Cybernetics Faculty, Military University of Technology, Warsaw, Poland

autor

Wroński M.

• Institute of Mathematics and Cryptology, Cybernetics Faculty, Military University of Technology, Warsaw, Poland

Bibliografia

• [1] I. F. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, Cambridge University Press, (1999).
• [2] J. Cilleruelo, J. Rue, P. Sarka, and A. Zumalacarregui, The least common multiple of sets of positive integers, ArXiv e-prints arXiv:1112.3013v1 [math.NT], (2011).
• [3] Compaq. Cryptography Using Compaq MultiPrime Technology in a Parallel Processing Environment, Compaq, (2000).
• [4] http://www.crypto-world.com/FactorRecords.html.
• [5] J. H. Ellis, The story of non-secret encryption, Available from http://cryptome.org/jya/ellisdoc.htm, (1997).
• [6] http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm.
• [7] P. Gaudry, A. Kruppa, F. Morain, L. Muller, E. Thom and P. Zimmermann, cado-nfs, An Implementation of the Number Field Sieve Algorithm, Release 1.1, available from http://cado-nfs.gforge.inria.fr/.
• [8] W. Geiselmann and R. Steinwandt, A Dedicated Sieving Hardware, In Public Key Cryptography, 6th International Workshop on Practice and Theory in Public Key Cryptography, PKC 2003 Proceedings, LNCS 2567, pp. 254–266, (2002).
• [9] A. Granville Smooth numbers: computational number theory and beyond, In Algorithmic Number Theory MSRI Publications, no. 44: pp. 267–323 (2008).
• [10] M. Jason Hinek, On the security of Multi – prime RSA. In J. Mathematical Cryptology, no. 2(2), pp 117–147 (2008).
• [11] A. K. Lenstra, Unbelievable Security. Matching AES Security Using Public Key Systems, In Advances in Cryptology - ASIACRYPT 2001, pp 67–86 (2001).
• [12] A. K. Lenstra, H. W. Lenstra, M. S. Manasse, and J. M. Pollard, The number field sieve, In Proc 22nd Annual ACM Symposium on the Theory of Computing, pp. 564–572 (1990).
• [13] A. K. Lenstra, A. Shamir, J. Tomlinson, and E. Tromer, Analysis of Bernstein’s Factorization Circuit. In Advances in Cryptology – ASIACRYPT 2002, pp. 1–26, (2002).
• [14] H. W. Lenstra, Factoring Integers with Elliptic Curves, In The Annals of Mathematics 126 : pp. 649–673 (1987).
• [15] C. Pomerance, Smooth numbers and the quadratic sieve, In Algorithmic Number Theory MSRI Publications, no. 44 : pp. 69–81 (2008).
• [16] S. Singh, Code book. Delacorte Press, pp. 21–220 (2002).
• [17] I. Tolkov, Counting points on elliptic curves: Hasse’s theorem and recent developments, http://igor.tolkov.com/essays/336paper.pdf, (2009).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).