Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding, auf Deutsch etwa Optimales asymmetrisches Verschlüsselungs-Padding, oft auch abgekürzt als OAEP, ist ein kryptographisches Paddingverfahren. Es ist eine spezielle Form eines Feistelnetzwerks, mit welchem im Zufallsorakel-Modell aus einer beliebigen Falltürpermutation ein gegen Gewählte-Klartext-Angriffe semantisch sicheres Kryptosystem gebaut werden kann. Das Verfahren wurde 1994 von Mihir Bellare und Philipp Rogaway veröffentlicht.

Verfahren

Es sei $k$ ein Sicherheitsparameter, und $k_{0}$ so, dass ein Angreifer nur deutlich weniger als $2^{k_{0}}$ Rechenschritte ausführen kann.

Weiters seien $f:\{0,1\}^{k}\mapsto \{0,1\}^{k}$ eine Falltürpermutation auf Nachrichten mit $k$ Bits, und $n=k-k_{0}$ die Länge der Nachrichten, welche übertragen werden sollen.

Schließlich seien $G:\{0,1\}^{k_{0}}\mapsto \{0,1\}^{n}$ und $H:\{0,1\}^{n}\mapsto \{0,1\}^{k_{0}}$ kryptographische Hashfunktionen.

Verschlüsselung

Um eine $n$-Bit Nachricht $m$ zu verschlüsseln, verfährt man nun wie folgt:

• Man wählt $r\in \{0,1\}^{k_{0}}$ als eine zufällige Folge von $k_{0}$ Bits.
• Der Schlüsseltext $c$ ist dann gegeben als:

$c=f(m\oplus G(r)||r\oplus H(m\oplus G(r)))$,

wobei $||$ hier für Konkatenation steht.

Entschlüsselung

Um die Nachricht $m$ zu rekonstruieren, führt man die folgenden Schritte aus:

• Zuerst verwendet man die Falltür, um

$u=u_{1}||u_{2}=f^{-1}(c)$

zu berechnen.

• Nun rekonstruiert man den Zufallswert $r$ als

$r=u_{1}\oplus H(u_{1})$.

• Schließlich erhält man die Nachricht $m$ wieder als

$m=u_{1}\oplus G(r)$ .

Varianten

Durch eine einfache Modifikation des obigen Protokolls kann man auch IND-CCA1 Sicherheit, also Sicherheit gegen Gewählte-Schlüsseltext-Angriffe erreichen. Dazu reduziert man die Länge der Nachricht $m$ auf $n-k_{1}$ Bits, und konkatiniert sie mit $k_{1}$ Nullen. Beim Entschlüsseln prüft man, ob der rekonstruierte Wert die korrekte Form hat, und bricht ansonsten ab.

Victor Shoup präsentierte eine Erweiterung des Verfahrens, mit welcher für jede beliebige Falltürpermutation auch IND-CCA2 Sicherheit erreicht werden kann.