Pollard's rho algorithm for computing discrete logs.

[u/mdw/catacomb] / fipstest.c

/* -*-c-*-
 *
 * $Id: fipstest.c,v 1.2 2000/06/17 12:21:39 mdw Exp $
 *
 * FIPS 140-1 randomness tests
 *
 * (c) 2000 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: fipstest.c,v $
 * Revision 1.2  2000/06/17 12:21:39  mdw
 * Add braces to shut compiler up.  Reformat code slightly.
 *
 * Revision 1.1  2000/06/17 10:55:38  mdw
 * FIPS 140-1 random generator test.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <mLib/bits.h>

#include "fipstest.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @monobit@ --- *
 *
 * Arguments:	@const octet *p@ = pointer to buffer
 *
 * Returns:	Zero if OK, @FIPSTEST_MONOBIT@ on failure.
 *
 * Use:		Performs the monobit test on a buffer of data.  If %$n_1$% is
 *		the number of 1 bits in the buffer, then the monobit test is
 *		passed when %$9654 < n_1 < 10346$%.
 */

static unsigned monobit(const octet *p)
{
  unsigned n1 = 0;
  unsigned i, j;

  for (i = 0; i < FIPSTEST_BUFSZ; i++) {
    octet x = p[i];
    for (j = 0; j < 8; j++) {
      if (x & 1)
	n1++;
      x >>= 1;
    }
  }

  if (9654 >= n1 || n1 >= 10346)
    return (FIPSTEST_MONOBIT);
  return (0);
}

/* --- @poker@ --- *
 *
 * Arguments:	@const octet *p@ = pointer to buffer
 *
 * Returns:	Zero if OK, @FIPSTEST_POKER@ on failure.
 *
 * Use:		Performs the poker test on a buffer of data.  The buffer is
 *		divided into 4-bit nibbles %$x_i$%.  If
 *		%$f(x) = \sum_{x_i = x} 1$% is the frequency of each nibble,
 *		then the test is passed if
 *		%$1.03 < 16/5000 \sum_i f(i)^2 - 5000 < 57.4$%.
 */

static unsigned poker(const octet *p)
{
  unsigned long f[16] = { 0 };
  unsigned i;
  unsigned long q = 0;

  /* --- Compute the frequencies --- */

  for (i = 0; i < FIPSTEST_BUFSZ; i++) {
    octet x = p[i];
    f[x & 0xf]++;
    f[(x >> 4) & 0xf]++;
  }

  /* --- Now do the comparison --- *
   *
   * This can be simplified.  Multiply through the inequality by 5000 and
   * we get %$5150 < 16 \sum_i f(i)^2 - 5000^2 < 287000$%.
   */

  for (i = 0; i < 16; i++)
    q += f[i] * f[i];
  q <<= 4;
  q -= 5000 * 5000;

  if (5150 >= q || q >= 287000)
    return (FIPSTEST_POKER);
  return (0);
}

/* --- @runs@ --- *
 *
 * Arguments:	@const octet *p@ = pointer to buffer
 *
 * Returns:	Zero for success, @FIPSTEST_RUNS@ or @FIPSTEST_LONGRUNS@ on
 *		failure.
 *
 * Use:		Performs the runs and long runs tests.  The frequency of each
 *		`run', or sequence of equal bits, is counted and tested.
 */

static unsigned runs(const octet *p)
{
  unsigned rc = 0;
  unsigned i, j;
  unsigned r = 0;
  unsigned bb = 0;
  unsigned f[2][6] = { { 0 } };

  /* --- Count the run lengths --- */

  for (i = 0; i < FIPSTEST_BUFSZ; i++) {
    octet x = p[i];
    for (j = 0; j < 8; j++) {
      unsigned b = x & 1;
      x >>= 1;
      if (b == bb)
	r++;
      else {
	if (r) {
	  if (r >= 34)
	    rc |= FIPSTEST_LONGRUNS;
	  if (r > 6)
	    r = 6;
	  f[bb][r - 1]++;
	}
	r = 1;
	bb = b;
      }
    }
  }
  
  if (r >= 34)
    rc |= FIPSTEST_LONGRUNS;
  if (r > 6)
    r = 6;
  f[bb][r - 1]++;

  /* --- Check the results --- */

  if (2267 > f[0][0] || f[0][0] > 2733 || 2267 > f[1][0] || f[1][0] > 2733 ||
      1079 > f[0][1] || f[0][1] > 1421 || 1079 > f[1][1] || f[1][1] > 1421 ||
       502 > f[0][2] || f[0][2] >  748 ||  502 > f[1][2] || f[1][2] >  748 ||
       223 > f[0][3] || f[0][3] >  402 ||  223 > f[1][3] || f[1][3] >  402 ||
        90 > f[0][4] || f[0][4] >  223 ||   90 > f[1][4] || f[1][4] >  223 ||
        90 > f[0][5] || f[0][5] >  223 ||   90 > f[1][5] || f[1][5] >  223)
    rc |= FIPSTEST_RUNS;

  return (rc);      
}

/* --- @fipstest@ --- *
 *
 * Arguments:	@const octet *p@ = pointer to a buffer of @FIPSTEST_BUFSZ@
 *			bytes
 *
 * Returns:	Zero if OK, or a bitmask of failed tests.
 *
 * Use:		Performs the FIPS 140-1 randomness tests on a block of data.
 */

unsigned fipstest(const octet *p)
{
  unsigned rc = 0;
  rc |= monobit(p);
  rc |= poker(p);
  rc |= runs(p);
  return (rc);
}

/*----- That's all, folks -------------------------------------------------*/