Surrogate factoring explained

jstevh_at_msn.com
Date: 02/24/05 

Date: 23 Feb 2005 17:06:57 -0800

The idea behind surrogate factoring is driven by the way numbers are
selected for RSA encryption, as the way it works is you get two primes
p_1 and p_2, specially chosen so that their product is hard to factor,
and then get that product p_1 p_2, which is your public key.

Now after that work in choosing p_1 and p_2, the front door attack of
directly factoring the public key is the "hard problem" of factoring.

The entire point of surrogate factoring is to render that useless by
what is esentially a back-door attack of shifting the factorization
from the hard target to an easier surrogate, which is factored, and its
factors are then used to factor the target.

For a while now I've been searching to see if there was a mathematical
way to implement that idea, that is, does the math support such an
approach?

My latest efforts focus on some relatively simple quadratics, but I
want to emphasize that the point of surrogate factoring is not so much
the specific equations being used with a given approach, but the entire
idea of breaking RSA encryption by factoring some surrogate connected
to the hard target, in order to factor the target.

Necessarily my efforts have been in rationals, where there are
additional difficulties created by the infinity of rational factors for
a given integer.

So a lot of research is actually focused on limiting the number of
rational solutions to a checkable finite set of possibles.

The current techniques can be proven--unlike previous attempts by
me--to have a solution within a finite space, where determining that
solution in general, is the next task.

My current focus is on two quadratics:

yx^2 + Ax - M^2 = 0

and

yz^2 + Az - j^2 = 0

where the surrogate is T, where T = M^2 - j^2, and M is the presumbably
hard target, and j is some chosen integer.

Here x, y and z are basically helper rationals, used in the search for
a solution, while A it turns out, is left undetermined.

Those quadratics are of interest because you can prove that x is
actually dependent on the factorization of T and j, while z is
dependent on the factorization of T and M, so I have a surrogate
situation.

It's not hard to show that the factorization of T itself is key in
determining solutions, so it's the key surrogate.

However, at this time, I personally haven't been able to always get a
solution, so surrogate factoring is still mostly a theoretical concept.

Yes, I have factored numbers with it, but it doesn't always factor, so
I have had to back down from prior claims declaring it to be a solution
to the factoring problem.

But, current results are still intriguing, though not yet perfect.

Remember, the point of surrogate factoring is to break the RSA
encryption technique, which depends on picking special primes so that
their product is very hard to factor, by instead shifting to some
easier to factor number, and relating its factorization to the
factorization of your target.

If it can be made viable, it would defeat the RSA encryption technique.

The latest quadratics that I'm researching are the best candidates yet
for finding a full solution, as a rational solution can be proven to
exist, and if the rules governing the system can be worked out, then it
is reasonable to suppose that a full methodology can be determined so
that the system always works.

Or, if it can be made to work a high percentage of the time with very
large numbers, it would still be valuable even if not perfect.

At this time, I have little data on the effectiveness of the algorithms
known to me with very large numbers in the range, say, of the RSA
Challenge numbers, though I suspect it is low, as given the prize money
attached to those numbers, if anyone factored them, that would be news!

So to recap, surrogate factoring is an idea that has to do with
factoring one number to try and factor another--presumably hard target
number--in order to break the RSA encryption technique of picking hard
targets.

At this time, the current state of the art appears to be well below the
goal, but the concept is still one that has not been proven to be
flawed.

Even if the current quadratics being researched are not the ones that
give a full solution, they may point the way to others, which may.

There is much basic research to be done, and I invite interested
parties to consider the world of surrogate factoring.

James Harris

Relevant Pages

  • Surrogate factoring explained
    ... The idea behind surrogate factoring is driven by the way numbers are ... selected for RSA encryption, as the way it works is you get two primes ... directly factoring the public key is the "hard problem" of factoring. ... to the hard target, in order to factor the target. ...
    (sci.crypt)
  • Proper evaluation of surrogate factoring
    ... Surrogate factoring is just kind of a wild idea that means you have to ... I am being very serious here, modern mathematicians lie a lot. ...
    (sci.crypt)
  • Re: SF: Areas of confusion, infinity
    ... > notably the set of rationals. ... choosing any integer is the same as the probability of any other ... That's what make the factoring problem interesting, i.e., not ... > is naive with the surrogate factoring theorem. ...
    (sci.crypt)
  • Re: What surrogate factoring theory now says
    ... Surrogate factoring theory says that you can turn factoring a hard ... once the engineering is figured out that is achievable. ... Mainly I just added one more congruence to the difference of squares. ...
    (sci.crypt)
  • Re: What surrogate factoring theory now says
    ... Surrogate factoring theory says that you can turn factoring a hard ... once the engineering is figured out that is achievable. ... Mainly I just added one more congruence to the difference of squares. ...
    (sci.crypt)
Quantcast