nnm.nc

elliptic curve加密源代码

		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "EQ_SQR_T42: mul r13, r15 \n\t"
		  "clr r24 \n\t"
		  "lsl r0 \n\t"
		  "rol r1 \n\t"
		  "rol r24 \n\t"
		  "add r4, r0 \n\t"
		  "adc r5, r1 \n\t"
		  "adc r6, r24 \n\t"
		  "brcc EQ_SQR_T43 \n\t"
		  "adc r7, r19 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "EQ_SQR_T43: mul r14, r15 \n\t"
		  "clr r24 \n\t"
		  "lsl r0 \n\t"
		  "rol r1 \n\t"
		  "rol r24 \n\t"
		  "add r5, r0 \n\t"
		  "adc r6, r1 \n\t"
		  "adc r7, r24 \n\t"
		  "brcc EQ_SQR_T44 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "EQ_SQR_T44: ld r15, Y+ \n\t"  //load c[j*d+1]
		  "mul r12, r15 \n\t"  //t=1
		  "add r4, r0 \n\t"
		  "adc r5, r1 \n\t"
		  "adc r6, r19 \n\t"
		  "brcc EQ_SQR_T52 \n\t"
		  "adc r7, r19 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "EQ_SQR_T52: mul r13, r15 \n\t"  //t=2
		  "clr r24 \n\t"
		  "lsl r0 \n\t"
		  "rol r1 \n\t"
		  "rol r24 \n\t"
		  "add r5, r0 \n\t"
		  "adc r6, r1 \n\t"
		  "adc r7, r24 \n\t"
		  "brcc EQ_SQR_T53 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "EQ_SQR_T53: mul r14, r15 \n\t"  //t=3
		  "clr r24 \n\t"
		  "lsl r0 \n\t"
		  "rol r1 \n\t"
		  "rol r24 \n\t"
		  "add r6, r0 \n\t"
		  "adc r7, r1 \n\t"
		  "adc r8, r24 \n\t"
		  "brcc EQ_SQR_T54 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "EQ_SQR_T54: ld r15, Y+ \n\t"  //load c[j*d+2]
		  "mul r13, r15 \n\t"  //t=2
		  "add r6, r0 \n\t"
		  "adc r7, r1 \n\t"
		  "brcc EQ_SQR_T63 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "EQ_SQR_T63: mul r14, r15 \n\t"  //t=3
		  "clr r24 \n\t"
		  "lsl r0 \n\t"
		  "rol r1 \n\t"
		  "rol r24 \n\t"
		  "add r7, r0 \n\t"
		  "adc r8, r1 \n\t"
		  "adc r9, r24 \n\t"
		  "adc r10, r19 \n\t"
		  "ld r15, Y+ \n\t"  //load c[j*d+3]
		  "mul r14, r15 \n\t"  //t=3
		  "add r8, r0 \n\t"
		  "adc r9, r1 \n\t"
		  "adc r10, r19 \n\t"
		  "SQR_LOOP4_EXIT: st Z+, r2 \n\t"  //a[i*d] = r2
		  "st Z+, r3 \n\t"
		  "st Z+, r4 \n\t"
		  "st Z+, r5 \n\t"
		  "movw r2, r6 \n\t"  //can be speed up use movw
		  "movw r4, r8 \n\t"
		  "mov r6, r10 \n\t"  //can be remove
		  "clr r7 \n\t"
		  "clr r8 \n\t"
		  "clr r9 \n\t"
		  "clr r10 \n\t"
		  "mov r0, %2 \n\t"
		  "lsl r0 \n\t"
		  "cp r16, r0 \n\t"
		  "breq SQR_LOOP3_EXIT \n\t"
		  "inc r16 \n\t"
		  "jmp SQR_LOOP3 \n\t"
		  "SQR_LOOP3_EXIT: st Z+, r2 \n\t"
		  "st Z+, r3 \n\t"
		  "st Z+, r4 \n\t"
		  "st Z+, r5 \n\t"
		  "pop r29 \n\t"
		  "pop r28 \n\t"
		  "pop r1 \n\t"
		  //"pop r0 \n\t"
		  :
		  :"z"(a),"a"(b),"r"(n_d)
		  :"r0","r1","r2","r3","r4","r5","r6","r7","r8","r9","r10","r11","r12","r13","r14","r15","r16","r17","r19","r24","r25","r26","r27","r28","r29"
		  );
#endif  //end of MICA

#ifdef TELOSB  //should implement in assembly
    NN_DIGIT t[2*MAX_NN_DIGITS];
    NN_UINT bDigits, i;

    NN_AssignZero (t, 2 * digits);
  
    bDigits = NN_Digits (b, digits);
    
    for (i = 0; i < bDigits; i++)
      t[i+bDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], b, bDigits);
  
    NN_Assign (a, t, 2 * digits);
#endif  //end of TELOSB

#else

    NN_DIGIT t[2*MAX_NN_DIGITS];
    NN_UINT bDigits, i;

    NN_AssignZero (t, 2 * digits);
  
    bDigits = NN_Digits (b, digits);
    
    for (i = 0; i < bDigits; i++)
      t[i+bDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], b, bDigits);
  
    NN_Assign (a, t, 2 * digits);

#endif
  }



  /* Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
     a, b can be same
     Lengths: a[digits], b[digits].
     Requires c < NN_DIGIT_BITS.
   */
  NN_DIGIT NN_LShift (NN_DIGIT *a, NN_DIGIT *b, NN_UINT c, NN_UINT digits)
  {
    NN_DIGIT bi, carry;
    NN_UINT i, t;
  
    if (c >= NN_DIGIT_BITS)
      return (0);
  
    t = NN_DIGIT_BITS - c;

    carry = 0;

    for (i = 0; i < digits; i++) {
      bi = b[i];
      a[i] = (bi << c) | carry;
      carry = c ? (bi >> t) : 0;
    }
  
    return (carry);
  }

  /* Computes a = b div 2^c (i.e., shifts right c bits), returning carry.
     a, b can be same
     Lengths: a[digits], b[digits].
     Requires: c < NN_DIGIT_BITS.
   */
  NN_DIGIT NN_RShift (NN_DIGIT *a, NN_DIGIT *b, NN_UINT c, NN_UINT digits)
  {
    NN_DIGIT bi, carry;
    int i;
    NN_UINT t;
  
    if (c >= NN_DIGIT_BITS)
      return (0);
  
    t = NN_DIGIT_BITS - c;

    carry = 0;

    for (i = digits - 1; i >= 0; i--) {
      bi = b[i];
      a[i] = (bi >> c) | carry;
      carry = c ? (bi << t) : 0;
    }
  
    return (carry);
  }

  /* Computes a = c div d and b = c mod d.
     a, c, d can be same
     b, c, d can be same
     Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
     Assumes d > 0, cDigits < 2 * MAX_NN_DIGITS,
             dDigits < MAX_NN_DIGITS.
   */
  void NN_Div (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT cDigits, NN_DIGIT *d, NN_UINT dDigits)
  {
    NN_DIGIT ai, cc[2*MAX_NN_DIGITS+1], dd[MAX_NN_DIGITS], t;

    int i;
    int ddDigits, shift;
  
    ddDigits = NN_Digits (d, dDigits);
    if (ddDigits == 0)
      return;
  
    /* Normalize operands.
     */
    shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]);
    NN_AssignZero (cc, ddDigits);
    cc[cDigits] = NN_LShift (cc, c, shift, cDigits);
    NN_LShift (dd, d, shift, ddDigits);
    t = dd[ddDigits-1];

    if (a != NULL)
    	NN_AssignZero (a, cDigits);

    for (i = cDigits-ddDigits; i >= 0; i--) {
      /* Underestimate quotient digit and subtract.
       */
      if (t == MAX_NN_DIGIT)
        ai = cc[i+ddDigits];
      else
        NN_DigitDiv (&ai, &cc[i+ddDigits-1], t + 1);
      cc[i+ddDigits] -= NN_SubDigitMult (&cc[i], &cc[i], ai, dd, ddDigits);

      /* Correct estimate.
       */
      while (cc[i+ddDigits] || (NN_Cmp (&cc[i], dd, ddDigits) >= 0)) {
        ai++;
        cc[i+ddDigits] -= NN_Sub (&cc[i], &cc[i], dd, ddDigits);
      }
      if (a != NULL)
        a[i] = ai;
    }  
    /* Restore result.
     */
    NN_AssignZero (b, dDigits);
    NN_RShift (b, cc, shift, ddDigits);
  }

  /* Computes a = b mod c.

     Lengths: a[cDigits], b[bDigits], c[cDigits].
     Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS.
   */
  void NN_Mod (NN_DIGIT *a, NN_DIGIT *b, NN_UINT bDigits, NN_DIGIT *c, NN_UINT cDigits)
  {  
    NN_Div (NULL, a, b, bDigits, c, cDigits);
  }

  /* Computes a = b * c mod d.
     a, b, c can be same
     Lengths: a[digits], b[digits], c[digits], d[digits].
     Assumes d > 0, digits < MAX_NN_DIGITS.
   */
  void NN_ModMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_DIGIT *d, NN_UINT digits)
  {
    NN_DIGIT t[2*MAX_NN_DIGITS];
    
    //memset(t, 0, 2*MAX_NN_DIGITS*NN_DIGIT_LEN);
    t[2*MAX_NN_DIGITS-1]=0;
    t[2*MAX_NN_DIGITS-2]=0;
    NN_Mult (t, b, c, digits);
    NN_Mod (a, t, 2 * digits, d, digits);
  }

  /* Computes a = b^c mod d.

     Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
     Assumes d > 0, cDigits > 0, dDigits < MAX_NN_DIGITS.
   */
  void NN_ModExp (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT cDigits, NN_DIGIT *d, NN_UINT dDigits)
  {
    NN_DIGIT bPower[3][MAX_NN_DIGITS], ci, t[MAX_NN_DIGITS];
    int i;
    uint8_t ciBits, j, s;

    /* Store b, b^2 mod d, and b^3 mod d.
     */
    NN_Assign (bPower[0], b, dDigits);
    NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
    NN_ModMult (bPower[2], bPower[1], b, d, dDigits);
  
    NN_ASSIGN_DIGIT (t, 1, dDigits);

    cDigits = NN_Digits (c, cDigits);
    for (i = cDigits - 1; i >= 0; i--) {
      ci = c[i];
      ciBits = NN_DIGIT_BITS;
      
      /* Scan past leading zero bits of most significant digit.
       */
      if (i == (int)(cDigits - 1)) {
        while (! DIGIT_2MSB (ci)) {
          ci <<= 2;
          ciBits -= 2;
        }
      }

      for (j = 0; j < ciBits; j += 2, ci <<= 2) {
        /* Compute t = t^4 * b^s mod d, where s = two MSB's of ci.
         */
        NN_ModMult (t, t, t, d, dDigits);
        NN_ModMult (t, t, t, d, dDigits);
        if ((s = DIGIT_2MSB (ci)) != 0)
          NN_ModMult (t, t, bPower[s-1], d, dDigits);
      }
    }
  
    NN_Assign (a, t, dDigits);
  }

  /* Compute a = 1/b mod c, assuming inverse exists.
     a, b, c can be same
     Lengths: a[digits], b[digits], c[digits].
     Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
   */
  void NN_ModInv (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits)
  {
    NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
      u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
      v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
    int u1Sign;

    /* Apply extended Euclidean algorithm, modified to avoid negative
       numbers.
     */
    NN_ASSIGN_DIGIT (u1, 1, digits);
    NN_AssignZero (v1, digits);
    NN_Assign (u3, b, digits);
    NN_Assign (v3, c, digits);
    u1Sign = 1;

    while (! NN_Zero (v3, digits)) {
      NN_Div (q, t3, u3, digits, v3, digits);
      NN_Mult (w, q, v1, digits);
      NN_Add (t1, u1, w, digits);
      NN_Assign (u1, v1, digits);
      NN_Assign (v1, t1, digits);
      NN_Assign (u3, v3, digits);
      NN_Assign (v3, t3, digits);
      u1Sign = -u1Sign;
    }
  
    /* Negate result if sign is negative.
      */
    if (u1Sign < 0)
      NN_Sub (a, c, u1, digits);
    else
      NN_Assign (a, u1, digits);

  }

  /*
   * a= b/c mod d
   * algorithm in "From Euclid's GCD to Montgomery Multiplication to the Great Divide"
   * 
   *
   */
  void NN_ModDivOpt (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_DIGIT *d, NN_UINT digits)
  {
    NN_DIGIT A[MAX_NN_DIGITS], B[MAX_NN_DIGITS], U[MAX_NN_DIGITS], V[MAX_NN_DIGITS];
    int tmp_even;

    NN_Assign(A, c, digits);
    NN_Assign(B, d, digits);
    NN_Assign(U, b, digits);
    NN_AssignZero(V, digits);
    
    while ((tmp_even = NN_Cmp(A, B, digits)) != 0){
      if (NN_EVEN(A, digits)){
	NN_RShift(A, A, 1, digits);
	if (NN_EVEN(U, digits)){
	  NN_RShift(U, U, 1, digits);
	}else{
	  NN_Add(U, U, d, digits);
	  NN_RShift(U, U, 1, digits);
	}
      }else if (NN_EVEN(B, digits)){
	NN_RShift(B, B, 1, digits);
	if (NN_EVEN(V, digits)){
	  NN_RShift(V, V, 1, digits);
	}else{
	  NN_Add(V, V, d, digits);
	  NN_RShift(V, V, 1, digits);
	}
      }else if (tmp_even > 0){
	NN_Sub(A, A, B, digits);
	NN_RShift(A, A, 1, digits);
	if (NN_Cmp(U, V, digits) < 0){
	  NN_Add(U, U, d, digits);
	}
	NN_Sub(U, U, V, digits);
	if (NN_EVEN(U, digits)){
	  NN_RShift(U, U, 1, digits);
	}else{
	  NN_Add(U, U, d, digits);
	  NN_RShift(U, U, 1, digits);
	}
      }else{
	NN_Sub(B, B, A, digits);
	NN_RShift(B, B, 1, digits);
	if (NN_Cmp(V, U, digits) < 0){
	  NN_Add(V, V, d, digits);
	}
	NN_Sub(V, V, U, digits);
	if (NN_EVEN(V, digits)){
	  NN_RShift(V, V, 1, digits);
	}else{
	  NN_Add(V, V, d, digits);
	  NN_RShift(V, V, 1, digits);
	}
      }
    }

    NN_Assign(a, U, digits);
  }

  /* Computes a = gcd(b, c).
     a, b, c can be same
     Lengths: a[digits], b[digits], c[digits].
     Assumes b > c, digits < MAX_NN_DIGITS.
   */
  void NN_Gcd (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits)
  {
    NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS];

    NN_Assign (u, b, digits);
    NN_Assign (v, c, digits);

    while (! NN_Zero (v, digits)) {
      NN_Mod (t, u, digits, v, digits);
      NN_Assign (u, v, digits);
      NN_Assign (v, t, digits);
    }

    NN_Assign (a, u, digits);

  }


  /* Returns sign of a - b.

     Lengths: a[digits], b[digits].
   */
  int NN_Cmp (NN_DIGIT *a, NN_DIGIT *b, NN_UINT digits)
  {
    int i;
  
    for (i = digits - 1; i >= 0; i--) { 
      if (a[i] > b[i])
        return (1);
      /* else added by Panos Kampankis*/
      else if (a[i] < b[i])
        return (-1); 
    }

    return (0);
  }

  /* Returns nonzero iff a is zero.

     Lengths: a[digits].
   */
  int NN_Zero (NN_DIGIT *a, NN_UINT digits)
  {
    NN_UINT i;
  
    for (i = 0; i < digits; i++)
      if (a[i])
        return (0);
    
    return (1);
  }

  /* Returns the significant length of a in bits.

     Lengths: a[digits].
   */
  unsigned int NN_Bits (NN_DIGIT *a, NN_UINT digits)
  {
    if ((digits = NN_Digits (a, digits)) == 0)
      return (0);
  
    return ((digits - 1) * NN_DIGIT_BITS + NN_DigitBits (a[digits-1]));
  }

  /* Returns the significant length of a in digits.

    Lengths: a[digits].
   */
  unsigned int NN_Digits (NN_DIGIT *a, NN_UINT digits)
  {
    int i;
  
    for (i = digits - 1; i >= 0; i--)
      if (a[i])
        break;

    return (i + 1);
  }

  /* Computes a = b + c*d, where c is a digit. Returns carry.
     a, b, c can be same
     Lengths: a[digits], b[digits], d[digits].
   */
  static NN_DIGIT NN_AddDigitMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT c, NN_DIGIT *d, NN_UINT digits)
  {
    NN_DIGIT carry;
    unsigned int i;

#ifndef INLINE_ASM
    NN_DOUBLE_DIGIT t