Download pdf
Evaluating RSA encryption: Primality testing, pollard’s algorithms, and security challenges
- 1 University of Nottingham Ningbo China
* Author to whom correspondence should be addressed.
Abstract
In the dynamic realm of cryptography, Rivest, Shamir, and Adleman (RSA) encryption stands as a pivotal element in ensuring secure communications. This analysis offers a detailed exploration of RSA encryption, emphasizing critical aspects such as primality testing, the intricacies of Pollard’s factorization algorithms, and the overarching security challenges intrinsic to this prevalent encryption paradigm. Delving deep into the heart of RSA, the research underscores the paramount role of primality testing in the RSA key generation process and critically evaluates the efficiency and reliability of diverse primality test methodologies. Moreover, it navigates the potential pitfalls introduced by Pollard’s algorithms and ponders their consequential implications for RSA’s security matrix. Beyond these technicalities, the analysis brings to the forefront a spectrum of security challenges besieging RSA. This encompasses nuances like vulnerabilities arising from diminutive private keys, pitfalls linked to common modulus attacks, and susceptibilities stemming from cache timing discrepancies. By illuminating both the robust facets and inherent vulnerabilities of RSA encryption, this scholarly work elevates the current narrative on cryptographic security. It accentuates the perpetual necessity for meticulous scrutiny and agile adaptability in the quest to shield sensitive digital information in our progressively interconnected world.
Keywords
Fermat’s Little Theory, Rabin-Miller Test, Pollard’s Rho, Pollard’s p-1
[1]. Milanov, E. (2009). The RSA algorithm. RSA laboratories, 1-11.
[2]. Barnes, C. (2004). Integer factorization algorithms. Oregon State University.
[3]. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
[4]. Boneh, D., & Shacham, H. (2004). Fast Variants of RSA. Cryptology ePrint Archive, Report 2004/086.
[5]. Schindler, W., & Wagner, D. (2005). Cryptanalysis of the RSA Implementations of Crypto‐Coprocessors. Cryptographic Hardware and Embedded Systems, 1-12.
[6]. Boneh, D., & Venkatesan, R. (1998). Breaking RSA may not be equivalent to factoring. In Advances in Cryptology—EUROCRYPT’98: International Conference on the Theory and Application of Cryptographic Techniques Espoo, Finland, May 31–June 4, 1998 Proceedings 17 (pp. 59-71). Springer Berlin Heidelberg.
[7]. Takagi, T. (1998). Fast RSA-type cryptosystem modulo pkq. In Advances in Cryptology—CRYPTO’98: 18th Annual International Cryptology Conference Santa Barbara, California, USA August 23–27, 1998 Proceedings 18 (pp. 318-326). Springer Berlin Heidelberg.
[8]. Rabin, M. O. (1980). Probabilistic algorithms in finite fields. SIAM Journal on computing, 9(2), 273-280.
[9]. Muhammad, S. J., Chiroma, H., & Mahmud, M. (2014). Cryptanalytic attacks on Rivest, Shamir, and Adleman (RSA) cryptosystem: issues and challenges. J Theor Appl Inf Technol, 61(1), 2349.
[10]. Samandari, N., Nazari, N. M., Olfat, J. A., Rafi, R., Azizi, Z., & Ulfat, W. I. (2023). Applications of Fermat’s Little Theorem. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 14(03), 209-215.
[11]. Boneh, D. (1999). Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46(2), 203-213.
[12]. Sarnaik, S., Bhakkad, R., & Desai, C. (2015, March). Comparative study on Integer Factorization algorithm -Pollard’s RHO and Pollard’s P-1. In 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom) (pp. 677-679). IEEE.
[13]. Kim, J. H., Montenegro, R., Peres, Y., & Tetali, P. (2010). A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm.
[14]. Galbraith, Steven D. (2012), “14.2.5 Towards a rigorous analysis of Pollard rho”, Mathematics of Public Key Cryptography, Cambridge University Press, pp. 272-273, ISBN 9781107013926.
[15]. Hegde, N., & Deepthi, P. (2015). Pollard RHO algorithm for integer factorization and discrete logarithm problem. International Journal of Computer Applications, 121(18), 14-17.
Cite this article
Liu,Z. (2023). Evaluating RSA encryption: Primality testing, pollard’s algorithms, and security challenges. Theoretical and Natural Science,13,287-292.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 3rd International Conference on Computing Innovation and Applied Physics
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).