Digital Signature Systems - Contemporary Cryptography - page 390

Algorithm 15.3 The PSS Sign algorithm.

( n, d, m )
r ∈ R { 0 , 1 }

k 0
w ← h ( m r )
r ∗ ← g 1 ( w ) ⊕ r
y ← 0 w r ∗ g 2 ( w )
s ← y d (mod n )
( s )

.K/

=

.K/
3

K L

3

Figure 15.1 The PSS Sign algorithm.

signature generation). It takes as input a signing key ( n, d ) and a message m ,andit
generates as output a signature s . As its name suggests, the PSS is probabilistic (i.e.,
a k 0 -bit random value r is used to digitally sign m ).
The PSS Verify algorithm is deterministic, and it is specified in Algorithm
15.4. It takes as input a verification key ( n, e ), a message m , and a signature s ,andit
generates as output one bit b saying whether s is a valid signature for message m with
respect to ( n, e ). Note that in step 2, y can be broken up into the four components b ,
w , r ∗ ,and γ , because every component has a fixed and known length (i.e., b is one
bit long, w is k 1 bits long, r ∗ is k 0 1 bits long).

Also note that b is set to true (or valid) if and only if all three conditions (i.e., b =0,
h ( m

bits long, and γ is k − k 0 − k 1 −

r )= w ,and g 2 ( w )= γ )aretrue.
As mentioned earlier, the PSS is very efficient. In fact, the PSS Sign and
Verify algorithms both take only one application of h , one application of g ,and
one application of the RSA function. This is only slightly more expensive than the
basic RSA DSS.