Cryptography Reference
In-Depth Information
e
and a random quadratic
(
+
)
=
1. Choose a random
l
1
-bit prime
e
such that
e
residue
y
←
QR
n
.
2. Compute the value
x
defined as follows:
e
h
−
H
(
m
)
mod
n
x
:=
(
y
)
∈ Z
n
.
∈ Z
n
such that:
3. Compute
y
xh
H
(
x
)
y
e
≡
(
mod
n
)
(note that this
e
th root modulo
n
is easy to compute given the private key, i.e.,
the factorization of
n
;seeRemarks9.6).
4. The signature corresponding to the message
m
is then the 3-tuple
y
)
(
e
,
y
,
.
}
∗
and its signature
y
)
•
Verification
. Given a message
m
∈{
0
,
1
(
e
,
y
,
,aswellas
e
)
the public key
(
n
,
h
,
x
,
, verification proceeds as follows:
-bit integer different from
e
.
1. Check that
e
is an odd
(
l
+
1
)
e
h
−
H
(
m
)
mod
n
2. Compute
x
=
(
y
)
∈ Z
n
.
y
e
h
−
H
(
x
)
mod
n
∈ Z
n
.
4. If both checks are affirmative then accept the signature, otherwise reject it.
3. Check whether
x
=
Remarks 9.6
1. All computations in the signing and verification algorithms take place in the
group
QR
n
. Since
n
is a product of two distinct odd primes, each quadratic
residue modulo
n
has exactly 4 square roots in
Z
n
by Corollary 2.7 and hence
|
QR
n
|=|Z
n
|
/
p
q
. Thus the computation
of
y
in the signing algorithm can be done as follows. Since
4
=
φ(
n
)/
4
=
(
p
−
1
)(
q
−
1
)/
4
=
QR
n
has order
p
q
,
the exponent
e
is defined modulo this order and the
e
th root can be computed
as
y
xh
H
(
x
)
)
e
−
1
mod
p
q
mod
n
. Indeed, since len
l
−
=
(
(
e
)
=
l
+
1
<
p
)
=
q
)
p
q
)
=
1 and hence the inverse
e
−
1
mod
p
q
∈ Z
p
q
exists and may be efficiently computed by means of the
extended Euclidean algorithm.
2. The prime
e
generated in the signing algorithm need not be randomly chosen.
Instead, the requirement is that the probability of generating the same prime
twice when signing different messages should be negligible. This will indeed
be the case if these primes are randomly chosen which, on the other hand, also
guarantees that
e
1
=
len
(
len
(
, we have that gcd
(
e
,
e
except with negligible probability. Since the quadratic
residue
y
is also randomly chosen, the signing algorithm is probabilistic.
3. Observe that the verification algorithm does not verify that
e
is prime, checking
only that
e
is odd. This is done for efficiency, since the security reduction to
which we refer below does not require checking primality.
4. As happenswith theCramer-Shoup encryption scheme, the existence of 'enough'
Sophie Germain primes is required for this signature scheme to be secure. As
we have mentioned, these primes are indeed conjectured to be abundant and we
=
