RSA and the factorizing problem

[Eóin]

Well I wish you luck, but 2^70 operations seems very small to me. Surely you'd be dealing with 2^200+ operations at least?

[Bieb]

If you can really do it in a reasonable amount of time, just spend some money, get the most powerful beast of a computer you can, and then start solving the challenge numbers. 

[Brett Kuntz]

I dont understand how these big numbers are used in encryption or why finding the two numbers which were multiplied together would 'crack' the encryption. Two prime numbers, 7907 and 7919, multiplied is 62,615,533. Now say I used the 62,615,533 in my encryption, how would knowing it was made from 7907 and 7919 help me beat the encryption?

BTW, if there was a formula to generate prime numbers exceptionally fast, would that help crack the RSA's encryption?

[aaustin]

Well I wish you luck, but 2^70 operations seems very small to me. Surely you'd be dealing with 2^200+ operations at least?

2^70 iterations is actually very high. 2^200 would be a virtual impossibility even if all supercomputers in the world were used for millions of years. A single NFS iteration takes about 7 seconds on my 2.4GHz P4 with 640MB of RAM varying with number size. Even if 2^24 or 16 million computers were used, it would still take 7*2^46 seconds, which is many people's lifetimes.

I dont understand how these big numbers are used in encryption or why finding the two numbers which were multiplied together would 'crack' the encryption. Two prime numbers, 7907 and 7919, multiplied is 62,615,533. Now say I used the 62,615,533 in my encryption, how would knowing it was made from 7907 and 7919 help me beat the encryption?

BTW, if there was a formula to generate prime numbers exceptionally fast, would that help crack the RSA's encryption?

It's not as simple as combining two prime numbers together. However, the strength of the algorithm relies on the fact that it is difficult to factor two very large numbers. A prime Generation formula will not affect the speed of factoring numbers except at very small sizes. For the large numbers that are used by RSA, you need a really fast algorithm for factoring numbers into their prime components. Supposedly this has not yet been discovered yet, so it is reasonable to assume it cannot be done. I don't believe this to be true which is why I'm working on a better sieve.

[Eóin]

kunt0r, Basically it comes from  the math behind RSA.

A public key consists of two number e and m say. m is the product of our two large distinct primes, call them p and q. So we have m = pq.

Now a private key also consists of two numbers d and m. There are special conditions on  e and d but assuming they're satisfied we can implement RSA encryption as follows.

• Convert our plain text into a number, t.
• Calculate c = t^e mod m.
  This is our cipher number. It can be converted back into giberish text for the purposes of transmitting
• On the recieving end we do c^d mod m = t and get the plain text version back.

Why this works is too complicated to get into here, but the important thing is that if someone intercepts a message encrypted with e and m they can only decrypt if they know d.

The potential achilles heel of RSA is that there is a formula for calculating d, specificially d = e^-1 mod (p-1)(q-1).

So if someone figures out a way of factoring m into p and q then they'll be able to work out d from what they know in the public key and decrypt any message.

aaustin, out of interest what size number are you aiming to factor?

[Brett Kuntz]

Ah it makes sense now, thanks.

[aaustin]

aaustin, out of interest what size number are you aiming to factor?

I have no idea yet. I'm still working on the logistics of the sieve. Hopefully pretty large numbers, RSA size. I'm trying to simplify it as much as possible before I make it.

[AeroASM]

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?

You are right, but it would be practically impossible. Also, it would not be instant, because electricity travels "only" at 300,000,000 metres/second

[Bieb]

Hmm, how impossible is practically impossible.  It would be pretty cool if the government could build such a device so as to be able to instantly decrypt RSA encrypted messages with just a public key.

[AeroASM]

You would have to custom-build your own silicon chip. Notice how the only people who do this are the people who then sell millions of these chips at relatively high prices - and so the design and manufacturing process is very expensive (several billion?). The only body who could make such a chip would be the government but I don't think the people would like the government to spend the taxpayers money on infringing the taxpayers' privacy.

[BigDaddy]

To answer the original question, factoring is an NP class problem.

[Bieb]

You would have to custom-build your own silicon chip. Notice how the only people who do this are the people who then sell millions of these chips at relatively high prices - and so the design and manufacturing process is very expensive (several billion?). The only body who could make such a chip would be the government but I don't think the people would like the government to spend the taxpayers money on infringing the taxpayers' privacy.

Well, there's always the "black" part of the budget  :eek

[dsouza123]

One of the RSA challenges RSA-200 (a 200 digit integer) was factored a few days ago.

The older ones were named by length of the number in digits, the newer by length in bits.

It wasn't for a prize, but to demonstrate what resources are needed to factor
a hard number of that size.
The prize numbers are still unfactored, except the smallest.
Also most of the non prize numbers remain unfactored.

Used GNFS, started sieving end December 2003 finished October 2004,
started matrix step December 2004.

Estimated 55 Opteron 2.2 years for the lattice sieving.
Used a cluster of 80 Opteron 2.2 three months for the matrix step.

One of the effects of the challenges is get people to optimize existing
algorithms and to come up with new ones,
so start thinking,  one of the earlier challenges RSA-129, when it was isssued
it was thought it would take 40 quadrillion years, it was factored in 1994 in 8 months,
17 years after the challenge was issued because of a new algorithm MPQS along with
advances in processing speed.

[Posit]

Interesting subject. One of my motiivations for learning MASM is to optimize a C++ arbitrary-length integer class I wrote as part of a BS capstone project. The project itself is a parallel system for factoring. Right now there are a dozen or so P4 machines busy working on RSA-640, although the odds of actually finding the factors any time soon are exceedingly slim, since the agorithm employed is a modified form of Fermat's method.

To understand the two algorithms that are currently the fastest, the Quadratic Sieve and the Number Field Sieve, requires quite a bit of math background, more than I had going in, for sure. I suspect I won't comprehend all the nuances until after taking a graduate course in Number Theory. One reason that both algorithms are so useful is that they are almost perfectly parallelizable, so are eminently suitable for distribution to thousands of clients over the internet. They still run in sub-exponential time, however. To date, no polynomial time factoring algorithm exists. (At least not publicly--with the NSA being the largest employer of mathematicians in the U.S., you never know.)

If, however, as aaustin wrote, "RSA and factorization in general is a little easier than previously suspected," then we will no doubt see your successful factoring of the RSA challenge numbers in the next few months. ;-)

Since factoring is a problem I will be delving into further in grad school, I'll definitely keep up with the posts here.

[aaustin]

Interesting subject. One of my motiivations for learning MASM is to optimize a C++ arbitrary-length integer class I wrote as part of a BS capstone project. The project itself is a parallel system for factoring. Right now there are a dozen or so P4 machines busy working on RSA-640, although the odds of actually finding the factors any time soon are exceedingly slim, since the agorithm employed is a modified form of Fermat's method.

To understand the two algorithms that are currently the fastest, the Quadratic Sieve and the Number Field Sieve, requires quite a bit of math background, more than I had going in, for sure. I suspect I won't comprehend all the nuances until after taking a graduate course in Number Theory. One reason that both algorithms are so useful is that they are almost perfectly parallelizable, so are eminently suitable for distribution to thousands of clients over the internet. They still run in sub-exponential time, however. To date, no polynomial time factoring algorithm exists. (At least not publicly--with the NSA being the largest employer of mathematicians in the U.S., you never know.)

If, however, as aaustin wrote, "RSA and factorization in general is a little easier than previously suspected," then we will no doubt see your successful factoring of the RSA challenge numbers in the next few months. ;-)

Since factoring is a problem I will be delving into further in grad school, I'll definitely keep up with the posts here.

I'm still working on the optimized large integer math routines. I haven't even started the factoring algorithm as I don't really have much time for programming. Neither NFS nor MPQS is good for numbers of RSA size so they're not really worth learning. NFS in particular is bad because it requires primorials, which are slow to calculate or require lots of memory. It also requires extensive prime testing (which is a pain in the neck) and GNFS is actually flawed in extreme cases. I'm designing QRSeive specifically to not use lots of constant data (only temporary data) in the hopes it won't need virtual memory disk space.