19
$\begingroup$

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?
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – tylo
    Sep 27, 2013 at 11:24
  • $\begingroup$ 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. $\endgroup$
    – user4982
    Sep 28, 2013 at 20:30
  • 1
    $\begingroup$ Your questions are not stupid at all. They are legit questions of someone being introduced in Cryptography. The (stupid) answer to the first is: Because mathematical properties must be in order. The (stupid) answer to the second is: We choose VERY, VERY large numbers so no, it doesn't reduce security and it's not easier for the attacker to find the private key. $\endgroup$
    – Aventinus
    Jan 15, 2016 at 7:12

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Sep 27, 2013 at 14:21
  • $\begingroup$ @poncho: Right, thanks, the implication goes the other way. Obviously, $d = 65$ satisfies $5d = 1 \pmod {\phi(133)}$. $\endgroup$ Sep 27, 2013 at 15:36
12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is a perfect explanation! Thank you! Now I have another silly one, the number displayed on a RSA Token, is that a "chunk" of n or an entire prime number? $\endgroup$
    – Bluz
    Nov 17, 2016 at 16:53
  • $\begingroup$ replying to myself, it looks like it's not, I just checked and the number displayed right now is not a prime. So where does the number on a RSA token comes from? $\endgroup$
    – Bluz
    Nov 17, 2016 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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