Definition of textbook RSA

Question

What is the definition of textbook or "raw" RSA?

What are some of the properties of textbook RSA?

How does it differ from other schemes based on RSA?

Answer 1

Textbook RSA:

Choose two large primes $p$ and $q$. Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\varphi(n))=1$ (where $\varphi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\bmod{\varphi(n)}$. In other words, $d$ is the modular inverse of $e$, ($d\equiv e^{-1}\bmod{\varphi(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 $65537 = 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.

Answer 3

A) RSA

RSA is an asymmetric encryption method. RSA is one of the Public Key Cryptography methods. This method makes use of two keys: a public key, known to all, for encryption and a private key, kept secret, for decryption.

Operations in RSA: The RSA algorithm involves three steps:

1. key generation - Key pairs are generated: a private key and a public key.

2. Encryption - by using the public key the message is encrypted.

3. Decryption - by using the private keys the message is decrypted.

B) Textbook RSA

Some points regarding textbook RSA is given below:

1. Textbook RSA is insecure

2. Textbook RSA encryption:

• public key: $(N,e)$ Encrypt: $C = M^e \pmod N$

• private key: $d$ Decrypt: $C^d = M \pmod N$

                           (M Î ZN)

3. Completely insecure cryptosystem:

   • Does not satisfy basic definitions of security. • Many attacks exist.

4. The RSA trapdoor permutation is not a cryptosystem.

5. A simple attack on textbook RSA

• Session-key $K$ is $64$ bits. View $K\in\{0,\ldots,2^{64}-1\}$

  Eavesdropper sees: $C = K^e \pmod N$ .

• Suppose $K = K1\cdot K2$ where $K1, K2 < 234$ . (prob. 20%)

  Then: $C/K1^e = K2^e \pmod N$

• Build table: $C/1^e, C/2^e, C/3^e, \ldots, C/2^{34e} . time: $2^34$

  For K2 = 0,…, 2^34 test if $K2^e$ is in the table. time: $2^{34} 34$

• Attack time: $2^{40} \ll 2^{64}$

6. Never use textbook RSA because of less security.