random.c

flint库 RSA算法

        break;
      default:
        rand_l (r_l, MIN (l, (int)CLINTMAXBIT));
        error = E_CLINT_RIN;
    }

  return error;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Purging of the internal state of a chosen PRNG                 */
/*  Syntax:    int PurgeRand_l (STATEPRNG *xrstate);                          */
/*  Input:     xrstate (Choice and initialized state of PRNG)                 */
/*  Output:    xrstate (Purged internal state of PRNG)                        */
/*  Returns:   E_CLINT_OK if everything is OK                                 */
/*             E_CLINT_RNG if choice of generator in xrstate is invalid       */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
PurgeRand_l (STATEPRNG *xrstate)
{
  int error = E_CLINT_OK;

  switch (xrstate->Generator)
    {
      case FLINT_RNDBBS:
        PurgeRandBBS_l (&xrstate->StateBBS);
        break;
      case FLINT_RNDAES:
        PurgeRandAES_l (&xrstate->StateAES);
        break;
      case FLINT_RNDRMDSHA1:
        PurgeRandRMDSHA1_l (&xrstate->StateRMDSHA1);
        break;
      case FLINT_RND64:
        break;
      default:
        error = E_CLINT_RNG;
    }
 
  return error;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Generation of a pseudorandom number of type CLINT              */
/*             w/ rmin_l <= r_l <= rmax_l, using one of the FLINT/C PRNG,     */
/*             preceeding initialization required!                            */
/*  Syntax:    int RandMinMax_l (CLINT r_l, STATEPRNG *xrstate, CLINT rmin_l, */
/*                                                        CLINT rmax_l);      */
/*  Input:     xrstate (Choice and initialized state of PRNG)                 */
/*             rmin_l (lower bound for r_l)                                   */
/*             rmax_l (upper bound for r_l)                                   */
/*  Output:    r_l (pseudorandom number)                                      */
/*             xrstate (State of chosen PRNG)                                 */
/*  Returns:   E_CLINT_OK if everything is OK                                 */
/*             E_CLINT_RGE if rmin_l > rmax_l                                 */
/*             E_CLINT_RNG if choice of generator in xrstate is invalid       */
/*             E_CLINT_RIN if PRNG is not initialized                         */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
RandMinMax_l (CLINT r_l, STATEPRNG *xrstate, CLINT rmin_l, CLINT rmax_l)
{
  CLINT t_l;
  int error = E_CLINT_OK;
  USHORT l = (ld_l (rmin_l) + ld_l (rmax_l)) >> 1;

  /* Plausibility: rmin_l <= rmax_l? */
  if (GT_L (rmin_l, rmax_l))
    {
      return E_CLINT_RGE;
    }

  sub_l (rmax_l, rmin_l, t_l);
  inc_l (t_l);

  switch (xrstate->Generator)
    {
      case FLINT_RNDAES:
        error = RandAES_l (r_l, &xrstate->StateAES, MIN (l, (int)CLINTMAXBIT));
        break;
      case FLINT_RNDRMDSHA1:
        error = RandRMDSHA1_l (r_l, &xrstate->StateRMDSHA1, MIN (l, (int)CLINTMAXBIT));
        break;
      case FLINT_RNDBBS:
        error = RandBBS_l (r_l, &xrstate->StateBBS, MIN (l, (int)CLINTMAXBIT));
        break;
      case FLINT_RND64:
        rand_l (r_l, MIN (l, (int)CLINTMAXBIT));
        /*      error = rand_l (r_l, MIN (l, (int)CLINTMAXBIT)); */
        break;
      default:
        return E_CLINT_RNG;
    }

  if (E_CLINT_OK != error)
    {
      return error;
    }

  if (LT_L (r_l, rmin_l))
    {
      add_l (r_l, rmin_l, r_l);
    }

  if (GT_L (r_l, rmax_l))
    {
      mod_l (r_l, t_l, r_l);
      add_l (r_l, rmin_l, r_l);
    }

  Assert (GE_L (r_l, rmin_l) && LE_L (r_l, rmax_l));

#ifdef FLINT_SECURE
  /* Purging of variables */
  local_memset (t_l, 0, sizeof (t_l));
  local_memset (&l, 0, sizeof (l));
#endif

  return error;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Generation of a random prime p_l of type CLINT                 */
/*             w/ 2^(l-1) <= p_l < 2^l, using one of the FLINT/C PRNG,        */
/*             preceeding initialization required!                            */
/*  Syntax:    int FindPrime_l (CLINT p_l, STATEPRNG *xrstate, USHORT l);     */
/*  Input:     xrstate (Choice and initialized state of PRNG)                 */
/*             l (number of binary digits of p_l)                             */
/*  Output:    p_l (random prime, determined with probabilistic MR-Test)      */
/*             xrstate (State of chosen PRNG)                                 */
/*  Returns:   E_CLINT_OK if everything is OK                                 */
/*             E_CLINT_RGE if l = 0                                           */
/*             E_CLINT_RNG if choice of generator in xrstate is invalid       */
/*             E_CLINT_RIN if PRNG is not initialized                         */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
FindPrime_l (CLINT p_l, STATEPRNG *xrstate, USHORT l)
{
  return (FindPrimeGcd_l (p_l, xrstate, l, one_l));
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Generation of a random prime p_l of type CLINT                 */
/*             w/ 2^(l-1) <= p_l < 2^l and ggT (p_l - 1, f_l) = 1, using one  */
/*             of the FLINT/C PRNG, preceeding initialization required!       */
/*  Syntax:    int FindPrimeGcd_l (CLINT p_l, STATEPRNG *xrstate, USHORT l,   */
/*                                                         CLINT f_l);        */
/*  Input:     xrstate (Choice and initialized state of PRNG)                 */
/*             l (number of binary digits of p_l)                             */
/*             f_l (number coprime to p_l - 1)                                */
/*  Output:    p_l (random prime, determined with probabilistic MR-Test)      */
/*             xrstate (State of chosen PRNG)                                 */
/*  Returns:   E_CLINT_OK if everything is OK                                 */
/*             E_CLINT_RGE if l = 0 or f_l is even                            */
/*             E_CLINT_RNG if choice of generator in xrstate is invalid       */
/*             E_CLINT_RIN if PRNG is not initialized                         */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
FindPrimeGcd_l (CLINT p_l, STATEPRNG *xrstate, USHORT l, CLINT f_l)
{
  CLINT rmin_l;
  clint rmax_l[CLINTMAXSHORT + 1];
  int error;
  if (0 == l)
    {
      return E_CLINT_RGE;
    }

  SETZERO_L (rmin_l);
  SETZERO_L (rmax_l);
  setbit_l (rmin_l, l - 1);
  setbit_l (rmax_l, l);
  dec_l (rmax_l);
  error = FindPrimeMinMaxGcd_l (p_l, xrstate, rmin_l, rmax_l, f_l);

#ifdef FLINT_SECURE
  /* Purging of variables */
  local_memset (rmin_l, 0, sizeof (rmin_l));
  local_memset (rmax_l, 0, sizeof (rmax_l));
#endif

  return error;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Generation of a random prime p_l of type CLINT                 */
/*             w/ rmin_l <= p_l <= rmax_l und ggT (p_l - 1, f_l) = 1, using   */
/*             one of the FLINT/C PRNG, preceeding initialization required!   */
/*  Syntax:    int FindPrimeMinMaxGcd_l (CLINT p_l, STATEPRNG *xrstate,       */
/*                                    CLINT rmin_l, CLINT rmax_l, CLINT f_l); */
/*  Input:     xrstate (Choice and initialized state of PRNG)                 */
/*             rmin_l (lower bound for p_l)                                   */
/*             rmax_l (upper bound for p_l)                                   */
/*             f_l (number coprime to p_l - 1)                                */
/*  Output:    p_l (random prime, determined with probabilistic MR-Test)      */
/*             xrstate (State of chosen PRNG)                                 */
/*  Returns:   E_CLINT_OK if everything is OK                                 */
/*             E_CLINT_RGE if rmin_l > rmax_l or f_l is even or prime that    */
/*                         meets the conditions can not be found              */
/*             E_CLINT_RNG if choice of generator in xrstate is invalid       */
/*             E_CLINT_RIN if PRNG is not initialized                         */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
FindPrimeMinMaxGcd_l (CLINT p_l, STATEPRNG *xrstate, CLINT rmin_l, 
                                                     CLINT rmax_l, CLINT f_l)
{
  CLINT t_l, rmin1_l, g_l;
  CLINT Pi_rmin_l, Pi_rmax_l, NoofCandidates_l, junk_l;
  int error;

  /* 0 < f_l has to be uneven */
  if (ISEVEN_L (f_l))
    {
      return E_CLINT_RGE;
    }

  udiv_l (rmin_l, (USHORT)ld_l (rmin_l), Pi_rmin_l, junk_l);
  udiv_l (rmax_l, (USHORT)ld_l (rmax_l), Pi_rmax_l, junk_l);
  sub_l (Pi_rmax_l, Pi_rmin_l, NoofCandidates_l);

  /* rmin_l <- ceil ((rmin_l - 1)/2) */
  dec_l (rmin_l);
  div_l (rmin_l, two_l, rmin_l, junk_l);
  if (GTZ_L (junk_l))
    {
      inc_l (rmin_l);
    }  

  /* rmax_l <- floor ((rmax_l - 1)/2) */
  dec_l (rmax_l);
  shr_l (rmax_l);

  do
    {
      /* Test if estimated number of candidates is counted back to zero */
      if (EQZ_L (NoofCandidates_l))
	{
          return (E_CLINT_RGE);
	}

      if (E_CLINT_OK != (error = RandMinMax_l (p_l, xrstate, rmin_l, rmax_l)))
        {
          return error;
        }

      /* p_l <- 2*p_l + 1 hence p_l is odd */
      shl_l (p_l);
      inc_l (p_l);

      cpy_l (rmin1_l, p_l);
      dec_l (rmin1_l);
      gcd_l (rmin1_l, f_l, g_l);

      dec_l (NoofCandidates_l);
    }
  while (!(EQONE_L (g_l) && ISPRIME_L (p_l)));


#ifdef FLINT_SECURE
  /* Purging of variables */
  local_memset (t_l, 0, sizeof (t_l));
  local_memset (rmin1_l, 0, sizeof (rmin1_l));
  local_memset (g_l, 0, sizeof (g_l));
#endif

  return error;
}


/******************************************************************************/
/*                                                                            */
/* Local memset-Function, does the same as memset()                           */
/* Needed to make compiler purge variables in spite of optimization.          */
/*                                                                            */
/******************************************************************************/
static void *
local_memset (void *ptr, int val, size_t len)
{
    return memset (ptr, val, len);
}