25
$\begingroup$

Despite having read What makes RSA secure by using prime numbers?, I seek a clarification because I am still struggling to really grasp the underlying concepts of RSA.

Specifically, why can't we choose a non-prime p and q?

I do understand the key concept: multiplying two integers, even two very large integers, is relatively simple. However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.

If this is correct, then the original question posed by the OP in this thread continues to befuddle me. This section from Henrick's answer in this post contains the relevant information:

It also means that if you were to select p,q just as odd integers, you would make it harder for yourself to find ϕ(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).

But I do not understand why we make it harder for ourselves to find ϕ(n). I BELIEVE that it has to do with the fact that for any prime, n, all integers up to n-1 are relatively prime. If the integer is not prime, then we actually need to find which integers up to n are actually relatively prime.

I understand how we are decreasing the relative size of the 2nd largest prime. For example: 10403 has prime factors of [101,103] while 11000 has prime factors of [2, 2, 2, 5, 5, 5, 11].

So, if I understand things correctly, choosing a non-prime p and a non-prime q would theoretically work, but the issue is that we would be creating a more insecure encryption scheme since:

  • the product of non-prime p and non-prime q are more easily factored (2nd largest prime is smaller than if p and q were prime);
  • finding ϕ(n) becomes more difficult for the key generator step, which decreases efficiency with the aforementioned decrease in security

Sorry if this is completely obvious, but I am a newbie in higher math and programming. I really want to understand this as deeply as I can.

$\endgroup$
  • 2
    $\begingroup$ It's harder to find $\varphi(a*b)$ where $a$ and $b$ are randomly selected odd integers because you have to know the prime factorization of each one as $ \varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$. If $a$ and $b$ are typical RSA size numbers factoring them is non-trivial. $\endgroup$ – puzzlepalace May 19 '16 at 18:52
  • 2
    $\begingroup$ By the way, it's not clear if your question is about the correctness of RSA or the security of RSA (i.e. does RSA need to have a modulus with two prime factors to be correct vs does RSA need to have a modulus with two prime factors to be secure). $\endgroup$ – puzzlepalace May 19 '16 at 23:24
  • $\begingroup$ The answers below are all good, but if you still struggle to get them, maybe enlightenment will come from looking at another angle: why use only /two/ primes ? the algorithm can be perfectly adapted to use three primes p, q and r. You just get a comparatively bigger modulus for equivalent security. $\endgroup$ – b0fh May 20 '16 at 13:09
23
$\begingroup$

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.

Not categorically. Factoring a large integer is trivial if it is only composed of small factors.

A fairly naive algorithm for factoring N is the following:

while N > 1:
  for p in increasing_primes:
    while p divides N:
      N = N / p
      factors.add(p)

With this algorithm, $340$ $282$ $366$ $920$ $938$ $463$ $463$ $374$ $607$ $431$ $768$ $211$ $456$ can be factored in exactly $128$ iterations of the innermost while. (The number, of course, is $2^{128}$)

The more prime factors a composite number has, the smaller those factors have to be. For example, $919 \cdot 677 = 622$ $163$. With the naive algorithm, this takes $157 + 1 = 158$ iterations to factor. A number of roughly the same size comprised of three factors, $73 \cdot 89 \cdot 97 = 630$ $209$, only takes $25 + 2 = 27$ iterations to factor.

Similarly, a 1000-digit number composed of two roughly equally-sized factors will take about $10^{497}$ iterations to factor. A 1000-digit number composed of 100 roughly equally-sized factors will take about $434$ $294$ $481 + 99 \approx 10^{9}$ iterations. And a 1000-digit number composed of 1000 roughly equally-sized factors will take about $4 + 999 \approx 10^{3}$ iterations.

So, to make factoring as difficult as possible, you want the prime factors to be as large as possible, which means you want N to have the fewest factors possible. With $p$ and $q$ prime, $N$ has two factors. With $p$ and $q$ composite, $N$ has at least four factors, possibly more.

Note that this is far from a complete answer on why (we think) RSA is secure, but I hope it gives a more intuitive / example-based idea of why $p$ and $q$ should be primes.

Note also that $p$ and $q$ should be similar in magnitude. If one is much larger than the other, factorization becomes easier. For example, if $p = 43$, the naive algorithm would only take $14$ iterations.

(After reading the comments (thanks Taemyr and Daz C), I corrected some mistakes in the answer. The main point is unaffected.)

$\endgroup$
  • 5
    $\begingroup$ if p divides N should be while p divides N. $\endgroup$ – Taemyr May 20 '16 at 22:27
  • 1
    $\begingroup$ How are the # of iterations determined? $\endgroup$ – Daz C May 21 '16 at 16:08
  • $\begingroup$ @Taemyr You're right, thanks! I corrected the algorithm. $\endgroup$ – marcelm May 21 '16 at 18:52
  • 1
    $\begingroup$ Nitpicking, but your code won't factor $2^{128}$ in 128 iterations as you loop over all the primes inside the while loop hence you'll check every prime in your list regardless of if $N$ was already completely factored. $\endgroup$ – puzzlepalace May 22 '16 at 8:24
  • 1
    $\begingroup$ Nitpicking too on for p in increasing_primes. It requires to know the list of consecutive primes: this is not possible for big numbers. $\endgroup$ – Biv May 22 '16 at 9:24
15
$\begingroup$

The main reasons we usually choose $p$ an $q$ prime numbers are:

  1. For a given size of $N=pq$, that makes $N$ harder to factor, hence RSA safer. Although efficient factoring algorithms do not find factors by trial division, it remains much easier to find very small prime factors than large ones. If we chose $p$ and/or $q$ at random without consideration for their factorization, they will tend to often have factors that it will be possible to pull out from $N$.
  2. If $p$ and $q$ were not prime, we would need to find their factorization to compute the RSA private function; or/and compute the RSA private exponent $d$ from the public exponent $e$ (or vice versa), since we need to know the factorization of $N$ to compute $\varphi(N)$ or $\lambda(N)$; and that would be quite hard (typically easier than factoring $N$, but still too hard for many practical purposes). It is much easier to generate a prime than it typically is to factorize an integer of equivalent size.

There are variants of RSA (Multiprime RSA) where $N$ is the product of more than two primes; that can be viewed as $p$ or/and $q$ not prime. This has some interest, despite fact 1.

$\endgroup$
11
$\begingroup$

RSA moduli are generally of the form $N = pq$ for two primes $p$ and $q$. It is also important that $p$ and $q$ have (roughly) the same size. The main reason is that the security of RSA is related to the factoring problem. The most difficult numbers to factor are numbers that are the product of two primes of similar size.


Note. There are basically two classes of methods for attacking the factoring problem:

  1. Methods like the number field sieve (NFS) whose complexity depends on the size of $N$. To protect against these methods an RSA modulus $N$ should have at least, say, 2048 bits.
  2. Methods like the elliptic curve method (ECM) whose complexity depends on the smallest prime factor of $N$. To protect against these methods an RSA modulus $N$ should have all its prime factors of size at least, say, 256 bits.
$\endgroup$
  • 2
    $\begingroup$ This is pretty much spot on. You could use non-primes, but then the difficulty to crack would be based upon the difficulty of factoring $p=p_1p_2$ and/or $q=q_1q_2$ which is by definition an easier problem than factoring $N=pq$. $\endgroup$ – Stephen Touset May 19 '16 at 22:16
  • $\begingroup$ But as far as I know many modern fast prime-generation algorithms will not guarantee that the output is a prime number, but only produce primes with a very high confidence ( 99.999% ) so there is a small chance of the generated p and q actually not being primes But I don't think this leads to a practical attack, since you don't know if your N has more than 2 factors (most of the time it will only have 2) $\endgroup$ – Falco May 20 '16 at 11:15
  • 1
    $\begingroup$ @StephenTouset: You can't use any odd non-primes, though -- it is important that $N$ is square-free, or the encryption and decryption primitives wouldn't be each other's inverses. $\endgroup$ – Henning Makholm May 20 '16 at 13:23
  • $\begingroup$ @Falco: The evidence of probabilistic primality tests stacks up exponentially, so "99.999%" vastly understates the confidence we get. It is simple and common to do enough rounds of the test that the risk of accepting a composite number due to the probabilistic nature of the test is only, say, $2^{-100}$ -- which is much smaller than EITHER OF the risk of the computer being destroyed by a random meteorite impact while executing the test OR the risk that a bit of your new prime will be corrupted by undetected DRAM faults ("cosmic rays") before you get around to using it for anything. $\endgroup$ – Henning Makholm May 22 '16 at 12:07
7
$\begingroup$

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, all RSA cares about is that it has some $N$ and $\varphi(N)$. The only reason we talk about $p$ and $q$ is because choosing $N=pq$ because it is the best way to satisfy the previous paragraph.

$\endgroup$
  • 1
    $\begingroup$ And possibly CRT? $\endgroup$ – Maarten Bodewes May 20 '16 at 0:24
0
$\begingroup$

I had the same question and so I landed here. RSA has two key properties

  1. The mapping $m \to m^e (mod\ N)$ is a bijection
  2. The inverse mapping $(m^e)^d \equiv m\ (mod\ N) $ is easy to compute (given $p$ and $q$ of course)

From what I read, the proof of working (of these two properties of RSA) assumes that $p$ and $q$ primes. So I worked on a few examples that violate this property and I found that it has, in my opinion, a more serious problem.

While all the answers focus on the practical aspect that it is harder for the encrypting party to compute the $totient$ of a large composite number that it chose, I think, allowing $p$ and $q$ to be composite has a fundamental problem that the encryption will lose its bijective property (decryption becomes ambiguous).

For example, if we let $p = 8$ and $q = 9$, then $N = 72$. $\phi(72) = 24$. A possible $e$ is $5$. With this public key $(N, e) = (72, 5)$, there is no bijection. Consider a message $m = 4$, upon encryption, it becomes $16$ while a message $m = 22$ also becomes $16$. ($m = 58,\ 40$ also become $16$ upon encryption).

I don't have a proof of this and I'm also to new to this theory. I would appreciate any suggestions and improvements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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