/*
  Author:  Pate Williams (c) 1997

  Exercise 10.1
  "Compute Pd_0 and Pd_1 for the following
  authenication code, represented in matrix
  form:

  key 1 2 3 4
   1  1 1 2 3
   2  1 2 3 1
   3  2 1 3 1
   4  2 3 1 2
   5  3 2 1 3
   6  3 3 2 1

  The probability distributions on S and K are as
  follows:

  p_s(1) = p_s(4) = 1 / 6, p_s(2) = p_s(3) = 1 / 3
  p_k(1) = p_k(6) = 1 / 4, p_k(2) = p_k(3) = 1 / 8
  p_k(4) = p_k(5) = 1 / 8.

  What are the optimal impersonation and
  substitution stategies?" -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by Douglas
  R. Stinson page 325.
*/

#include <stdio.h>

int main(void)
{
  double Pd_0 = 0.0, Pd_1 = 0.0, sum;
  double payoff[5][4], p_k[7], p_s[5];
  double p[5][4], po[5][4][5][4];
  long A[7][5], a, ap, k, s, sp;

  A[1][1] = 1, A[1][2] = 1, A[1][3] = 2, A[1][4] = 3;
  A[2][1] = 1, A[2][2] = 2, A[2][3] = 3, A[2][4] = 1;
  A[3][1] = 2, A[3][2] = 1, A[3][3] = 3, A[3][4] = 1;
  A[4][1] = 2, A[4][2] = 3, A[4][3] = 1, A[4][4] = 2;
  A[5][1] = 3, A[5][2] = 2, A[5][3] = 1, A[5][4] = 3;
  A[6][1] = 3, A[6][2] = 3, A[6][3] = 2, A[6][4] = 1;
  p_s[1] = p_s[4] = 1.0 / 6.0;
  p_s[2] = p_s[3] = 1.0 / 3.0;
  p_k[1] = p_k[6] = 1.0 / 4.0;
  p_k[2] = p_k[3] = p_k[4] = p_k[5] = 1.0 / 8.0;
  printf("the authenication matrix is:\n");
  for (k = 1; k <= 6; k++) {
    printf("%ld ", k);
    for (s = 1; s <= 4; s++)
      printf("%ld ", A[k][s]);
    printf("\n");
  }
  printf("the source probabilities are:\n");
  for (s = 1; s <= 4; s++)
    printf("%7.5lf ", p_s[s]);
  printf("\nthe key probabilities are:\n");
  for (k = 1; k <= 6; k++)
    printf("%7.5lf ", p_k[k]);
  printf("\nthe payoffs are:\n");
  for (s = 1; s <= 4; s++) {
    for (a = 1; a <= 3; a++) {
      sum = 0.0;
      for (k = 1; k <= 6; k++)
        if (a == A[k][s]) sum += p_k[k];
      payoff[s][a] = sum;
      if (sum > Pd_0) Pd_0 = sum;
      printf("%7.5lf ", sum);
    }
    printf("\n");
  }
  printf("Pd_0 = %7.5lf\n", Pd_0);
  printf("the optimal impersonation strategy is:\n");
  for (s = 1; s <= 4; s++) {
    for (a = 1; a <= 3; a++)
      if (payoff[s][a] == Pd_0)
        printf("(%ld, %ld) ", s, a);
  }
  printf("\n");
  for (s = 1; s <= 4; s++) {
    for (a = 1; a <= 3; a++) {
      for (sp = 1; sp <= 4; sp++) {
        for (ap = 1; ap <= 3; ap++) {
          sum = 0.0;
          for (k = 1; k <= 6; k++)
            if (A[k][s] == a && A[k][sp] == ap)
              sum += p_k[k];
          po[s][a][sp][ap] = sum;
        }
      }
      sum = 0.0;
      for (sp = 1; sp <= 4; sp++) {
        for (ap = 1; ap <= 3; ap++)
          if (po[s][a][sp][a] > sum) sum = po[s][a][sp][ap];
      }
      p[s][a] = sum;
    }
  }
  printf("the p_s,a matrix is:\n");
  for (s = 1; s <= 4; s++) {
    for (a = 1; a <= 3; a++) {
      Pd_1 += p_s[s] * payoff[s][a] * p[s][a];
      printf("%7.5lf ", p[s][a]);
    }
    printf("\n");
  }
  printf("Pd_1 = %7.5lf\n", Pd_1);
  printf("the optimal substitution strategy is:\n");
  for (s = 1; s <= 4; s++) {
    for (a = 1; a <= 3; a++) {
      printf("(%ld, %ld) -> ", s, a);
      sum = p[s][a];
      for (sp = 1; sp <= 4; sp++)
        for (ap = 1; ap <= 3; ap++)
          if (sum == po[s][a][sp][ap])
            printf("(%ld, %ld) ", sp, ap);
      printf("\n");
    }
  }
  return 0;
}