rabinmiller.c

voltage 公司提供的一个开发Ibe的工具包

/* Copyright 2003-2004, Voltage Security, all rights reserved.
 */

#include "vibecrypto.h"
#include "environment.h"
#include "base.h"
#include "libctx.h"
#include "algobj.h"
#include "mpint.h"
#include "prime.h"
#include "errorctx.h"

/* Check that prime - 1 is relatively prime with relativePrime.
 * <p>If they are relatively prime, set relPrime to 1 (true, yes), and
 * if they are not, set it to 0 (false, no).
 * <p>The caller must pass in two temp mpInts. This function will
 * change them and not restore them. By passing them, the function does
 * not need to create new ones all the time.
 *
 * @param mpCtx The MpCtx to use, both MpInts should have been built
 * using this ctx.
 * @param relativPrime The value against we're checking all prime
 * candidates.
 * @param prime The prime candidate, we'll check to see that prime - 1
 * is relatively prime with the relativePrime arg.
 * @param relPrime The address where the function will deposit the
 * result, 1 for true, 0 for false.
 * @param temp1 A temp mpInt for the function to use.
 * @param temp2 Another temp mpInt for the function to use.
 * @return an int, 0 if the function completed successfully or a
 * non-zero error code.
 */
static int VOLT_CALLING_CONV CheckRelativePrime VOLT_PROTO_LIST ((
   VoltMpIntCtx *mpCtx,
   VoltMpInt *relativePrime,
   VoltMpInt *prime,
   VoltMpInt *temp1,
   VoltMpInt *temp2,
   unsigned int *relPrime
));

int VoltGeneratePrimeRabinMiller (
   unsigned int primeSizeBits,
   unsigned int leadingBits,
   VtRandomObject random,
   VoltMpInt *relativePrime,
   VoltMpInt *prime
   )
{
  int status, count;
  unsigned int bufferSize, index, sieveSize, isPrime, relPrime;
  unsigned int bitMask, bitSet0, bitSet1, increment;
  unsigned char *buffer = (unsigned char *)0;
  unsigned char *sieve = (unsigned char *)0;
  VoltMpIntCtx *mpCtx = (VoltMpIntCtx *)(prime->mpCtx);
  VoltLibCtx *libCtx = (VoltLibCtx *)(mpCtx->voltObject.libraryCtx);
  VoltMpInt *mpIncrement = (VoltMpInt *)0;
  VoltMpInt *temp1 = (VoltMpInt *)0;
  VoltMpInt *temp2 = (VoltMpInt *)0;
  unsigned int firstPrimes[100] = FIRST_100_ODD_PRIMES;
  VOLT_DECLARE_ERROR_TYPE (errorType)
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  /* This function accepts only 1 or 2 as valid leadingBits values.
   */
  if (leadingBits != 1)
    leadingBits = 2;

  do
  {
    /*
     */
    VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = VT_ERROR_INVALID_INPUT_LENGTH;
    if (primeSizeBits <= 32)
      break;

    /* Create a buffer of the appropriate size. We'll fill it with
     * random bytes and use that as a starting point.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = VT_ERROR_MEMORY;
    bufferSize = (primeSizeBits + 7) / 8;
    buffer = (unsigned char *)Z2Malloc (bufferSize, VOLT_MEMORY_SENSITIVE);
    if (buffer == (unsigned char *)0)
      break;

    /* Create a mask for the first byte. Depending on the bit length,
     * we may want to trim some bits off the top.
     * Then make sure the msbit is set. Create a value to OR with the
     * first byte that will set the msbit.
     * Finally, create a value to OR with the second byte. If the
     * caller wants the two most significant bits set, and the bit
     * length is such that the second most significant bit appears in
     * the second byte, set that bit.
     */
    bitSet0 = primeSizeBits % 8;
    bitSet1 = 0;
    if (bitSet0 == 0)
    {
      bitSet0 = 0x80;
      if (leadingBits == 2)
        bitSet0 = 0xc0;
      bitMask = 0xff;
    }
    else if (bitSet0 == 1)
    {
      bitSet0 = 1;
      if (leadingBits == 2)
        bitSet1 = 0x80;
      bitMask = 1;
    }
    else
    {
      bitMask = 0xff >> (8 - bitSet0);
      increment = bitSet0 - leadingBits;
      bitSet0 = 1;
      if (leadingBits == 2)
        bitSet0 = 3;
      bitSet0 = (bitSet0 << increment);
    }

    /* Create a sieve buffer.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    sieveSize = VOLT_SIEVE_SIZE;
    sieve = (unsigned char *)Z2Malloc (sieveSize, VOLT_MEMORY_SENSITIVE);
    if (sieve == (unsigned char *)0)
      break;

    /* We'll need the increment as an MpInt later on.
     */
    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    if ((status = mpCtx->CreateMpInt ((Pointer)mpCtx, &mpIncrement)) != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    if ((status = mpCtx->CreateMpInt ((Pointer)mpCtx, &temp1)) != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    if ((status = mpCtx->CreateMpInt ((Pointer)mpCtx, &temp2)) != 0)
      break;

    count = 0;
    isPrime = 1;
    relPrime = 1;
    do
    {
      /* Generate random bytes of the appropriate bit length.
       */
      VOLT_SET_ERROR_TYPE (errorType, 0)
      VOLT_SET_FNCT_LINE (fnctLine)
      status = VtGenerateRandomBytes (random, buffer, bufferSize);
      if (status != 0)
        break;

      /* Make sure the msbytes are set properly.
       */
      buffer[0] &= (unsigned char)bitMask;
      buffer[0] |= (unsigned char)bitSet0;
      buffer[1] |= (unsigned char)bitSet1;

      /* Set the lsbit to guarantee it is odd.
       */
      buffer[bufferSize - 1] |= 1;

      /* Set the MpInt to this value.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->OctetStringToMpInt (0, buffer, bufferSize, prime);
      if (status != 0)
        break;

      /* Create the sieve for this candidate.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = VoltSieveCandidate (
        prime, firstPrimes, 100, sieve, sieveSize);
      if (status != 0)
        break;

      /* Now run Rabin-Miller on numbers that fell through the sieve.
       */
      increment = 0;
      for (index = 0; index < sieveSize; ++index)
      {
        if (sieve[index] != 0)
        {
          increment += 2;
          continue;
        }

        /* Add increment to prime, this is the number we want to check.
         */
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->IntToMpInt (0, increment, mpIncrement);
        if (status != 0)
          break;

        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Add (prime, mpIncrement, prime);
        if (status != 0)
          break;

        if (relativePrime != (VoltMpInt *)0)
        {
          VOLT_SET_FNCT_LINE (fnctLine)
          status = CheckRelativePrime (
            mpCtx, relativePrime, prime, temp1, temp2, &relPrime);
          if (status != 0)
            break;
        }

        /* If TRUE (non zero), the two numbers pass the relative
         * prime test, continue. If FALSE (zero) the two numbers fail
         * the test, move on.
         */
        if (relPrime != 0)
        {
          VOLT_SET_FNCT_LINE (fnctLine)
          status = VoltRabinMillerTest (prime, primeSizeBits, random, &isPrime);
          if (status != 0)
            break;

          /* If this came back prime, we're done.
           */
          if (isPrime != 0)
            break;
        }

        /* Reset increment.
         */
        increment = 2;
      }
      if (status != 0)
        break;

      if (isPrime != 0)
        break;

      /* The Rabin-Miller test indicates that none of the numbers that
       * fell through the sieve were prime, get a new random starting
       * point. But first, don't run this test forever.  Try up to 100
       * times. Actually, it will almost certainly pass eventually,
       * but put the count in there just to be safe.
       */
      VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)
      VOLT_SET_FNCT_LINE (fnctLine)
      status = VT_ERROR_NO_PRIME_FOUND;
      count++;
      if (count > 100)
        break;

    } while (1);

  } while (0);

  if (buffer != (unsigned char *)0)
    Z2Free (buffer);

  if (sieve != (unsigned char *)0)
    Z2Free (sieve);

  mpCtx->DestroyMpInt (&mpIncrement);
  mpCtx->DestroyMpInt (&temp1);
  mpCtx->DestroyMpInt (&temp2);

  VOLT_LOG_ERROR_COMPARE (
    status, (VtLibCtx)libCtx, status, errorType, fnctLine,
    "VoltGeneratePrimeRabinMiller", (char *)0)

  return (status);
}

/* The Rabin-Miller algorithm as described in FIPS 186-2.
 * Step 1. Set i = 1 and n >= 50.
 * Step 2. Set w = the integer to be tested,
 *             w = 1 + (2^a)m, where m is odd and 2^a is the largest
 *             power of 2 dividing w - 1.
 * Step 3. Generate a random integer b in the range 1 < b < w.
 * Step 4. Set j = 0 and z = b^m mod w.
 * Step 5. If j = 0 and z = 1, or if z = w - 1, go to step 9.
 * Step 6. If j > 0 and z = 1, go to step 8.
 * Step 7. j = j + 1. If j < a, set z = z^2 mod w and go to step 5.
 * Step 8. w is not prime. Stop.
 * Step 9. If i < n, set i = i + 1 and go to step 3. Otherwise,
 *         w is probably prime.
 */
int VoltRabinMillerTest (
   VoltMpInt *primeCandidate,
   unsigned int primeSizeBits,
   VtRandomObject random,
   unsigned int *isPrime
   )
{
  int status, compareResult;
  unsigned int index, count, expo, bufferSize, value;
  unsigned char *buffer = (unsigned char *)0;
  VoltMpIntCtx *mpCtx = (VoltMpIntCtx *)(primeCandidate->mpCtx);
  VoltLibCtx *libCtx = (VoltLibCtx *)(mpCtx->voltObject.libraryCtx);
  VoltMpInt *candidateMinusOne = (VoltMpInt *)0;
  VoltMpInt *mVal = (VoltMpInt *)0;
  VoltMpInt *zVal = (VoltMpInt *)0;
  VoltMpInt *randVal = (VoltMpInt *)0;
  VOLT_DECLARE_ERROR_TYPE (errorType)
  VOLT_DECLARE_FNCT_LINE (fnctLine)