Optimale asymmetrische Verschlüsselungsauffüllung

In der Kryptographie ist optimales asymmetrisches Verschlüsselungs-Padding ( OAEP ) ein Padding-Verfahren, das häufig zusammen mit der RSA-Verschlüsselung verwendet wird . OAEP wurde von Bellare und Rogaway ^{[ 1 ]} eingeführt und anschließend in PKCS #1 v2 und RFC 2437 standardisiert.

Der OAEP-Algorithmus ist eine Form des Feistel-Netzwerks , das zwei Zufallsorakel G und H verwendet, um den Klartext vor der asymmetrischen Verschlüsselung zu verarbeiten . In Kombination mit einer beliebigen sicheren Einwegpermutation mit Falltür ist dieses Verfahren im Zufallsorakelmodell nachweislich semantisch sicher gegen Angriffe mit gewähltem Klartext (IND-CPA) . Bei Verwendung bestimmter Falltürpermutationen (z. B. RSA) ist OAEP auch gegen Angriffe mit gewähltem Geheimtext sicher. OAEP kann zur Konstruktion einer Alles-oder-Nichts-Transformation verwendet werden . $f$

OAEP erfüllt die folgenden beiden Ziele:

Fügen Sie ein Zufallselement hinzu, mit dem ein deterministisches Verschlüsselungsverfahren (z. B. das traditionelle RSA ) in ein probabilistisches Verfahren umgewandelt werden kann.
Die teilweise Entschlüsselung von Chiffretexten (oder andere Informationslecks) wird verhindert, indem sichergestellt wird, dass ein Angreifer keinen Teil des Klartextes wiederherstellen kann, ohne die Einwegpermutation der Falltür umkehren zu können . $f$

Die ursprüngliche Version von OAEP (Bellare/Rogaway, 1994) zeigte eine Form von „ Klartextbewusstsein “ (was ihrer Ansicht nach Sicherheit gegen Angriffe mit gewähltem Chiffretext impliziert ) im Random-Oracle-Modell, wenn OAEP mit einer beliebigen Trapdoor-Permutation verwendet wird. Spätere Ergebnisse widersprachen dieser Behauptung und zeigten, dass OAEP nur IND-CCA1- sicher ist. Es wurde jedoch bewiesen, dass das ursprüngliche Schema im Random-Oracle-Modell IND-CCA2- sicher ist , wenn OAEP mit der RSA-Permutation unter Verwendung von Standard-Verschlüsselungsexponenten verwendet wird, wie im Fall von RSA-OAEP. ^{[ 2 ]} Ein verbessertes Schema (OAEP+ genannt), das mit jeder Trapdoor-Einwegpermutation funktioniert, wurde von Victor Shoup vorgeschlagen , um dieses Problem zu lösen. ^{[ 3 ]} Neuere Arbeiten haben gezeigt, dass es im Standardmodell (d. h. wenn Hashfunktionen nicht als Random Oracles modelliert werden) unmöglich ist, die IND-CCA2-Sicherheit von RSA-OAEP unter der angenommenen Schwierigkeit des RSA-Problems zu beweisen . ^{[ 4 ]}^{[ 5 ]}

Algorithmus

Im Diagramm,

MGF ist die Maskenerzeugungsfunktion , üblicherweise MGF1.
Hash ist die gewählte Hash-Funktion ,
hLen ist die Länge der Ausgabe der Hash-Funktion in Bytes.
k ist die Länge des RSA- Moduls n in Bytes.
M ist die aufzufüllende Nachricht mit einer Länge von mLen (maximal Bytes). $\mathrm {mLen} =k-2\cdot \mathrm {hLen} -2$
L ist eine optionale Bezeichnung, die der Nachricht zugeordnet werden kann (standardmäßig ist die Bezeichnung eine leere Zeichenkette und kann zur Authentifizierung von Daten verwendet werden, ohne dass eine Verschlüsselung erforderlich ist).
PS ist eine Bytefolge aus Nullbytes. $k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2$
⊕ ist eine XOR -Operation.

Codierung

RFC 8017 ^{[ 6 ]} für PKCS#1 v2.2 spezifiziert das OAEP-Schema für die Kodierung wie folgt:

Hashen Sie die Bezeichnung L mithilfe der gewählten Hash-Funktion: $\mathrm {lHash} =\mathrm {Hash} (L)$
Erzeugen Sie eine Auffüllzeichenkette PS bestehend aus den Bytes (0x00 und 0x01). $k-\mathrm {mLen} -2\cdot \mathrm {hLen} -2$
Verkette lHash , PS , das einzelne Byte 0x01 und die Nachricht M zu einem Datenblock DB : . Dieser Datenblock hat die Länge Bytes. $\mathrm {DB} =\mathrm {lHash} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M}$ $k-\mathrm {hLen} -1$
Generiere einen Zufallsstartwert der Länge hLen .
Verwenden Sie die Maskengenerierungsfunktion, um eine Maske der passenden Länge für den Datenblock zu erzeugen: $\mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)$
Maskieren Sie den Datenblock mit der generierten Maske: $\mathrm {maskedDB} =\mathrm {DB} \oplus \mathrm {dbMask}$
Verwenden Sie die Maskengenerierungsfunktion, um eine Maske der Länge hLen für den Seed zu erzeugen: $\mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )$
Maskieren Sie den Seed mit der generierten Maske: $\mathrm {maskedSeed} =\mathrm {seed} \oplus \mathrm {seedMask}$
Die kodierte (aufgefüllte) Nachricht ist das Byte 0x00, verkettet mit maskedSeed und maskedDB : $\mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB}$

Dekodierung

Die Dekodierung funktioniert durch Umkehrung der Schritte des Kodierungsalgorithmus:

Hashen Sie die Bezeichnung L mithilfe der gewählten Hash-Funktion: $\mathrm {lHash} =\mathrm {Hash} (L)$
Um Schritt 9 rückgängig zu machen, teilen Sie die kodierte Nachricht EM in das Byte 0x00, den maskedSeed (mit der Länge hLen ) und den maskedDB auf : $\mathrm {EM} =\mathrm {0x00} ||\mathrm {maskedSeed} ||\mathrm {maskedDB}$
Generieren Sie die Seed-Maske , die zum Maskieren des Seeds verwendet wurde : $\mathrm {seedMask} =\mathrm {MGF} (\mathrm {maskedDB} ,\mathrm {hLen} )$
Um Schritt 8 rückgängig zu machen, stellen Sie den Seed mithilfe der SeedMask wieder her : $\mathrm {seed} =\mathrm {maskedSeed} \oplus \mathrm {seedMask}$
Generieren Sie die dbMask , die zum Maskieren des Datenblocks verwendet wurde: $\mathrm {dbMask} =\mathrm {MGF} (\mathrm {seed} ,k-\mathrm {hLen} -1)$
Um Schritt 6 rückgängig zu machen, muss der Datenblock DB wiederhergestellt werden: $\mathrm {DB} =\mathrm {maskedDB} \oplus \mathrm {dbMask}$
Um Schritt 3 rückgängig zu machen, teilen Sie den Datenblock in seine Teile auf: . $\mathrm {DB} =\mathrm {lHash'} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M}$ $\mathrm {DB} =\mathrm {lHash'} ||\mathrm {PS} ||\mathrm {0x01} ||\mathrm {M}$
1. Überprüfen Sie Folgendes:
  - lHash' ist gleich dem berechneten lHash.
  - PS besteht nur aus Bytes 0x00
  - PS und M sind durch das Byte 0x01 getrennt und
  - Das erste Byte von EM ist das Byte 0x00.
2. Wenn eine dieser Bedingungen nicht erfüllt ist, ist die Auffüllung ungültig.

Anwendung in RSA: Die kodierte Nachricht kann anschließend mit RSA verschlüsselt werden. Die deterministische Eigenschaft von RSA wird durch die Verwendung der OAEP-Kodierung umgangen, da der Seed zufällig generiert wird und die gesamte kodierte Nachricht beeinflusst.

Sicherheit

Die „ Alles-oder-nichts “-Sicherheit beruht darauf, dass zur Wiederherstellung von M sowohl die gesamte maskedDB als auch der gesamte maskedSeed wiederhergestellt werden müssen . Die maskedDB wird benötigt, um den Seed aus dem maskedSeed zu extrahieren , und der Seed wiederum wird benötigt, um den Datenblock DB aus der maskedDB wiederherzustellen . Da jedes geänderte Bit eines kryptografischen Hashs das Ergebnis vollständig verändert, müssen sowohl die gesamte maskedDB als auch der gesamte maskedSeed vollständig wiederhergestellt werden.

Durchführung

Im PKCS#1-Standard sind die Zufallsorakel identisch. Der PKCS#1-Standard fordert außerdem, dass die Zufallsorakel MGF1- Funktionen mit einer geeigneten Hash-Funktion sind. ^{[ 7 ]}

Siehe auch

Schlüsselkapselung

Referenzen

^ M. Bellare , P. Rogaway . Optimale asymmetrische Verschlüsselung – Wie man mit RSA verschlüsselt . Erweiterte Zusammenfassung in: Advances in Cryptology – Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis (Hrsg.), Springer-Verlag , 1995. Vollversion (PDF)
^ Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval und Jacques Stern . RSA – OAEP ist unter der RSA-Annahme sicher . In: J. Kilian (Hrsg.), Advances in Cryptology – CRYPTO 2001, Band 2139 der Lecture Notes in Computer Science, Springer-Verlag, 2001. Vollversion (PDF)
^ Victor Shoup. OAEP neu betrachtet . IBM Zurich Research Lab, Saumerstr. 4, 8803 Rüschlikon, Schweiz. 18. September 2001. Vollversion (PDF)
^ P. Paillier und J. Villar, Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption , Advances in Cryptology – Asiacrypt 2006.
^ D. Brown, Welche Hashes machen RSA-OAEP sicher? , IACR ePrint 2006/233.
^ „Verschlüsselungsoperation“ . PKCS #1: RSA Cryptography Specifications Version 2.2 . IETF . November 2016. S. 22. Abschn. 7.1.1. doi : 10.17487/RFC8017 . RFC 8017. Abgerufen am 4. Juni 2022 .
^ Brown, Daniel RL (2006). „What Hashes Make RSA-OAEP Secure?“ (PDF) . IACR Cryptology ePrint Archive . Abgerufen am 3. April 2019 .

[1] M. Bellare , P. Rogaway . Optimale asymmetrische Verschlüsselung – Wie man mit RSA verschlüsselt . Erweiterte Zusammenfassung in: Advances in Cryptology – Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis (Hrsg.), Springer-Verlag , 1995. Vollversion (PDF)

[2] Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval und Jacques Stern . RSA – OAEP ist unter der RSA-Annahme sicher . In: J. Kilian (Hrsg.), Advances in Cryptology – CRYPTO 2001, Band 2139 der Lecture Notes in Computer Science, Springer-Verlag, 2001. Vollversion (PDF)

[3] Victor Shoup. OAEP neu betrachtet . IBM Zurich Research Lab, Saumerstr. 4, 8803 Rüschlikon, Schweiz. 18. September 2001. Vollversion (PDF)

[4] P. Paillier und J. Villar, Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption , Advances in Cryptology – Asiacrypt 2006.

[5] D. Brown, Welche Hashes machen RSA-OAEP sicher? , IACR ePrint 2006/233.

[6] „Verschlüsselungsoperation“ . PKCS #1: RSA Cryptography Specifications Version 2.2 . IETF . November 2016. S. 22. Abschn. 7.1.1. doi : 10.17487/RFC8017 . RFC 8017. Abgerufen am 4. Juni 2022 .

[7] Brown, Daniel RL (2006). „What Hashes Make RSA-OAEP Secure?“ (PDF) . IACR Cryptology ePrint Archive . Abgerufen am 3. April 2019 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]