最適な非対称暗号化パディング

暗号学において、最適非対称暗号パディング（OAEP）は、 RSA暗号化と併用されることが多いパディング方式です。OAEPはBellareとRogawayによって導入され、^[1]その後PKCS#1 v2とRFC 2437で標準化されました。

OAEP アルゴリズムは、非対称暗号化の前に、一対のランダムオラクルG と H を使用して平文を処理するFeistel ネットワークの一種です。任意の安全なトラップドア一方向置換と組み合わせると、この処理はランダムオラクルモデルで証明され、選択平文攻撃(IND-CPA)に対して意味的に安全な組み合わせ方式になります。特定のトラップドア置換 (RSA など) を実装すると、OAEP は選択暗号文攻撃に対しても安全であることが証明されています。OAEP は、全か無かの変換を構築するために使用できます。 ${\displaystyle f}$

OAEP は次の 2 つの目標を満たします。

1. 決定論的暗号化方式 (従来のRSAなど)を確率的方式に変換するために使用できるランダム要素を追加します。
2. 攻撃者がトラップドア一方向置換を 反転できずに平文の一部を復元できないようにすることで、暗号文の部分的な復号化 (またはその他の情報漏洩) を防止します。${\displaystyle f}$

OAEP のオリジナル バージョン (Bellare/Rogaway、1994) は、OAEP を任意のトラップドア順列と共に使用した場合、ランダム オラクル モデルで「平文認識」(選択暗号文攻撃に対するセキュリティを意味すると主張) の形式を示しました。その後の結果はこの主張に反し、OAEP はIND-CCA1セキュアに過ぎないことを示しました。ただし、RSA-OAEP の場合のように、OAEP を標準暗号化指数を使用した RSA 順列と共に使用した場合、ランダムオラクル モデルでオリジナルの方式はIND-CCA2セキュアであることが証明されました。 ^[2]この問題を解決するために、Victor Shoup によって、任意のトラップドア一方向順列で機能する改良方式 (OAEP+ と呼ばれる) が提案されました。 ^[3] 最近の研究では、標準モデル（つまり、ハッシュ関数がランダムオラクルとしてモデル化されていない場合）では、RSA問題の想定される困難性の下でRSA-OAEPのIND-CCA2セキュリティを証明することは不可能であることが示されています。^{[4] [5]}

図では、

• MGFはマスク生成関数であり、通常はMGF1である。
• ハッシュは選択されたハッシュ関数であり、
• hLenはハッシュ関数の出力の長さ（バイト単位）である。
• kはRSA係数nのバイト単位の長さです。
• Mはパディングされるメッセージであり、長さはmLen（最大バイト）である。${\displaystyle \mathrm {mLen} =k-2\cdot \mathrm {hLen} -2}$
• Lはメッセージに関連付けるオプションのラベルです（ラベルはデフォルトでは空の文字列であり、暗号化を必要とせずにデータを認証するために使用できます）。
• PS はヌルバイトのバイト文字列です。${\displaystyle k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2}$
• ⊕ はXOR演算です。

PKCS#1 v2.2のRFC 8017 ^[6]では、エンコードにOAEPスキームを次のように規定しています。

1. 選択したハッシュ関数を使用してラベルLをハッシュします。${\displaystyle \mathrm {lHash} =\mathrm {ハッシュ} (L)}$
2. 値 0x00 のバイトで構成されるパディング文字列PS を生成します。${\displaystyle k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2}$
3. lHash、PS、単一バイト 0x01、およびメッセージMを連結してデータ ブロックDB :を形成します。このデータ ブロックの長さはバイトです。${\displaystyle \mathrm {DB} =\mathrm {lHash} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M} }$${\displaystyle k-\mathrm {hLen} -1}$
4. 長さhLenのランダムシードを生成します。
5. マスク生成関数を使用して、データ ブロックに適切な長さのマスクを生成します。${\displaystyle \mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)}$
6. 生成されたマスクでデータ ブロックをマスクします。${\displaystyle \mathrm {maskedDB} =\mathrm {DB} \oplus \mathrm {dbMask} }$
7. マスク生成関数を使用して、シードの長さhLenのマスクを生成します。${\displaystyle \mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )}$
8. 生成されたマスクでシードをマスクします。${\displaystyle \mathrm {maskedSeed} =\mathrm {seed} \oplus \mathrm {seedMask} }$
9. エンコードされた（パディングされた）メッセージは、 maskedSeedとmaskedDBが連結されたバイト 0x00 です。${\displaystyle \mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB} }$

デコードは、エンコード アルゴリズムで実行された手順を逆に実行することで機能します。

1. 選択したハッシュ関数を使用してラベルLをハッシュします。${\displaystyle \mathrm {lHash} =\mathrm {ハッシュ} (L)}$
2. 手順 9 を元に戻すには、エンコードされたメッセージEM をバイト 0x00、maskedSeed (長さhLen )、およびmaskedDBに分割します。 ${\displaystyle \mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB} }$
3. シードをマスクするために使用されたseedMaskを生成します。${\displaystyle \mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )}$
4. 手順 8 を元に戻すには、seedMaskを使用してシードを復元します。${\displaystyle \mathrm {seed} =\mathrm {maskedSeed} \oplus \mathrm {seedMask} }$
5. データ ブロックをマスクするために使用されたdbMaskを生成します。${\displaystyle \mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)}$
6. 手順 6 を元に戻すには、データ ブロックDB を回復します。 ${\displaystyle \mathrm {DB} =\mathrm {maskedDB} \oplus \mathrm {dbMask} }$
7. 手順 3 を元に戻すには、データ ブロックを次の部分に分割します。 ${\displaystyle \mathrm {DB} =\mathrm {lHash'} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M} }$
   1. 次のことを確認してください:
      • lHash'は計算されたlHashと等しい
      • PSはバイト0x00のみで構成されています
      • PSとMは0x01バイトで区切られており、
      • EMの最初のバイトはバイト 0x00 です。
   2. これらの条件のいずれかが満たされない場合、パディングは無効になります。

RSA での使用: エンコードされたメッセージは、RSA で暗号化できます。シードはランダムに生成され、エンコードされたメッセージ全体に影響を及ぼすため、OAEP エンコードを使用することで RSA の決定論的特性は回避されます。

「オール・オア・ナッシング」セキュリティは、 M を復元するには、 maskedDB全体とmaskedSeed全体を復元する必要があるという事実から生まれます。maskedDB はmaskedSeedからシードを復元する必要があり、シードはmaskedDBからデータ ブロックDBを復元する必要があります。暗号ハッシュのビットが変更されると結果が完全に変わるため、maskedDB全体とmaskedSeed全体の両方を完全に復元する必要があります。

PKCS#1標準では、ランダムオラクルは同一です。PKCS#1標準ではさらに、ランダムオラクルが適切なハッシュ関数を持つMGF1であることが要求されています。 ^[7]

• キーのカプセル化