rabinmiller.c

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

  /* Init the isPrime return to not prime, change it if it passes the
   * tests.
   */
  *isPrime = 0;

  do
  {
    /* Create a buffer big enough to hold the random values we'll
     * generate as part of the test.
     * The random values must be < the prime candidate. So set the
     * length in bytes to be primeSizeBits / 8. If the bit size is a
     * multiple of 8, the buffer size will be the same byte size as the
     * prime. If the bit size is not a multiple of 8, then the buffer
     * size will be one byte shorter than the byte size of the prime.
     * If the byte size is smaller, then the random value we generate
     * will be smaller. If the byte size is the same, then the random
     * value we generate might be bigger than the prime. If the byte
     * size is the same, that means the bit length is a multiple of 8
     * which means the most significant bit of the most significant
     * byte of the prime is set. So if we clear the most significant
     * bit of the most significant byte of the random value, it will be
     * < the prime.
     */
    VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = VT_ERROR_MEMORY;
    bufferSize = primeSizeBits / 8;
    buffer = (unsigned char *)Z2Malloc (bufferSize, VOLT_MEMORY_SENSITIVE);
    if (buffer == (unsigned char *)0)
      break;

    /* The Rabin-Miller test starts out by representing the prime
     * candidate as
     *    candidate = 1 + (mVal * 2^expo)
     * This is what's going on.
     *    Find candidate - 1, this is an even number (candidate is odd)
     *    How many trailing 0's are there in the binary representation
     *      of candidate - 1. That's expo.
     *    Shift candidate right expo bits, that's now mVal.
     */
    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->CreateMpInt ((Pointer)mpCtx, &mVal);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->MpIntToMpInt (primeCandidate, mVal);
    if (status != 0)
      break;

    /* Find primeCandidate - 1. We'll use it for comparison purposes
     * later.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->CreateMpInt ((Pointer)mpCtx, &candidateMinusOne);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->MpIntToMpInt (primeCandidate, candidateMinusOne);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->SetBit (candidateMinusOne, 0, 0);
    if (status != 0)
      break;

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

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

    /* Find the number of trailing 0's. After subtracting 1, the 0'th
     * bit is 0, so start looking at bit position 1. Use index as a
     * temp variable.
     */
    for (expo = 1; expo < primeSizeBits; ++expo)
    {
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->GetBit (mVal, expo, &index);
      if (status != 0)
        break;
      if (index == 1)
        break;
    }

    VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)
    VOLT_SET_FNCT_LINE (fnctLine)
    if (expo >= primeSizeBits)
      status = VT_ERROR_MP_INT_RANGE;
    if (status != 0)
      break;

    /* Step 2, find expo and mVal, we have expo, but the MpInt mVal is
     * currently equal to candidate. Shift it right expo bits and we
     * have mVal.
     */
    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->ShiftRightBits (mVal, expo);
    if (status != 0)
      break;

    /* Perform the Rabin-Miller algorithm the prescribed number of
     * times.
     */
    for (index = 0; index < VOLT_RABIN_MILLER_COUNT; ++index)
    {
      /* Step 3, get a random number < candidate.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = VtGenerateRandomBytes (random, buffer, bufferSize);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      buffer[0] &= 0x7f;
      status = mpCtx->OctetStringToMpInt (0, buffer, bufferSize, randVal);
      if (status != 0)
        break;

      /* Step 4, find zVal = (randVal ^ mVal) mod candidate
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->ModExp (randVal, mVal, primeCandidate, zVal);
      if (status != 0)
        break;

      /* Step 5, if zVal == 1, the test passes this iteration.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->MpIntToInt (zVal, 1, &value);
      if (status != VT_ERROR_MP_INT_RANGE)
      {
        if (status != 0)
          break;

        if (value == 1)
          continue;
      }
      else
      {
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Compare (zVal, candidateMinusOne, &compareResult);
        if (status != 0)
          break;

        if (compareResult == 0)
          continue;
      }

      /* Step 6, square zVal, make a comparison (step 5), then loop.
       */
      for (count = 1; count < expo; ++count)
      {
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Square (zVal, randVal);
        if (status != 0)
          break;

        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->ModReduce (randVal, primeCandidate, zVal);
        if (status != 0)
          break;

        /* Step 5 comparison, if zVal now == candidate - 1, this
         * iteration passes, move on to the next random number.
         * We had earlier set the MpInt primeCandidate to actually
         * contain primeCandidate - 1.
         */
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Compare (zVal, candidateMinusOne, &compareResult);
        if (status != 0)
          break;

        if (compareResult == 0)
          break;

        /* If zVal is now 1, we know the candidate is not prime.
         */
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->MpIntToInt (zVal, 1,&value);
        if (status != VT_ERROR_MP_INT_RANGE)
        {
          if (status != 0)
            break;

          /* Set expo to count to skip the rest of the zVal^2 tests, we
           * know the number is not prime.
           */
          if (value == 1)
            count = expo;
        }
        status = 0;
      }
      if (status != 0)
        break;

      /* If we broke out of the step 6 loop early, the comparison was
       * equal, we can move on to the next iteration.
       * If we looped step 6 every time and found no match, this number
       * is not prime. Exit the Rabin-Miller iterations.
       */
      if (count >= expo)
        break;
    }
    if (status != 0)
      break;

    /* If we didn't break out of the loop early, we did every
     * iteration, which means the number passes.
     */
    if (index >= VOLT_RABIN_MILLER_COUNT)
      *isPrime = 1;

  } while (0);

  /* We cleared the low order bit for comparison purposes, set it back.
   */
  mpCtx->SetBit (primeCandidate, 0, 1);

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

  mpCtx->DestroyMpInt (&candidateMinusOne);
  mpCtx->DestroyMpInt (&mVal);
  mpCtx->DestroyMpInt (&zVal);
  mpCtx->DestroyMpInt (&randVal);

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

  return (status);
}

static int CheckRelativePrime (
   VoltMpIntCtx *mpCtx,
   VoltMpInt *relativePrime,
   VoltMpInt *prime,
   VoltMpInt *temp1,
   VoltMpInt *temp2,
   unsigned int *relPrime
   )
{
  int status;
  unsigned int bitLen;
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  /* Initialize to true, if they turn out not to be relatively prime,
   * we'll reset it.
   */
  *relPrime = 1;

  do
  {
    /* Find prime / relativePrime. If the remainder is 1, then p - 1
     * would not be relatively prime.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Divide (prime, relativePrime, temp1, temp2);
    if (status != 0)
      break;

    /* If the bitLen of the remainder is not 1, the remainder cannot be
     * 1, so the values are relatively prime.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->GetBitLength (temp2, &bitLen);
    if (status != 0)
      break;

    if (bitLen != 1)
      break;

    /* The bit length is 1, but there is a very slight chance that the
     * remainder is 0. That would mean prime (actually a prime
     * candidate) is a multiple of relativePrime. Even though the
     * chance is slim, we have to program for the possibility.
     * Use bitLen as a temp variable.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->GetBit (temp2, 0, &bitLen);
    if (status != 0)
      break;

    /* If the bit is 0, the remainder is 0, so p - 1 and relativePrime
     * are indeed relatively prime.
     */
    if (bitLen != 0)
      *relPrime = 0;

  } while (0);

  VOLT_LOG_ERROR_INFO_COMPARE (
    status, 0, mpCtx, status, 0, 0,
    (char *)0, "CheckRelativePrime", fnctLine, (char *)0)

  return (status);
}