Cryptography Reference
In-Depth Information
Exercise 10.4.
Define a signature scheme which is similar to the ElGamal signature
scheme, but which uses an elliptic curve modulo p instead of the
Z
p
group. Precisely
describe the setup, signature, and verification algorithms.
(Hint: Assume that we can easily compute the order of an elliptic curve.)
If we now want to design an algorithm similar to the Schnorr signature, we have
to face a new problem. What is this problem?
Exercise 10.5.
Let us assume that a lazy signer has precomputed one
(
k
r
)
pair for
the DSS signature scheme and that he always uses the same one. Show how to attack
him and recover his secret key.
,
Exercise 10.6.
Let us assume that a lazy signer has one precomputed
(
k
r
)
pair for
the Schnorr signature. Each time he needs to sign, he uses the precomputed signature
and replaces
(
k
,
r
2
mod
p
)
. What is the complexity gain? Show how
to attack him and recover his secret key.
,
r
)
by
(2
k
mod
q
,
Exercise 10.7.
The DSA scheme is nondeterministic. Let us assume that the signer now
chooses k by using a pseudorandom generator fed with a secret key and the message
to be signed. Show that a verifier which has the secret key can efficiently verify the
signature.
Exercise 10.8 (Ong-Schnorr-Shamir).
Precisely define a public-key signature
scheme such that there is a common large composite modulus n (of unknown factoriza-
tion), a public key K
p
=
s such that s
2
k, a secret key K
s
=
≡−
k
(mod
n
)
, andwhere
y
)
consists of checking that x
2
ky
2
the verification of a signature
σ
=
(
x
,
+
≡
H
(
m
)
(mod
n
)
.
3
(Note: This is insecure. It has been broken by Pollard and Schnorr.)
4
Exercise 10.9.
Let us assume that we have n ElGamal signatures to verify. We need to
check n triplets
(
M
i
,
r
i
,
s
i
)
, where M
i
is the message and
(
r
i
,
s
i
)
is the signature. We
assume all signatures come from the same signer and correspond to the same public
key y and the same p
,
g parameters.
What is the complexity of verifying all the signatures sequentially in terms of the
size
of p in bits?
3
This exercise was inspired by Ref. [144].
4
See Ref. [151].
Search WWH ::
Custom Search