# A question about RSA key generation algorithm

I'm fairly new to this stuff so be forgiving. I'm trying to learn how RSA works, My resources for the manner of sake:

This is what I got so far:

since

$$m^{phi(n)} \equiv 1 \bmod n$$

as long as $$m$$ coprimes to $$n$$.

So eventually:

$$m^{k * phi(n)+1} \equiv m \bmod n$$

Now we construct $$e$$ and $$d$$:

$$k*phi(n) +1 = e * d$$

$$e$$ is selected so that it coprimes with $$phi(n)$$

I have 2 questions:

1. Since $$m$$ can be anything (this is the encrypted content right?), how do you verify that $$m$$ and $$n$$ coprimes, as needed for the Euler's theorom to work?

2. Why do $$e$$ needs to comprime to $$phi(n)$$ ?

Thanks!

• 1, RSA can encrypt any messages $m < n$. there are at least two good answers to this. 1 2. How do you find the inverse of $e$? Please search this site before asking? If something is not clear on the answers you can ask. Jan 27 at 17:06
• As you will see the problem here How to compute m value from RSA if phi(n) is not relative prime with the e? and remember the correctness requirement Jan 27 at 18:59
• Even the 'simple' version of wikipedia correctly notes you can, and we generally do, use Carmichael's $lambda(pq)=lcm(p-1,q-1)$ instead of Euler's $phi$, but real wikipedia is more detailed. Jan 28 at 0:47