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

This question already has an answer here:

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 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

## 1 Answer

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.