IV054 Coding, Cryptography and Cryptographic Protocols
2008 ­ Exercises IX.
1. Consider the Shamir's threshold scheme.
(a) Prove that f(xk)  yk (mod p) for 1  k  t.
(b) Let n = 5 and t = 3. Reconstruct the secret if p = 3361 and participants
P2, P3 and P5 have the shares (2, 596), (3, 1407) and (5, 334), respectively.
2. Prove correctness of the following identification protocol:
(1) Peggy chooses distinct primes p and q, computes n = pq and chooses e such
that gcd(e, (n)) = 1.
She chooses x  Z
n and computes y = xe
(mod n). Peggy's public key is
(n, e, y) and her private key is x.
(2) Peggy randomly chooses r  Z
n and sends a = re
(mod n) to Victor.
(3) Victor randomly chooses b  Ze and sends it to Peggy.
(4) Peggy computes c = xb
r (mod n) and sends it to Victor.
(5) Victor accepts if and only if ce
 yb
a (mod n).
3. Consider Feldman's (k, n)-protocol for secret sharing with verification. Prove
that if the dealer is honest, the equality
gyi
=
k-1
j=0
(vj)xi
j
(mod p)
is satisfied for each i  {1, . . . , n}.
4. Peggy and Victor share a bit string k. Peggy identifies herself to Victor using
the following protocol:
(1) Victor randomly chooses a bit string r and sends it to Peggy.
(2) Peggy computes r  k and sends it to Victor.
(3) Victor accepts if and only if k = r  c where c is the received bit string.
Is this protocol secure? Explain your reasoning.
5. Suppose Alice is using the Schnorr identification scheme where q = 617, p =
4937, t = 9 and  = 1624.
(a) Verify that  has order q in Z
p.
(b) Let Alice's secret exponent be a = 55. Compute v.
(c) Suppose that k = 29. Compute .
(d) Suppose that Bob sends the challenge r = 105. Compute Alice's response
y.
(e) Perform Bob's calculations to verify y.
6. Let E be a block cipher which produces blocks of length k using keys of length
k. Consider the following hash function. The message m which is to be hashed
is divided into a sequence m1, m2, . . . , mn of blocks, each of length k. For the
sake of simplicity, the length of m is supposed to be a multiple of k. The hash
hn of m is computed in the following way:
* h0 = IV (initialization vector)
* hi = Emi
(hi-1)
Let h and m be any hash value and any message, respectively. Propose an
attack which extends m with two more blocks in such a way that h is a hash
value of the resulting message. The number of decryptions and encryptions of
a single block performed by your attack should be O(2k
).