US-12621148-B2 - System and method for performing operation using linear-integer-programing for RSA factorization

US12621148B2US 12621148 B2US12621148 B2US 12621148B2US-12621148-B2

Abstract

A system for performing operations using linear integer programming for RSA factorization is provided, including an n/e extractor, a prime factorization calculator, a private key determiner, and a decryptor. The n/e extractor is configured to extract a modulus and a public key exponent from a public key. The prime factorization calculator is configured to: determine a semi-prime number of the modulus according to the modulus; use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors. The private key determiner is configured to determine a private key using the public key exponent and the two prime numbers. The decryptor is configured to decrypt an encrypted message using the private key so as to generate a decrypted message.

Inventors

Han-Lin Li
Way Kuo

Assignees

CITY UNIVERSITY OF HONG KONG

Dates

Publication Date: 20260505
Application Date: 20240208

Claims (12)

1 . A system for reducing computer processing time during private key decryption during digital communication, the system performing operations using linear integer programming for RSA factorization, comprising: an n/e extractor configured to extract a modulus and a public key exponent from a public key; a prime factorization calculator electrically coupled with the n/e extractor and configured to: determine a semi-prime number of the modulus according to the modulus; use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via one of a first mode, a second mode, and a third mode, wherein the tail digit represents the last or least significant digit of the semi-prime number, and the head digit set represents the first two or most significant digits of the semi-prime number; and a private key determiner electrically coupled with the prime factorization calculator and configured to determine a private key using the public key exponent and the two prime numbers; and a decryptor electrically coupled with the private key determiner and configured to decrypt an encrypted message using the private key, so as to generate a decrypted message; wherein the prime factorization calculator is further configured to determine if the semi-prime number is in a form of 4k+1, k being a positive integer, wherein the decomposition and factorization is performed via the first mode as the semi-prime number is in the form of 4k+1, and the decomposition and factorization is performed via the third mode as the semi-prime number is not in the form of 4k+1; wherein the prime factorization calculator performs the decomposition by creating subproblems that are structured as linear integer programming problems, using the tail digit and the head digit set of the semi-prime number as decimal digit information, and performs the factorization by solving corresponding linear binary programs derived from the decomposition, such that, during execution of the private key decryption on a computer, the system solves the subproblems using linear integer programming techniques to reduce computer processing time and power consumption.
2 . The system of claim 1 , wherein the two prime factors are determined at the third mode, if the performing the decomposition and factorization by the prime factorization calculator begins from the third mode, as a form of 4m+1 and 4n+3 by the prime factorization calculator, where m and n are different positive integers, and m is not equal to n.
3 . The system of claim 1 , wherein the prime factorization calculator is further configured to determine if the decomposition and factorization is performed via the second mode, after the prime factorization calculator performs decomposition and factorization via the first mode.
4 . The system of claim 3 , wherein the two prime factors are determined at the second mode, if performing the decomposition and factorization by the prime factorization calculator is via the second mode, as a form of 4m+3 and 4n+3 by the prime factorization calculator, where m and n are different positive integers, and m is not equal to n.
5 . The system of claim 3 , wherein the two prime factors are determined at the first mode, if determining by the prime factorization calculator is not to perform decomposition and factorization via the second mode, as a form of 4m+1 and 4n+1 by the prime factorization calculator, where m and n are different positive integers, and m is not equal to n.
6 . The system of claim 1 , further comprising a result presenter electrically couple with the decryptor and configured to: extract relevant details from the decrypted message; and provide an interface to access and display the decrypted message.
7 . A method for reducing computer processing time during private key decryption during digital communication, the method performing operations using linear integer programming for RSA factorization, comprising: extracting a modulus and a public key exponent from a public key; determining a semi-prime number of the modulus according to the modulus; using a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via one of a first mode, a second mode, and a third mode, wherein the tail digit represents the last or least significant digit of the semi-prime number, and the head digit set represents the first two or most significant digits of the semi-prime number; determining a private key using the public key exponent and the two prime numbers; decrypting an encrypted message using the private key so as to generate a decrypted message; and determining if the semi-prime number is in a form of 4k+1, k being a positive integer, wherein the decomposition and factorization is performed via the first mode as the semi-prime number is in the form of 4k+1, and wherein the decomposition and factorization is performed via the third mode as the semi-prime number is not in the form of 4k+1; wherein the decomposition comprises creating subproblems that are structured as linear integer programming problems using the tail digit and the head digit set of the semi-prime number as decimal digit information, and the factorization comprises solving corresponding linear binary programs derived from the decomposition, such that, during execution of the private key decryption on a computer, the subproblems are solved using linear integer programming techniques to reduce computer processing time and power consumption.
8 . The method of claim 7 , wherein the two prime factors are determined at the third mode, if the performing the decomposition and factorization begins from the third mode, as a form of 4m+1 and 4n+3, where m and n are different positive integers, and m is not equal to n.
9 . The method of claim 7 , further comprising: determining if the decomposition and factorization is performed via the second mode, upon the performing decomposition and factorization via the first mode.
10 . The method of claim 9 , wherein the two prime factors are determined at the second mode, if the performing the decomposition and factorization is via the second mode, as a form of 4m+3 and 4n+3, where m and n are different positive integers, and m is not equal to n.
11 . The method of claim 9 , wherein the two prime factors are determined at the first mode, if the determining is not to perform decomposition and factorization via the second mode, as a form of 4m+1 and 4n+1, where m and n are different positive integers, and m is not equal to n.
12 . The method of claim 7 , further comprising: extracting relevant details from the decrypted message; and providing an interface to access and display the decrypted message.

Description

TECHNICAL FIELD The present invention generally relates to the field of public-key encryption and digital signature, particularly to systems and methods for performing operations using linear integer programming for RSA factorization. BACKGROUND A semi-prime number is the product of exactly two different prime numbers. An RSA factorization method is to decompose a semi-prime number into its two prime factors. RSA factorization is an essential technique that is widely used in today's cryptography research such as the RSA public-key encryption and RSA digital signature. Many mathematicians and computer scientists have been developing new RSA factorization methods to secure today's digital communication systems. Specifically, in RSA encryption, a public key is created from two large prime numbers, and the product of these two primes (a semiprime) is used as part of this key. The security of RSA encryption relies heavily on the computational difficulty of factoring large semiprime numbers. If it is easy to factorize the semiprime, the encryption could be easily broken, rendering the encrypted data insecure. A semiprime factorization calculator could theoretically be used to break RSA encryption by factorizing the semiprime number in the public key to find the original prime numbers. However, in practice, the prime numbers used in RSA encryption are so large (e.g., hundreds of digits) that it is computationally infeasible to factorize the semiprime number with current technology and known algorithms. Therefore, while a semiprime factorization calculator fits into the technical field of encryption/decryption in theory, its practical application for breaking modern encryption is currently limited. The currently available RSA factorization methods using traditional computers can be casted in three categories. The first category, including the well-known “Trial Sieve method,” utilizes the exhaustive brute force techniques. The second category, including the “Pollard's Rho” and “Lenstra Elliptic Curve” methods develops special-purpose quadratic sieve methods. The third one is the general-purpose quadratic sieve category, including the General Number Field Sieve method (GNFS) and Shanks's method. There also exits an RSA factorization method using the quantum computer, which may become scalable in the future. The above-mentioned RSA factoring methods have their features and limitations described as follows: To factorize a semi-prime number θ, these methods may not utilize the information of decimal digits, but factorize θ directly. These methods employ heuristic techniques, which may not converge to a final feasible solution. For example, the feasibility of GNFS method depends on how to specify the two polynomial functions involved, and the Pollard Rho method is a probabilistic algorithm with no guarantee to find a feasible solution. To factorize a semi-prime number θ, a typical sieve method needs to know the prime numbers smaller than √{square root over (θ)} beforehand. For instance, the GNFS method spends more than half of its computing time (e.g., more than 50%) in detecting if a number is smooth or not. It is noted that a number is called B-smooth if all factors of the number are not larger than a number B. Some of these methods can only factorize a semi-prime number θ with certain specific structure. For instance, SNFS can only factorizing θ with limited smoothness values. Some of these methods, such as the Trial Division, Wheel Factorization, Pollard's Rho, and Elliptic Curve methods are special-purpose factoring algorithms, whose running time depends on the size of the smallest prime factor of θ. Special-purpose factorization algorithms are usually applied to remove small factors before employing the General Quadratic Sieve method. Therefore, there is a need to develop systems and methods for performing RSA factorization operations to address the challenges and shortcomings of the currently applied RSA factorization approaches. SUMMARY OF INVENTION It is an objective of the present invention to provide systems and methods for performing operations using linear integer programming for RSA factorization to address the aforementioned shortcomings and unmet needs in the state of the art. To overcome the shortcomings of the current available RSA factorization methods, the present disclosure develops a novel RSA factorization approach, called Linear-Integer-Programming (LIP) method, for factorizing semi-prime numbers. The features of the LIP method are given in the following: (i) To factorize a semi-prime primal θ with λ+2 decimal digits, LIP utilizes the decimal digit information of θ to formulate several subproblems in linear integer programming models with A equations and 10λ binary variables. Solving the resulting subproblems leads to the factorization of θ into two primes. This is totally different from the known methods, which do not use any of the decimal digit information of θ.(ii) LIP is an exact method that