RSA and the factorizing problem

[realcr]

RSA algorithm's security is dependend on the fact the there is no fast way to find the divisors of a number
N=pq , when p,q are primes.
I wish to know what fast means? Does it mean that there is no polynomial algorithm to do that?

realcr.

[dsouza123]

The fastest algorithm I am aware of is NFS (number field seive).

There are other algorithms that search an extremely large number range
that could be written in MASM but would have to start the search very
near a factor or the number for the function that leads to a factor.

The big integer routines that a few people in the forum have been writing
or one of your own, could be used to implement the simpler of the algorithms.

Trial division using integer numbers that are half the bit length of the RSA.
Using integer division or mod (mod result 0 means a factor is found).

Difference of two integer squares, one of the square roots of the integer squares
is half the bit length the other could be much shorter.
Using addition(optimized) or multiplication(unoptimed) and square root.

I have done both in ubasic and may recode them in MASM to see how fast they could get,
and if just the right starting point is picked, factor a RSA number. :U

[roticv]

RSA algorithm's security is dependend on the fact the there is no fast way to find the divisors of a number
N=pq , when p,q are primes.
I wish to know what fast means? Does it mean that there is no polynomial algorithm to do that?

realcr.

It is polynomial, but even so it is too slow to factorise, say the 1024bit RSA number. I think it would take years to factorise the 1024bit RSA number using the current fastest alogrithm and hardware, but don't take my word, since I am not yet a mathematican.

[Tedd]

'Fast' just means 'within a reasonable amount of time.'
What you choose reasonable to mean depends on the context.

A number seive is a reasonable method for finding primes (remove all multiples of 2,3,5,7,11,...(upto square-root of highest number required) -- whatever remain are primes.) But it's a general method. There are special methods that go a lot faster for special types of primes (Mersenne Primes: 2^n-1)

There are also faster general statistical methods which 'assure' that a number is prime after 'enough' tests (the more tests, the more sure you can be that it is prime; but it's not a definite test)

To see what 'fast' really means, see http://www.rsasecurity.com/rsalabs/challenges/factoring/
(576-bits has been factored)

[dsouza123]

An unoptimized direct translation of ubasic/pascal code of the Difference of two squares factoring
of a tiny (64 bit) RSA type number.

n   = RSA type number
srt = sqrt(n)

bsrt = srt+1  initially
bs   = bsrt*bsrt
while not done
  ls    = bs - n
  lsrt  = sqrt(ls)
  if ls isn't integer square
    bsrt++
  else
    done

lsrt is the integer sqrt of ls
bf = bsrt + lsrt
lf  = bsrt  - lsrt

[attachment deleted by admin]

[aaustin]

I am working on this problem as we speak. RSA and factorization in general is a little easier than previously suspected. I am programming my custom sieve which I expect will be able to factor numbers faster than the number field sieve. It should also be fast enough to be able to prove primality faster than other primality methods. Right now I'm stuck on large integer multiplication, division, and square root taking(Anyone know how to do FFT multiplication?). Once I have those the rest of the program will be somewhat easy and high level. I'm not going to divulge the method just yet as I understand there is money at stake.  :dance:

[rea]

I dont know exactly how this things work, but I like this things ;).

[Mark_Larson]

I am working on this problem as we speak. RSA and factorization in general is a little easier than previously suspected. I am programming my custom sieve which I expect will be able to factor numbers faster than the number field sieve. It should also be fast enough to be able to prove primality faster than other primality methods. Right now I'm stuck on large integer multiplication, division, and square root taking(Anyone know how to do FFT multiplication?). Once I have those the rest of the program will be somewhat easy and high level. I'm not going to divulge the method just yet as I understand there is money at stake.  :dance:

  GRIN  So why should we "help" you if money is at stake? ;)

  I've got fast code for all 3 of your slow operations.

[dsouza123]

The RSA problem is take a large integer number of various bit lengths, 1024 bit for example.
It is the product (multiplication) of two prime numbers (positive integers with only 1 and itself as factors)
each (exactly ?) half the bit length of the RSA number.

The issue is given the RSA what are the two factors.

For example  
35 = 5 * 7
100011 = 101 * 111

Austin if you want to prototype your algorithm (and verify that it works) before
implementing it in assembly, you can use the free  ubasic which has all the math operations
you mentioned and handles numbers 2600 digits long, it has a 32 bit version, it is written in assembly
language and is fairly efficient (some factoring algorithms have been written with it and are available).

[Bieb]

I'm probably wrong here, but since any alorithm can be implemented in hardware, then in theory, if you wrote a factoring algorithm that would take years to execute in software and implemented it as a circuit, wouldn't it instantly return an answer?

[aaustin]

Hard wiring a factoring algorithm will only make it some factor faster; say for instance, 100 to 1000 times faster. Since even the number field sieve would take 2^70 iterations on a single computer, this device would not necessarily be fast enough to factor the number in a reasonable amount of time.

[Bieb]

What do you mean by reasonable?  Obviously, you won't be able to do it fast enough to jeapordize the security of RSA, but if you could do it in a couple of years, it would certainly be worth it to get that cash prize.

[roticv]

I think the key to factorising would to be figure out a even better algorithm (faster in general) than say number sieve factorising. Actually I am pretty much interested in this topic, but I have hit a dead end on figuring out a faster algorithm.

[dsouza123]

New algorithms along with faster hardware are what has greatly reduced factoring time.

The NFS replaced the QS, quadratic sieve. 
Distributed networks of x GHZ PC's with 100s of MB of RAM have replaced Cray supercomputers.

[aaustin]

What do you mean by reasonable?  Obviously, you won't be able to do it fast enough to jeapordize the security of RSA, but if you could do it in a couple of years, it would certainly be worth it to get that cash prize.

By reasonable, even a year or so would be reasonable. I quoted 2^70 iterations already using the GNFS. It would take several million computers a few hundred years to complete.

I've been working with the Quadratic Residue Sieve. It turns out that it's perfect for RSA numbers. If optimized, it should be able to factor an RSA number on a single PC in less than a year. It does require quite a lot of memory though. I'm writing my library to use 256MB.