flint.c

rsa加密算法的c++实现,此程序实现利用公钥解密

      mi = (USHORT)((ULONG)nprime * (ULONG)*tptr_l);
      for (nptr_l = LSDPTR_L (n_l), tiptr_l = tptr_l; nptr_l <= lastnptr; nptr_l++, tiptr_l++)
        {
          Assert (tiptr_l <= t_l + (CLINTMAXDIGIT << 1));
          *tiptr_l = (USHORT)(carry = (ULONG)mi * (ULONG)*nptr_l +
                     (ULONG)*tiptr_l + (ULONG)(USHORT)(carry >> BITPERDGT));
        }

      for (; ((carry >> BITPERDGT) > 0) && tiptr_l <= MSDPTR_L (t_l); tiptr_l++)
        {
          Assert (tiptr_l <= t_l + (CLINTMAXDIGIT << 1));
          *tiptr_l = (USHORT)(carry = (ULONG)*tiptr_l + (ULONG)(USHORT)(carry >> BITPERDGT));
        }

      if (((carry >> BITPERDGT) > 0) && tiptr_l > MSDPTR_L (t_l))
        {
          Assert (tiptr_l <= t_l + 1 + (CLINTMAXDIGIT << 1));
          *tiptr_l = (USHORT)(carry >> BITPERDGT);
          INCDIGITS_L (t_l);
        }
    }

  tptr_l = t_l + logB_r;
  SETDIGITS_L (tptr_l, DIGITS_L (t_l) - logB_r);

  if (GE_L (tptr_l, n_l))
    {
      sub_l (tptr_l, n_l, p_l);
    }
  else
    {
      cpy_l (p_l, tptr_l);
    }

  Assert (DIGITS_L (p_l) <= CLINTMAXDIGIT);

  /* Purging of variables */
  PURGEVARS_L ((3, sizeof (mi), &mi,
                   sizeof (carry), &carry,
                   sizeof (t_l), t_l));

  ISPURGED_L ((3,  sizeof (mi), &mi,
                   sizeof (carry), &carry,
                   sizeof (t_l), t_l));
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Inverse -n^(-1) mod B for odd n                                */
/*  Syntax:    USHORT invmon_l (CLINT n_l);                                   */
/*  Input:     n_l (Modulus)                                                  */
/*  Output:    -                                                              */
/*  Returns:   -n^(-1) mod B                                                  */
/*                                                                            */
/******************************************************************************/
USHORT __FLINT_API
invmon_l (CLINT n_l)
{
  unsigned int i;
  ULONG x = 2, y = 1;

  if (ISEVEN_L (n_l))
    {
      return (USHORT)E_CLINT_MOD;
    }

  for (i = 2; i <= BITPERDGT; i++, x <<= 1)
    {
      if (x < (((ULONG)((ULONG)(*LSDPTR_L (n_l)) * (ULONG)y)) & ((x << 1) - 1)))
        {
          y += x;
        }
    }

  return (USHORT)(x - y);
}


/******************************************************************************/

static int twotab[] =
{0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0,
 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0,
 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};


static USHORT oddtab[] =
{0, 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5, 21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1,
 33, 17, 35, 9, 37, 19, 39, 5, 41, 21, 43, 11, 45, 23, 47, 3, 49, 25, 51, 13, 53, 27, 55, 7, 57, 29, 59, 15,
 61, 31, 63, 1, 65, 33, 67, 17, 69, 35, 71, 9, 73, 37, 75, 19, 77, 39, 79, 5, 81, 41, 83, 21, 85, 43, 87, 11,
 89, 45, 91, 23, 93, 47, 95, 3, 97, 49, 99, 25, 101, 51, 103, 13, 105, 53, 107, 27, 109, 55, 111, 7, 113,
 57, 115, 29, 117, 59, 119, 15, 121, 61, 123, 31, 125, 63, 127, 1, 129, 65, 131, 33, 133, 67, 135, 17,
 137, 69, 139, 35, 141, 71, 143, 9, 145, 73, 147, 37, 149, 75, 151, 19, 153, 77, 155, 39, 157, 79, 159,
 5, 161, 81, 163, 41, 165, 83, 167, 21, 169, 85, 171, 43, 173, 87, 175, 11, 177, 89, 179, 45, 181, 91,
 183, 23, 185, 93, 187, 47, 189, 95, 191, 3, 193, 97, 195, 49, 197, 99, 199, 25, 201, 101, 203, 51, 205,
 103, 207, 13, 209, 105, 211, 53, 213, 107, 215, 27, 217, 109, 219, 55, 221, 111, 223, 7, 225, 113,
 227, 57, 229, 115, 231, 29, 233, 117, 235, 59, 237, 119, 239, 15, 241, 121, 243, 61, 245, 123, 247, 31,
 249, 125, 251, 63, 253, 127, 255};


/******************************************************************************/
/*                                                                            */
/*  Function:  Modular exponentiation                                         */
/*             Automatic application of Montgomery exponentiation mexpkm_l    */
/*             if modulus is even, else mexpk_l is used                       */
/*  Syntax:    int mexp_l (CLINT bas_l, CLINT exp_l, CLINT p_l, CLINT m_l);   */
/*  Input:     bas_l (Base), exp_l (Exponent), m_l (Modulus)                  */
/*  Output:    p_l (Remainder of bas_l^exp_l mod m_l)                         */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*                                                                            */
/******************************************************************************/
 int __FLINT_API
mexp_l (CLINT bas_l, CLINT exp_l, CLINT p_l, CLINT m_l)
{
  if (ISODD_L (m_l))              // Montgomery exponentiation possible 
    {
      return mexpkm_l (bas_l, exp_l, p_l, m_l);
    }
  else
    {
      return mexpk_l (bas_l, exp_l, p_l, m_l);
    }
}



/******************************************************************************/
/*                                                                            */
/*  Function:  Modular Exponentiation                                         */
/*             with representation of exponent to base 2^k                    */
/*  Syntax:    int mexpk_l (CLINT bas_l, CLINT exp_l, CLINT p_l, CLINT m_l);  */
/*  Input:     bas_l (Base), exp_l (Exponent), m_l (Modulus)                  */
/*  Output:    p_l (Remainder of bas_l^exp_l mod m_l)                         */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*             E_CLINT_MAL: Error with malloc()                               */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
mexpk_l (CLINT bas_l, CLINT exp_l, CLINT p_l, CLINT m_l)
{
  CLINT a_l, a2_l;
  clint e_l[CLINTMAXSHORT + 1];
  CLINTD acc_l;
  clint **aptr_l, *ptr_l = NULL;
  int noofdigits, s, t, i;
  unsigned int k, lge, bit, digit, fk, word, pow2k, k_mask;

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

  if (EQONE_L (m_l))
    {
      SETZERO_L (p_l);             /* Modulus = 1 ==> Remainder = 0 */
      return E_CLINT_OK;
    }

  cpy_l (a_l, bas_l);
  cpy_l (e_l, exp_l);

  if (DIGITS_L (e_l) == 0)
    {
      SETONE_L (p_l);

      PURGEVARS_L ((1, sizeof (a_l), a_l));
      ISPURGED_L  ((1, sizeof (a_l), a_l));

      return E_CLINT_OK;
    }

  if (DIGITS_L (a_l) == 0)
    {
      SETZERO_L (p_l);

      PURGEVARS_L ((1, sizeof (e_l), e_l));
      ISPURGED_L  ((1, sizeof (e_l), e_l));

      return E_CLINT_OK;
    }

  lge = ld_l (e_l);

  k = 8;

  while (k > 1 && ((k - 1) * (k << ((k - 1) << 1)) / ((1 << k) - k - 1)) >= lge - 1)
    {
      --k;
    }

  pow2k = 1U << k;                 /*lint !e644*/

#if defined FLINT_DEBUG && defined FLINT_VERBOSE
  printf ("ld(e) = %d, k = %ld, pow2k = %u\n", lge, k, pow2k);
#endif

  k_mask = pow2k - 1U;

  if ((aptr_l = (clint **)malloc (sizeof (clint *) * pow2k)) == NULL)
    {
      PURGEVARS_L ((2, sizeof (a_l), a_l,
                       sizeof (e_l), e_l));
      ISPURGED_L  ((2, sizeof (a_l), a_l,
                       sizeof (e_l), e_l));
      return E_CLINT_MAL;
    }

  mod_l (a_l, m_l, a_l);
  aptr_l[1] = a_l;

  if (k > 1)
    {
      if ((ptr_l = (clint *)malloc (sizeof (CLINT) * ((pow2k >> 1) - 1))) == NULL)
        {
          free (aptr_l);
          PURGEVARS_L ((2, sizeof (a_l), a_l,
                           sizeof (e_l), e_l));
          ISPURGED_L  ((2, sizeof (a_l), a_l,
                           sizeof (e_l), e_l));
          return E_CLINT_MAL;
        }
      aptr_l[2] = a2_l;
      msqr_l (a_l, aptr_l[2], m_l);

      for (aptr_l[3] = ptr_l, i = 5; i < (int)pow2k; i += 2)
        {
          aptr_l[i] = aptr_l[i - 2] + CLINTMAXSHORT;   /*lint !e661 !e662 */
        }

      for (i = 3; i < (int)pow2k; i += 2)
        {
          mmul_l (aptr_l[2], aptr_l[i - 2], aptr_l[i], m_l);
        }
    }

  *(MSDPTR_L (e_l) + 1) = 0;    /* 0 follows most significant digit of e_l */

  noofdigits = (lge - 1)/k;                                   /*lint !e713 */
  fk = noofdigits * k;              /*  >>loss of precision<< not critical */

  word = (unsigned int)(fk >> LDBITPERDGT);         /* fk div 16 */
  bit = (unsigned int)(fk & (BITPERDGT - 1UL));     /* fk mod 16 */

  switch (k)
    {
      case 1:
      case 2:
      case 4:
      case 8:
        digit = ((ULONG)(e_l[word + 1]) >> bit) & k_mask;
        break;
      default:
        digit = ((ULONG)(e_l[word + 1] | ((ULONG)e_l[word + 2]
                                 << BITPERDGT)) >> bit) & k_mask;
    }

  if (digit != 0)                  /* k-digit > 0 */
    {
      cpy_l (acc_l, aptr_l[oddtab[digit]]);

      t = twotab[digit];
      for (; t > 0; t--)
        {
          msqr_l (acc_l, acc_l, m_l);
        }
    }
  else
    {
      SETONE_L (acc_l);
    }

  for (noofdigits--, fk -= k; noofdigits >= 0; noofdigits--, fk -= k)
    {
      word = (unsigned int)(fk >> LDBITPERDGT);       /* fk div 16 */
      bit = (unsigned int)(fk & (BITPERDGT - 1UL));   /* fk mod 16 */

      switch (k)
        {
          case 1:
          case 2:
          case 4:
          case 8:
            digit = ((ULONG)(e_l[word + 1]) >> bit) & k_mask;
            break;
          default:
            digit = ((ULONG)(e_l[word + 1] | ((ULONG)e_l[word + 2]
                                     << BITPERDGT)) >> bit) & k_mask;
        }

      if (digit != 0)              /* k-digit > 0 */
        {
          t = twotab[digit];

          for (s = (int)(k - t); s > 0; s--)
            {
              msqr_l (acc_l, acc_l, m_l);
            }

          mmul_l (acc_l, aptr_l[oddtab[digit]], acc_l, m_l);

          for (; t > 0; t--)
            {
              msqr_l (acc_l, acc_l, m_l);
            }
        }
      else                         /* k-digit == 0 */
        {
          for (s = (int)k; s > 0; s--)
            {
              msqr_l (acc_l, acc_l, m_l);
            }
        }
    }

  cpy_l (p_l, acc_l);

  free (aptr_l);
  if (ptr_l != NULL)
    {

#ifdef FLINT_SECURE
      memset (ptr_l, 0, sizeof (CLINT) * ((pow2k >> 1) - 1));   /*lint !e668*/
#endif

      free (ptr_l);                /*lint !e644 */
    }

  /* Purging of variables */
  PURGEVARS_L ((12, sizeof (i), &i,
                    sizeof (noofdigits), &noofdigits,
                    sizeof (s), &s,
                    sizeof (t), &t,
                    sizeof (bit), &bit,
                    sizeof (digit), &digit,
                    sizeof (k), &k,
                    sizeof (lge), &lge,
                    sizeof (fk), &fk,
                    sizeof (word), &word,
                    sizeof (pow2k), &pow2k,
                    sizeof (k_mask), &k_mask));
  PURGEVARS_L ((4,  sizeof (a_l), a_l,
                    sizeof (a2_l), a2_l,
                    sizeof (e_l), e_l,
                    sizeof (acc_l), acc_l));

  ISPURGED_L  ((16, sizeof (i), &i,
                    sizeof (noofdigits), &noofdigits,
                    sizeof (s), &s,
                    sizeof (t), &t,
                    sizeof (bit), &bit,
                    sizeof (digit), &digit,
                    sizeof (k), &k,
                    sizeof (lge), &lge,
                    sizeof (fk), &fk,
                    sizeof (word), &word,
                    sizeof (pow2k), &pow2k,
                    sizeof (k_mask), &k_mask,
                    sizeof (a_l), a_l,
                    sizeof (a2_l), a2_l,
                    sizeof (e_l), e_l,
                    sizeof (acc_l), acc_l));

  return E_CLINT_OK;
}



/******************************************************************************/
/*                                                                            */
/*  Function:  Modular Exponentiation for odd moduli (Montgomery reduction)   */
/*  Syntax:    int mexpkm_l (CLINT bas_l, CLINT exp_l, CLINT p_l, CLINT m_l); */
/*  Input:     bas_l (Base), exp_l (Exponent), m_l (Modulus )                 */
/*  Output:    p_l (Remainder of bas_l ^ exp_l mod m_l)                       */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero