/*
  Author:  Pate Williams (c) 1997

  The following program implements and tests the
  Micali-Schnorr random bits generator. The test
  suite is according to FIPS 140-1. See "Handbook
  of Applied Cryptography" by Alfred J. Menezes
  et al Section 5.4.4 pages 181 - 183 and 5.37
  Algorithm page 186.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "lip.h"

#define BIT_STRING_LENGTH 20000l
#define MONOBIT_LO 9654l
#define MONOBIT_HI 10346l
#define POKER_LO 1.03
#define POKER_HI 57.4

void Micali_Schnorr_gen_key(long bit_length, verylong *ze,
                            verylong *zn, verylong *zx0,
                            long *k, long *r)
/* generates the key and seed for the Micali-Schnorr
   pseudorandom bits generator */
{
  long length = bit_length / 2, N;
  verylong zd = 0, zp = 0, zq = 0, zs = 0, zt = 0;
  verylong zphi = 0;

  zrstarts(time(NULL));
  zrandomprime(length, 5l, &zp, zrandomb);
  zrandomprime(length, 5l, &zq, zrandomb);
  zmul(zp, zq, zn);
  zsadd(zp, - 1l, &zs);
  zsadd(zq, - 1l, &zt);
  zmul(zs, zt, &zphi);
  N = z2log(*zn);
  zpstart();
  do {
    zintoz(zpnext(), ze);
    zgcd(*ze, zphi, &zd);
    zsmul(*ze, 80l, &zs);
  } while (zscompare(zd, 1l) != 0 && zscompare(zs, N) > 0);
  *k = N * (1.0 - 2 / (double) ztoint(*ze));
  *r = N - *k;
  zrandomprime(*r, 5l, zx0, zrandomb);
  zfree(&zd);
  zfree(&zp);
  zfree(&zq);
  zfree(&zs);
  zfree(&zt);
  zfree(&zphi);
}

void Micali_Schnorr_next_bits(long k, long r, verylong ze,
                              verylong zn, verylong *zx,
                              verylong *zz)
/* gets the next bits in the sequence */
{
  verylong zx0 = 0, zy = 0;

  zcopy(*zx, &zx0);
  zexpmod(zx0, ze, zn, &zy);
  zhighbits(zy, r, zx);
  zlowbits(zy, k, zz);
  zfree(&zx0);
  zfree(&zy);
}

int FIPS_140_1(char *bit_string)
/* Statistical tests for randomness returns - 3
   if bit_string fails monobit test, - 2 if it
   fails poker test, - 1 if it fails runs test,
   0 if it fails the long run test 1 otherwise */
{
  float X3, sum = 0.0;
  long B[6]= {0}, G[6] = {0}, n[16] = {0};
  long i, index, j, k, max_run = 0, n1 = 0;
  long interval_lo[6] = {2267, 1079, 502, 223, 90, 90};
  long interval_hi[6] = {2733, 1421, 748, 402, 223, 223};

  /* monobit test */
  for (i = 0; i < BIT_STRING_LENGTH; i++)
    if (bit_string[i] == 1) n1++;
  /* poker test */
  i = 0;
  k = BIT_STRING_LENGTH / 4;
  for (j = 0; j < k; j++) {
    index = 8 * bit_string[i + 3] + 4 * bit_string[i + 2]
          + 2 * bit_string[i + 1] + bit_string[i];
    n[index]++;
    i += 4;
  }
  for (i = 0; i < 16; i++) sum += n[i] * n[i];
  X3 = 16.0 * sum / k - k;
  /* runs test */
  i = 0;
  while (i < BIT_STRING_LENGTH) {
    j = 0;
    while (i < BIT_STRING_LENGTH && bit_string[i] == 1) i++, j++;
    if (j <= 6) B[j - 1]++; else B[5]++;
    if (j > max_run) max_run = j;
    while (i < BIT_STRING_LENGTH && bit_string[i] == 0) i++;
 }
  i = 0;
  while (i < BIT_STRING_LENGTH) {
    j = 0;
    while (i < BIT_STRING_LENGTH && bit_string[i] == 0) i++, j++;
    if (j <= 6) G[j - 1]++; else G[5]++;
    if (j > max_run) max_run = j;
    while (i < BIT_STRING_LENGTH && bit_string[i] == 1) i++;
  }
  /* print out results of the tests */
  printf("monobit statistic: %ld\n", n1);
  printf("poker test statistic: %lf\n", X3);
  printf("# blocks\tgaps\n");
  for (i = 0; i < 6; i++)
    printf("%ld %4ld\t\t%4ld\n", i + 1, B[i], G[i]);
  printf("long runs statistic: %ld\n", max_run);
  /* compute return value based on statistics */
  if (n1 <= MONOBIT_LO || n1 >= MONOBIT_HI) return - 3;
  if (X3 <= POKER_LO || X3 >= POKER_HI) return - 2;
  for (i = 0; i < 6; i++) {
    if (B[i] < interval_lo[i] || B[i] > interval_hi[i]) return - 1;
    if (G[i] < interval_lo[i] || G[i] > interval_hi[i]) return - 1;
  }
  if (max_run >= 34) return 0;
  return 1;
}

int main(void)
{
  char bit_string[BIT_STRING_LENGTH];
  long i = 0, j, k, r;
  verylong ze = 0, zn = 0, zx = 0, zy = 0, zz = 0;

  /* fill the buffer to be tested */
  Micali_Schnorr_gen_key(256l, &ze, &zn, &zx, &k, &r);
  printf("%ld %ld\n", k, r);
  zwriteln(zx);
  while (i < BIT_STRING_LENGTH) {
    Micali_Schnorr_next_bits(k, r, ze, zn, &zx, &zz);
    for (j = 0; j < k; j++) {
      zlowbits(zz, 1l, &zy);
      if (i < BIT_STRING_LENGTH)
        bit_string[i++] = (char) ztoint(zy);
      zrshift(zz, 1l, &zy);
      zcopy(zy, &zz);
    }
  }
  printf("value of FIPS_140_1 = %d\n", FIPS_140_1(bit_string));
  zfree(&ze);
  zfree(&zn);
  zfree(&zx);
  zfree(&zy);
  zfree(&zz);
  return 0;
}