Hacker Newsnew | comments | show | ask | jobs | submit login

"But if you have that result, figuring out which two prime numbers divide it requires you to check every single one of them"

It does not. There are many factorization algorithms that are significantly faster than trial division for large numbers (http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.ht...)

And your description makes little sense to me. I guess it is based on a bad understanding of RSA (http://en.wikipedia.org/wiki/RSA_%28algorithm%29). That does not convert your message to a prime.




Not for numbers made of only two primes (i.e. a semiprime). Those algorithms are for numbers with more than two prime divisors.

Read the description again then, RSA is a public key algorithm, and is not what I am describing.

-----


Many, but not all, of those algorithms will work for numbers which are a product of two roughly even sized primes (depending on size). Especially the Quadratic Sieve and Number Field Sieve class of algorithms (NFS, GNFS, SNFS, etc).

Size is key though. A rough guide of the GNFS times for a quad core PC would give:-

    c100 - c120: hours
    c120 - c140: days
    c140 - c160: weeks
    c160 - c180: months
    c180 - c200: years 
    
    source: http://www.mersenneforum.org/showthread.php?t=16311
(c100 means a 100 digit composite number, doesn't matter if it is just the sum of just two evenly sized primes).

For comparative sizing:-

    2^256 =~ c80
    2^512 =~ c160
    2^1024 =~ c320
So a 512-bit composite can be quite reliably factorised in a few months by a commodity PC. Parallelisation is a partial help, the first stage of the algorithm can be distributed, but the final stage(s) (~25% of the work) still requires a single machine to do the work.

Part of the hard work in choosing random primes to use within such encryption algorithms is avoiding numbers which are susceptible to each of those algorithms, e.g. avoiding primes with simple p-1 factorisations to avoid being susceptible to Pollard's P-1 algorithm.

The wrong choice of prime and the factorisation becomes (relatively) trivial.

-----


512 bit keys taking weeks was the case a few years ago on old hardware, but even then you could do it in a few hours/days with a modest BOINC setup.

I'm not sure how a modern CPU would do, but I suspect on the low end of "weeks".

-----


A 512 bit composite is not a lot of entropy - it's about 45 bits of entropy, which isn't much. sqrt(512) * 2 (since each prime is approx the size of the sqrt of the number, and there are two of them).

A few months to crack a 45 bit encryption doesn't sound quick to me. Even a 64 bit encryption would take many centuries at that rate.

-----


Each prime is approximately sqrt of the product, not of size that is sqrt of size of product, the size of primes is approximately half of the size of their product. As they are primes their entropy is slightly lower than their length, but not too much (there are approximately x/ln(x) primes smaller than x, which would lead to entropy of 256bit prime being 248.5bits)

-----




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: