RSA modulus length regression prediction based on the Run Test and machine learning in the ciphertext-only scenarios - Ke Yuan; Chenmeng Zhao; Longwei Yang; Hanlin Sun; Sufang Zhou; Chunfu Jia (Complex & Intelligent Systems)
Abstract RSA is a classical public key cryptographic algorithm, over 40 years of widespread use has proven that its security is reliable when the key parameters are properly configured. Attacks against RSA mainly rely on its internal mathematical constructs, such as modulus factorization, co-modulus attack, small exponent Attack, etc. Modulus length is one of the most important security metrics for RSA, considering that in some scenarios, the public key of RSA is not always public in order to improve the security strength of communication, and there is no ciphertext-only attack on modulus length in the existing attack methods, this paper designs a Modulus Length Regression Scheme (MLRS) using the Run Test and machine learning for RSA algorithm, aiming to identify the length of modulus used in RSA ciphertexts in the ciphertext-only scenario, and provide a reference for further attacks. In the proposed MLRS, we use National Institute of Standards and Technology (NIST) Run Test and Machine Learning models as ciphertext feature extraction method and modulus length regression tools, respectively, along with a hyperparameter tuple in MLRS to find a balance between resource overhead and regression effects, so as to achieve better results at a smaller cost. The experimental results show that this scheme using DTR-based AdaBoost can achieve a modulus length regression prediction of RMSE  $$=$$ =  34.16, $$R^{2}$$ R 2 Score  $$=$$ =  0.9738 for RSA ciphertexts without filling. In addition, we analyzed the effect of variation in modulus length on the Run Test and find that the longer the modulus, the more indistinguishable the corresponding ciphertext features are, which laterally verifies that the longer the RSA modulus length is, the more secure it is from the perspective of artificial intelligence cryptanalysis.