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

Scheme often used with RSA encryption

暗号学において、最適非対称暗号パディング（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の場合のように、標準的な暗号化指数を用いたRSA順列とOAEPを併用した場合、ランダムオラクルモデルにおいてIND-CCA2安全性を持つことが証明された。 ^[2]この問題を解決するために、Victor Shoupによって、任意のトラップドア一方向性順列で動作する改良方式（OAEP+と呼ばれる）が提案された。 ^[3]最近の研究では、標準モデル（つまり、ハッシュ関数がランダムオラクルとしてモデル化されていない場合）では、 RSA問題の想定される困難性の下でRSA-OAEPのIND-CCA2安全性を証明することは不可能であることが示されています。^{[4] [5]}

アルゴリズム

RFC 8017に準拠したOAEPエンコーディングスキーマ

図では、

• 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 {Hash} (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 {Hash} (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]

参照

• キーのカプセル化

参考文献

1. M. Bellare、P. Rogaway「最適非対称暗号化 - RSAによる暗号化方法」。Advances in Cryptology – Eurocrypt '94 Proceedings、Lecture Notes in Computer Science Vol. 950、A. De Santis 編、Springer-Verlag、1995年。完全版（pdf）
2. 藤崎英一郎、岡本達明、デイヴィッド・ポインシュヴァル、ジャック・スターン。RSA --OAEPはRSA仮定の下で安全である。J. Kilian編『Advances in Cryptology – CRYPTO 2001』、Lecture Notes in Computer Science第2139巻、SpringerVerlag、2001年。完全版（pdf）
3. Victor Shoup. OAEP再考. IBMチューリッヒ研究所, Saumerstr. 4, 8803 Ruschlikon, スイス. 2001年9月18日. 完全版 (pdf)
4. P. Paillier と J. Villar、「因数分解ベース暗号化における選択暗号文セキュリティに対する一方向性のトレードオフ」、Advances in Cryptology – Asiacrypt 2006。
5. D. Brown、「RSA-OAEP を安全にするハッシュは何ですか?」IACR ePrint 2006/233。
6. 「暗号化操作」。PKCS #1: RSA暗号化仕様バージョン2.2。IETF 。 2016年11月。p. 22。sec. 7.1.1。doi : 10.17487/RFC8017。RFC 8017。2022年6月4日閲覧。
7. Brown, Daniel RL (2006). 「RSA-OAEPを安全にするハッシュとは？」(PDF) . IACR Cryptology ePrint Archive . 2019年4月3日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Optimal_asymmetric_encryption_padding&oldid=1314652857"