flint.c

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

                   sizeof (bits), &bits));

  return error;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Reduction modulo m                                             */
/*  Syntax:    int mod_l (CLINT dv_l, CLINT ds_l, CLINT r_l);                 */
/*  Input:     dv_l (Dividend), ds_l (Divisor)                                */
/*  Output:    r_l (Remainder of dv_l mod ds_l)                               */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
mod_l (CLINT dv_l, CLINT ds_l, CLINT r_l)
{
  CLINTD junk_l;
  int err;

  err = div_l (dv_l, ds_l, junk_l, r_l);

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

  return err;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Reduction mod 2^k                                              */
/*  Syntax:    int mod2_l (CLINT d_l, ULONG k, CLINT r_l);                    */
/*  Input:     d_l (Dividend), k (Exponent of 2^k)                            */
/*  Output:    r_l (Remainder of d_l mod 2^k)                                 */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
mod2_l (CLINT d_l, ULONG k, CLINT r_l)
{
  int i;

  cpy_l (r_l, d_l);

  if (k > CLINTMAXBIT)
    {
      return E_CLINT_OK;
    }

  i = 1 + (k >> LDBITPERDGT);

  if (i > (int)DIGITS_L (r_l))
    {
      return E_CLINT_OK;
    }

  r_l[i] &= (1U << (k & (BITPERDGT - 1UL))) - 1U;
  SETDIGITS_L (r_l, i);            /* r_l[i] = 2^(k mod BITPERDGT) - 1 */

  RMLDZRS_L (r_l);
  return E_CLINT_OK;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Modular addition                                               */
/*  Syntax:    int madd_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l);     */
/*  Input:     aa_l, bb_l, m_l (Operands)                                     */
/*  Output:    c_l (Remainder of aa_l + bb_l mod m_l)                         */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
madd_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l)
{
  CLINT a_l, b_l;
  clint tmp_l[CLINTMAXSHORT + 1];

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

  cpy_l (a_l, aa_l);
  cpy_l (b_l, bb_l);

  if (GE_L (a_l, m_l) || GE_L (b_l, m_l))
    {
      add (a_l, b_l, tmp_l);
      mod_l (tmp_l, m_l, c_l);
    }
  else
    {
      add (a_l, b_l, tmp_l);
      if (GE_L (tmp_l, m_l))
        {
          sub_l (tmp_l, m_l, tmp_l);    /* Underflow prevented */
        }
      cpy_l (c_l, tmp_l);
    }

  Assert(DIGITS_L (c_l) <= CLINTMAXDIGIT);

  /* Purging of variables */
  PURGEVARS_L ((3, sizeof (a_l), a_l,
                   sizeof (b_l), b_l,
                   sizeof (tmp_l), tmp_l));

  ISPURGED_L  ((3, sizeof (a_l), a_l,
                   sizeof (b_l), b_l,
                   sizeof (tmp_l), tmp_l));

  return E_CLINT_OK;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Modular subtraction                                            */
/*  Syntax:    int msub_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l);     */
/*  Input:     aa_l, bb_l, m_l (Operands)                                     */
/*  Output:    c_l (Remainder of aa_l - bb_l mod m_l)                         */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
msub_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l)
{
  CLINT a_l, b_l, tmp_l;

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

  cpy_l (a_l, aa_l);
  cpy_l (b_l, bb_l);

  if (GE_L (a_l, b_l))
    {
      sub (a_l, b_l, tmp_l);
      mod_l (tmp_l, m_l, c_l);
    }
  else
    {
      sub (b_l, a_l, tmp_l);       /* Sign tmp_l = -1 */
      mod_l (tmp_l, m_l, tmp_l);
      if (GTZ_L (tmp_l))
        {
          sub (m_l, tmp_l, c_l);
        }
      else
        {
          SETZERO_L (c_l);
        }
    }

  /* Purging of variables */
  PURGEVARS_L ((3, sizeof (a_l), a_l,
                   sizeof (b_l), b_l,
                   sizeof (tmp_l), tmp_l));

  ISPURGED_L  ((3, sizeof (a_l), a_l,
                   sizeof (b_l), b_l,
                   sizeof (tmp_l), tmp_l));

  return E_CLINT_OK;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Modular Multiplication                                         */
/*  Syntax:    int mmul_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l);     */
/*  Input:     aa_l, bb_l, m_l (Operands)                                     */
/*  Output:    c_l (Remainder of aa_l * bb_l mod m_l)                         */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
mmul_l (CLINT aa_l, CLINT bb_l, CLINT c_l, CLINT m_l)
{
  CLINT a_l, b_l;
  CLINTD tmp_l;

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

  cpy_l (a_l, aa_l);
  cpy_l (b_l, bb_l);

  mult (a_l, b_l, tmp_l);
  mod_l (tmp_l, m_l, c_l);

  /* Purging of variables */
  PURGEVARS_L ((3, sizeof (a_l), a_l,
                   sizeof (b_l), b_l,
                   sizeof (tmp_l), tmp_l));

  ISPURGED_L  ((3, sizeof (a_l), a_l,
                   sizeof (b_l), b_l,
                   sizeof (tmp_l), tmp_l));

  return E_CLINT_OK;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Modular squaring                                               */
/*  Syntax:    int msqr_l (CLINT aa_l, CLINT c_l, CLINT m_l);                 */
/*  Input:     aa_l, m_l (Operands)                                           */
/*  Output:    c_l (Remainder of aa_l * aa_l mod m_l)                         */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_DBZ: Division by Zero                                  */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
msqr_l (CLINT aa_l, CLINT c_l, CLINT m_l)
{
  CLINT a_l;
  CLINTD tmp_l;

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

  cpy_l (a_l, aa_l);

  sqr (a_l, tmp_l);
  mod_l (tmp_l, m_l, c_l);

  /* Purging of variables */
  PURGEVARS_L ((2, sizeof (a_l), a_l,
                   sizeof (tmp_l), tmp_l));

  ISPURGED_L  ((2, sizeof (a_l), a_l,
                   sizeof (tmp_l), tmp_l));

  return E_CLINT_OK;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Montgomery multiplication                                      */
/*  Syntax:    void mulmon_l (CLINT a_l, CLINT b_l, CLINT n_l, USHORT nprime, */
/*                                                 USHORT logB_r, CLINT p_l); */
/*  Input:     a_l, b_l (Factors)                                             */
/*             n_l (Modulus, odd, n_l > a_l, b_l)                             */
/*             nprime (-n_l^(-1) 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 of a_l * b_l * r^(-1) mod n_l)                  */
/*             with r := B^logB_r, B^(logB_r-1) <= n_l < B^logB_r)            */
/*  Returns:   -                                                              */
/*                                                                            */
/******************************************************************************/
void __FLINT_API
mulmon_l(CLINT a_l, CLINT b_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;

  mult (a_l, b_l, t_l);
  Assert (DIGITS_L (t_l) <= (1 + (CLINTMAXDIGIT << 1)));

  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++)
    {
      Assert (i < sizeof (t_l));
      t_l[i] = 0;
    }

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

  Assert (DIGITS_L (t_l) <= (CLINTMAXDIGIT << 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))
        {
          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;