x931prime.c

来自「IBE是一种非对称密码技术」· C语言 代码 · 共 340 行

/* Copyright 2005-2006, Voltage Security, all rights reserved.
 */

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

int VoltGeneratePrimeX931 (
   unsigned int primeSizeBits,
   VtRandomObject random,
   VoltSurrenderCtx *surrCtx,
   unsigned int surrFlag,
   unsigned int *callNumber,
   VoltMpInt *relativePrime,
   VoltMpInt *prime
   )
{
  int status, cmpResult;
  unsigned int bufferSize, getBit, isPrime, relPrime, callNum;
  VoltMpIntCtx *mpCtx = (VoltMpIntCtx *)(prime->mpCtx);
  VoltLibCtx *libCtx = (VoltLibCtx *)(mpCtx->voltObject.libraryCtx);
  VoltMpInt *Xp = (VoltMpInt *)0;
  VoltMpInt *Yi = (VoltMpInt *)0;
  VoltMpInt *p1 = (VoltMpInt *)0;
  VoltMpInt *p2 = (VoltMpInt *)0;
  VoltMpInt *Rp = (VoltMpInt *)0;
  VoltMpInt *inverse = (VoltMpInt *)0;
  VoltMpInt *p1p2 = (VoltMpInt *)0;
  unsigned char *buffer = (unsigned char *)0;
  VOLT_DECLARE_ERROR_TYPE (errorType)
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  callNum = 1;
  if (callNumber != (unsigned int *)0)
    callNum = *callNumber;

  do
  {
    /* The only acceptable toolkit/X9.31 key lengths are 1024 and 2048.
     * That means the only acceptable prime lengths are 512 and 1024.
     */
    VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = VT_ERROR_INVALID_KEY_LENGTH;
    if ( (primeSizeBits != 512) && (primeSizeBits != 1024) )
      break;

    /* Build a buffer to hold the random starting point.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    bufferSize = primeSizeBits / 8;
    status = VT_ERROR_MEMORY;
    buffer = (unsigned char *)Z2Malloc (bufferSize, VOLT_MEMORY_SENSITIVE);
    if (buffer == (unsigned char *)0)
      break;

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

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

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

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

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

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

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

    do
    {
      /* Generate a random starting point for the actual prime. This is
       * Xp.
       * The number has to be >= sqrt(2) * 2^(bitLen-1). If the first
       * byte is >= 0xB6, it will be.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = VtGenerateRandomBytes (random, buffer, 1);
      if (status != 0)
        break;

      if (buffer[0] >= 0xB6)
        break;

    } while (1);

    VOLT_SET_FNCT_LINE (fnctLine)
    status = VtGenerateRandomBytes (random, buffer + 1, bufferSize - 1);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->OctetStringToMpInt (0, buffer, bufferSize, Xp);
    if (status != 0)
      break;

    callNum++;
    VOLT_CALL_SURRENDER (surrCtx, surrFlag, 0, callNum)

    /* Generate two prime factors. They must be at least 101 bits
     * long, but no more than 120 bits. We'll make them 101 bits to
     * pass FIPS alg tests.
     * The standard calls for 27 iterations of the Rabin-Miller test.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = VoltGeneratePrimeRabinMiller (
      101, 1, 1, 27, random, surrCtx, surrFlag, &callNum, relativePrime, p1);
    if (status != 0)
      break;

    callNum++;
    VOLT_CALL_SURRENDER (surrCtx, surrFlag, 0, callNum)

    VOLT_SET_FNCT_LINE (fnctLine)
    status = VoltGeneratePrimeRabinMiller (
      101, 1, 1, 27, random, surrCtx, surrFlag, &callNum, relativePrime, p2);
    if (status != 0)
      break;

    /* We may need p1 * p2 for computing Rp, and we will definitely
     * need it for computing Yi, so we might as well compute it now.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Multiply (p1, p2, p1p2);
    if (status != 0)
      break;

    /* Compute Rp = (p2^-1 mod p1)p2 - (p1^-1 mod p2)p1
     * If Rp < 0, then Rp += p1p2
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->ModInvert (p2, p1, inverse);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Multiply (p2, inverse, Rp);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->ModInvert (p1, p2, inverse);
    if (status != 0)
      break;

    /* Use Yi as a temp variable.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Multiply (p1, inverse, Yi);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Compare (Rp, Yi, &cmpResult);
    if (status != 0)
      break;

    if (cmpResult < 0)
    {
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->Add (p1p2, Rp, Rp);
      if (status != 0)
        break;
    }

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Subtract (Rp, Yi, Rp);
    if (status != 0)
      break;

    /* Compute Y0 = Xp + (Rp - Xp mod p1p2)
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->ModReduce (Xp, p1p2, Yi);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Compare (Rp, Yi, &cmpResult);
    if (status != 0)
      break;

    if (cmpResult < 0)
    {
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->Add (p1p2, Rp, Rp);
      if (status != 0)
        break;
    }

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Subtract (Rp, Yi, Rp);
    if (status != 0)
      break;

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

    /* Y0 is a number for which p1 is a factor of Y0 - 1 and p2 is a
     * factor of Y0 + 1. We'll check to see if it's prime. If so, we
     * found our prime. If not, we'll need to find another Y such
     * that p1 and p2 are appropriate factors of Y - 1 and Y + 1.
     * Y0 + p1p2 will be such a number.
     * We want to make sure every number we test is odd. Because p1
     * and p2 are odd, p1p2 is odd. If Y0 is even, Y0 + p1p2 will be
     * odd.
     * If Y0 is not prime, then we're going to add p1p2 to Y0 to get
     * our next candidate. But adding odd to odd will produce even.
     * We'll need to add p1p2 again. So after we get our first odd Y,
     * each time we want to increment, increment by 2 * p1p2.
     */

    /* If Y0 is even, add p1p2.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->GetBit (prime, 0, &getBit);
    if (status != 0)
      break;

    if (getBit == 0)
    {
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->Add (p1p2, prime, prime);
      if (status != 0)
        break;
    }

    /* Find 2 * p1p2.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Add (p1p2, p1p2, p1p2);
    if (status != 0)
      break;

    do
    {
      /* Make sure the candidate is relatively prime with the
       * relativePrime value.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = VoltCheckRelativePrime (
        mpCtx, relativePrime, prime, Rp, Xp, &relPrime);
      if (status != 0)
        break;

      /* If not zero, the prime candidate is relatively prime with the
       * relativePrime value, continue.
       */
      if (relPrime != 0)
      {
        callNum++;
        VOLT_CALL_SURRENDER (surrCtx, surrFlag, 0, callNum)

        /* Test the current Y for primality using Rabin-Miller with 8
         * iterations, then test using Lucas.
         */
        VOLT_SET_FNCT_LINE (fnctLine)
        status = VoltRabinMillerTest (
          prime, primeSizeBits, 8, random, &isPrime);
        if (status != 0)
          break;

        /* If Rabin-Miller says it's prime, run the Lucas test.
         */
        if (isPrime != 0)
        {
          VOLT_SET_FNCT_LINE (fnctLine)
          status = VoltLucasTest (prime, &isPrime);
          if (status != 0)
            break;

          /* If Lucas says it's prime, we're done.
           */
          if (isPrime != 0)
            break;
        }
      }

      /* Not prime (or not relatively prime), add 2 * p1p2.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->Add (p1p2, prime, prime);
      if (status != 0)
        break;

    } while (1);

  } while (0);

  if (callNumber != (unsigned int *)0)
    *callNumber = callNum;

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

  mpCtx->DestroyMpInt (&p1);
  mpCtx->DestroyMpInt (&p2);
  mpCtx->DestroyMpInt (&Rp);
  mpCtx->DestroyMpInt (&Xp);
  mpCtx->DestroyMpInt (&Yi);
  mpCtx->DestroyMpInt (&p1p2);
  mpCtx->DestroyMpInt (&inverse);

  VOLT_LOG_ERROR_INFO_COMPARE (
    status, 0, mpCtx, status, 0, errorType,
    (char *)0, "VoltGeneratePrimeX931", fnctLine, (char *)0)

  return (status);
}