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?


3 Answers 3


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.

  • 3
    $\begingroup$ Addition: $p$ and $q$ must be distinct, random and secret. Note: Some textbooks, and actual implementations, use $e\cdot d\equiv 1\pmod{\operatorname{lcm}(p-1,q-1)}$, which covers all working $d$, rather than some working $d$. Other require $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, which uniquely specifies $d$ for given $p,q,e$, and makes $d$ the lowest valid working $d$. $\endgroup$
    – fgrieu
    Commented Dec 13, 2011 at 18:03
  • 6
    $\begingroup$ Also it leaks the jacobi symbole of the message. You can know if your medsage is a quadratic residue $\endgroup$ Commented Dec 9, 2014 at 1:27
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 24, 2016 at 16:35
  • 2
    $\begingroup$ @David天宇Wong Can you explain (or give a reference) the Jacobi symbol leakage? $\endgroup$
    – user48832
    Commented Nov 22, 2018 at 13:03
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Commented Nov 22, 2018 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.

  • $\begingroup$ The acronyms were thrown at my face too violently, but great answer overall. $\endgroup$
    – doubleOrt
    Commented Apr 14, 2018 at 16:40


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)
  1. Completely insecure cryptosystem:

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

  2. The RSA trapdoor permutation is not a cryptosystem.

  3. A simple attack on textbook RSA

enter image description here

  • 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}$

  1. Never use textbook RSA because of less security.
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Commented Nov 22, 2018 at 15:28
  • $\begingroup$ Hi Maarten, thanks for your support, I will use the applications you mentioned. $\endgroup$
    – Anu Davis
    Commented Nov 23, 2018 at 4:54
  • 3
    $\begingroup$ This answer is taken from Dan Boneh and a credit is due. $\endgroup$
    – Emolga
    Commented Dec 9, 2020 at 2:06
  • $\begingroup$ I would add to Operations: signature and signature verification $\endgroup$ Commented Aug 5, 2022 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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