random.c

flint库 RSA算法

/******************************************************************************/
/*                                                                            */
/* Functions for arithmetic and number theory with large integers in C        */
/* Software supplement to the book "Cryptography in C and C++"                */
/* by Michael Welschenbach                                                    */
/*                                                                            */
/* Module random.c         Revision: 17.04.2005                               */
/*                                                                            */
/*  Copyright (C) 1998-2005 by Michael Welschenbach                           */
/*  Copyright (C) 2001-2005 by Springer-Verlag Berlin, Heidelberg             */
/*  Copyright (C) 2001-2005 by Apress L.P., Berkeley, CA                      */
/*  Copyright (C) 2002-2005 by Wydawnictwa MIKOM, Poland                      */
/*  Copyright (C) 2002-2005 by PHEI, P.R.China                                */
/*  Copyright (C) 2002-2005 by InfoBook, Korea                                */
/*  Copyright (C) 2002-2005 by Triumph Publishing, Russia                     */
/*                                                                            */
/*  All Rights Reserved                                                       */
/*                                                                            */
/*  The software may be used for noncommercial purposes and may be altered,   */
/*  as long as the following conditions are accepted without any              */
/*  qualification:                                                            */
/*                                                                            */
/*  (1) All changes to the sources must be identified in such a way that the  */
/*      changed software cannot be misinterpreted as the original software.   */
/*                                                                            */
/*  (2) The statements of copyright may not be removed or altered.            */
/*                                                                            */
/*  (3) The following DISCLAIMER is accepted:                                 */
/*                                                                            */
/*  DISCLAIMER:                                                               */
/*                                                                            */
/*  There is no warranty for the software contained in this distribution, to  */
/*  the extent permitted by applicable law. The copyright holders provide the */
/*  software `as is' without warranty of any kind, either expressed or        */
/*  implied, including, but not limited to, the implied warranty of fitness   */
/*  for a particular purpose. The entire risk as to the quality and           */
/*  performance of the program is with you.                                   */
/*                                                                            */
/*  In no event unless required by applicable law or agreed to in writing     */
/*  will the copyright holders, or any of the individual authors named in     */
/*  the source files, be liable to you for damages, including any general,    */
/*  special, incidental or consequential damages arising out of any use of    */
/*  the software or out of inability to use the software (including but not   */
/*  limited to any financial losses, loss of data or data being rendered      */
/*  inaccurate or losses sustained by you or by third parties as a result of  */
/*  a failure of the software to operate with any other programs), even if    */
/*  such holder or other party has been advised of the possibility of such    */
/*  damages.                                                                  */
/*                                                                            */
/******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "flint.h"
#include "random.h"

#define NO_ASSERTS 1

#ifdef FLINT_DEBUG
#undef NO_ASSERTS
#define ASSERT_LOG_AND_QUIT
#include "_assert.h"
#include "_alloc.h"
#ifdef COVERAGE
#include "utclog.h"
#endif
#endif

#ifdef NO_ASSERTS
#define Assert(a) (void)0
#endif

static void *
local_memset (void *ptr, int val, size_t len);


static int Rand64Init = 0;


/******************************************************************************/
/*                                                                            */
/*  Function:  Initialization of the linear congruential PRNG Rand64          */
/*             Do not use Rand64 for any cryptographic purposes!              */
/*  Syntax:    int InitRand64_l (char *UsrStr, int LenUsrStr,                 */
/*                                                    int AddEntropy);        */
/*  Input:     UsrStr (User supplied byte vector for initialization of        */
/*                     Rand64)                                                */
/*             LenUsrStr (Length of UsrString in byte)                        */
/*             AddEntropy (Number of additionally required entropy bytes)     */
/*  Output:    -                                                              */
/*  Returns:   Number of requested entropy bytes missing                      */
/*             0: OK                                                          */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
InitRand64_l (char *UsrStr, int LenUsrStr, int AddEntropy)
{
  int MissingEntropy;
  CLINT Seed_l;

  /* Get Required Entropy and Seed */
  MissingEntropy = GetEntropy_l (Seed_l, NULL, AddEntropy, UsrStr, LenUsrStr);

  /* Initialize internal state */
  seed64_l (Seed_l);

#ifdef FLINT_SECURE
  /* Security: Purge random variable Seed_l */
  local_memset (Seed_l, 0, sizeof (CLINT));
#endif

  /* Set Flag: PRNG is initialized */
  Rand64Init = 1;

  return MissingEntropy;
}


/************************* RipeMD-160 / SHA-1 based PRNG **********************/

/******************************************************************************/
/*                                                                            */
/*  Function:  Initialisation of the SHA-1/Ripemd-160 based Pseudorandom-     */
/*             numbergenerator (RandRMDSHA1)                                  */
/*  Syntax:    int InitRandRMDSHA1_l (STATERMDSHA1 *rstate, char *UsrStr,     */
/*                                     int LenUsrStr, int AddEntropy);        */
/*  Input:     UsrStr (User supplied byte vector for initialization of        */
/*                     RandRMDSHA1)                                           */
/*             LenUsrStr (Length of UsrString in byte)                        */
/*             AddEntropy (Number of additionally required entropy bytes)     */
/*  Output:    rstate (Initialized internal state of PRNG)                    */
/*  Returns:   Number of requested entropy bytes missing                      */
/*             0: OK                                                          */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
InitRandRMDSHA1_l (STATERMDSHA1 *rstate, char *UsrStr, int LenUsrStr, int AddEntropy)
{
  int MissingEntropy;
  /* Get Required Entropy and Seed */
  MissingEntropy = GetEntropy_l (NULL, rstate->XRMDSHA1, AddEntropy, UsrStr, LenUsrStr);

  /* Switch internal state */
  ripemd160_l (rstate->XRMDSHA1, rstate->XRMDSHA1, 20);

  /* Initialize RoundRMDSHA1 for picking single bytes out of random stream */
  rstate->RoundRMDSHA1 = 1;

  /* Set Flag: PRNG is initialized */
  rstate->RandRMDSHA1Init = 1;

  return MissingEntropy;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Switching of RandRMDSHA1 to next state, generating one         */
/*             random byte                                                    */
/*  Syntax:    UCHAR SwitchRandRMDSHA1_l (STATERMDSHA1 *rstate)               */
/*  Input:     rstate (Initialized State)                                     */
/*  Output:    rstate (Internal State)                                        */
/*  Returns:   One byte random value                                          */
/*                                                                            */
/******************************************************************************/
UCHAR __FLINT_API
SwitchRandRMDSHA1_l (STATERMDSHA1 *rstate)
{
  UCHAR rbyte;
  
  /* Generate random value */
  sha1_l (rstate->SRMDSHA1, rstate->XRMDSHA1, 20);
  rbyte = rstate->SRMDSHA1[(rstate->RoundRMDSHA1)++ & 15]; /* RoundRMDSHA1 mod 16 */

  /* Switch internal state */
  ripemd160_l (rstate->XRMDSHA1, rstate->XRMDSHA1, 20);

#ifdef FLINT_SECURE
  /* Security: Purge random variable SRMDSHA1 */
  local_memset (rstate->SRMDSHA1, 0, sizeof (rstate->SRMDSHA1));
#endif

  return rbyte;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Generation of pseudorandom number of CLINT-Type                */
/*             (Preceding Initialization by InitRandRMDSHA1() required)       */
/*  Syntax:    int RandRMDSHA1_l (STATERMDSHA1 *rstate, CLINT r_l, int l);    */
/*  Input:     rstate (Initialized state)                                     */
/*             l (Number of binary digits of random number to generated)      */
/*  Output:    r_l (Pseudorandom number)                                      */
/*             rstate (New internal state of PRNG)                            */
/*  Returns:   E_CLINT_OK if everything is OK                                 */
/*             E_CLINT_RIN if generator is not initialized                    */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
RandRMDSHA1_l (CLINT r_l, STATERMDSHA1 *rstate, int l)
{
  USHORT i, j;
  USHORT ls, lr;

  if (!rstate->RandRMDSHA1Init)
    {
      return E_CLINT_RIN;
    }

  l = MIN ((unsigned int)l, CLINTMAXBIT);
  ls = (USHORT) l >> LDBITPERDGT;
  lr = (USHORT) l & ((USHORT)BITPERDGT - 1);

  for (i = 1; i <= ls; i++)
    {
      r_l[i] = sRandRMDSHA1_l (rstate);
    }
  if (lr > 0)
    {
      r_l[++ls] = sRandRMDSHA1_l (rstate);
      j = 1U << (lr - 1);                         /* j <- 2^(lr - 1) */
      r_l[ls] = (r_l[ls] | j) & ((j << 1) - 1);   /* Bit lr set to 1, higher bits to 0 */
    }
  else
    {
      r_l[ls] |= BASEDIV2;
    }

  SETDIGITS_L (r_l, ls);
  return 0;
}


/******************************************************************************/
/*                                                                            */
/*  Function:   Purging of internat status of RandRMDSHA1                     */
/*  Syntax:     void PurgeRandRMDSHA1_l (STATERMDSHA1 *rstate);               */
/*  Input:      rstate (Initialized state)                                    */
/*  Output:     rstate (Purged internal state)                                */
/*  Returns:    -                                                             */
/*                                                                            */
/******************************************************************************/
void __FLINT_API
PurgeRandRMDSHA1_l (STATERMDSHA1 *rstate)
{
  /* Purge status of RipeMD-160/Sha-1 based PRNG */
  memset (rstate->XRMDSHA1, 0, sizeof (rstate->XRMDSHA1));
  memset (rstate->SRMDSHA1, 0, sizeof (rstate->SRMDSHA1));
  rstate->RoundRMDSHA1 = 0;

  /* Reset initialization flag */
  rstate->RandRMDSHA1Init = 0;
}


/************************* AES based PRNG with key update *********************/

static const unsigned char RandAESKey[] =
{0x0f, 0x1e, 0x2d, 0x3c, 0x4b, 0x5a, 0x69, 0x78,
 0x87, 0x96, 0xa5, 0xb4, 0xc3, 0xd2, 0xe1, 0xf0, 
 0x12, 0x23, 0x34, 0x45, 0x56, 0x78, 0x89, 0x9a,
 0xab, 0xbc, 0xcd, 0xde, 0xef, 0xf0, 0x01, 0x12};

/******************************************************************************/
/*                                                                            */
/*  Function:  Initialisation of the AES based Pseudorandom-                  */
/*             numbergenerator (RandAES)                                      */
/*  Syntax:    int InitRandRMDSHA1_l (STATEAES *rstate, char *UsrStr,         */
/*                                    int LenUsrStr, int AddEntropy);         */
/*  Input:     UsrStr (User supplied byte vector for initialization of        */
/*                     RandAES)                                               */
/*             LenUsrStr (Length of UsrString in byte)                        */
/*             AddEntropy (Number of additionally required entropy bytes)     */
/*             update (Frequency AES-key-update by XORing with output value:  */
/*                     update = 0: Never update key, fastest                  */
/*                     update = 1: Always update key, slowest, most secure    */
/*                     update = 1 < n: Update key every n'th call to RandAES  */
/*  Output:    rstate (Initialized internal state of PRNG)                    */
/*  Returns:   Number of requested entropy bytes missing                      */
/*             0: OK                                                          */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
InitRandAES_l (STATEAES *rstate, char *UsrStr, int LenUsrStr, int AddEntropy, int update)
{
  int MissingEntropy, i;
  /* Get Required Entropy and Seed */
  MissingEntropy = GetEntropy_l (NULL, rstate->XAES, AddEntropy, UsrStr, LenUsrStr);

  /* Initialize AES */
  for (i = 0; i < 32; i++)
    {