CSE 539

Applied Cryptography
Assignment 3

Please submit hard copy. Typed preferred.

1.

a)
A general problem relating to hash functions is the following.

Suppose a hash function H, has an output range of n values (i.e. given an input, the output is one of n numbers). Suppose H is applied to k random inputs. What must be the value of k so that the probability that there is at least one collision, that is for some two inputs, x and y,  H(y)=H(x) is 0.5?

2.

b)
Suppose the above hash function produces an m-bit output. What is the value of k that so that the probability of collision is 0.5?

3.

a) Explain the structure of a digital certificate.

b) Who can be a certification authority?

4.

Explain the various techniques used by the antivirus software for the detection of the viruses.

5.

Explain the concept of biometric encryption and the problems associated with it?

6.

What is the principle of electronic voting method? What is the future of it?

7.

Alice has an RSA-like public value n = pq. Alice’s secret is the pair of big primes p and q. Bob who knows the value n, wants to identify Alice. Consider the following identification scheme:

1. Bob sends a random challenge x to Alice;
2. Alice’s response is a square root y of x;
3. Bob verified that y2 = x mod n,

Suppose that Alice and Bob perform several rounds of the above scheme. Show that the identification scheme is flawed.