Cryptography Reference
In-Depth Information
}
∗
and a private key
sk
•
∈{
,
:=
(
,
)
Sign
acts as follows on input a message
m
0
1
n
d
:
k
0
.
- A random seed
r
is chosen:
r
←{
0
,
1
}
-
w
:=
H
(
m
||
r
)
.
-
r
∗
:=
G
1
(
w
)
⊕
r
.
r
∗
||
-
y
.
- Output the signature of
m
,
:=
0
||
w
||
G
2
(
w
)
y
d
mod
n
.
σ
:=
•
Ve r
acts as follows on input a signedmessage
(
m
,σ)
and a public key
pk
:=
(
n
,
e
)
:
e
mod
n
.
-
y
is parsed as
y
-
y
:=
σ
r
∗
||
γ
r
∗
)
=
=
b
||
w
||
, where len
(
b
)
=
1
,
len
(
w
)
=
k
1
and len
(
k
0
.
r
∗
⊕
-
r
:=
G
1
(
w
)
.
-If
H
(
m
||
r
)
=
w
and
G
2
(
w
)
=
γ
and
b
=
0 then output
Ve r
(
pk
,
m
,σ)
:=
1,
otherwise output
Ve r
(
pk
,
m
,σ)
:=
0.
A graphical depiction of PSS encoding is the following:
Remarks 9.3
We next give a brief explanation of some details in the preceding defi-
nition:
1. The PSS scheme was designed with
H
and
G
modeled as ideal hash functions,
i.e., as random oracles, which makes it possible to obtain a security reduction to
the RSA problem. In practical implementations, these functions are constructed
from a cryptographic hash function such as SHA-256.
2. To sign a message, the signer first picks a random
r
k
0
, concatenates it
to the message and hashes the result with the compressor obtaining a
k
1
-bit string
w
(thus the algorithm is randomized and, except with negligible probability, a
different signature will be obtained each time a given message is signed with a
given key). Afterwards,
r
∗
is obtained by applying the generator to the hashed
value
w
, taking the first
k
0
bits, and using them to 'mask'
r
by means of the
bitwise Xor operation. Then
w
←{
0
,
1
}
r
∗
is prepended with a 0 bit and appended with
||
G
2
(
w
)
to obtain a bit string
y
. The length of
y
is
k
, i.e., it is equal to len
(
n
)
.The
fact that the leading bit of
y
is 0 implies that
y
<
n
when regarded as an integer,
so that
y
∈ Z
n
and it can be 'decrypted' with the RSA function to obtain the
signature.