Probabilistic Signature Scheme

Probabilistic Signature Scheme (PSS) or probabilistic signature method is a cryptographic padding method developed by Mihir Bellare and Phillip Rogaway . In the random oracle model , the PSS can be used to construct a verifiably secure signature method from a trap door permutation .

Procedure

PSS was developed because there was no evidence of security for the signature processes existing at the time, which correlated the security of the signature process with the difficulty of the problem on which the process was based. Such a proof could be given for PSS with the help of random oracles that model ideal cryptological hash functions .

Sign

Signature at RSA-PSS

The method uses a hash function and is parameterized by three values: ${\displaystyle H}$

• ${\displaystyle k}$, the bit length of the set on which the permutation operates
• ${\displaystyle k_{0}}$, the length of the random number
• ${\displaystyle k_{1}}$, the output length of the hash function ${\displaystyle H}$

For signing, the message is hashed together with a random number to form a value . Since verification is required, it is masked with . Another function supplies the missing bits. The signature is now calculated from the bit string by means of the secret inversion of the one-way permutation . ${\displaystyle M}$ ${\displaystyle r}$ ${\displaystyle w=H(M|r)}$ ${\displaystyle r}$ ${\displaystyle g_{1}(w)}$ ${\displaystyle g_{2}(w)}$ ${\displaystyle k-k_{0}-k_{1}-1}$ ${\displaystyle y=0|w|r}$ ${\displaystyle \oplus }$ ${\displaystyle g_{1}(w)|g_{2}(w)}$ ${\displaystyle s=P^{-1}(y)}$

To verify

Verification at RSA-PSS

In order to verify a signature of a message , it is first calculated and parsed in. Then the random number is retrieved and checked that , and is. If these conditions are met, the signature is valid, otherwise not. ${\displaystyle s}$ ${\displaystyle M}$ ${\displaystyle y=P(s)}$ ${\displaystyle b|w|r'|s'}$ ${\displaystyle r=r'\oplus g_{1}(w)}$ ${\displaystyle w=H(M|r)}$ ${\displaystyle s'=g_{2}(w)}$ ${\displaystyle b=0}$

Variants RSA-PSS

In 1996, Bellare and Rogaway described the combination of PSS with RSA as a trapdoor permutation in their paper. In the random oracle model, RSA-PSS is existentially unforgeable under chosen-message attacks ( EUF-CMA ) under the RSA assumption.

A variant of RSA-PSS is standardized in PKCS # 1 from version 2.1. In particular, in this standard the message is hashed first; this should enable the use of smart cards with low bandwidth as signature cards.

RSA-PSS is part of the large manufacturer standard Public-Key Cryptography Standard (PKCS), which has been gradually converted into Request for Comments (RFC). The further development of RSAPSS only takes place via RFC publications.

Norms and standards

• RFC 8017 - Public-Key Cryptography Standards (PKCS) # 1: RSA Cryptography Specifications Version 2.2, from 2016.
• RFC 4056 - Use of the RSASSA-PSS Signature Algorithm in Cryptographic Message Syntax (CMS), from 2005.
• RFC 5756 - Updates for RSAES-OAEP and RSASSA-PSS Algorithm Parameters, from 2010. [Convention for X.509 Certificates].

Individual evidence

1. ↑ ^{a b} Mihir Bellare and 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 ). tape 1070 . Springer, 1996, p. 399-416 ( ucdavis.edu ).
2. ↑ RSA Laboratories (ed.): PKCS # 1 v2.1: RSA Cryptography Standard . 2002 ( rsasecurity.com [PDF]).