Evaluating Cryptoanalysis on Low-Exponent Implementation of Rivest-Shamir-Adleman
Muhammad Ilham Bayhaqi, Baskoro Adi Pratomo · 2023
In information security, cryptography plays an important role in disguising information so that it can only be accessed by authorised parties. One of the cryptographic algorithms that is still widely used today is RSA (Rivest-Shamir-Adleman). RSA is an asymmetric cryptographic algorithm that uses a key pair, public and private keys. The main concept that makes RSA secure is the infeasibility to factorise large numbers. Despite being mathematically secure, implementations of cryptographic algorithms may still create a security hole. This security hole can be caused by several factors, for example, the use of weak keys or weak padding schemes. To find out the strength of an algorithm used in cryptography, of course it is necessary to do a test. This test is done by cryptanalysis. Cryptanalysis is an action to decrypt a message that has been encrypted without permission or without a key. In this research, cryptanalysis is carried out to determine the strength of the RSA algorithm of an existing cryptosystem using the Coppersmith method. The Coppersmith method is a cryptanalysis method using the lattice basis reduction algorithm, namely LLL. Based on the results of the cryptanalysis carried out, the test for the value of e = 3 has a success rate of 25 out of 49 total cases or 51.02%. For the value of e = 5, it has a success of 8 out of 49 or 16.33% of the total cases. The value of e = 7 only has success in 8 of 65 cases or around 12.31% of the total cases.