Cryptanalytic attacks on RSA algorithm and its variants

• Autorzy: Savić Dragan , Milić Petar , Mazinjanin Borislaw , Spalević Petar

Identyfikatory

DOI

10.15199/48.2022.02.04

Warianty tytułu

PL

Ataki kryptoanalityczne na algorytm RSA i jego warianty

• Języki publikacji: EN

Abstrakty

EN

The goal of this paper is to provide a review of principles and techniques used in public-key cryptanalysis with special attention on RSA algorithm. The ways to defend against attacks on RSA algorithm are suggested. Furthermore, we provide a retrospective of results obtained during the research separately treated in the final part of the paper through the description of brute-force, low-exponent attack, chosen-plaintext attack and timing attack.

PL

Celem tego artykułu jest przedstawienie przeglądu zasad i technik stosowanych w kryptoanalizie klucza publicznego ze szczególnym uwzględnieniem algorytmu RSA. Sugerowane są sposoby obrony przed atakami na algorytm RSA. Ponadto przedstawiamy retrospektywę wyników uzyskanych podczas badań oddzielnie potraktowanych w końcowej części artykułu poprzez opis ataku brute-force, ataku o niskim wykładniku, ataku z wybranym tekstem jawnym i ataku czasowego.

Słowa kluczowe

EN

public key; RSA; cryptanalysis; attack

PL

kryptografia; RSA; atak kryptograficzny

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2022
• Tom: R. 98, nr 2
• Strony: 14--20
• Opis fizyczny: Bibliogr. 28 poz., tab.

Twórcy

autor

Savić Dragan

• Singidunum University

• https://orcid.org/0000-0003-0427-8379

autor

Milić Petar

• University of Pristina – Kosovska Mitrovica, Faculty of Technical Sciences

autor

Mazinjanin Borislaw

• Academy for National Security

autor

Spalević Petar

• University of Pristina – Kosovska Mitrovica, Faculty of Technical Sciences

Bibliografia

• [1] Jaju, A. S. and Chowhan, S. S. (2015) A Modified RSA Algorithm to Enhance Security for Digital Signature, In Proceedings of the 2015 International Conference and Workshop on Computing and Communication (IEMCON), Vancouver, BC, Canada, pp. 1–5.
• [2] Jeřábek, E. (2016) Integer factoring and modular square roots, Journal of Computer and System Sciences, Vol. 82, No. 2, pp. 380–394.
• [3] Ye, X., Liu, C. and Gardner, D. (2018) Weakness of RSA cryptosystem characteristic, In Proceedings of the International Conference of Computational Methods in Sciences and Engineering, Thessaloniki, Greece, Vol. 2040, pp. 1–10.
• [4] Barak, B. (2017) The Complexity of Public-Key Cryptography, In: Lindell Y. (eds) Tutorials on the Foundations of Cryptography. Information Security and Cryptography. Springer, pp. 45–77.
• [5] Overmars,A.andVenkatraman,S.(2020)MathematicalAttack of RSA by Extending the Sum of Squares of Primes to Factorize a Semi-Prime, Mathematical and Computational Applications, Vol. 25, No. 4. pp. 1–15.
• [6] Simmons, J. G. (2010) A weak privacy protocol using the RSA crypto algorithm, Cryptology, Vol. 4, No. 1, pp. 58-93.
• [7] Peng,L.,Hu,L.,Lu,Y.,Sarkar,S.,Xu,J.andHuang,Z.(2015) Cryptanalysis of Variants of RSA with Multiple Small Secret Exponents, In Proceedings of 2015 International Conference on Cryptology (INDOCRYPT 2015), Bangalore, India, pp. 105-123.
• [8] Raghunandan, K. R., Aithal, G. and Shetty, S. (2019) Comparative Analysis of Encryption and Decryption Techniques Using Mersenne Prime Numbers and Phony Modulus to Avoid Factorization Attack of RSA, In Proceedings of the 2019 International Conference on Advanced Mechatronic Systems, Kusatsu, Japan, pp. 152–157.
• [9] Takayasu, A. and Kunihiro, N. (2016) Small secreet exponent attacks on RSA with unbalanced prime factors, In Proceedings of the 2016 International Symposium on Information Theory and Its Applications (ISITA), Monterey, USA, pp. 236–240.
• [10 ]Lu, Y., Zhang, R., Peng, L. and Lin, D. (2015) Solving Linear Equations Modulo Unkown Divisors: Revisited, In Proceedings of the 2015 International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2015), Auckland, New Zeland, pp. 189–2013.
• [11] Boudabra, M. and Nitaj, A. (2017) A new generalization of the KMOV cryptosystem, Journal of Applied Mathematics and Computing, Vol. 57. No. 1. pp. 229–245.
• [12] Padmaja, J. C., Srinivas, B. and Bhagavan, S. V. (2018) A Systematic Mapping Study of the Published Research on Cryptanalytic Attacks on RSA, International Journal of Pure and Applied Mathematics, Vol. 118, No. 23, pp. 283–291.
• [13] Savić, D. and Damjanović, S. (2016) The Attacks on the RSA Algorithm, In Proceedings of the 2016 International Scientific Conference on ICT and E-business Related Research (SINTEZA 2016), Belgrade, Serbia, pp. 131–136.
• [14] Wang, S., Qu, L., Li, C. and Fu, S. (2015) A New Attack on RSA with Known Middle Bits of the Private Key, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 98. No. 12, pp. 2677–2685.
• [15] Takayasu, A. and Kunihiro, N. (2017) A Tool Kit for Partial Key Exposure Attacks on RSA, In Proceedings of the Cryptographer's Track at the RSA Conference 2017 (CT-RSA 2017), San Francisco, USA, pp. 58–73.
• [16] Meng, X. and Zheng, X. (2015) Cryptanalysis of RSA with a small parameter revisited, Vol. 115, No. 11, pp. 858–862.
• [17] Bahig, M. H., Nassr, I. D., Bhery, A. and Nitaj, A. (2020) A Unified Method for Private Exponent Attacks on RSA Using Lattices, International Journal of Foundations of Computer Science, Vol. 31, No. 02, pp. 207- 231.
• [18] Asbullah, A. M., Rahman, A. N. N., Ariffin, K. R. M., Sapar, H. S. and Yunos, F. (2020) Cryptanalysis of RSA Key Equation of N=p^2q For Small | 2q - p | Using Continued Fraction, Malaysian Journal of Science, Vol. 39, No. 1, pp. 72-80.
• [19] Susilo, W., Tonien, J. and Yang, G. (2019) The Wiener Attack on RSA Revisited: A Quest for the Exact Bound, In the Proceedings of the Australasian Conference on Information Security and Privacy, Christchurch, New Zeland, pp. 381-398.
• [20] Nitaj, A., Susilo, W. and Tonien, J. (2019) Improved Cryptanalysis of the KMOV Elliptic Curve Cryptosystem, In the Proceedings of the 13th International Conference on Provable Security, Cairns, Australia, pp. 206-221.
• [21] Santosh, R., Narasimham, C. and Pallam, S. (2015) Short Secret Exponent Attack on LSBS-RSA, Vol. 12. No. 6A, pp. 714-718.
• [22] Mumtaz, M. and Ping, L. (2021) An improved cryptanalysis of large RSA decryption exponent with constrained key, International Journal of Information and Computer Security, Vol. 14. No. 2, pp. 102–117.
• [23] Kumar, V., Kumar, R. and Pandey, K. S. (2017) An Enhanced and Secured RSA Public Key Cryptosystem Algorithm Using Chinese Remainder Theorem, In Proceedings of the 3rd International Conference on Next Generation Computing Technologies (NGCT 2017), Dehradun, India, pp. 543–554.
• [24] Al Barazanchi, I., Shawkat, A. S., Hammed, H. M. and Al-Badri, L. S. K. (2019) Modified RSA-based algorithm: a double secure approach, TELKOMNIKA, Vol. 17. No. 6, pp. 2818–2825.
• [25] Patil, P., Narayankar, P., Narayan, D. G. and Mena, S. M. (2016) A Comprehensive Evaluation of Cryptographic Algorithms: DES, 3DES, AES, RSA and Blowfish, Procedia Computer Science, Vol. 78, pp. 617–624.
• [26] Kong, F., Yu, J., Zhou, D., Jiang, Y. and Shang, J. (2017) Security Analysis of Two Inter-Organization Cryptographic Schemes, In Proceedings of the 4th International Conference on Machinery, Materials and Information Technology Applications (ICMMITA 2016), pp. 1323–1327.
• [27] Abobeah, M. R., Ezz, M. M. and Harb, M. H. (2015) Public-Key Cryptography Techniques Evaluation, International Journal of Computer Networks and Applications, Vol. 2, No. 2. pp. 64–75.
• [28] Akchiche, O. and Khadir, O. (2018) Factoring RSA moduli with primes sharing bits in the middle, Applicable Algebra in Engineering, Communication and Computing, Vol. 29, No. 3, pp. 245–259.