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