Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What is the definition of Textbook RSA?

What are some of the properties of textbook RSA?

How does it differ from other RSAs?

share|improve this question

2 Answers 2

up vote 14 down vote accepted

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 $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.

share|improve this answer
    
Thank you Mike. –  Bobby S Dec 12 '11 at 20:19
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
    
Also it leaks the jacobi symbole of the message. You can know if your medsage is a quadratic residue –  David 天宇 Wong Dec 9 at 1:27

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.

share|improve this answer
    
Thank you PulpSpy. –  Bobby S Dec 12 '11 at 20:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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