New Semi-Prime Factorization and Application in Large RSA Key Attacks
Semi-prime factorization is an increasingly important number theoretic problem, since it is computationally intractable. Further, this property has been applied in public-key cryptography, such as the Rivest–Shamir–Adleman (RSA) encryption systems for secure digital communications. Hence, alternate...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-11-01
|
| Series: | Journal of Cybersecurity and Privacy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2624-800X/1/4/33 |
| _version_ | 1797503413893726208 |
|---|---|
| author | Anthony Overmars Sitalakshmi Venkatraman |
| author_facet | Anthony Overmars Sitalakshmi Venkatraman |
| author_sort | Anthony Overmars |
| collection | DOAJ |
| description | Semi-prime factorization is an increasingly important number theoretic problem, since it is computationally intractable. Further, this property has been applied in public-key cryptography, such as the Rivest–Shamir–Adleman (RSA) encryption systems for secure digital communications. Hence, alternate approaches to solve the semi-prime factorization problem are proposed. Recently, Pythagorean tuples to factor semi-primes have been explored to consider Fermat’s Christmas theorem, with the two squares having opposite parity. This paper is motivated by the property that the integer separating these two squares being odd reduces the search for semi-prime factorization by half. In this paper, we prove that if a Pythagorean quadruple is known and one of its squares represents a Pythagorean triple, then the semi-prime is factorized. The problem of semi-prime factorization is reduced to the problem of finding only one such sum of three squares to factorize a semi-prime. We modify the Lebesgue identity as the sum of four squares to obtain four sums of three squares. These are then expressed as four Pythagorean quadruples. The Brahmagupta–Fibonacci identity reduces these four Pythagorean quadruples to two Pythagorean triples. The greatest common divisors of the sides contained therein are the factors of the semi-prime. We then prove that to factor a semi-prime, it is sufficient that only one of these Pythagorean quadruples be known. We provide the algorithm of our proposed semi-prime factorization method, highlighting its complexity and comparative advantage of the solution space with Fermat’s method. Our algorithm has the advantage when the factors of a semi-prime are congruent to 1 modulus 4. Illustrations of our method for real-world applications, such as factorization of the 768-bit number RSA-768, are established. Further, the computational viabilities, despite the mathematical constraints and the unexplored properties, are suggested as opportunities for future research. |
| first_indexed | 2024-03-10T03:50:17Z |
| format | Article |
| id | doaj.art-f2a3635dcb11429dbc21550541bd6d0e |
| institution | Directory Open Access Journal |
| issn | 2624-800X |
| language | English |
| last_indexed | 2024-03-10T03:50:17Z |
| publishDate | 2021-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Journal of Cybersecurity and Privacy |
| spelling | doaj.art-f2a3635dcb11429dbc21550541bd6d0e2023-11-23T08:59:07ZengMDPI AGJournal of Cybersecurity and Privacy2624-800X2021-11-011466067410.3390/jcp1040033New Semi-Prime Factorization and Application in Large RSA Key AttacksAnthony Overmars0Sitalakshmi Venkatraman1Department of Information Technology, Melbourne Polytechnic, 77 St. Georges Rd., Preston, VIC 3072, AustraliaDepartment of Information Technology, Melbourne Polytechnic, 77 St. Georges Rd., Preston, VIC 3072, AustraliaSemi-prime factorization is an increasingly important number theoretic problem, since it is computationally intractable. Further, this property has been applied in public-key cryptography, such as the Rivest–Shamir–Adleman (RSA) encryption systems for secure digital communications. Hence, alternate approaches to solve the semi-prime factorization problem are proposed. Recently, Pythagorean tuples to factor semi-primes have been explored to consider Fermat’s Christmas theorem, with the two squares having opposite parity. This paper is motivated by the property that the integer separating these two squares being odd reduces the search for semi-prime factorization by half. In this paper, we prove that if a Pythagorean quadruple is known and one of its squares represents a Pythagorean triple, then the semi-prime is factorized. The problem of semi-prime factorization is reduced to the problem of finding only one such sum of three squares to factorize a semi-prime. We modify the Lebesgue identity as the sum of four squares to obtain four sums of three squares. These are then expressed as four Pythagorean quadruples. The Brahmagupta–Fibonacci identity reduces these four Pythagorean quadruples to two Pythagorean triples. The greatest common divisors of the sides contained therein are the factors of the semi-prime. We then prove that to factor a semi-prime, it is sufficient that only one of these Pythagorean quadruples be known. We provide the algorithm of our proposed semi-prime factorization method, highlighting its complexity and comparative advantage of the solution space with Fermat’s method. Our algorithm has the advantage when the factors of a semi-prime are congruent to 1 modulus 4. Illustrations of our method for real-world applications, such as factorization of the 768-bit number RSA-768, are established. Further, the computational viabilities, despite the mathematical constraints and the unexplored properties, are suggested as opportunities for future research.https://www.mdpi.com/2624-800X/1/4/33Euler’s factorizationPythagorean quadvery minimal, with most computations operating onruplesPythagorean triplesLebesgue identityBrahmagupta–Fibonacci identitysemi-primes |
| spellingShingle | Anthony Overmars Sitalakshmi Venkatraman New Semi-Prime Factorization and Application in Large RSA Key Attacks Journal of Cybersecurity and Privacy Euler’s factorization Pythagorean quadvery minimal, with most computations operating onruples Pythagorean triples Lebesgue identity Brahmagupta–Fibonacci identity semi-primes |
| title | New Semi-Prime Factorization and Application in Large RSA Key Attacks |
| title_full | New Semi-Prime Factorization and Application in Large RSA Key Attacks |
| title_fullStr | New Semi-Prime Factorization and Application in Large RSA Key Attacks |
| title_full_unstemmed | New Semi-Prime Factorization and Application in Large RSA Key Attacks |
| title_short | New Semi-Prime Factorization and Application in Large RSA Key Attacks |
| title_sort | new semi prime factorization and application in large rsa key attacks |
| topic | Euler’s factorization Pythagorean quadvery minimal, with most computations operating onruples Pythagorean triples Lebesgue identity Brahmagupta–Fibonacci identity semi-primes |
| url | https://www.mdpi.com/2624-800X/1/4/33 |
| work_keys_str_mv | AT anthonyovermars newsemiprimefactorizationandapplicationinlargersakeyattacks AT sitalakshmivenkatraman newsemiprimefactorizationandapplicationinlargersakeyattacks |