# How does the math part of RSA work? [duplicate]

I understand the theoretical part of RSA (the concept of public and private keys), but I don't understand the mathematical part. Can anyone please explain it to me in simple terms? Thanks.

## marked as duplicate by otus, yyyyyyy, e-sushiMar 10 '16 at 19:37

• What do you not understand about it? What remains unclear after e.g. this answer and the Wikipedia page? – otus Mar 10 '16 at 15:43
• Can you please link to the things you've already read, and walk us through what you already know, and where your stumbling blocks are? Right now, your question is asking for a full explanation of RSA, of which there are many on the internet. – Mike Ounsworth Mar 10 '16 at 15:45

Assuming you've understood the "theoretical part", I try to explain the mathematical one.

Plaintext and ciphertext are integers between 0 and n-1 for some n.
Encryption and decryption are of the following form, for some plaintext M and ciphertext C:

C = $M^e$ (mod n)
M = $C^d$ (mod n) = ($M^e)^d$ (mod n) = $M^{ed}$ (mod n)

Each communicating entity has one public/private key pair PU={e,n} e PR={d,n}, where e and d are each the multiplicative inverse (mod $\Phi$(n)) of the other.

e and d are inverses (mod $\Phi$(n)), or ed $\equiv$ 1 (mod $\Phi$(n)), or equivalently ed = 1 + k$\Phi$(n).

Therefore, to decrypt a ciphertext C = $M^{ed}$ (mod n), we only need to calculate $C^d$ (mod n) because $C^d$ (mod n) = $M^{ed}$ (mod n) = $M^{1 + k\Phi(n)}$ (mod n) = $M^1$ x ($M^{\Phi(n)})^k$ (mod $\Phi$(n)) = $M^1$ x $1^k$ (mod n) = M.

Note that the function $\Phi$(n) is the Euler's totient function and that $M^{\Phi(n)}$ (mod n) = 1 is true for the Euler's theorem.

I know my English isn't the best but, I hope I was helpful.