Textbook RSA:
Choose two large primes $p$ and $q$.
Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\phi(n))=1$ (where $\phi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\mod\phi(n)$.
$(e, n)$ is the public key, $(d, n)$ the private one.
- To encrypt a message $m$, compute $c\equiv m^e\mod n$.
- To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.
Signing and verifying messages is also defined (omitted for brevity).
Some (Undesirable) Properties of Textbook RSA:
- It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
- It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).
Differences with Deployed RSA:
- Padding
- Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
- $e$ is often statically set to $65567 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
- Side-channel attack mitigations can be put in place for deployed systems too.
In no way is my list comprehensive, but hopefully this helps.
