Computing security protocols often are based upon intractable problems. The hardness of the problem thwarts any efforts at circumventing the security measures. And, intractable simply means “hard” or “difficult” not “impossible” or “unsolvable”.
During the earlier “early years of computing”, it was deemed the factoring a 256-bit number composed of a pair of large primes would take over one quadrillion years. With, the computational processing powering and known algorithms at the time.
So, the public exchange of security keys and private information was based upon this principle. Unfortunately, the factoring problems was not as difficult as originally thought. And whether, the key is compromised in transit via a quick factoring algorithm, like the one shared below. Or, the secured information is obtain via a trojan horse virus or spyware. No computer-based conversation or electronic document is truly securable.
The mathematicians who developed the protocol for public key exchange are Whitfield Diffie and Martin Hillman. The last of which has seen the spelling of his name change over the years becoming Hellman. However, it is clearly remembered that the first paper read on the protocol while in secondary school during the late 80s had the last name Hillman attached. Unless, it were a typo then. That be the original surname used.
Regardless of how the protocol is presented. It simply involves enciphering a message with a large prime number, the secret key. And then, combining that secret key with another large prime number also held by the receiver for transmission. The composition of these primes under multiplication represents that public key. Seeing that, the secret prime held by both the sender and receiver is so large that it cannot be guessed by brute force in short order. The message should be highly secure. In ways, it is not.
The product of a pair of prime (odd) numbers is (2x+1) (2y+1). Which is also 4xy+2x+2y+1. That might be simplified and parameterized by factoring out a 2 from the first three terms. So, we have 2(2xy+x+y)+1 or another odd number based upon C. Where C is 2xy+x+y and or composite odd number is 2C+1. Seeing that our odd composite N = 2C+1. Factoring is only requires finding the solution of the Diophantine equation C = 2xy+x+y. A Diophantine equation is one with only whole number solutions. The question is, “How might that be done quickly?” We must use a general-purpose solver. Like, the one who works well with Diophantine equations. It is called the Miller-Kovarik Secondary Method.
It is as follows. The equation f(x,y)=2xy+x+y=C. So, g(x,y)=f(x,y)-C=0. If, we take g(x,y) and compose it with the equation for a parabola h(z) = z2 = 0. The solution for g(x,y)=0 are the x and y that make h(z) zero. The question is. How are those found.
If, one graphs the parabolic surface that arises. He will see the zero coinciding with the x and y from C = 2xy+x+y. It should be mentioned again that N = 2C+1. So, C = (N-1)/2. And, that might be substituted in the previous equations for C. Yet, of all those points on the surface, how does one identify x and y procedurally and not by visual inspection of a graph.
If, we plot a discrete mesh which forms a network describing the graph. We are half-way there with that approximation. From the set of points, who form the mesh, we must take the portion nearest the root of the parabolic surface. These can be identified by taken the average of the population of range values. Then, they can be set aside. So, this process might be completed within the boundaries of the surface which the represent. So, we create a new discrete mesh of a given resolution in this area and repeat the above process setting aside the lower portion, a secondary set. We, repeat this process until we locate a zero among the secondary set. Or, it is all that remains of the possible searchable discrete points.
The x and y whose range value is that zero. They are the solution for our Diophantine equation. And, 2x+1 and 2y+1 are our odd numbers that are the factors of N.
Such a efficient general-solver was not expected by Diffie and Hillman. Its time complexity is logarithmic. When, one considers the total number of the integral coordinates that form the graph of the parabolic surface as the input for the algorithm.
Also, in the case of a composite formed by a pair of primes, only a singular zero exists on either side of the boundary line, x = y.