Cryptography: Theory and Practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


Exercises

10.1  Compute Pd0 and Pd1 for the following authentication code, represented in matrix form:

The probability distributions on and are as follows:

What are the optimal impersonation and substitution strategies?

10.2  We have seen a construction for an orthogonal array OA(p, p, 1) when p is prime. Prove that this OA(p, p, 1) can always be extended by one extra column to form an OA(p, p + 1, 1). Illustrate your construction in the case p = 5.
10.3  Suppose A is an OA(n1, k, λ1) on symbol set {1, …, n1} and suppose B is an OA(n2, k, λ2) on symbol set {1, …, n2}. We construct C, an OA(n1n2, k, λ1 λ2) on symbol set {1, …, n1} × {1, …, n2}, as follows: for each row r1 = (x1, …, xk) of A and for each row s1 = (y1, …, yk) of B, define a row

of C. Prove that C is indeed an OA(n1 n2, k, λ1 λ2).

10.4  Construct an orthogonal array OA(3, 13, 3).
10.5  Write a computer program to compute H(K), H(K|M) and H(K|M2) for the authentication code from Exercise 10.1. The probability distribution on sequences of two sources is as follows:

Compare the entropy bounds for Pd0 and Pd1 with the actual values you computed in Exercise 10.1.

HINT  To compute , use Bayes’ formula

We already know how to calculate . To compute , write m = (s, a) and then observe that if ek(s) = a, and otherwise.

To compute , use Bayes’ formula

can be calculated as follows: write m1 = (s1, a1) and m2 = (s2, a2). Then

(Note the similarity with the computation of p(m).) To compute , observe that and ek(s2) = a2, and , otherwise.


Previous Table of Contents Next

Copyright © CRC Press LLC