Optimal asymmetric encryption padding: Difference between revisions

Content deleted Content added
The algorithm was poorly described, missing a few bytes (like the 0x01 byte between PS and M), and the associated diagram was not conforming to RFC 8017.
Tags: nowiki added Visual edit
Line 19:
 
==Algorithm==
[[ImageFile:Oaep-diagram-20080305OAEP padding schema.png|thumb|upright=1.2|right410x410px|OAEP isencoding schema according ato [[FeistelRFC network]]8017]]
In the diagram,
 
* ''MGF'' is the [[Mask generation function|mask generating function]], usually MGF1,
In the diagram,
* ''nHash'' is the numberchosen of[[Cryptographic bitshash infunction|hash the RSA modulus.function]],
* ''hLen'' is the length of the output of the hash function in bytes,
* ''k''<sub>0</sub> and ''k''<sub>1</sub> are integers fixed by the protocol.
* ''m'' is the plaintext message, an (''n''&nbsp;−&nbsp;''k''<sub>0</sub>&nbsp;−&nbsp;''k''<sub>1</sub> )-bit string
* ''G'' and ''H'' are [[mask generation function]]s based on chosen [[cryptographic hash function]]s
* ⊕ is an xor operation.
 
* ''k'' is to the length of the [[RSA (cryptosystem)|RSA]] modulus ''n'' in bytes,
To encode,
* ''M'' is the message to be padded (at most <math>k - 2 \cdot \mathrm{hLen} - 2</math> bytes),
# messages are padded with ''k''<sub>1</sub> zeros to be ''n''&nbsp;−&nbsp;''k''<sub>0</sub> bits in length.
* ''L'' is an optional label to be associated with the message (the label is the empty string by default and can be used to authenticate data without requiring encryption),
# ''r'' is a randomly generated ''k''<sub>0</sub>-bit string
* ''PS'' is a byte string of <math>k - \mathrm{mLen} - 2 \cdot \mathrm{hLen} - 2</math> null-bytes.
# ''G'' expands the ''k''<sub>0</sub> bits of ''r'' to ''n''&nbsp;−&nbsp;''k''<sub>0</sub> bits.
* ⊕ is an [[Exclusive or|XOR]]-Operation.
# ''X'' = ''m''00...0 ⊕ ''G''(''r'')
# ''H'' reduces the ''n''&nbsp;−&nbsp;''k''<sub>0</sub> bits of ''X'' to ''k''<sub>0</sub> bits.
# ''Y'' = ''r'' ⊕ ''H''(''X'')
# The output is ''X'' || ''Y'' where ''X'' is shown in the diagram as the leftmost block and ''Y'' as the rightmost block.
 
=== Encoding ===
Usage in RSA:
<nowiki>RFC 8017</nowiki><ref>{{cite IETF|title=PKCS #1: RSA Cryptography Specifications Version 2.2|rfc=8017|sectionname=Encryption Operation|section=7.1.1|page=22|last=|first=|author-link=|date=November 2016|publisher=[[Internet Engineering Task Force|IETF]]|access-date=2022-06-04|doi=10.17487/RFC8017}}</ref> for PKCS#1 v2.2 specifies the OAEP scheme as follows for encoding:
The encoded message can then be encrypted with RSA. The deterministic property of RSA is now avoided by using the OAEP encoding.
 
# Hash the label ''L'' using the chosen hash function: <math>\mathrm{lHash} = \mathrm{Hash}(L)</math>
To decode,
# Generate a padding string ''PS'' consisting of <math>k - \mathrm{mLen} - 2 \cdot \mathrm{hLen} - 2</math> bytes with the value 0x00.
# recover the random string as ''r'' = ''Y'' ⊕ ''H''(''X'')
# Concatenate ''lHash'', ''PS'', the single byte 0x01, and the message ''M'' to form a data block ''DB'': <math>\mathrm{DB} = \mathrm{lHash} || \mathrm{PS} || \mathrm{0x01} || \mathrm{M}</math>. This data block has length <math>k - \mathrm{hLen} - 1</math> bytes.
# recover the message as ''m''00...0 = ''X'' ⊕ ''G''(''r'')
# Generate a random seed of length ''hLen''.
# Use the mask generating function to generate a mask of the appropriate length for the data block: <math>\mathrm{dbMask} = \mathrm{MGF}(\mathrm{seed}, k - \mathrm{hLen} - 1)</math>
# Mask the data block with the generated mask: <math>\mathrm{maskedDB} = \mathrm{DB} \oplus \mathrm{dbMask}</math>
# Use the mask generating function to generate a mask of length ''hLen'' for the seed: <math>\mathrm{seedMask} = \mathrm{MGF}(\mathrm{maskedDB}, \mathrm{hLen})</math>
# Mask the seed with the generated mask: <math>\mathrm{maskedSeed} = \mathrm{seed} \oplus \mathrm{seedMask}</math>
# The encoded (padded) message is the byte 0x00 concatenated with the ''maskedSeed'' and ''maskedDB'': <math>\mathrm{EM} = \mathrm{0x00} || \mathrm{maskedSeed} || \mathrm{maskedDB}</math>
 
=== Decoding ===
Decoding works by reversing the steps taken in the encoding algorithm:
 
# Hash the label ''L'' using the chosen hash function: <math>\mathrm{lHash} = \mathrm{Hash}(L)</math>
# To reverse step 9, split the encoded message ''EM'' into the byte 0x00, the ''maskedSeed'' and the ''maskedDB'': <math>\mathrm{EM} = \mathrm{0x00} || \mathrm{maskedSeed} || \mathrm{maskedDB}</math>
# Generate the ''seedMask'' which was used to mask the ''seed'': <math>\mathrm{seedMask} = \mathrm{MGF}(\mathrm{maskedDB}, \mathrm{hLen})</math>
# To reverse step 8, recover the ''seed'' with the ''seedMask'': <math>\mathrm{seed} = \mathrm{maskedSeed} \oplus \mathrm{seedMask}</math>
# Generate the ''dbMask'' which was used to mask the data block: <math>\mathrm{dbMask} = \mathrm{MGF}(\mathrm{seed}, k - \mathrm{hLen} - 1)</math>
# To reverse step 6, recover the data block ''DB:'' <math>\mathrm{DB} = \mathrm{maskedDB} \oplus \mathrm{dbMask}</math>
# To reverse step 3, split the data block into its parts: <math>\mathrm{DB} = \mathrm{lHash'} || \mathrm{PS} || \mathrm{0x01} || \mathrm{M}</math>.
## Verifiy that:
##* ''lHash''' is equal to the computed ''lHash''
##* ''PS'' only consists of bytes 0x00
##* ''PS'' and ''M'' are seperated by the 0x01 byte and
##* the first byte of ''EM'' is the byte 0x00.
## If any of these conditions aren't met, then the padding is invalid.
 
Usage in RSA: The encoded message can then be encrypted with RSA. The deterministic property of RSA is now avoided by using the OAEP encoding because the ''seed'' is randomly generated and influences the entire encoded message.
 
===Security===
The "[[All-or-nothing transform|all-or-nothing]]" security is from the fact that to recover ''mM'', one must recover the entire ''XmaskedDB'' and the entire ''YmaskedSeed''; ''XmaskedDB'' is required to recover the ''rseed'' from the ''YmaskedSeed'', and the ''rseed'' is required to recover the data block ''mDB'' from ''XmaskedDB''. Since any changed bit of a cryptographic hash completely changes the result, the entire ''XmaskedDB'', and the entire ''YmaskedSeed'' must both be completely recovered.
 
===Implementation===
In the PKCS#1 standard, the random oracles ''G'' and ''H'' are identical. The PKCS#1 standard further requires that the random oracles be [[MGF1]] with an appropriate hash function.<ref>{{Cite journal|url=https://eprint.iacr.org/2006/223.pdf| title=What Hashes Make RSA-OAEP Secure?|journal = IACR Cryptology ePrint Archive| last=Brown |first=Daniel R. L.| date=2006| language=en|access-date=2019-04-03}}</ref>
 
==See also==