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.
 
Search WWH ::




Custom Search