Assessing the Cryptographic Strength of RSA Moduli Using Algorithmic Entropy Reduction in Bivariate Polynomials
Nicole Soder, Chase Deluca, David Biersach, Michael P. DePhillips · 2018
We develop an innovative approach to factoring semiprimes, numbers that are the product of two large primes. These composite numbers form the foundation of the widely used RSA encryption method which protects vast amounts of digitally transmitted data. With the current rate of technological growth, experts believe that the best-known factoring algorithms would take thousands of years to break a single RSA composite. But with a more efficient method, government agencies could quickly decrypt big data sets to better confront national security concerns. Our technique, Algorithmic Entropy Reduction in Bivariate Polynomials, takes a different approach from traditional methods in that it addresses the binary expansion of the primes without relying on number theory. The method evaluates if a valid solution can exist for a given bivariate polynomial (BVP) representation of each prime at every bit position. In doing so, the method ascertains each binary digit from least significant bit on the right-hand side to most significant bit on the left-hand side (entropy reduction). We execute the algorithm by generating code in C++ and Python and reduce its computational work by a factor of two using multiprocessing.