apwrx.c

brew代码里面的一个文件

      /* subtract p*q from xy */

      for (j = 0; j <= p_mspos; j++)
      {
        tx[0] = p[j];
        WORD_mul(t,tx,q);

        /* subtract from xy, propagating borrow to msw */

        for (k = j-p_mspos+i; k < 2*N; k++)
        {
          if (t[0] > xy[k])
            /* there's a borrow */
            t[1]++;
          xy[k] -= t[0];
          if (t[1] == 0)
            break;
          t[0] = t[1];
          t[1] = 0;
        }
      }
      /* set t again for loop test */
      if (i < xy_order-1)
        t[1] = xy[i+1];
      else
        t[1] = 0;
      t[0] = xy[i];
    } /* while >= d */
  } /* for i */

  return(0);
}

/* set up the Montgomery information.  */

void InitMont(unsigned WORD *m,   /* storage for -1/p */
        unsigned WORD *p)   /* modulus */
{
  unsigned WORD x, t, u;

  /* determine m.  m is such that m*p[0] modulo 2**BITCT is -1.  Note this
     routine only works if p is odd. */

  x = p[0];
  t = 1;
  u = 2;
  while(u) 
  {
    if ((x*t) & u)
      t += u;
    u <<= 1;
  }
  
  *m = (unsigned WORD)(-(WORD)t);  /* this is to avoid compiler complaints */
}

/* Montgomery reduction */

static
void MontRedN(int N,          /* number of unsigned WORDs in p */
        unsigned WORD *xxr,   /* 2N+1 entries */
        unsigned WORD m,      /* -1/p */
        unsigned WORD *p)     /* modulus */
{
  int i,j,k;
  unsigned WORD c, t[2], tx[2];
  unsigned WORD v, w;

  tx[1] = xxr[2*N] = 0;

  for (i = 0; i < N; i++)
  {
    /* create Montgomery term v = xxr[i]*m */

    v = xxr[i]*m;

    /* add v*p to xxr */

    for (j = 0; j < N; j++)
    {
      tx[0] = p[j];
      WORD_mul(t,tx,v);

      for (k = i+j; k <= 2*N; k++)
      {
        xxr[k] += t[0];
        t[0] = t[1] + (xxr[k] < t[0]);
        t[1] = 0;

        if (t[0] == 0)
          break;
      }
    }
  }

  t[0] = xxr[2*N];  /* xxr[2*N] holds any carries off end */

  /* if no carry, compare result to p, subtract if greater than or equal */

  if (t[0] == 0)
  {
    t[0] = 1;
    for (i = N-1; i >= 0; i--)
    {
      if (p[i] != xxr[i+N])
      {
        if (p[i] > xxr[i+N])
          t[0] = 0;
        break;
      }
    } /* falls off end if equal, with t[0] set to 1 */
  }
  else
    t[0] = 2;

  /* if there was a carry off the end or else if p < xxr, subtract p */

  if (t[0])
  {
    c = 0;
    for (k = 0; k < N; k++)
    {
      w = xxr[k+N];
      v = w - c;
      c = (v > w);
      w = v - p[k];
      c += (w > v);
      xxr[k+N] = w;
    }
  }
}

/* Montgomery a**x mod p */

/*  temporary storage:

  pb:   copy of modulus, dimension Nmax
  axb:  intermediate result, dimension Nmax
  at:   temp used for multiplications, dimension 2*Nmax+1
  ap:   window elements, dimension WindowStorage*Nmax

*/

static unsigned WORD apwrxNtemp[1+((4+WindowStorage)*Nmax)];

int apwrxN(int n,       /* number of bits in p */
       unsigned WORD *a,  /* generator */
       unsigned WORD *x,  /* exponent */
       unsigned WORD *ax, /* result */
       unsigned WORD *p   /* modulus */
      )
{
  int i,j, N;
  int xsize, xisone;
  unsigned WORD mask, m;
  unsigned WORD *axb, *pb, *at, *ap;
  word sigs;  /* Mask of signals returned by rex */


  /* if p is not an odd number, return error */

  if (!(p[0] & 1))
    return(-1);

  /* compute number of unsigned WORDs in n */

  N = (n+BITCT-1)/BITCT;

  if (N > Nmax)
    return(-1);

  /* set pointers */

  axb = apwrxNtemp;
  pb = axb+N;
  at = pb+N;
  ap = at + 2*N+1;

  /* copy the modulus into the buffer; this is to ensure that all arguments
     to the assembly routines have the same segment offset. */

  memcpy(pb, p, N*sizeof(unsigned WORD));

  /* note that by making R and R2 static one could avoid repeating the init step
     for the second exponentiation of Diffie-Hellman */

  InitMont(&m, pb);

  /* compute aR = a*(2**(BITCT*N)) mod p and save in ap[0] */

  memcpy(&at[N], a, N*sizeof(unsigned WORD));
  memset(at, 0, N*sizeof(unsigned WORD));
  if (modpN(N,at,pb,2*N))
    return(-1);
  memcpy(ap, at, N*sizeof(unsigned WORD));

  /* set axb to R mod p */

  memset(at, 0, N*sizeof(unsigned WORD));
  at[N] = 1;
  if (modpN(N,at,pb,N+1))
    return(-1);
  memcpy(axb, at, N*sizeof(unsigned WORD));

  xisone = 1;

  /* set xsize as bit shift to last nonzero word of x */

  /* find leftmost nonzero word */
  for (i = N-1; i >= 0; i--)
    if (x[i] != 0)
      break;

  if (i < 0)
  /* x is zero, the answer is 1 */
  {
    memset(&ax[1], 0, (N-1)*sizeof(unsigned WORD));
    ax[0] = 1;
    return(0);
  }

  /* set xsize to number of bits in nonzero words */

  xsize = (BITCT/WindowSize)*(i+1);
  
  /* adjust to most significant nonzero bit of x[i] */
  
  mask = (unsigned WORD)WindowMask << (BITCT - WindowSize);
  while (mask != 0)
  {
    if (x[i] & mask)
      break;
    xsize--;
    mask >>= WindowSize;
  }

  /* initialize the x**n values */

  for (i = 0; i < WindowStorage/2; i++)
  {
    /* square the value at i (x**(i+1)) to produce the value at 2*i+1 */

    squareN(N, &ap[N*i], at);
    MontRedN(N, at, m, pb);
    memcpy(&ap[N*(2*i+1)], &at[N], N*sizeof(unsigned WORD));

    /* multiply the value at 0 by the value at 2*i+1 to produce
       the value at 2*i+2 */

    mulN(N, ap, &ap[N*(2*i+1)], at);
    MontRedN(N, at, m, pb);
    memcpy(&ap[N*(2*i+2)], &at[N], N*sizeof(unsigned WORD));
  }

  /* multiply by appropriate power of a for each nonzero bit of x */

  for (i = xsize-1; i >= 0; i--)
  {
    if (!xisone)
    {
      for (j = 0; j < WindowSize; j++)
      {
        squareN(N,axb,at);
        MontRedN(N,at,m,pb);
        memcpy(axb, &at[N], N*sizeof(unsigned WORD));
      }
    }

    j = (x[i/(BITCT/WindowSize)] >> WindowSize*(i%(BITCT/WindowSize))) & WindowMask;
    
    if (j)
    /* multiply ax by a**n (depending on window), result in ax */
    {
      xisone = 0;

      /* multiply axb by ap[0]**j, mod p */
      
      mulN(N, &ap[N*(j-1)], axb, at);
      MontRedN(N, at, m, pb);
      memcpy(axb, &at[N], N*sizeof(unsigned WORD));
    }

    sigs = rex_get_sigs(&dh_tcb);
    if ((sigs & DH_RPT_TIMER_SIG) != 0)
    {
       /* -----------------------------
       ** Kick watchdog and reset timer
       ** ----------------------------- */
       dog_report(DOG_DH_RPT);
       (void) rex_set_timer( &dh_rpt_timer, DOG_DH_RPT_TIME );
    }

    if ((sigs & DH_RAND_USED_SIG) != 0)
    {
       /* -----------------------------
       ** Generate random number
       ** ----------------------------- */
       MSG_MED(" RAND_USED_SIG received",0,0,0);
       (void) rex_clr_sigs( &dh_tcb, DH_RAND_USED_SIG );
       generate_rand();
    }

    if ((sigs & DH_ABORT_EXP_SIG) != 0)
    {
       /* -------------------------------
       ** Abort the processing and return
       ** ----------------------------- */
       MSG_MED(" DH_ABORT_EXP_SIG received",0,0,0);
       (void) rex_clr_sigs( &dh_tcb, DH_ABORT_EXP_SIG );
       return(0);
    }
    if ((sigs & TASK_STOP_SIG) != 0)
    {
       /* -------------------------------
       ** ACK the STOP signal and return
       ** ----------------------------- */
       MSG_MED(" TASK_STOP_SIG received",0,0,0);
       (void) rex_clr_sigs( &dh_tcb, TASK_STOP_SIG );
       (void) rex_set_sigs( &mc_tcb, MC_ACK_SIG);
       return(0);
    }
    if ((sigs & TASK_OFFLINE_SIG) != 0)
    {
       /* -------------------------------
       ** ACK the OFFLINE signal and return
       ** ----------------------------- */
       MSG_MED(" TASK_OFFLINE_SIG received",0,0,0);
       (void) rex_clr_sigs( &dh_tcb, TASK_OFFLINE_SIG );
       (void) rex_set_sigs( &mc_tcb, MC_ACK_SIG);
       return(0);
    }
  }

  /* last reduction removes R */

  memcpy(at, axb, N*sizeof(unsigned WORD));
  memset(&at[N], 0, N*sizeof(unsigned WORD));
  MontRedN(N, at, m, pb);

  /* store result in actual ax */

  memcpy(ax, &at[N], N*sizeof(unsigned WORD));

  return(0);
}
#endif /* FEATURE_DH and FEATURE_DH_EXP */