Despite having read What makes RSA secure by using prime numbers?, I seek 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.
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 lose 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 $\phi(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 $\phi(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.