Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am just learning about the RSA algorithm. Looking at the first two steps:

  1. Choose two distinct prime numbers $p$ and $q$.
  2. Compute $n = pq$.

I have some probably stupid questions:

  • Why do $p$ and $q$ have to be prime numbers? Why couldn't they be any integers or odd integers? Or does that break the whole algorithm?
  • Because prime numbers are rare in comparison to regular integers, does restricting the algorithm to only prime numbers reduce security? It would seem easier to find the private key if an attacker knows it's only going to be some prime number?
share|improve this question
    
In really short: Because to calculate $\phi(n)$ you need its factorization. If there are one or more small (and easy to find) factors, you could just have removed them before (then they are meaningless for security, only make the numbers longer). The assumption of prime numbers being "rare" is only partially true: There are more non-primes, but even for 1000 bit long numbers it is still every $ln(2^{1000}) \approx 700.$ number in average. And that is still a lot. –  tylo Sep 27 '13 at 11:24
    
RSA is usually based on exactly two prime numbers. If you have three prime numbers (or more), n = pqr, you'll basically have multi-prime RSA (try googling for it). However, if you just use random numbers (p and q are random numbers, thus commonly composites of many numbers), it'll likely not give good results. –  user4982 Sep 28 '13 at 20:30

2 Answers 2

up vote 3 down vote accepted

In order to generate a RSA key pair, you are to find a public exponent $e$ and a private exponent $d$ such that, for all $m \in \mathbb Z_n^*$, i.e. $m$ is relatively prime to $n$, $(m^e)^d \equiv m \pmod n$. It is a consequence of Euler's theorem that if $e, d$ satisfy the equation $ed \equiv 1 \pmod {\phi(n)}$, they are such a valid public/private exponent pair.

The fundamental theorem of arithmetic says that every integer has a factorization into powers of prime numbers that is unique to the integer, save for the order of the factors.

The definition of Euler's $\phi$ function is that $\phi(n)$ equals the number of integers less than $n$ and relatively prime to $n$. In order to determine this number, you have to know the factorization of $n$.

Consequently, if you select a number $n = pq$ where $p, q$ are both prime, you will have selected a number you can factor, but, if it is large enough, no one else can factor. The reason for this is because, using known factorization algorithms for arbitrary integers, the running time of such algorithms depends on the relative size of the second largest prime factor of the input. This means that given the public exponent $e$ only you can determine the private exponent $d$.

(Note: The hardness of performing the RSA private key operation $m \equiv c^d \mod n$ given only the public key $e, n$ as above, is known as the RSA problem, which hasn't been proved to be as hard as factoring the modulus. The best known method is however by factoring the modulus $n$ in order to determine $d$ given $e$.)

It also means that if you were to select $p, q$ just as odd integers, you would make it harder for yourself to find $\phi(n)$, while at the same time decreasing the relative size of the second largest prime factor, and thereby making it easier for everyone else to factor $n$. In fact, it would be as hard for you to factor $n$ as it would be for everyone else, so you would completely loose the trapdoor component of your scheme (if not making it completely infeasible to find a pair $e, d$).

Regarding your second question, for large $x$, the number of primes less than $x$ equals $\pi(x) \approx \frac x {log(x)}$. Hence, the number of primes roughly equal to $\sqrt n$ is, for large $n = pq$, large enough to make factorization algorithms faster than a brute force search. Besides, by the arithmetic theorem above, the adversary is really only interested in prime numbers anyway, so the question is moot.

share|improve this answer
    
Minor nit: it's not true that $e, d$ must meet (satisfy) the equation $ed \equiv 1 (\bmod \phi(n))$. One counterexample is $n=133$, $e=5$, $d=11$. That has $ed \equiv 55\ (\bmod \phi(n) = 108)$, however ${(m^e)}^d \equiv m\ (\bmod\ n)$ for all $m$. This is a minor point, however we should avoid telling beginners things which aren't true. –  poncho Sep 27 '13 at 14:21
    
@poncho: Right, thanks, the implication goes the other way. Obviously, $d = 65$ satisfies $5d = 1 \pmod {\phi(133)}$. –  Henrick Hellström Sep 27 '13 at 15:36

Assume $n$ is 21. If you try to find the possible factors you have to try around until you find 3 and 7. This is of course easy because of the small numbers, but there is no effective way to do that for big numbers. (And those used in RSA are really big)

Now assume $n$ is 32. You can split that into 2 * 2 * 2 * 2 * 2. Now you only have to multipy those (bruteforce) until you get two numbers.

Possible Combinations here would be:

0,32 / 2,16 / 4, 8 / 8,4 / 16,2 / 32,0

(that means: one of those few combinations has to be the right answer)

Now that of course gets more complicated with bigger numbers too, but still quite easy/fast. So basically if those numbers are not primes, that you can just split up $n$ as much as possible and from there you have an easier way to find $p$ and $q$. If both are primes you have to try values for $p$ and $q$ until you find exactly the right values.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.