September 25th, 2009, 05:36 AM

What's so special about prime numbers? (RSA)
So I've been trying to get a much deeper understanding of why the RSA cryptosystem works, and one of the questions that I've had problems finding an answer to, is what is actually so special about prime numbers?
The premise of RSA is the factorization of primes. The only reason I've been able to find as to why primes are used instead of any other integer is that it is believed to be much more difficult to factorize primes. I can understand why this is an advantage, but when I try to use nonprimes as the values for p and q, the decrypted message is not the same as the one which was decrypted, meaning that the algorithm only works when p and q are prime numbers. The main thing which keeps coming up in my research about primes is that all nonprime integers can be written as a product of primes (fundamental theorem of arithmetic), but I don't really see why that would determine whether or not RSA works. So why is it that prime numbers are necessary for RSA to work?
Thanks
September 25th, 2009, 10:32 AM

Answer 1: If gcd(a,n)=1, then a^phi(n) is congruent to 1 modulo n. phi(n) is the totient function that counts the number of residues modulo n that are coprime to n. These facts comprise Euler's theorem.
For n>3, every positive integer a<n satisfies gcd(a,n)=1 (in other words, phi(n)=n1) if and only if n is prime.
The completeness of RSA is based on these properties.
Answer 2: There is no shortcut here  if you want to understand public key cryptography, you MUST learn basic number theory. There are many fine books and web pages that offer a good introduction to these concepts, for people who are new to this kind of math. Some of these books and webpages are specifically oriented to RSA.
If you don't have the interest or enthusiasm to study number theory, your PK cryptography project will go nowhere, and I recommend that you stop right now, and change direction!
If you want to learn number theory, find a good book, and if necessary a tutor. Within two weeks of hard studying, you can learn enough number theory to fully understand the completeness argument for RSA.
BTW: Your post seems to show a lack of very basic understanding. It doesn't make sense to "factorize primes," or to speak of this as being difficult! If we know that p is a prime, then its only prime factor is p! It cannot be decomposed into any other primes, so factorization takes no effort at all!
What is difficult, is to factor composite numbers, with at least two very large (100+ decimal digit) randomly chosen prime factors.
For an RSA modulus n=pq, phi(n)=(p1)(q1). If you know phi(n), then you can quickly compute the secret (decryption)exponent. If you can factor n, you can compute phi(n) by simple multiplication. Nobody knows a quicker way to find phi(n) than factoring n, or any other shortcut to compute the secret exponent. So the supposed security of RSA rests on the supposed difficulty of factoring n into p and q, where p and q are big primes that were chosen at random.
You MUST learn these basic concepts, in order to understand RSA!
Comments on this post
Last edited by mah$us; September 25th, 2009 at 10:49 AM.
September 26th, 2009, 05:19 AM

Haha, I guess I miscommunicated, I am completely aware that you can't factorize primes. I meant factorizing the product of two primes (n=pq). Thanks for the information though.
December 3rd, 2012, 04:27 AM

The RSA encryption takes direct advantage of the awesome compactness of modern numbers, as compared, for example, to the caveman's numbering notation.
As you increase the length of a modern number, the actual quantity expressed by it grows incredibly rapidly.
For example, by simply making up an arbitrary number that fills an entire white page, you will express a quantity that surpasses the imagination of any normal person. Put differently, you will create a "search space" so big that no computational instrument will ever be able to explore it entirely.
By asking someone to find the factors of an RSA number, you take direct advantage of this huge search space.
Why prime factors? Simply to ensure that there are two factors and two factors only that the number can be decomposed into. If the answer was not unique, or there were many possible answers, then this technique will not be so useful.
EDIT: That is to say, you want to create a computational challenge where only two numbers can divide the word provided.