Definition of Textbook RSA

Question

What is the definition of Textbook RSA?

What are some of the properties of textbook RSA?

How does it differ from other RSAs?

Answer 1

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:

1. 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.
2. 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:

1. Padding
2. Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
3. $e$ is often statically set to $65567 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
4. Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.

Answer 2

RSA is both an encryption and signature function. I have heard the term "textbook RSA" used mostly with the encryption function, but the same basic principle applies to RSA signatures as well. It is essentially RSA without any padding.

There is no canonical definition of textbook RSA (e.g., does it include restrictions on choosing safe primes or not?) and so it may differ by context, but it is what is called "plain RSA" on the Wikipedia article. Since Wikipedia evolves, also see these slides from Dan Boneh.

Textbook RSA has no semantic security, therefore it is not secure against chosen plaintext attacks or ciphertext attacks. This is because, respectively, it is deterministic (encrypting the same message twice produces the same ciphertext) and multiplicatively homomorphic (an encrypted values can be multiplicatively modified under encryption).

The main alternative to textbook RSA encryption is RSA with OAEP. This variant is semantically, CPA-, and CCA-secure. RSA+OAEP is randomized and has no homomorphisms. OAEP itself is a second generation padding scheme, the first generation only providing semantic/CPA-security for RSA.

RSA signatures can also be padded. RSA with PSS makes the signatures randomized.