This is a clarifying thread after finding: What makes RSA secure by using prime numbers?.
Despite the fact that this question was answered already, I am still struggling to really grasp the underlying concepts that make RSA work well.
Specifically, I understand that the fundamental key concept is that: 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 understanding is correct, then the original question posed by the OP in this thread continues to befuddle me. Why can we not choose non-prime p and q?
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 us 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 am understanding 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 super obvious, but I am a newbie in higher math and programming. I really want to understand as deeply as I can.