If we were to solve this diophantine equation, we would easily have the roots of n:
xy+x(x-1)=n
x²+xy-x=n
with y=0, it is simply the square root of n+x.
y=1 always gives the square root of n.
y=2 always gives the square root of n-x.
y=3 always gives the square root of

Now then, assume that f(x)=x²+xy-x=n.  Let us try n=221 first.  It's factors are p=13 and q=17, where pq=221=n.  Now, f(p)=n and f(q)=n.  In f(x), there is a y variable.  With f(p), y=(q-p+1), and with f(q), y=(p-q+1) So the question is, how to solve it as a diophantine equation.

Anyone have any experience with diophantine equations? (Please don't post links to wikipedia)

http://www.engadget.com/2010/03/09/1024-bit-rsa-encryption-cracked-by-carefully-starving-cpu-of-ele/


was this mentioned yet? ^ ^

oh, sry then, my bad..

We can't use the hashes to find the private key.  I believe, that this is because of how a signature works.  Anyway, I'm gonna go look up how they sign it.  I think it's just encryption of the MD5 hash, with the private key, and that might allow some Chinese remainder magic, but I don't know.  We would have to know how the hashes are made in the first place.  EG, over what data is the hash made.

Anyway, I still think that the best way to do it is to factor the numbers.

If you have oppenssl, then this page can help here

If you have any more questions, feel free to ask.

We've already had lots of talk about factoring the key, in another topic (but it's understandable that you missed it: there's lots of activity on the forum, and that is a good thing): http://ourl.ca/6236

I have summarized multiple times how impractical the factorization is (unless some ground-breaking algorithm comes to the rescue, which we should not hold our breath on): basically, three orders of magnitude harder than the state of the art.
A linear extrapolation of the figures given in the paper detailing the factorization of RSA-768, consistent with what we know of 512-bit RSA factoring, gives the need of sifting through 10000-100000 TB (yes, I really mean terabytes) of data, after those have been produced by several dozen thousands of computers running for years (or ten times as many computers, running for one tenth of the time).
This does not, however, mean that we can't spend up to several CPU-years trying to find a factor by Trial Factoring (beyond that would not be reasonable): it's extremely unlikely that we'll succeed by sifting through a search space which represents an vanishingly small part of a particle, compared to the whole universe - but such is the beauty of random.

No argument there
I was just explaining him that distributed computing probably wouldn't help enough for the factorization to become practical, with the current algorithms