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.
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.