/*
  Author:  Pate Williams (c) 1997

  Exercise
  "6.8 In the Bos-Chaum Scheme with k = 6 and n = 4,
  suppose that the messages x = (0, 1, 0, 0, 1, 1)
  and x' = (1, 1, 0, 1, 1, 1) are signed. Determine
  the new messages that can be signed by Oscar
  knowing the signatures of x and x'."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by Douglas
  R. Stinson page 231.
*/

#include <math.h>
#include <stdio.h>

#define SIZE 10

long factorial(long n)
/* computes n factorial = n! */
{
  long f = 1, i;

  for (i = 2; i <= n; i++) f *= i;
  return f;
}

long binomial(long n, long m)
/* computes the binomial coefficient B(n, m) */
{
  return factorial(n) / (factorial(n - m) *
                         factorial(m));
}

void Bos_Chaum(long n, long x, long *phi, long *count)
{
  long b, e = n, t = n << 1;

  *count = 0;
  while (t > 0) {
    t = t - 1;
    b = binomial(t, e);
    if (x > b) {
      x -= b;
      e--;
      phi[*count] = t + 1;
      *count = *count + 1;
    }
  }
}

long Horner(long n, long *x)
{
  long i, s = x[n - 1];

  for (i = n - 2; i >= 0; i--)
    s = 2 * s + x[i];
  return s;
}

void construct(long count, long k, long n,
               long *phi, long *x, long *X)
{
  int equal;
  long i, j, max = pow(2, k), y;
  long p_count, phip[SIZE];

  for (i = 0; i < max; i++) {
    Bos_Chaum(n, i, phip, &p_count);
    if (count == p_count) {
      equal = phi[0] == phip[0];
      for (j = 1; equal && j < count; j++)
        equal = phi[j] == phip[j];
      if (equal) {
        y = *X = i;
        for (j = 0; j < k; j++) {
          x[j] = y & 1;
          y >>= 1;
        }
        return;
      }
    }
  }
  *X = 0;
}

int main(void)
{
  long i, k = 6, n = 4, r, s;
  long u_count, v_count;
  long x_count = 3, y_count = 4;
  long u[SIZE] = {0, 1, 0, 0, 1, 1};
  long v[SIZE] = {1, 1, 0, 1, 1, 1};
  long x[SIZE], y[SIZE];
  long u_phi[SIZE], v_phi[SIZE];
  long x_phi[SIZE] = {8, 6, 4};
  long y_phi[SIZE] = {8, 7, 4, 2};

  r = Horner(k, u);
  s = Horner(k, v);
  Bos_Chaum(n, r, u_phi, &u_count);
  Bos_Chaum(n, s, v_phi, &v_count);
  printf("the original messages are:\n");
  printf("x  = %ld = ", r);
  for (i = 0; i < k; i++)
    printf("%ld ", u[i]);
  printf("\nx' = %ld = ", s);
  for (i = 0; i < k; i++)
    printf("%ld ", v[i]);
  printf("\np  = ");
  for (i = 0; i < u_count; i++)
    printf("%ld ", u_phi[i]);
  printf("\np' = ");
  for (i = 0; i < v_count; i++)
    printf("%ld ", v_phi[i]);
  construct(x_count, k, n, x_phi, x, &r);
  construct(y_count, k, n, y_phi, y, &s);
  r = Horner(k, x);
  s = Horner(k, y);
  Bos_Chaum(n, r, x_phi, &x_count);
  Bos_Chaum(n, s, y_phi, &y_count);
  printf("\nthe new messages are:\n");
  printf("x  = %ld = ", r);
  for (i = 0; i < k; i++)
    printf("%ld ", x[i]);
  printf("\nx' = %ld = ", s);
  for (i = 0; i < k; i++)
    printf("%ld ", y[i]);
  printf("\np  = ");
  for (i = 0; i < x_count; i++)
    printf("%ld ", x_phi[i]);
  printf("\np' = ");
  for (i = 0; i < y_count; i++)
    printf("%ld ", y_phi[i]);
  return 0;
}