System and method for performing operation using linear-integer-programing for RSA factorization
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.
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.