2
$\begingroup$

Using RSA public key (n,e) the encryption of a message is

c= (m^e) mod n

and the corresponding message is decrypted as

m = (c^d) mod n

How does the RSAES-OAEP algorithm specified in PKSC#1 v2.1 differ from the above basic method?

Is it possible to decrypt a text encrypted using RSA PCKS1 v2.1 RSAES-OAEP algorithm with Raw rsa decryption method (ie, m = (c^d) mod n ) ?

$\endgroup$
  • $\begingroup$ FWIW: PCKS#1 v2.1 has been obsoleted by PCKS#1 v2.2. $\endgroup$ – fgrieu Feb 4 at 17:11
  • $\begingroup$ ... although ES-OAEP changes only trivially (in the list of hashes allowed) between 2.1 and 2.2, and doesn't change substantively between 2.0 and 2.1 although they did change some notation and rearrange parts of the document which makes the equivalence less obvious. $\endgroup$ – dave_thompson_085 Feb 5 at 3:08
9
$\begingroup$

Directly applying the RSA-function to a message is not secure in real life. The function leaks all kinds of information about the underlying plaintext and is particularly vulnerable to active attacks (where the attacker might be able to learn something about some related message also encrypted under RSA, and use this to learn what the original message was). Unfortunately, some textbooks only present RSA as you have done above and leaves it at that, hence the term textbook-RSA is often used for this raw application of the RSA-function to the message.

However, the good news is that if your message was somehow chosen completely at random within $\mathbb{Z}_n$ (the full plaintext space), then applying the RSA-function would actually be secure. Unfortunately, in real life, our messages are seldom completely random, but rather chosen from a very tiny subset within $\mathbb{Z}_n$. The solution is to randomize the message using padding so that our messages takes up a much larger possible subset within the plaintext space. Additionally we make it so that equal messages encrypt to different ciphertexts each time which is important. In real life we use RSA like this:

Encrypt: $m \mapsto$ randomize message using some padding scheme $\mapsto x$ $\mapsto c = x^e \pmod n$

Decrypt: $x = c^d \pmod n \mapsto$ check whether $x$ has the approptiate padding $\mapsto$ if yes: strip of the padding from $x$ and return $m$; if no: return Fail.

The question then becomes: how should we pad the message $m$? OAEP is one such padding scheme (there are actually many ways how this can be done, but not all of them are secure. RSA-OAEP fortunately is). So how does OAEP-work? You should check out the description on Wikipedia, but this picture goes a long way of explaining it:

$\hskip 2 in$

After the message you pad with some zero's then append a completely random string $r$. Then feed these through a couple of hash functions $G$ and $H$ and some XOR-applications and output the padded message $x \| y$. Then you encrypt this padded output. When you decrypt you basically reverse the whole process and verify that you have the right number of zeroes at the end (before the $r$).

$\endgroup$
  • $\begingroup$ Note wikipedia describes and shows the original publication by Bellare&Rogaway. The scheme specified in PKCS1 v2.0+ is slightly different: the order of inputs is reversed, the rigid padding is slighly different, and it adds a binding (via hash) to contextual data (called parameters P in 2.0 and label L in 2.1+). This doesn't change the concept or (AFAICS) the security analysis, but it does matter to implementation. $\endgroup$ – dave_thompson_085 Feb 5 at 3:08
2
$\begingroup$

It is actually the same method, the OAEP part simply defines how the plaintext is padded prior to encryption.

$\endgroup$

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.