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

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.

Das Verfahren benutzt eine Hashfunktion ${\displaystyle H}$ und wird durch drei Werte parametrisiert:

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

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

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

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.^[1]

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.^[2]

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.

• 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).

1. ↑ ^{a b} Mihir Bellare, Phillip Rogaway: The exact security of digital signatures: How to sign with RSA and Rabin. In: Advances in Cryptology – EUROCRYPT 96 (= Lecture Notes in Computer Science). Band 1070. Springer, 1996, S. 399–416 (ucdavis.edu). 
2. ↑ RSA Laboratories (Hrsg.): PKCS #1 v2.1: RSA Cryptography Standard. 2002 (rsasecurity.com [PDF]).