RSA breaking math

[s. roelants]

As i am one of the mathematically challenged :D i was wondering:

Seems the basic thing todo while wanting break some RSA type of code would be finding the prime numbers p en q.

We know n=p*q which is sent with the message.

So to find p and q is seems quite hard because it involves prime factoring of n.

The question now is:
if you would have a list of all prime numbers between 2 and sqrt(n) such that you would be able to do P[i]=pi

Would this effectively break the RSA code? Or would the prime factoring difficulty still not have been solved?

would you still have to run through the entire list looking for a
n%P[i]=0 ?
Maybe this would just be a bit faster since you don't have to check if your number is prime??

Of course the list would be quite big :D but it's a theoretical question, seeing that computer hardware evolves exponentially and all

[galathaea]

The problem with this method (on the most secure key sizes used today) is twofold:

The memory requirements for holding all of those numbers would be greater than the estimated number of particles in the universe.
The time to run such a test O(sqrt(n)) would take more time than the current age of the universe on todays fastest computer.


However, there are faster factoring algorithms out there besides the one you mention, with much smaller memory requirements. There is a modified general number sieve method (working over certain algebraic rings) that is the fastes known method. Using distributed computing, it was able to break a key over a hundred digits long in a matter of months. But this method would not work on 500 digit keys in decades, even with the fastest computers. However, mathematicians are coming out with better and better algorithms regularly.

This will all be a moot point, however, once quantum computing begins. There is already a well known quantum factoring algorithm that works O(ln(n)), the fastest possible order of magnitude....

[Amn]

Galatheaea, man, i have gotten impression you know a lot about encryption techniques, and i happen to be digging this stuff too, however without any experience in the area. Would you recommend some good online reading about the topic please ?

Thanks in advance ! :D

[galathaea]

Amn, I'd love to help you with your search! However, this is such a huge topic, that I can only give you some general resources until I know more about what you desire...
First, here are some general resources (the standards):
RSAs FAQs (http://www.rsasecurity.com/rsalabs/faq/index.html)
a pdf intro (http://vig.pearsoned.com/samplechapter/0130915181.pdf)
another FAQ (more on breaking) (http://www.faqs.org/faqs/cryptography-faq/)
and finally,
NISTs publications (http://csrc.nist.gov/publications/)

Basically, however, there are a lot of subfields you should get acquainted with if you wish to become more familiar with the field of cryptography. These are, most generally,

Encryption algorithms (the basic, past and modern, including substitutions, block/stream -- I put these in the same category contrary to most, public key, etc...)
Pseudo random number generators
Cryptanalysis (linear, differential, etc...)


To really have a good understanding of what is going on in the field, it is important to have a good mathematical knowledge as well. This should cover

Group theory
Number theory (both abstract and analytical)
Abstract algebra (rings, fields, algebras -- including the theories of ideals and class fields)
Combinatorics (permutations/combinations, graphs, trees, etc...)
Variety theory (at least enough to understand elliptic curves and their relations to the other listed topics)


I am very glad to hear you are interested in this mysterious area filled with intrigue, deception, and lies! I can give you more internet resources on any particular topic, but I am sure you will find that the internet is littered with info on this, and that a google search may be faster than consulting me. But I'm always here as well!

[Amn]

Sorry man, didnt mean to pursuade you to write t\so much. I am acquinted with encryption generally, but i am mmore interested in algorythms and estimations that deal with BREAKING ENCRYPTIONS ;)

I heard there are people breaking the RSA5 in a matter of month without any extra computing power. Dont know about MD5 or the CryptoAPI stuff...

Still, thanks SO MUCH for the links and explanations, i ll get on to them ASAP !