Question about why RSA is hard to attack

Question

I think I understand why RSA is hard to attack but I'd like to get clarification if I actually do.

Assume there are two people, Alice and Bob, who are attempting to communicate privately but that we can listen to all of their messages to each other. Assume we know they're attempting to communicate using RSA and that Alice has sent $n$ and $e$ to Bob and Bob has sent $c$ to Alice. Because we know they're using RSA, we also know that $n$ is the product of some primes $p$ and $q$, that $e\in\mathbb{N}$ with $1<e<\phi\left(n\right)$ (notice that $\phi\left(n\right)$ is hard to calculate because we do not know $p$ and $q$, but this has no significance in terms of the bounds of $e$ since we know $e$ explicitely), and that $e$ is relatively prime (aka coprime) to n (i.e. $\text{gcd}\left(e,n\right)=1$).

We know that Bob's message to Alice can be expressed in terms of $n$, $e$, $c$, and Bob's intended message, $m$ given by $c\equiv m^{e}\bmod{n}$. For the sake of thoroughness, we also know $m<n$.

I hope this is right so far.

Tactic 1

As an attacker, we want to find $m$, and since we have an equation including it, one way to go about finding it is to re-express said equation.

$c\equiv m^{e}\bmod{n}$

implies

$\exists k\in\mathbb{N}:m^{e}=c+kn$

implies

$\exists k\in\mathbb{N}:m=\left(c+kn\right)^{\frac{1}{e}}$

Now comes my question! As the attacker, in order to find $m$, we'd have to try all $k$'s in the natural numbers until we found an $m$ that looked like a message--and even then, even if it's intelligible, it's possible what we've found is still actually not Bob's intended message. Is this a correct assertion? Is this a possible yet obviously futile attack? (Further questions: Is it possible for the attacker to verify if the $m$ computed via the above method is equivalent to Bob's $m$ using the assumptions above? If yes, if someone were to execute this attack, how long on average would it take to find the correct $m$ given $m$ is random?)

Tactic 2

Another tactic we might take would be to compute Alice's secret key, $d$, such that $ed\equiv1\bmod{\phi\left(n\right)}$ (i.e. $d$ is the multiplicative inverse of $e\bmod{\phi\left(n\right)}$). We can, again, re-express this.

$ed\equiv1\bmod{\phi\left(n\right)}$

implies

$\exists j\in\mathbb{N}:1=ed+j\phi\left(n\right)$

implies

$\exists j\in\mathbb{N}:d=\frac{1-j\phi\left(n\right)}{e}$

Now the second question! As the attacker, calculating $\phi\left(n\right)$ is hard. This is because there are two ways we could calculate this: 1) by the definition, i.e. the cardinality of the set of relatively prime numbers to $n$ (which would take at most $\sqrt{n}$ steps, right?) or 2) since we know $n$ is the product of 2 relatively prime numbers, attempt to find $p$ and $q$ and then $\phi\left(n\right)=\left(p-1\right)\left(q-1\right)$. This is hard to do for large $n$. Is this correct assertion?

Actually, wait, I've caught myself. Because even after calculating $\phi\left(n\right)$, we'd still have to find $j$, no?

Could someone answer these questions and possibly answer succinctly way attacking RSA is hard? I feel like I'm so close and just need a little help-nudge.

Answer 1

There are a number of small mistakes in the question. Let's clean up that first.

$\gcd(e,n)=1$ is likely, but neither necessary nor sufficient for RSA to work; the right condition is $\gcd(e,p-1)=\gcd(e,q-1)=1$. Notice this implies $e$ odd for any non-trivial choice of $p$ and $q$.

Even in textbook RSA, the right equation is not $c\equiv m^e \bmod n$, but $c=m^e\bmod n$. The first can be understood as $c\equiv m^e \pmod n$, and only the second implies that $0\le c<n$. The distinction is important: $c'=m^e$ satisfies the first, but (for most $m$) not the second, and would make RSA both unsafe and (except for small $e$ like $e=3$) extremely impractical as an encryption method.

Although that is not directly relevant to the questions, RSA as practiced is PKCS#1. A number of things change. The most important is that $m$ is not the message, but rather a randomized and reversible function of the message. Also, it is used $p≠q$, $1<e<n$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ where the question and the original RSA article uses $\phi(n)=(p-1)⋅(q-1)$, for determining the private exponent $d$ such that $e\cdot d\equiv1\pmod{\lambda(n)}$ and $1<d<n$.

---

Coming to the question about tactic 1:

An attacker Eve has the choice of means; she do not have to try a particular strategy, as in "in order to find $m$, we'd have to try all $k$'s in the natural numbers.."; she could try that strategy.

If she elected to follow the proposed strategy, try some $k$'s in the natural numbers and compute $m=(c+k\cdot n)^{1/e}$, she'd have a much better option than trying to guess if the resulting $m$ looks like a message; she can conclusively rule out a guess of $k$ when the resulting $m$ is not an integer, which occurs for the overwhelming majority of $k$. And also, she can decide if an integer $m$ in range $[0\dots n-1]$ is the right message by computing $m^e\bmod n$ and comparing that to $c$; they are equal if and only if she guessed the right $k$, and/or otherwise recovered $m$.

Tactic 1 is of course futile because they are too many $k$ to test.

---

Concerning tactic 2: the assertion is correct, for some loose use of "This is because"; exposing two methods to find $\phi(n)$ does not implies that they are the best ones, much less the only ones.

Notice that if an attacker Eve knew $\phi(n)=(p-1)\cdot(q-1)$, she's done: she can then compute an $f$ such that $f\cdot e\equiv 1\pmod{\phi(n)}$ and that let her decipher using that $m=c^f\bmod n$. Although her $f$ might not be the $d$ used by the legitimate key holder, which is any $d$ such that $d\equiv f\pmod{\lambda(n)}$, she does not care.

---

Attacking RSA encryption is believed hard when $n$ and $e$ have been properly chosen, and the message $m$ is a random integer in the set $[0\dots n-1]$, and all else that's known about $m$ is $c=m^e\bmod n$, because the best methods we have to solve that problem are of cost as high as factoring $n$, and the best general method known for that is GNFS, and the expected cost for that is prohibitive by definition of "$n$ has been properly chosen". This is circular, loose, and not a mathematical proof that RSA or factoring is hard. Neither is known with certainty. Notably, the definition of "$n$ has been properly chosen" has changed drastically since that original RSA article. That "RSA hard" implies "factoring hard" is obvious, but the converse is an open problem.