IV054 Coding, Cryptography and Cryptographic Protocols
2008 ­ Exercises VI.
1. Assume that the ciphertext c = (512, 303) was obtained using the ElGamal
cryptosystem with the following parameters: p = 941, q = 2, x = 14 and r = 9.
Find the plaintext.
2. Consider probability distributions p0, p1 over {0, 1}n
where n  N. Let A be
a polynomial time algorithm with inputs from {0, 1}n
and outputs from {0, 1}
which has the property
Pr(A(p0) = 1) - Pr(A(p1) = 1)  ,
where > 0 and A(pi) denotes the result of a computation of A for an input
chosen according to the distribution pi. Alice and Bob decided to play the
following game:
(a) Alice chooses randomly and uniformly a bit b  {0, 1}.
(b) Alice chooses a string x according to the distribution pb and sends it to
Bob.
(c) Bob returns a bit b  {0, 1}.
(d) Bob wins if b = b .
Suppose that Bob is able to use the algorithm A. Show that he can win with
probability greater than 1
2
.
3. Suppose that an adversary Eve can solve the Diffie-Hellman problem (i.e. given
x
and y
she can compute xy
(modulo p)). Show that Eve can then easily
break the ElGamal encryption scheme.
4. Let n  N and s  {0, 1}n
. Let further G : {0, 1}n
 {0, 1}m
be a pseudorandom
generator and  : {0, 1}×{0, 1}  {0, 1}. Finally, let n be an extension
of  to bit strings of length n obtained by applying  bitwise.
Consider the encryption scheme with P = C = {0, 1}m
and K = {0, 1}n
.
The encryption e of a message p using a secret key k is defined as e(p, k) =
G(k) m p.
(a) Suppose that  is the  operation. Decide whether this encryption scheme
is secure against a chosen plaintext attack. Explain your reasoning.
(b) Is there any other function  : {0, 1} × {0, 1}  {0, 1} which can be used
as ? What is its necessary property?
5. Assume that the Shanks' algorithm is used to compute
log5 71 (mod 167).
Show the computation steps.
6. Consider a prime p and an integer 1 < a < p - 1.
(a) Suppose that there is n such that n2
 a (mod p). Show that a is not a
primitive root (mod p).
(b) Suppose that there is no n such that n2
 a (mod p) and that p-1
2
is a
prime. Show that a is a primitive root (mod p).
7. Let f(n) = 1
(2n
n )
and g(n) = 1
(n+42
n )
. Decide which of these functions is negligible.