Cryptography Reference
In-Depth Information
By applying this construction to the family of RSA permutations, plain RSA
signatures were introduced in [164] as the following scheme:
Definition 9.4
The
plain RSA signature scheme
is the signature scheme (
Gen
,
Sign
,
Ve r
) defined by the following algorithms:
Gen
: On input 1
k
, run the RSA instance generator (Algorithm 8.1) to obtain
(
•
n
,
e
,
d
)
←
Gen
RSA
.
Then set
pk
:=
(
n
,
e
)
and
sk
:=
(
n
,
d
)
.
pk
is the public
1
k
key and
sk
is the secret key, so that
(
pk
,
sk
)
←
Gen
(
)
.
•
Sign
: On input a private key
sk
=
(
n
,
d
)
and a message
m
∈ Z
n
, compute the
signature:
m
d
mod
n
σ
:=
Sign
(
sk
,
m
)
=
RSA
)
(
m
)
=
∈ Z
n
.
(
n
,
d
•
Ve r
: On input a public key
pk
=
(
n
,
e
)
, a message
m
∈ Z
n
, and a signature
σ
∈ Z
n
, compute:
m
:=
e
mod
n
RSA
(
n
,
e
)
(σ )
=
σ
∈ Z
n
,
and set
if and only if
m
=
(
,
,σ)
:=
.
Ve r
pk
m
1
m
The verification algorithmalways accepts valid signatures because, by Proposition
8.1, the permutations RSA
are inverses of each other. However,
plain RSA signatures are completely insecure and are vulnerable even to key-only
attacks. To see this observe that an existential forgery is obtained by picking
and RSA
(
n
,
d
)
(
n
,
e
)
σ
← Z
n
e
mod
n
and computing
m
:=
σ
∈ Z
n
. The pair
(
m
,σ)
is then accepted as valid by
the verification algorithm.
Another attack against plain RSA signatures, similar to one we have seen against
plain RSA encryption, exploits the malleability of plain RSA or, more precisely,
the multiplicative property. This attack is more dangerous than the preceding one
because, although it is a message attack that assumes a more powerful adversary, it
also achieves a stronger goal, namely, a selective forgery. Indeed, if the adversary
wants to forge a signature on a message
m
∈ Z
n
, then it simply chooses twomessages
m
1
,
m
(it is clear
that this can be done efficiently). Then it submits
m
1
and
m
2
to the signing oracle,
obtaining pairs
m
2
∈ Z
n
that are different from
m
and satisfy
m
1
m
2
mod
n
=
(
m
1
,σ
1
)
,
(
m
2
,σ
2
)
. Then, because of RSA's multiplicative property,
it is clear that if
is a forgery.
Each of these two attacks shows that plain RSA signatures are not secure in the
sense of Definition 9.3. More generally, signature schemes based on the trapdoor
permutation paradigm mentioned above are also insecure because the first of these
two attacks also applies to them.
σ
:=
σ
1
σ
2
mod
n
, the pair
(
m
,σ)
Exercise 9.1
Define plain Rabin signatures in a way similar to plain RSA signatures
but using the Blum-Williams trapdoor permutations (introduced in Sect.
3.3.3
and
