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?

up vote 53 down vote accepted

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.

  • 1
    Some textbooks, and actual implementations, use $e\cdot d\equiv 1\pmod{ LCM(p-1,q-1)}$, which covers all working $d$, rather than some working $d$. – fgrieu Dec 13 '11 at 18:03
  • 3
    Also it leaks the jacobi symbole of the message. You can know if your medsage is a quadratic residue – David 天宇 Wong Dec 9 '14 at 1:27
  • For completeness, you might also want to note that textbook RSA is insecure for short messages. In particular, there's an obvious attack whenever $m^e < n$ (just take the non-modular $e$-th root), but there are other attacks that apply even when $e$ is large but $m$ is small. – Ilmari Karonen Sep 24 '16 at 16:35
  • @David天宇Wong Can you explain (or give a reference) the Jacobi symbol leakage? – tamhzeo Nov 22 at 13:03
  • I've tried to get a list of attacks that are possible on textbook RSA here. That kind-of failed as there were a lot more than expected. As indicated correctly in this answer "In no way is my list comprehensive"... And neither should it be, it is a separate topic - if not more - on its own. – Maarten Bodewes Nov 22 at 15:23

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.

  • The acronyms were thrown at my face too violently, but great answer overall. – doubleOrt Apr 14 at 16:40

A) RSA

RSA is assymetric encryption method. RSA is one of the Public Key Cryptography methods. This method make 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 public key the message is encrypted.

3) Decryption - by using private key 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(mod N)

• private key: d Decrypt: C^d = M (mod 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

enter image description here

  • Session-key K is 64 bits. View K {0,…,264}

               Eavesdropper sees: C = K^e(mod N) .
    
  • Suppose K = K1×K2 where K1, K2 < 234 . (prob. 20%)

    Then: C/K1^e = K2^e(mod N)

  • Build table: C/1^e, C/2^e, C/3^e, …, C/2^(34e) . time: 2^34 For K2 = 0,…, 2^34 test if K2^e is in table. time: 2^34 34
  • Attack time: 2^40 << 2^64

6) Never use textbook RSA because of less security.

  • 1
    Hi Anu, and thanks for your answer. Currently it is pretty hard to read. Maybe you could take a look at our supported MathJax formatting. Instead of A / B you could use sections. For numbered lists, please use the MarkDown list feature. I'm certainly not sure what "(M Î ZN)" is, but it certainly should not be using the code formatting feature. – Maarten Bodewes Nov 22 at 15:28
  • Hi Maarten, thanks for your support, I will use the applications you mentioned. – Anu Davis Nov 23 at 4:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.