A New Methodology to Find Private Key of RSA Based on Euler Totient Function
Article Sidebar
Main Article Content
Abstract
The aim of this paper is to present a new methodology to find the private key of RSA. A new initial value which is generated from a new equation is selected to speed up the process. In fact, after this value is found, brute force attack is chosen to discover the private key. In addition, for a proposed equation, the multiplier of Euler totient function to find both of the public key and the private key is assigned as 1. Then, it implies that an equation that estimates a new initial value is suitable for the small multiplier. The experimental results show that if all prime factors of the modulus are assigned larger than 3 and the multiplier is 1, the distance between an initial value and the private key is decreased about 66%. On the other hand, the distance is decreased less than 1% when the multiplier is larger than 66. Therefore, to avoid attacking by using the proposed method, the multiplier which is larger than 66 should be chosen. Furthermore, it is shown that if the public key equals 3, the multiplier always equals 2.
Received 11/11/2019, Accepted 26/10/2020, Published Online First 11/1/2021
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
References
Alka R, Gupta A, Jaiswal M. An enhanced AES algorithm using cascading method on 400 bits key size used in enhancing the safety of next generation internet of things (IOT), Proceedings of the International Conference on Computing, Communication and Automation, India, 2017, pp. 422 - 427.
Yu L, Zhang, D, Wu L, Xie S, Su D, Wang X. AES Design Improvements Towards Information Security Considering Scan Attack, Proceedings of the IEEE International Conference On Trust, Security and Privacy In Computing And Communications/ IEEE International Conference On Big Data Science And Engineering, Communication and Automation, USA, 2018, pp. 322 - 326.
Diffie W, Hellman M. New directions in cryptography. IEEE Transactions on Information Theory. 1976; 22(6): 644-654.
Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public key cryptosystems. Communications of ACM. 1978; 21: 120 – 126.
Priyadarshini P, Prashant N, Narayan DG, Meena SM. A Comprehensive Evaluation of Cryptographic Algorithms: DES, 3DES, AES, RSA and Blowfish. Procedia Computer Science. 2015; 78: 617 – 624.
Hosung J, Heejin P. Fast Prime Generation Algorithms using proposed GCD test on Mobile Smart Devices, Proceedings of the International Conference on Big Data and Smart Computing, China. 2016; pp. 374-377.
Wiener, M. Cryptanalysis of short RSA secret exponents. Proc. IEEE. 1990; 36: 553-558.
Thuc D N, Than DN, Long DT. Attacks on Low Private Exponent RSA: An Experimental Study, Proceedings of the International Conference on Computational Science and Its Applications, Vietnam. 2013; pp. 162-165.
Hastad J. On using RSA with Low Exponent in a Public-Key Network. Advances in Cryptology. 1986; 218: 404-408.
Imad KS, Abdullah D, Saleh O. Mathematical Attacks on RSA Cryptosystem. Journal of Computer Sciences. 2006; 2(8): 665 – 671.
Dongmuanthang P, Prabir S. Redesigned the Architecture of Extended-Euclidean Algorithm for Modular Multiplicative Inverse and Jacobi Symbol, Proceedings of the International Conference on Trends in Electronics and Informatics, India. 2018; pp. 1345 - 1349.
Ibrahim H, Fayez G, Atef I. High Speed and Low Area Complexity Extended Euclidean Inversion Over Binary Fields. IEEE Trans. Consum. Electron. 2019; 65: 408 – 417.
Farah J, Endroyono, Achmad A. Security System Analysis in Combination Method: RSA Encryption and Digital Signature Algorithm, Proceedings of the International Conference on Science and Technology, Indonesia. 2018; pp. 1- 5.
Muhammad R P, Deden IA, Riri FS. Comparison of ECDSA and RSA signature scheme on NLSR performance, Proceedings of EEE Asia Pacific Conference on Wireless and Mobile, Indonesia. 2018; pp. 7- 11.
Nidhi L, Anurag P, Shishupal K. Modified Trial Division Algorithm Using KNJ-Factorization Method To Factorize RSA Public Key Encryption, Proceedings of the International Conference on Contemporary Computing and Informatics, India. 2014; pp. 992 – 995.
Ambedkar BR, Gupta A, Gautam P, Bedi SS. An Efficient Method to Factorize the RSA Public Key Encryption, Proceedings of the International Conference on Communication Systems and Network Technologies. Katra. 2011; pp. 108 -111.
Somsuk K, Chiawchanwattana T, Sanemueang C. Estimating the new Initial Value of Trial Division Algorithm for Balanced Modulus to Decrease Computation Loops, Proceedings of the International Joint Conference on Computer Science and Software Engineering. Thailand. 2019; pp. 137 – 141.
Wu ME, Tso R, Sun HM. On the improvement of Fermat factorization using a continued fraction technique. Future Gener Comput Syst. 2014; 30(1): 162 – 168.
Omar K, Szalay L. Sufficient conditions for factoring a class of large integers. J. Discret. Math. Sci. Cryptogr. 2010; 13: 95-103.
Somsuk K, Tientanopajai K. An Improvement of Fermat's Factorization by Considering the Last m Digits of Modulus to Decrease Computation Time. Int. J. Netw. Secur. 2017; 19: 99 – 111.
Somsuk K. The improvement of initial value closer to the target for Fermat’s factorization algorithm. J. Discret. Math. Sci. Cryptogr. 2013; 7-8: 1573 – 1580.
Bishop D. Introduction to Cryptography with java Applets, Jones and Bartlett Publisher, London, England, 2003.
Sarnaik S, Bhakkad R, Desai C. Comparative study on Integer Factorization Algorithm-Pollard's RHO and Pollard's P-1, Proceedings of the International Conference on Computing for Sustainable Global Development. India, 2015; pp.677 – 679.
Nikita YM, Ivan YS, Vasiliy IY, Olga AS, Irina VR, Angrey GL, et al. Modification and Optimization of Solovey–Strassen’s Fast Exponentiation Probablistic Test Binary Algorithm. Proceedings of the IEEE East-West Design & Test Symposium, Georgia. 2019, pp.1-3.
Murat S. Generalized Trial Division. IJCMS.2011; 6(2): 59 – 64.
Boneh D, Durfee G. Cryptanalysis of RSA with Private Key d less than N0.292. Lect. Notes Comput. Sci. 1999; 1592: 1 – 11.
Kong F, Zhou D, Jiang Y, Shang J, Yu J. Fault Attack on an Improved CRT-RSA algorithm with the Modulus Chaining Method, Proceedings of IEEE International Conference on Computational Science and Engineering and IEEE International Conference on Embedded and Ubiquitous Computing, China. 2017; pp. 866 – 869.
Somsuk K, Chiawchanwattana T, Sanemueang C. Speed up RSA’s Decryption Process with Large sub Exponents using Improved CRT, Proceedings of International Conference on Information Technology. Thailand, 2018, pp. 1-5. IEEE.