My question is: what problem is the RSA decryption equivalent with?
- factorization
- Euler-phi function calculation
- Rabin decryption
- RSA key calculation
My question is: what problem is the RSA decryption equivalent with?
For create a RSA cipher environment, you need to choose to big prime numbers p ans q.
By multiplying p and q you get n. Then you need to use phi function to choice encrypt key e (which has no common divisor with phi(n)).
e and n will be public.
To compute d (the private decryption key) from e, you need to know the modular multiplicative inverse of e modulus phi(n). This is easy to compute with the Extended Euclidean algorithm (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)
BUT...
you don't know phi(n). And to compute phi(n) you NEED to know its primes factor (p and q)
So RSA decryption problem should be equivalent to big number factorization...but no one never prove it.
If you are interested about why: https://en.wikipedia.org/wiki/RSA_problem.
In fact, compute d from e is (as far as we currently know but we cannot exclude that a quickest way exists) as hard as factorization problem. BUT, find d is not strictly mandatory to reverse the original clear message M from C (C = M^e mod n). This is just the current quickest way that we know.
The most direct attack should be to retrieve M only from e and n. We cannot do that for now, but there is no proof that it is unfeasible.
Also, many "side channel" attacks can break RSA: bad choice for p and q (when p is near from q for example), bad padding, etc. All theses way can simplify RSA decryption in comparison to factorization.
And about your initial question:
phi function calculation is a very low complexity (quite instantaneous).
RSA key calculation (if you mean find d from e and phi(n)) is easy too. You have to use the extended euclidean algorithm which is simple.
Rabin decryption is harder or equal to RSA decryption problem whether or not someone, one day, prove that RSA is actually as hard as factorization problem.