# New Semi-Prime Factorization and Application in Large RSA Key Attacks
## 5 Case Study Examples Applied to RSA Key Factorization
** In computer security applications, the aim of a cryptosystem is to encrypt a message before communication, and only the authenticated user that has the right key can be able to decrypt the message, thereby enforcing message integrity, confidentiality, authentication, and privacy. Among several ciphers developed for this purpose, RSA is widely used in key exchange, digital signatures, and small blocks of data encryption. For the second application example, we consider RSA where the key is derived from a very large number (a semi-prime). Since determining the two prime factors of the large number is computationally difficult, research studies on evaluating the RSA and the factorization schemes are gaining attention [65, 66, 67]. Hence, we describe how our proposed semi-prime factorization method can be applied to factorize RSA quickly. The steps involved in RSA encryption are given below:  
1. Pick two large prime numbers \(c_{1}\) and \(c_{2}\);
2. Consider the semi-prime \(N=c_{1}c_{2}\);
3. Consider \(\varphi(N)=(c_{1}-1)*(c_{2}-1)\);
4. Choose an integer \(e\) such that \(1<e<\varphi(N)\) and \(\gcd(e,\ \varphi(N))=1\);
5. Compute \(d\) such that \(de\equiv 1\ (\bmod\varphi(N))\). While the public key \((N,e)\) is distributed for encrypting a message, the private key \((N,d)\) is kept a secret for decrypting the message only by an authorized entity. Hence,  
\[\{\alpha\}\
subseteq\{\beta\}\ \Rightarrow\gcd(\alpha,\beta)=1,\]1 An illustration of Pythagorean triples. based on this RSA scheme, it is evident that with the factorization of \(N\), we can compute \(de\equiv 1\pmod{\varphi(N)}\)[68], which gives the private key \((N,d)\). When the factorization is efficient, RSA can be broken. The factoring challenge was introduced to identify the safety limits of the key length to be used for the RSA encryption algorithm that can ensure information security. Hence, researchers focus on mathematically proving the cryptanalytic strength using efficient RSA factorization methods. Table 1 demonstrates the application of our proposed semi-prime factorization method for a key length of 768 decimal digits, denoted as RSA-768. The sums of squares and polynomials have been explored for semi-prime factorization in previous research works [1, 46, 69]. However, there are more than 50 properties of Pythagorean triples that have been reported and new patterns yet to be explored [15, 70]. In this research work, the proposed method has applied such unique patterns unexplored so far in the literature and maintains the algorithm's order of computational complexity, similar to the existing approaches that have been evaluated and reported recently [71, 72]. A recent experimental study employed the representation of primes in the form \(p=6\cdot x\pm 1\) and applied the theory to the RSA factorization problem [73]. Another work shows the decomposition of the two prime numbers with the Pisano period factorization method, which has been proven to be a subexponential complexity method [74]. Several integer factorization methods have also suggested direct application to cryptanalysis of RSA by applying different genetic algorithms [75]. While genetic algorithms could be a promising avenue of research for integer factorization, they are computationally complex. This paper's focus to involve new simple arithmetic operations while exploring unique structures of prime numbers has resulted in an efficient factorization. In our computationally simple method, the need to square the number that is to be factorized could be considered a constraint for large semi-primes to be attacked quickly. An example for RSA-768 is given below, illustrating our method of squaring the number to achieve semi-prime factorization. Future work will be devoted towards how the inherent mathematical constraint can be overcome by reducing the solution search space. One method is to use low order prime multipliers congruent to 1 mod 4 (for example