1
$\begingroup$

enter image description here So I've been studying RSA for a class and I'm having a hard time understanding how it works. Why do we choose the value of e such that e is relatively prime to the totient (as opposed to just being relatively prime to n?) How does e being relatively prime ensure that there is only one possible value for d? And are the calculations based on the totient of n just an arbitrary way of encrypting or is there significance to them?

Also, if both e and n are public then how is that secure at all (or is this article wrong about e being public?) I guess I'm confused because if everyone is receiving the same public key then isn't the inverse operation going to be the same for everyone and thus not secure? And since we know that ed mod totient(n) = 1, and we know both n and e can't d easily be calculated?

Thank you for your help and patience :)

$\endgroup$
1
  • $\begingroup$ A comment on a particular question from the list: How does e being relatively prime ensure that there is only one possible value for d? - That's a false assumption, see this question that was answered just yesterday... $\endgroup$
    – tum_
    Apr 1 '20 at 14:28
5
$\begingroup$

Why do we choose the value of e such that e is relatively prime to the totient (as opposed to just being relatively prime to n?)

The final goal of RSA encryption is to have $m = c^d \bmod n$, which is the same as $m = (m^e)^d \bmod n \rightarrow m = m^{ed} \bmod n$, i.e., if you encrypt and then decrypt, you get the same original message. For that last equality to be true, raising to $ed$ needs to be the same as raising to $1$.

When you work with powers modulo some number, you eventually "go back to the start". For example, if you compute $m^1 \bmod n$, $m^2 \bmod n$, $m^3 \bmod n$, the result will eventually go back to $1$ (unless $m\bmod n=0$). The exponent where this happens is called the order of $m$. If $n$ is the product of two distinct primes, then this happens at $\phi(n) = (p-1)(q-1)$ (it happens sooner: at $\lambda(n) = \operatorname{lcm}(p-1, q-1)$, the Carmichael's Function; or sooner depending on $m$; but it doesn't matter for this explanation).

Therefore, we know that $m^{\phi(n)} = 1 \bmod n$ and therefore $m^{\phi(n)+1} = m \bmod n$. And if you add any multiple of $\phi(n)$ to the exponent the result stays the same. In short, in the exponent, you're working modulo $\phi(n)$. And since you need $ed$ to be the same as $1$ in the exponent, then $d$ must be chosen such that $ed \equiv 1 \pmod{\phi(n)}$

Also, if both e and n are public then how is that secure at all? I guess I'm confused because if everyone is receiving the same public key then isn't the inverse operation going to be the same for everyone and thus not secure?

Each person has a different public key and matching private key. Thus the inverse operation is not going to be the same for everyone, it's the same for each person (each public key holder). The values $e$ and $n$ are indeed public, because the secret value (the private key) is $d$. Each person has their own $e, n, d$ values (tough $e$ is usually the same for everyone, but the others should always be different).

$\endgroup$
1
  • $\begingroup$ This completely answered my questions, thank you so much for taking the time to explain :) $\endgroup$ Apr 1 '20 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.