Honestly I'm really confused about padding in RSA scheme. I don't study computer science, and I'm a beginner learning cryptography (self-taught). Can anyone give me suggestions?

  • $\begingroup$ Padding schemes in RSA remove otherwise exploitable mathematical structure in ciphertext and signature. That should not be too confusing. $\endgroup$
    – DannyNiu
    Mar 19 '19 at 9:26
  • $\begingroup$ @DannyNiu a source to learn more detail ? $\endgroup$
    – Onta Ss
    Mar 19 '19 at 9:29
  • $\begingroup$ Have you tried to read David Pointcheval's How to Encrypt Properly with RSA ? $\endgroup$
    – fgrieu
    Mar 19 '19 at 9:31
  • $\begingroup$ @fgrieu nope.but i have read about RSA primitive $\endgroup$
    – Onta Ss
    Mar 19 '19 at 9:37
  • 3
    $\begingroup$ A note about stackexchange in general: "Can anyone give me suggestions?" is not a good question format (unless you're on the site for software recommendations). We require questions to be narrow in scope so that they can be objectively answered, rather than discussed. A better format for your question would be to ask things like "Why is the RSA-OAEP padding scheme used", "Why/how does the RSA-OEAP padding scheme work", etc. You can use the "edit" link below the question to make changes. On another note: If someone links to a resource, consider reading it. $\endgroup$
    – Ella Rose
    Mar 20 '19 at 14:35

Direct use of textbook RSA for encryption is very insecure. For example, a guess of the plaintext can be checked: if what's encrypted is a name on the class roll, enciphering all names on the class roll until getting the ciphertext breaks confidentiality. There are several other attacks.

That motivates RSA-OAEP. It turns textbook RSA, a hash, and a source of random bits, into a demonstrably secure encryption scheme. Encryption of message $M$ first transforms $M$ into padded message $X$ by mixing it with random bits and applying reversible transformations with the hash; then enciphers $X$ into $X^e\bmod N$, that is per textbook RSA encryption. Decryption starts by textbook RSA decryption, yielding $X$; then the padding is undone, yielding $M$ or an error indication.

I essence, the distribution of $X$ is random enough that textbook RSA becomes secure. A proof of that can be made for the strongest definition of security of a cipher, IND-CCA2, and under some hypothesis:

  • the RSA problem of finding a random $X$ given $X^e\bmod N$ is hard;
  • the hash is undistinguishable from a public function selected at random;
  • the source of random bits is indistinguishable from one producing uniformly random and independent bits;
  • a decryption device given a cryptogram only outputs the correct plaintext or an error indication (it does not leak any other information).

A (highly technical) reference proof is in Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern's RSA-OAEP Is Secure under the RSA Assumption, in Journal of Cryptology, 2004. A more gentle text is David Pointcheval's How to Encrypt Properly with RSA?, originally in Cryptobytes 5n1, 2002.

The practical form of RSA-OAEP is named RSAES-OAEP and defined in PKCS#1 v2.2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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