Probabilistic Signature Scheme

Probabilistic Signature Scheme (PSS) oder probabilistisches Signaturverfahren ist ein von Mihir Bellare und Phillip Rogaway entwickeltes kryptographisches Paddingverfahren. Im Zufallsorakelmodell kann mit dem PSS aus einer Falltürpermutation ein beweisbar sicheres Signaturverfahren konstruiert werden.

Verfahren

PSS wurde entwickelt, weil es für die damals existierenden Signaturverfahren keine Sicherheitsbeweise gab, die die Sicherheit des Signaturverfahrens in eine enge Beziehung zur Schwierigkeit des dem Verfahren zugrundeliegenden Problems setzten. Ein solcher Beweis konnte für PSS mit Hilfe von Zufallsorakeln, die ideale kryptologische Hashfunktionen modellieren, angegeben werden.

Signieren

Signatur bei RSA-PSS

Das Verfahren benutzt eine Hashfunktion $H$ und wird durch drei Werte parametrisiert:

• $k$, die Bitlänge der Menge auf der die Permutation operiert
• $k_{0}$, die Länge der Zufallszahl
• $k_{1}$, die Ausgabelänge der Hashfunktion $H$

Zum Signieren wird die Nachricht $M$ zusammen mit einer Zufallszahl $r$ zu einem Wert $w=H(M|r)$ gehasht. Da $r$ zur Verifikation benötigt wird, wird sie mit $g_{1}(w)$ maskiert. Eine weitere Funktion liefert $g_{2}(w)$, die $k-k_{0}-k_{1}-1$ fehlenden Bits. Aus dem Bitstring $y=0|w|r$ $\oplus$ $g_{1}(w)|g_{2}(w)$ ist nun mittels der geheimen Umkehrung der Einwegpermutation die Signatur $s=P^{-1}(y)$ berechnet.

Verifizieren

Verifikation bei RSA-PSS

Um eine Signatur $s$ einer Nachricht $M$ zu verifizieren, wird zuerst $y=P(s)$ berechnet und in $b|w|r'|s'$ geparst. Dann wird die Zufallszahl $r=r'\oplus g_{1}(w)$ wiedergewonnen und überprüft, dass $w=H(M|r)$, $s'=g_{2}(w)$ und $b=0$ ist. Falls diese Bedingungen erfüllt sind, ist die Signatur gültig, andernfalls nicht.

Varianten RSA-PSS

1996 beschrieben Bellare und Rogaway in ihrem Papier die Kombination von PSS mit RSA als Falltürpermutation. Im Zufallsorakelmodell ist RSA-PSS existentially unforgeable under chosen-message attacks (EUF-CMA) unter der RSA-Annahme.

RSA-PSS ist in einer Variante im PKCS#1 ab Version 2.1 standardisiert. Insbesondere wird in diesem Standard die Nachricht zuerst gehasht; dies soll den Einsatz von Smartcards mit geringer Bandbreite als Signaturkarten ermöglichen.

RSA-PSS ist Teil des großen Herstellerstandard Public-Key Cryptography Standards (PKCS), welcher schrittweise in Request for Comments (RFC) überführt wurde. Die Weiterentwicklung von RSAPSS erfolgt nur noch über RFC-Veröffentlichungen.

Normen und Standards

• RFC: 8017 – Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.2. 2016 (englisch).
• RFC: 4056 – Use of the RSASSA-PSS Signature Algorithm in Cryptographic Message Syntax (CMS). 2005 (englisch).
• RFC: 5756 – Updates for RSAES-OAEP and RSASSA-PSS Algorithm Parameters. 2010 (Konvention für X.509 Zertifikate, englisch).