International Journal of Research and Innovation in Applied Science (IJRIAS) |Volume VIII, Issue I, January 2023|ISSN 2454-6194

Computational Difficulty of Factoring Large Integers Using Generalize System Equations

Samaila Abdullahi1, Sadiq Shehu2, Tukur Shehu3
^1,2Department of Mathematics, Faculty of Science, Sokoto State University, Sokoto Nigeria
³Department of Mathematics, School of Science,
Shehu Shagari College of Education, Sokoto Nigeria
Received: 26 January 2023; Accepted: 03 February 2023; Published: 28 February 2023

Abstract: The RSA algorithm is the foundation of a cryptosystem, which permits public key encryption and is frequently used to establish a secure connection, particularly when it is delivered over an unprotected network such as the internet. Let and be unbalance prime, we offer two novel attacks in this paper using prime power modulus N = p^rq^s. Our first results are based on the RSA equation  ex²-φ(N)y²= 1 e,N  and x,p,q,φ(N) are public key and private key tuples respectively. If  P ≤q ≤λ^1/r+1N^1/r+1, then x < √ 1/2 (N-(2λ^r/r+1 N^r/r+1 -λ^1/r+1 N^1/r+1))and y²/x² can be obtained among the convergent of the continued fractions expansion  of  e/N-(2λ^r/r+1 N^r/r+1 -λ^1/r+1 N^1/r+1) which lead to the factorization of moduli N. In second part we consider the generalize system of equation using the proper approximation of φ(N) which allowed us to factored the prime power moduli N_s=p^r_sq_s simultaneously in polynomial time.

Keywords: RSA Prime Power, Factorization, Polynomial time, Generalize system, Diophantine approximations, Continued fraction, convergent.

I. Introduction

Cryptanalysis is the science of studying information systems in order to learn more about the system’s hidden elements. Even if the cryptography key is unknown, cryptanalysis is used to break into a cryptography security system and gain access to the content of encrypted messages. There are two sorts of keys in this category of cryptography: symmetric and asymmetric keys. Only one key can be disclosed for both encryption and decryption in symmetric cryptanalysis. Asymmetric cryptography is the subject of this study. The term “asymmetric” refers to the existence of two distinct keys. Because one of the keys can be provided to anybody while the private key is kept secret, this is also known as public key cryptography. When a cryptosystem’s secure instances aren’t utilised, a protocol failure occurs.

Ronal Revest was the one who came up with the concept of cryptosystem. The most frequently used asymmetric cryptographic technique, RSA, was devised by Adi Shamir and Leonard Adleman in 1977. The RSA public key cryptosystem, for example, is used to protect web traffic, email, remote login sessions, and electronic credit card payment systems. The integer factorization problem is RSA’s underlying one-way function: multiplying two large primes is computationally simple, but factoring the resulting product is extremely difficult. The complexity of solving the so-called RSA problem is also well-known for RSA’s security. Calculate the plaintext m using an RSA public key (e, N) and a ciphertext c ≡ me (mod N), Because factoring modulus N leads to obtaining the private exponent d and solving the RSA problem, the RSA problem isn’t any more difficult to solve than the integer factorization problem. The converse, on the other hand, is not evident. Rivest R.; Shamir, A.; Adleman, L. (1978).

The public modulus N = pq in the RSA cryptosystem is the product of two primes of the same bit size. The congruence is satisfied by the public and private exponents e and d, respectively.

ed ≡ 1 (mod Ф(N)),

The Euler totient function Ф(N) = (p – 1)(q – 1) is used. In RSA, heavy exponentiations are needed for encryption, decryption signature, and signature verification. To reduce the encryption time or the signature verification time, one can use a small public exponent e such as 3 or 216 + 1.On the other hand to reduce the decryption time or the signature generation time, one can be tempted to use a small private exponent d. Many attacks show that using a very small private exponent is measure. Indeed, Wiener showed

Read More