flint.c

用扩展欧拉法求逆元 rsa算法的必须组成函数模块 带对话框

      if (((carry >> BITPERDGT) > 0))
        {
          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);
  Assert (DIGITS_L (tptr_l) <= (CLINTMAXDIGIT + 1));

  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:  Montgomery squaring                                            */
/*  Syntax:    void sqrmon_l (CLINT a_l, CLINT n_l, USHORT nprime,            */
/*                                                 USHORT logB_r, CLINT p_l); */
/*  Input:     a_l (factor),  n_l (Modulus, odd)                              */
/*             nprime (n' mod B),                                             */
/*             logB_r (Integral Part of Logarithm of r to base B)             */
/*             (For an explanation of the operands cf. Chap. 6)               */
/*  Output:    p_l (Remainder a_l * a_l * r^(-1) mod n_l)                     */
/*             with r := B^logB_r, B^(logB_r-1) <= n_l < B^logB_r)            */
/*  Returns:   -                                                              */
/*                                                                            */
/******************************************************************************/
void __FLINT_API
sqrmon_l(CLINT a_l, CLINT n_l, USHORT nprime, USHORT logB_r, CLINT p_l)
{
  clint t_l[2 + (CLINTMAXDIGIT << 1)];
  clint *tptr_l, *nptr_l, *tiptr_l, *lasttnptr, *lastnptr;
  ULONG carry;
  USHORT mi;
  int i;

  sqr (a_l, t_l);

  lasttnptr = t_l + DIGITS_L (n_l);
  lastnptr = MSDPTR_L (n_l);

  for (i = (int)DIGITS_L (t_l) + 1; i <= (int)(DIGITS_L (n_l) << 1); i++)
    {
      t_l[i] = 0;
    }

  SETDIGITS_L (t_l, MAX(DIGITS_L (t_l), DIGITS_L (n_l) << 1));

  for (tptr_l = LSDPTR_L (t_l); tptr_l <= lasttnptr; tptr_l++)
    {
      carry = 0;
      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^5                    */
/*  Syntax:    int mexp5_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
mexp5_l (CLINT bas_l, CLINT exp_l, CLINT p_l, CLINT m_l)
{
  CLINT a_l;
  clint e_l[CLINTMAXSHORT + 1];
  CLINTD acc_l;
  CLINT a2_l, a3_l, a5_l, a7_l, a9_l, a11_l, a13_l, a15_l, a17_l, a19_l,
      a21_l, a23_l, a25_l, a27_l, a29_l, a31_l;
  clint *aptr_l[32];
  int i, noofdigits, s, t;
  unsigned int bit, digit, f5, word;

  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;
    }

  mod_l (a_l, m_l, a_l);

  aptr_l[1] = a_l;
  aptr_l[3] = a3_l;
  aptr_l[5] = a5_l;
  aptr_l[7] = a7_l;
  aptr_l[9] = a9_l;
  aptr_l[11] = a11_l;
  aptr_l[13] = a13_l;
  aptr_l[15] = a15_l;
  aptr_l[17] = a17_l;
  aptr_l[19] = a19_l;
  aptr_l[21] = a21_l;
  aptr_l[23] = a23_l;
  aptr_l[25] = a25_l;
  aptr_l[27] = a27_l;
  aptr_l[29] = a29_l;
  aptr_l[31] = a31_l;

  msqr_l (a_l, a2_l, m_l);
  for (i = 3; i <= 31; i += 2)
    {
      mmul_l (a2_l, aptr_l[i - 2], aptr_l[i], m_l);
    }

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

  noofdigits = (ld_l (e_l) - 1)/5;                               /*lint !e713 */
  f5 = (unsigned)(noofdigits * 5);      /* >>loss of precision<< not critical */

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

      digit = ((ULONG)(e_l[word + 1] | ((ULONG)e_l[word + 2] << BITPERDGT)) >> bit) & 0x1f;

  if (digit != 0)                  /* 5-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--, f5 -= 5; noofdigits >= 0; noofdigits--, f5 -= 5)
    {
      word = (unsigned int)f5 >> LDBITPERDGT;    /* f5 div 16 */
      bit = f5 & (BITPERDGT - 1UL);              /* f5 mod 16 */

      digit = ((ULONG)(e_l[word + 1] | ((ULONG)e_l[word + 2] << BITPERDGT)) >> bit) & 0x1f;

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

          for (s = 5 - 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                        /* 5-digit > 0 */
        {
          for (s = 5; s > 0; s--)
            {
              msqr_l (acc_l, acc_l, m_l);
            }
        }
    }

  cpy_l (p_l, acc_l);

  /* Purging of variables */
  PURGEVARS_L ((8,  sizeof (i), &i,
                    sizeof (noofdigits), &noofdigits,
                    sizeof (s), &s,
                    sizeof (t), &t,
                    sizeof (bit), &bit,
                    sizeof (digit), &digit,
                    sizeof (f5), &f5,
                    sizeof (word), &word));
  PURGEVARS_L ((19, sizeof (acc_l), acc_l,
                    sizeof (a_l), a_l,
                    sizeof (e_l), e_l,
                    sizeof (a2_l), a2_l,
                    sizeof (a3_l), a3_l,
                    sizeof (a5_l), a5_l,
                    sizeof (a7_l), a7_l,
                    sizeof (a9_l), a9_l,
                    sizeof (a11_l), a11_l,
                    sizeof (a13_l), a13_l,
                    sizeof (a15_l), a15_l,
                    sizeof (a17_l), a17_l,
                    sizeof (a19_l), a19_l,
                    sizeof (a21_l), a21_l,
                    sizeof (a23_l), a23_l,
                    sizeof (a25_l), a25_l,
                    sizeof (a27_l), a27_l,
                    sizeof (a29_l), a29_l,
                    sizeof (a31_l), a31_l));

  ISPURGED_L  ((8,  sizeof (i), &i,
                    sizeof (noofdigits), &noofdigits,
                    sizeof (s), &s,
                    sizeof (t), &t,
                    size