How does RSA padding work exactly?

Question

I've read everywhere online and people say plain text RSA is very unsafe. To make it safe you pad it but no examples are shown anywhere on how to do it. It's explained that random data is added to the encryption process to change up the final encryption so it can't be guessed at random by comparison to similar looking encryptions.

So far what I understand is you have a plain text, you turn that into a hash and pad it with extra bytes then you encrypt it and send it over and then it is decrypted into a hash with bytes and turned to plain text. Where does the padding go? Do you add random 'trash' bytes to the plain text to fill it up and then hash it and encrypt? Or do you do some extra math in the encryption process? What is this process? What about figuring out what is a padding byte and what isn't?

Apart from that how do you turn it back to text from a hash? What if I turn it into SHA-512 hash with a salt? How will the person be able to decrypt the data once they decrypt the RSA to find the hash? Is my understanding wrong of the process? Does turning the plain text into hex help with anything?

Answer 1

While OAEP uses a one-way function on the plaintext, it's not quite a hash: it's called a mask generation function (MGF), and unlike a hash it can produce as much or as little output as you want (the output length is an argument to the function, and input length is decoupled from output length). This output should be pseudorandom.

You use this in a construction called a Feistel network. To pad a message to length $k$ (so you're ultimately passing $k$ bits through textbook RSA), you create two blocks. One of them (the seed $S$) is a short fixed-length random string; the other (the data block $D$) is longer, and includes the message and some more conventional padding (details aren't important) to make it so the two blocks have a combined length of $k$.

Once you have these blocks, it's time to use your MGF. You first run MGF on $S$ to get a mask as long as $D$; you XOR that mask with $D$ to get $D^\prime$. You then run MGF on $D^\prime$ to get a mask as long as $S$, and XOR that with $S$ to get $S^\prime$. Concatenate $D^\prime$ and $S^\prime$ to get the thing you pass through RSA.

On the other end, you decrypt to get $D^\prime$ and $S^\prime$. You first recover $S$ by computing $MGF(D^\prime)$ and XORing with $S^\prime$ (this is exactly what you did to get $S^\prime$; it works just as well in reverse). Once you have $S$, you XOR $D^\prime$ with $MGF(S)$ to get $D$, and once you have $D$ you take off the normal padding to get the message.

Feistel networks are generally a good way to turn a one-way function into a reversible function. In general, you divide the thing you're processing into two blocks, $A_1$ and $B_1$ (these have fixed length). You then compute $A_{i+1}=A_i\oplus f(B_i)$ and $B_{i+1}=B_i\oplus f(A_{i+1})$, and repeat till you have $A_n,B_n$ as your output. To reverse it, you compute $B_{i-1}=B_i\oplus f(A_i)$ and $A_{i-1}=A_i\oplus f(B_{i-1})$, and repeat until you have $A_1,B_1$ again. This construction is used in several block ciphers; there, $f$ also takes a subkey as input, so without the subkey you can't reverse the network. It's especially nice in hardware; a Feistel network means encryption and decryption are almost identical (you basically just reverse the order of the subkeys).

Answer 2

There exist many standards which describe a lot of padding modes and security protocols. If you're new in that field, I strongly recommend you to study the family of PKCS standards which are the reference in the domain. There also exist other distinct standards depending of very specific application fields (Banking, mobile, Cloud, Embedding ... or Global Platforms).

Briefly, as you've certainly observed the RSA primitive is based on modular exponentiation and this operation is homomorphic in the sense that if someone knows two ciphertexts $c_1=m_1^d$ and $c_2=m_2^d$, then he can immediately deduce : $(m_1.m_2)^d= c_1.c_2=c$. This is the essential reason to break this "homomorphism", by adding inside the plaintext some hash or other techniques.

Other security protocols allow an attacker to interact with an oracle to prove the security of the scheme. Then randomization can be included in some cases to prevent the attacker from deducing any bit of information about the plaintext when she is given the ciphertext. The subject is very vast.