IV054 Coding, Cryptography and Cryptographic Protocols
2012 - Exercises VII.
1. Let m be a message which the adversary Eve intends to sign using the RSA signature scheme with
a public key (n, e) and a private key d. Suppose that Eve can obtain a signature of any message
m = m. Show that this enables her to sign m.
2. Consider the RSA signature scheme with public key (n, e) = (1927, 1483). Verify signatures si of
messages wi.
(a) w1 = 11, s1 = 416;
(b) w2 = 123, s2 = 1477;
(c) w3 = 56, s3 = 200.
3. Consider the following signature scheme. Alice has a public key (p, g, X, Y ), where p ≥ 3 is a prime,
g is a generator of (Z∗
p, ·), X = gx
(mod p) and Y = gy
(mod p), and a private key (x, y) where
x, y ∈ Z∗
p. The signature of a message m is s = y + xm (mod p). Find a verification algorithm for
this scheme and show its correctness.
4. Suppose Alice uses the Fiat-Shamir signature scheme with v1 = 6003, v2 = 1919, v3 = 2980, s1 =
44, s2 = 45, s3 = 46, h(x) = x mod 2011 and n = 7223.
Show in detail the computation steps of signing message 33 with r1 = 1200, r2 = 2400, r3 = 3600.
5. Consider the DSA signature scheme with a hash function H. If H is not one-way, show that we can
forge a triplet (m, a, b) such that (a, b) is valid signature for the message m.
6. Consider the DSA signature scheme. Let (p, q, r, x, y) be a key. Suppose the public parameters
p = 48731, q = 443, and r = 5260.
The element r was computed as r ≡ 748730/443
(mod 48731), where 7 is a primitive root modulo
48731. Alice chooses the secret signing key x = 242.
(a) What is Alice’s public verification key y?
(b) Alice signs the message m = 343 using k = 427. What is the signature? Perform all steps of
her calculation and all steps of Bob’s verification.
7. Let n be a large composite modulus (of unknown factorization), k and s be two elements of Z∗
n such
that s2
= −k (mod n). Let H : {0, 1}∗
→ Zn be a cryptographic hash function. Find a signature
algorithm which uses the public key k, the secret key s if you know that the verification of a signature
(x, y) of a message m consists in checking that
x2
+ ky2
≡ H(m) (mod n).