eccm.nc

elliptic curve加密源代码

    {
      call NN.AssignZero(Z0, NUMWORDS);
      return;
    }

    // n1
    if (Z_is_one(Z1))
    {
      // n1 = 3 * P1->x^2 + param.E.a
      call NN.ModSqrOpt(n0, P1->x, param.p, param.omega, NUMWORDS);
      call NN.LShift(n1, n0, 1, NUMWORDS);
      call NN.ModSmall(n1, param.p, NUMWORDS);
      call NN.ModAdd(n0, n0, n1, param.p, NUMWORDS);
      call NN.ModAdd(n1, n0, param.E.a, param.p, NUMWORDS);
    }
    else
    {
      if (param.E.a_minus3)
      {
        //for a = -3
	// n1 = 3 * (X1 + Z1^2) * (X1 - Z1^2) = 3 * X1^2 - 3 * Z1^4
	call NN.ModSqrOpt(n1, Z1, param.p, param.omega, NUMWORDS);
	call NN.ModAdd(n0, P1->x, n1, param.p, NUMWORDS);
	call NN.ModSub(n2, P1->x, n1, param.p, NUMWORDS);
	call NN.ModMultOpt(n1, n0, n2, param.p, param.omega, NUMWORDS);
	call NN.LShift(n0, n1, 1, NUMWORDS);
	call NN.ModSmall(n0, param.p, NUMWORDS);
	call NN.ModAdd(n1, n0, n1, param.p, NUMWORDS);
      }
      else if (param.E.a_zero)
      {
	// n1 = 3 * P1->x^2
	call NN.ModSqrOpt(n0, P1->x, param.p, param.omega, NUMWORDS);
	call NN.LShift(n1, n0, 1, NUMWORDS);
	call NN.ModSmall(n1, param.p, NUMWORDS);
	call NN.ModAdd(n1, n0, n1, param.p, NUMWORDS);
      }
      else
      {
	// n1 = 3 * P1->x^2 + param.E.a * Z1^4
	call NN.ModSqrOpt(n0, P1->x, param.p, param.omega, NUMWORDS);
	call NN.LShift(n1, n0, 1, NUMWORDS);
	call NN.ModSmall(n1, param.p, NUMWORDS);
	call NN.ModAdd(n0, n0, n1, param.p, NUMWORDS);
	call NN.ModSqrOpt(n1, Z1, param.p, param.omega, NUMWORDS);
	call NN.ModSqrOpt(n1, n1, param.p, param.omega, NUMWORDS);
	call NN.ModMultOpt(n1, n1, param.E.a, param.p, param.omega, NUMWORDS);
	call NN.ModAdd(n1, n1, n0, param.p, NUMWORDS);
      }
    }

    // Z0 = 2 * P1->y * Z1
    if (Z_is_one(Z1))
    {
      call NN.Assign(n0, P1->y, NUMWORDS);
    }
    else
    {
      call NN.ModMultOpt(n0, P1->y, Z1, param.p, param.omega, NUMWORDS);
    }
    call NN.LShift(Z0, n0, 1, NUMWORDS);
    call NN.ModSmall(Z0, param.p, NUMWORDS);

    // n2 = 4 * P1->x * P1->y^2
    call NN.ModSqrOpt(n3, P1->y, param.p, param.omega, NUMWORDS);
    call NN.ModMultOpt(n2, P1->x, n3, param.p, param.omega, NUMWORDS);
    call NN.LShift(n2, n2, 2, NUMWORDS);
    call NN.ModSmall(n2, param.p, NUMWORDS);

    // P0->x = n1^2 - 2 * n2
    call NN.LShift(n0, n2, 1, NUMWORDS);
    call NN.ModSmall(n0, param.p, NUMWORDS);
    call NN.ModSqrOpt(P0->x, n1, param.p, param.omega, NUMWORDS);
    call NN.ModSub(P0->x, P0->x, n0, param.p, NUMWORDS);

    // n3 = 8 * P1->y^4
    call NN.ModSqrOpt(n0, n3, param.p, param.omega, NUMWORDS);
    call NN.LShift(n3, n0, 3, NUMWORDS);
    call NN.ModSmall(n3, param.p, NUMWORDS);

    // P0->y = n1 * (n2 - P0->x) - n3
    call NN.ModSub(n0, n2, P0->x, param.p, NUMWORDS);
    call NN.ModMultOpt(n0, n1, n0, param.p, param.omega, NUMWORDS);
    call NN.ModSub(P0->y, n0, n3, param.p, NUMWORDS);

  }

  //m repeated point doublings (Algorithm 3.23 in "Guide to ECC")
  void c_m_dbl_projective(Point * P0, NN_DIGIT *Z0, uint8_t m){
    uint8_t i;
    NN_DIGIT W[NUMWORDS];
    NN_DIGIT A[NUMWORDS];
    NN_DIGIT B[NUMWORDS];
    NN_DIGIT t1[NUMWORDS];
    NN_DIGIT y2[NUMWORDS];
    
    if (call NN.Zero(Z0, NUMWORDS)){
      return;
    }

    //P0->y = 2*P0->y
    call NN.LShift(P0->y, P0->y, 1, NUMWORDS);
    call NN.ModSmall(P0->y, param.p, NUMWORDS);
    //W = Z^4
    call NN.ModSqrOpt(W, Z0, param.p, param.omega, NUMWORDS);
    call NN.ModSqrOpt(W, W, param.p, param.omega, NUMWORDS);
    
    for (i=0; i<m; i++){
      if (param.E.a_minus3){
	//A = 3(X^2-W)
	call NN.ModSqrOpt(A, P0->x, param.p, param.omega, NUMWORDS);
	call NN.ModSub(A, A, W, param.p, NUMWORDS);
	call NN.LShift(t1, A, 1, NUMWORDS);
	call NN.ModSmall(t1, param.p, NUMWORDS);
	call NN.ModAdd(A, A, t1, param.p, NUMWORDS);
      }else if (param.E.a_zero){
	//A = 3*X^2
	call NN.ModSqrOpt(t1, P0->x, param.p, param.omega, NUMWORDS);
	call NN.LShift(A, t1, 1, NUMWORDS);
	call NN.ModSmall(A, param.p, NUMWORDS);
	call NN.ModAdd(A, A, t1, param.p, NUMWORDS);
      }else{
	//A = 3*X^2 + a*W
	call NN.ModSqrOpt(t1, P0->x, param.p, param.omega, NUMWORDS);
	call NN.LShift(A, t1, 1, NUMWORDS);
	call NN.ModSmall(A, param.p, NUMWORDS);
	call NN.ModAdd(A, A, t1, param.p, NUMWORDS);
	call NN.ModMultOpt(t1, param.E.a, W, param.p, param.omega, NUMWORDS);
	call NN.ModAdd(A, A, t1, param.p, NUMWORDS);
      }
      //B = X*Y^2
      call NN.ModSqrOpt(y2, P0->y, param.p, param.omega, NUMWORDS);
      call NN.ModMultOpt(B, P0->x, y2, param.p, param.omega, NUMWORDS);
      //X = A^2 - 2B
      call NN.ModSqrOpt(P0->x, A, param.p, param.omega, NUMWORDS);
      call NN.LShift(t1, B, 1, NUMWORDS);
      call NN.ModSmall(t1, param.p, NUMWORDS);
      call NN.ModSub(P0->x, P0->x, t1, param.p, NUMWORDS);
      //Z = Z*Y
      call NN.ModMultOpt(Z0, Z0, P0->y, param.p, param.omega, NUMWORDS);
      call NN.ModSqrOpt(y2, y2, param.p, param.omega, NUMWORDS);
      if (i < m-1){
	//W = W*Y^4
	call NN.ModMultOpt(W, W, y2, param.p, param.omega, NUMWORDS);
      }
      //Y = 2A(B-X)-Y^4
      call NN.LShift(A, A, 1, NUMWORDS);
      call NN.ModSmall(A, param.p, NUMWORDS);
      call NN.ModSub(B, B, P0->x, param.p, NUMWORDS);
      call NN.ModMultOpt(A, A, B, param.p, param.omega, NUMWORDS);
      call NN.ModSub(P0->y, A, y2, param.p, NUMWORDS);
    }
    if ((P0->y[0] % 2) == 1)
      call NN.Add(P0->y, P0->y, param.p, NUMWORDS);
    call NN.RShift(P0->y, P0->y, 1, NUMWORDS);
  }

  // precompute the array of the base point for sliding window method 
  void win_precompute(Point * baseP, Point * pointArray)
  {
    uint8_t i;
    
    call NN.Assign(pointArray[0].x, baseP->x, NUMWORDS);
    call NN.Assign(pointArray[0].y, baseP->y, NUMWORDS);
    
    for (i = 1; i < NUM_POINTS; i++)
    {
      c_add(&(pointArray[i]), &(pointArray[i-1]), baseP); 
    }
    
    for (i = 0; i < NUM_MASKS; i++)
      mask[i] = BASIC_MASK << (W_BITS*i);

  }
  
  //initialize parameters for ECC module
  command void ECC.init()
  {
    // get parameters
    call CurveParam.get_param(&param);
    
    //precompute array for base point
    win_precompute(&(param.G), pBaseArray);

  }
  
  command void ECC.get_order(NN_DIGIT * order)
  {
    call NN.Assign(order, param.r, NUMWORDS);
  }
  
  // curve routines
  // P0 = P1 + P2
  command void ECC.add(Point * P0, Point * P1, Point * P2)
  {
    c_add(P0, P1, P2);
  }

  // scalar point multiplication
  // P0 = n*P1
  // P0 and P1 can not be same pointer
  command void ECC.mul(Point * P0, Point * P1, NN_DIGIT * n)
  {
    int16_t i, tmp;
    NN_DIGIT Z0[NUMWORDS];
    NN_DIGIT Z1[NUMWORDS];

    // clear point
    p_clear(P0);
    
    //convert to Jprojective coordinate
    call NN.AssignZero(Z0, NUMWORDS);
    call NN.AssignZero(Z1, NUMWORDS);
    Z1[0] = 0x01;

    tmp = call NN.Bits(n, NUMWORDS);

    for (i = tmp-1; i >= 0; i--)
    {

      c_dbl_projective(P0, Z0, P0, Z0);

      if (b_testbit(n, i))
      {
        	
#ifdef ADD_MIX
	c_add_mix(P0, Z0, P0, Z0, P1);
#else
	c_add_projective(P0, Z0, P0, Z0, P1, Z1);
#endif
      }
    }   
    //convert back to affine coordinate
    if (!Z_is_one(Z0))
    {
      call NN.ModInv(Z1, Z0, param.p, NUMWORDS);
      call NN.ModMultOpt(Z0, Z1, Z1, param.p, param.omega, NUMWORDS);
      call NN.ModMultOpt(P0->x, P0->x, Z0, param.p, param.omega, NUMWORDS);
      call NN.ModMultOpt(Z0, Z0, Z1, param.p, param.omega, NUMWORDS);
      call NN.ModMultOpt(P0->y, P0->y, Z0, param.p, param.omega, NUMWORDS);
    }

  }

  // precompute the array of base point for sliding window method
  command void ECC.win_precompute(Point * baseP, Point * pointArray)
  {
    uint8_t i;
    
    call NN.Assign(pointArray[0].x, baseP->x, NUMWORDS);
    call NN.Assign(pointArray[0].y, baseP->y, NUMWORDS);
    
    for (i = 1; i < NUM_POINTS; i++){
      c_add(&(pointArray[i]), &(pointArray[i-1]), baseP);
    }
    
    for (i = 0; i < NUM_MASKS; i++)
      mask[i] = BASIC_MASK << (W_BITS*i);


  }

  // scalar point multiplication
  // P0 = n*basepoint
  // pointArray is array of basepoint, pointArray[0] = basepoint, pointArray[1] = 2*basepoint ...
  void win_mul(Point * P0, NN_DIGIT * n, Point * pointArray)
  {
    
    int16_t i, tmp;
    int8_t j;
    NN_DIGIT windex;
    NN_DIGIT Z0[NUMWORDS];
    NN_DIGIT Z1[NUMWORDS];
#ifndef REPEAT_DOUBLE
    int8_t k;
#endif

    p_clear(P0);
    
    //convert to Jprojective coordinate
    call NN.AssignZero(Z0, NUMWORDS);
    call NN.AssignZero(Z1, NUMWORDS);
    Z1[0] = 0x01;	
    
    tmp = call NN.Digits(n, NUMWORDS);

    for (i = tmp - 1; i >= 0; i--){ 
      for (j = NN_DIGIT_BITS/W_BITS - 1; j >= 0; j--){

#ifndef REPEAT_DOUBLE
	for (k = 0; k < W_BITS; k++){
	  c_dbl_projective(P0, Z0, P0, Z0);
	}
#else
	c_m_dbl_projective(P0, Z0, W_BITS);
#endif

        windex = mask[j] & n[i];

        if (windex)
        {

          windex = windex >> (j*W_BITS);

#ifdef ADD_MIX 
	  c_add_mix(P0, Z0, P0, Z0, &(pointArray[windex-1]));
#else
	  c_add_projective(P0, Z0, P0, Z0, &(pointArray[windex-1]), Z1);
#endif
	}
      }	
    }

       
    //convert back to affine coordinate
    if (!Z_is_one(Z0))
    {
    
      call NN.ModInv(Z1, Z0, param.p, NUMWORDS);
      call NN.ModMultOpt(Z0, Z1, Z1, param.p, param.omega, NUMWORDS);
      call NN.ModMultOpt(P0->x, P0->x, Z0, param.p, param.omega, NUMWORDS);
      call NN.ModMultOpt(Z0, Z0, Z1, param.p, param.omega, NUMWORDS);
      call NN.ModMultOpt(P0->y, P0->y, Z0, param.p, param.omega, NUMWORDS);
    }
    
  }
  
  /**
   * P0 = n * point, point is pointArray[0]
   * win_precompute must be called before win_mul
   */
  command void ECC.win_mul(Point * P0, NN_DIGIT * n, Point * pointArray)
  {
    win_mul(P0, n, pointArray);
  }
  
  /**
   * P0 = n * basepoint of curve
   * Don't need to call win_precompute before this func, cause init() has called win_precompute
   */
  command void ECC.win_mul_base(Point * P0, NN_DIGIT * n)
  {
    win_mul(P0, n, pBaseArray);
  }

  command Point * ECC.get_baseP(){
    return &(param.G);
  }

  command Params * ECC.get_param(){
    return &param;
  }

  command void ECC.add_proj(Point * P0, NN_DIGIT *Z0, Point * P1, NN_DIGIT * Z1, Point * P2, NN_DIGIT * Z2){
    return c_add_projective(P0, Z0, P1, Z1, P2, Z2);
  }

  command void ECC.dbl_proj(Point * P0, NN_DIGIT *Z0, Point * P1, NN_DIGIT * Z1){
    return c_dbl_projective(P0, Z0, P1, Z1);
  }
}