flint.c

用扩展欧拉法求逆元 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, published by Apress Berkeley CA, 2001            */
/*                                                                            */
/*  Module flint.c          Revision: 14.04.2002                              */
/*                                                                            */
/*  Copyright (C) 1998-2003 by Michael Welschenbach                           */
/*  Copyright (C) 1998-2003 by Springer-Verlag Berlin, Heidelberg             */
/*  Copyright (C) 2001-2003 by Apress L.P., Berkeley, CA                      */
/*  Copyright (C) 2002-2003 by Wydawnictwa MIKOM, Poland                      */
/*  Copyright (C) 2002-2003 by PHEI, P.R.China                                */
/*  Copyright (C) 2002-2003 by InfoBook, Korea                                */
/*  Copyright (C) 2002-2003 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 removed or altered.               */
/*                                                                            */
/*  (3) The following DISCLAIMER is accepted:                                 */
/*                                                                            */
/*  DISCLAIMER:                                                               */
/*                                                                            */
/*  There is no warranty for the software contained on this CD-ROM, 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.                                                                  */
/*                                                                            */
/******************************************************************************/
/*                                                                            */
/*  Requirements:                                                             */
/*                                                                            */
/*  sizeof (ULONG)  == 4                                                      */
/*  sizeof (USHORT) == 2                                                      */
/*                                                                            */
/******************************************************************************/

#ifndef FLINT_ANSI
#define FLINT_ANSI
#endif

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

#include "flint.h"

#define NO_ASSERTS 1

#define FLINTCVMAJ  2
#define FLINTCVMIN  3

#if ((FLINTCVMIN != FLINT_VERMIN) || (FLINTCVMAJ != FLINT_VERMAJ))
#error Error: Incomaptible versions of FLINT.C and FLINT.H
#endif

#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


/* Mute wrap up error messages of PC-lint */
/*lint -esym(14,add,sub,mul,umul,sqr)   */
/*lint -esym(15,add,sub,mul,umul,sqr)   */
/*lint -esym(515,add,sub,mul,umul,sqr)  */
/*lint -esym(516,add,sub,mul,umul,sqr)  */
/*lint -esym(532,add,sub,mul,umul,sqr)  */
/*lint -esym(533,add,sub,mul,umul,sqr)  */
/*lint -esym(1066,add,sub,mul,umul,sqr) */
/*lint -esym(534,add_l,sub_l,mul_l,sqr_l,div_l,mmul_l,msub_l,dec_l,madd_l) */
/*lint -esym(534,msqr_l,mexp_l,mexp5_l,mexpk_l,mod_l,mod2_l,mexp2_l) */


/***********  Prototypes of local functions ***********************************/

/* Private register functions */
static void
destroy_reg_l (void);
static int
allocate_reg_l (void);
/* Integer square roots from ULONG values */
static ULONG
ul_iroot (unsigned long n);

#ifdef FLINT_SECURE
#define PURGEVARS_L(X) purgevars_l X
/* Function to purge variables */
static void purgevars_l (int noofvars, ...);
#ifdef FLINT_DEBUG
#define ISPURGED_L(X) Assert(ispurged_l X)
/* Function to check, whether variables have been purged */
static int ispurged_l (int noofvars, ...);
#else
#define ISPURGED_L(X) (void)0
#endif /* FLINT_DEBUG */
#else
#define PURGEVARS_L(X) (void)0
#define ISPURGED_L(X) (void)0
#endif /* FLINT_SECURE */
/******************************************************************************/

/* CLINT-Constant Values */
clint __FLINT_API_DATA
nul_l[] = {0, 0, 0, 0, 0};
clint __FLINT_API_DATA
one_l[] = {1, 1, 0, 0, 0};
clint __FLINT_API_DATA
two_l[] = {1, 2, 0, 0, 0};



/******************************************************************************/
/*                                                                            */
/*  Function:   Initialization of FLINT/C-Library                             */
/*              If the FLINT/C functions are provided as DLL                  */
/*              the function initializing the DLL, e. g. DllMain(),           */
/*              should call this function.                                    */
/*                                                                            */
/*  Syntax:     FLINTInit_l() (void);                                         */
/*  Input:      -                                                             */
/*  Output:     -                                                             */
/*  Returns:    E_CLINT_OK if everything is O.K.                              */
/*              -1 else                                                       */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
FLINTInit_l (void)
{
  int error;
  initrand64_lt();
  initrandBBS_lt();
  error = create_reg_l();

  if (!error)
    return E_CLINT_OK;
  else
    return -1;
}


/******************************************************************************/
/*                                                                            */
/*  Function:   Exit the FLINT/C-Library                                      */
/*  Syntax:     FLINTExit_l (void);                                           */
/*  Input:      -                                                             */
/*  Output:     -                                                             */
/*  Returns:    E_CLINT_OK if everything is O.K.                              */
/*              -1 else                                                       */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
FLINTExit_l (void)
{
  free_reg_l();

  return E_CLINT_OK;
}


/******************************************************************************/
/*                                                                            */
/*  Function:   Copy CLINT to CLINT                                           */
/*  Syntax:     void cpy_l (CLINT dest_l, CLINT src_l);                       */
/*  Input:      CLINT src_l                                                   */
/*  Output:     CLINT dest_l                                                  */
/*  Returns:    -                                                             */
/*                                                                            */
/******************************************************************************/
void __FLINT_API
cpy_l (CLINT dest_l, CLINT src_l)
{
  clint *lastsrc_l = MSDPTR_L (src_l);
  *dest_l = *src_l;

  while ((*lastsrc_l == 0) && (*dest_l > 0))
    {
      --lastsrc_l;
      --*dest_l;
    }

  while (src_l < lastsrc_l)
    {
      *++dest_l = *++src_l;
    }
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Swap two CLINT operands                                        */
/*  Syntax:    void fswap_l (CLINT a_l, CLINT b_l);                           */
/*  Input:     CLINT a_l, b_l                                                 */
/*  Output:    Swapped CLINT operands b_l, a_l                                */
/*  Returns:   -                                                              */
/*                                                                            */
/******************************************************************************/
void __FLINT_API
fswap_l (CLINT a_l, CLINT b_l)
{
  CLINT tmp_l;

  cpy_l (tmp_l, a_l);
  cpy_l (a_l, b_l);
  cpy_l (b_l, tmp_l);

  /* Purging of variables */
  PURGEVARS_L ((1, sizeof (tmp_l), tmp_l));
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Test whether two CLINT operands are equal                      */
/*  Syntax:    int equ_l (CLINT a_l, CLINT b_l);                              */
/*  Input:     CLINT a_l, b_l                                                 */
/*  Output:    -                                                              */
/*  Returns:   1 : a_l have b_l equal values                                  */
/*             0 : otherwise                                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
equ_l (CLINT a_l, CLINT b_l)
{
  clint *msdptra_l, *msdptrb_l;
  int la = (int)DIGITS_L (a_l);
  int lb = (int)DIGITS_L (b_l);

  if (la == 0 && lb == 0)
    {
      return 1;
    }

  while (a_l[la] == 0 && la > 0)
    {
      --la;
    }

  while (b_l[lb] == 0 && lb > 0)
    {
      --lb;
    }

  if (la == 0 && lb == 0)
    {
      return 1;
    }

  if (la != lb)
    {
      return 0;
    }

  msdptra_l = a_l + la;
  msdptrb_l = b_l + lb;

  while ((*msdptra_l == *msdptrb_l) && (msdptra_l > a_l))
    {
      msdptra_l--;
      msdptrb_l--;
    }

  /* Purging of variables */
  PURGEVARS_L ((2, sizeof (la), &la,
                   sizeof (lb), &lb));

  ISPURGED_L ((2, sizeof (la), &la,
                  sizeof (lb), &lb));

  return (msdptra_l > a_l ? 0 : 1);
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Test whether two CLINT operands are equal modulo m             */
/*  Syntax:    int mequ_l (CLINT a_l, CLINT b_l, CLINT m_l);                  */
/*  Input:     CLINT a_l, b_l (Values to compare), CLINT m_l (Modulus)        */
/*  Output:    -                                                              */
/*  Returns:   1          : a_l = b_l mod m_l                                 */
/*             0          : a_l != b_l mod m_l                                */
/*             E_CLINT_DBZ: division by 0                                     */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
mequ_l (CLINT a_l, CLINT b_l, CLINT m_l)
{
  CLINT r_l;
  int res;

  if (EQZ_L (m_l))
    {
      return E_CLINT_DBZ;          /* Division by Zero? */
    }

  msub_l (a_l, b_l, r_l, m_l);

  res = (0 == DIGITS_L (r_l))?1:0;

  /* Purging of variables */
  PURGEVARS_L ((1, sizeof (r_l), r_l));
  ISPURGED_L ((1, sizeof (r_l), r_l));

  return res;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Comparison of two CLINT operands                               */
/*  Syntax:    int cmp_l (CLINT a_l, CLINT b_l);                              */
/*  Input:     CLINT a_l, b_l (Values to compare)                             */
/*  Output:    -                                                              */
/*  Returns:   -1: a_l < b_l,                                                 */
/*              0: a_l == b_l,                                                */
/*              1: a_l > b_l                                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
cmp_l (CLINT a_l, CLINT b_l)
{
  clint *msdptra_l, *msdptrb_l;
  int la = (int)DIGITS_L (a_l);
  int lb = (int)DIGITS_L (b_l);

  if (la == 0 && lb == 0)
    {
      return 0;
    }

  while (a_l[la] == 0 && la > 0)
    {
      --la;
    }

  while (b_l[lb] == 0 && lb > 0)
    {
      --lb;
    }

  if (la == 0 && lb == 0)
    {
      return 0;
    }

  if (la > lb)
    {
      PURGEVARS_L ((2, sizeof (la), &la,