nnm.nc

elliptic curve加密源代码

/**
 * All new code in this distribution is Copyright 2005 by North Carolina
 * State University. All rights reserved. Redistribution and use in
 * source and binary forms are permitted provided that this entire
 * copyright notice is duplicated in all such copies, and that any
 * documentation, announcements, and other materials related to such
 * distribution and use acknowledge that the software was developed at
 * North Carolina State University, Raleigh, NC. No charge may be made
 * for copies, derivations, or distributions of this material without the
 * express written consent of the copyright holder. Neither the name of
 * the University nor the name of the author may be used to endorse or
 * promote products derived from this material without specific prior
 * written permission.
 *
 * IN NO EVENT SHALL THE NORTH CAROLINA STATE UNIVERSITY BE LIABLE TO ANY
 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION,
 * EVEN IF THE NORTH CAROLINA STATE UNIVERSITY HAS BEEN ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN
 * "AS IS" BASIS, AND THE NORTH CAROLINA STATE UNIVERSITY HAS NO
 * OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
 * MODIFICATIONS. "
 *
 */


/**
 * module NNM, provide interface NN
 * modified from nn.h and nn.c from RSAREF 2.0
 * 
 * Implement several well known optimized algorithms for ECC operations
 * such as: ModAdd, ModSub, ModMultOpt, ModSqrOpt
 *
 * Author: An Liu
 * Date: 09/29/2006
 */

includes NN;

#define MODINVOPT

#define MAX(a,b) ((a) < (b) ? (b) : (a))
#define DIGIT_MSB(x) (NN_DIGIT)(((x) >> (NN_DIGIT_BITS - 1)) & 1)
#define DIGIT_2MSB(x) (NN_DIGIT)(((x) >> (NN_DIGIT_BITS - 2)) & 3)

#define NN_ASSIGN_DIGIT(a, b, digits) {NN_AssignZero (a, digits); a[0] = b;}
#define NN_EQUAL(a, b, digits) (! NN_Cmp (a, b, digits))
#define NN_EVEN(a, digits) (((digits) == 0) || ! (a[0] & 1))

module NNM {
  provides interface NN;
  uses interface CurveParam;
}

implementation
{
/*
   CONVERSIONS
   NN_Decode (a, digits, b, len)   Decodes character string b into a.
   NN_Encode (a, len, b, digits)   Encodes a into character string b.

   ASSIGNMENTS
   NN_Assign (a, b, digits)        Assigns a = b.
   NN_ASSIGN_DIGIT (a, b, digits)  Assigns a = b, where b is a digit.
   NN_AssignZero (a, digits)    Assigns a = 0.
   NN_Assign2Exp (a, b, digits)    Assigns a = 2^b.
     
   ARITHMETIC OPERATIONS
   NN_Add (a, b, c, digits)        Computes a = b + c.
   NN_Sub (a, b, c, digits)        Computes a = b - c.
   NN_Mult (a, b, c, digits)       Computes a = b * c.
   NN_LShift (a, b, c, digits)     Computes a = b * 2^c.
   NN_RShift (a, b, c, digits)     Computes a = b / 2^c.
   NN_Div (a, b, c, cDigits, d, dDigits)  Computes a = c div d and b = c mod d.

   NUMBER THEORY
   NN_Mod (a, b, bDigits, c, cDigits)  Computes a = b mod c.
   NN_ModMult (a, b, c, d, digits) Computes a = b * c mod d.
   NN_ModExp (a, b, c, cDigits, d, dDigits)  Computes a = b^c mod d.
   NN_ModInv (a, b, c, digits)     Computes a = 1/b mod c.
   NN_Gcd (a, b, c, digits)        Computes a = gcd (b, c).

   OTHER OPERATIONS
   NN_EVEN (a, digits)             Returns 1 iff a is even.
   NN_Cmp (a, b, digits)           Returns sign of a - b.
   NN_EQUAL (a, digits)            Returns 1 iff a = b.
   NN_Zero (a, digits)             Returns 1 iff a = 0.
   NN_Digits (a, digits)           Returns significant length of a in digits.
   NN_Bits (a, digits)             Returns significant length of a in bits.
*/

               void  NN_DigitDiv (NN_DIGIT *a, NN_DIGIT b[2], NN_DIGIT c);
               void  NN_Decode (NN_DIGIT *a, NN_UINT digits, unsigned char *b, NN_UINT len);
               void  NN_Encode (unsigned char *a, NN_UINT len, NN_DIGIT *b, NN_UINT digits);
               void  NN_Assign (NN_DIGIT *a, NN_DIGIT *b, NN_UINT digits);
               void  NN_AssignZero (NN_DIGIT *a, NN_UINT digits);
               void  NN_Assign2Exp (NN_DIGIT *a, NN_UINT2 b, NN_UINT digits);
           NN_DIGIT  NN_Add (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits);
           NN_DIGIT  NN_Sub (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits);
               void  NN_Mult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits);
           NN_DIGIT  NN_LShift (NN_DIGIT *a, NN_DIGIT *b, NN_UINT c, NN_UINT digits);
           NN_DIGIT  NN_RShift (NN_DIGIT *a, NN_DIGIT *b, NN_UINT c, NN_UINT digits);
               void  NN_Div (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT cDigits, NN_DIGIT *d, NN_UINT dDigits);
               void  NN_Mod (NN_DIGIT *a, NN_DIGIT *b, NN_UINT bDigits, NN_DIGIT *c, NN_UINT cDigits);
               void  NN_ModMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_DIGIT *d, NN_UINT digits);
               void  NN_ModExp (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT cDigits, NN_DIGIT *d, NN_UINT dDigits);
               void  NN_ModInv (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits);
               void  NN_Gcd (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits);
                int  NN_Cmp (NN_DIGIT *a, NN_DIGIT *b, NN_UINT digits);
                int  NN_Zero (NN_DIGIT *a, NN_UINT digits);
       unsigned int  NN_Bits (NN_DIGIT *a, NN_UINT digits);
       unsigned int  NN_Digits (NN_DIGIT *a, NN_UINT digits);
    static NN_DIGIT  NN_AddDigitMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT c, NN_DIGIT *d, NN_UINT digits);
    static NN_DIGIT  NN_SubDigitMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT c, NN_DIGIT *d, NN_UINT digits);
static unsigned int  NN_DigitBits (NN_DIGIT a);
   


/* Return b * c, where b and c are NN_DIGITs. The result is a NN_DOUBLE_DIGIT
  */

#ifdef MICA
#define NN_DigitMult(b, c) (NN_DOUBLE_DIGIT)(b) * (c)
#endif

#ifdef TELOSB
#ifdef INLINE_ASM
     
  NN_DOUBLE_DIGIT NN_DigitMult(NN_DIGIT b, NN_DIGIT c)
  {
    NN_DIGIT result_h;
    NN_DIGIT result_l;
            
    asm volatile ("mov %2, &0x130 \n\t"
                  "mov %3, &0x138 \n\t"
                  "mov &0x13C, %0 \n\t"
                  "mov &0x13A, %1 \n\t"
                  :"=r"(result_h), "=r"(result_l)
                  :"r"(b), "r"(c)
                  );

    return (((NN_DOUBLE_DIGIT)result_h << 16) ^ (NN_DOUBLE_DIGIT)result_l);
  }
  
#else
  #define NN_DigitMult(b, c) (NN_DOUBLE_DIGIT)(b) * (c)
#endif
#endif

#ifdef IMOTE2
#define NN_DigitMult(b, c) (NN_DOUBLE_DIGIT)(b) * (c)
#endif

  
  /* Sets a = b / c, where a and c are digits.

     Lengths: b[2].
     Assumes b[1] < c and HIGH_HALF (c) > 0. For efficiency, c should be
     normalized.
     from digit.c
  */
  void NN_DigitDiv (NN_DIGIT *a, NN_DIGIT b[2], NN_DIGIT c)
  {
    NN_DOUBLE_DIGIT t;
  
    t = (((NN_DOUBLE_DIGIT)b[1]) << NN_DIGIT_BITS) ^ ((NN_DOUBLE_DIGIT)b[0]);
  
    *a = t/c;
  }

  /* Decodes character string b into a, where character string is ordered
     from most to least significant.

    Lengths: a[digits], b[len].
     Assumes b[i] = 0 for i < len - digits * NN_DIGIT_LEN. (Otherwise most
     significant bytes are truncated.)
  */
  void NN_Decode (NN_DIGIT *a, NN_UINT digits, unsigned char *b, NN_UINT len)
  {
    NN_DIGIT t;
    int j;
    unsigned int i, u;
  
    for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
      t = 0;
      for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
        t |= ((NN_DIGIT)b[j]) << u;
      a[i] = t;
    }
  
    for (; i < digits; i++)
      a[i] = 0;
  }

  /* Encodes b into character string a, where character string is ordered
     from most to least significant.

     Lengths: a[len], b[digits].
     Assumes NN_Bits (b, digits) <= 8 * len. (Otherwise most significant
     digits are truncated.)
   */
  void NN_Encode (unsigned char *a, NN_UINT len, NN_DIGIT *b, NN_UINT digits)
  {
    NN_DIGIT t;
    int j;
    unsigned int i, u;

    for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
      t = b[i];
      for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
        a[j] = (unsigned char)(t >> u);
    }

    for (; j >= 0; j--)
      a[j] = 0;
  }

  /* Assigns a = b.

     Lengths: a[digits], b[digits].
   */
  void NN_Assign (NN_DIGIT *a, NN_DIGIT *b, NN_UINT digits)
  {
    memcpy(a, b, digits*NN_DIGIT_LEN);
  }

  /* Assigns a = 0.

     Lengths: a[digits].
   */
  void NN_AssignZero (NN_DIGIT *a, NN_UINT digits)
  {

    uint8_t i;

    for (i = 0; i < digits; i++)
      a[i] = 0;

  }

  /* Assigns a = 2^b.

     Lengths: a[digits].
     Requires b < digits * NN_DIGIT_BITS.
   */
  void NN_Assign2Exp (NN_DIGIT *a, NN_UINT2 b, NN_UINT digits)
  {
    NN_AssignZero (a, digits);

    if (b >= digits * NN_DIGIT_BITS)
      return;

    a[b / NN_DIGIT_BITS] = (NN_DIGIT)1 << (b % NN_DIGIT_BITS);
  }


  /* Computes a = b + c. Returns carry.
     a, b ,c can be same
     Lengths: a[digits], b[digits], c[digits].
   */
  NN_DIGIT NN_Add (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits) __attribute__ ((noinline))
  {
    //inline assembly for micaz
#ifdef INLINE_ASM
#ifdef MICA
     
    NN_DIGIT carry;
    if (digits == 0)
      return 0;

    asm volatile ("dec %4 \n\t"
		  "ld r0, Y+ \n\t"
		  "ld r2, Z+ \n\t"
		  "add r0, r2 \n\t"
		  "st X+, r0 \n\t"
		  "ADD_LOOP1: tst %4 \n\t"
		  "breq ADD_LOOP1_EXIT \n\t"
		  "dec %4 \n\t"
		  "ld r0, Y+ \n\t"
		  "ld r2, Z+ \n\t"
		  "adc r0, r2 \n\t"
		  "st X+, r0 \n\t"
		  "jmp ADD_LOOP1 \n\t"
		  "ADD_LOOP1_EXIT: clr %0 \n\t"
		  "rol %0 \n\t"
		  :"=a"(carry)
		  :"x"(a),"y"(b),"z"(c), "r"(digits)
		  :"r0", "r2"
		  );

    return carry;
    
#endif
#ifdef TELOSB
    NN_DIGIT carry;
    NN_UINT i;

    carry = 0;

    for (i = 0; i < digits; i++) {
      asm volatile ("rrc %1 \n\t"
                    "addc %3, %2 \n\t"
                    "mov %2, %0 \n\t"
                    "rlc %1 \n\t"
		    :"=r"(a[i]), "+r"(carry)
                    :"r"(b[i]), "r"(c[i])
                    );
    }     
#endif
#endif

#ifndef INLINE_ASM

    NN_DIGIT carry, ai;
    NN_UINT i;

    carry = 0;

    for (i = 0; i < digits; i++) {
      if ((ai = b[i] + carry) < carry)
        ai = c[i];
      else if ((ai += c[i]) < c[i])
        carry = 1;
      else
        carry = 0;
      a[i] = ai;
    }
    
#endif

    return (carry);
  }

  /* Computes a = b - c. Returns borrow.
     a, b, c can be same
     Lengths: a[digits], b[digits], c[digits].
   */
  NN_DIGIT NN_Sub (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits) __attribute__ ((noinline))
  {

#ifdef INLINE_ASM
#ifdef MICA

    NN_DIGIT borrow;
    if (digits == 0)
      return 0;

    asm volatile ("dec %4 \n\t"
		  "ld r0, Y+ \n\t"
		  "ld r2, Z+ \n\t"
		  "sub r0, r2 \n\t"
		  "st X+, r0 \n\t"
		  "SUB_LOOP1: tst %4 \n\t"
		  "breq SUB_LOOP1_EXIT \n\t"
		  "dec %4 \n\t"
		  "ld r0, Y+ \n\t"
		  "ld r2, Z+ \n\t"
		  "sbc r0, r2 \n\t"
		  "st X+, r0 \n\t"
		  "jmp SUB_LOOP1 \n\t"
		  "SUB_LOOP1_EXIT: clr %0 \n\t"
		  "rol %0 \n\t"
		  :"=a"(borrow)
		  :"x"(a),"y"(b),"z"(c), "r"(digits)
		  :"r0", "r2"
		  );

    return borrow;

#endif
#ifdef TELOSB
    NN_DIGIT borrow;
    NN_UINT i;

    borrow = 1;

    for (i = 0; i < digits; i++) {
      asm volatile ("rrc %1 \n\t"
                    "subc %3, %2 \n\t"
                    "mov %2, %0 \n\t"
                    "rlc %1 \n\t"
                    :"=r"(a[i]), "+r"(borrow)
                    :"r"(b[i]), "r"(c[i])
                    );
    }
    borrow = borrow ^ 0x0001;
#endif
#endif


#ifndef INLINE_ASM

    NN_DIGIT ai, borrow;
    NN_UINT i;

    borrow = 0;

    for (i = 0; i < digits; i++) {
      if ((ai = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
        ai = MAX_NN_DIGIT - c[i];
      else if ((ai -= c[i]) > (MAX_NN_DIGIT - c[i]))
        borrow = 1;
      else
        borrow = 0;
      a[i] = ai;
    }

#endif

    return (borrow);
  }

  /* Computes a = b * c.
     a, b, c can be same
     Lengths: a[2*digits], b[digits], c[digits].
     Assumes digits < MAX_NN_DIGITS.
   */
  void NN_Mult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_UINT digits) __attribute__ ((noinline))
  {

#ifdef INLINE_ASM
#ifdef MICA
#ifdef HYBRID_MUL_WIDTH4
    uint8_t n_d;
    
    n_d = digits/4;

    //r2~r10
    //r11~r14
    //r15
    //r16 i
    //r17 j
    //r19 0
    //r21:r20 b
    //r23:r22 c
    //r18 (i-j)*d ----------------
    //r20 j*d  ----------------
    //r25 d
    asm volatile (//"push r0 \n\t"
		  "push r1 \n\t"
		  "push r28 \n\t"
		  "push r29 \n\t"
		  "clr r2 \n\t"  //init 9 registers for accumulator
		  "clr r3 \n\t"
		  "clr r4 \n\t"
		  "clr r5 \n\t"
		  "clr r6 \n\t"
		  "clr r7 \n\t"
		  "clr r8 \n\t"
		  "clr r9 \n\t"
		  "clr r10 \n\t"  //end of init
		  "clr r19 \n\t"  //zero
		  "ldi r25, 4 \n\t"  //d=4
		  "dec %3 \n\t"
		  "ldi r16, 0 \n\t"  //i
		  "LOOP1: ldi r17, 0 \n\t"  //j=0
		  "mul r16, r25 \n\t"
		  "add r0, r25 \n\t"
		  "movw r26, %A1 \n\t"
		  "add r26, r0 \n\t"
		  "adc r27, r1 \n\t"  //load b, (i-j+1)*d-1
		  "movw r28, %A2 \n\t"  //load c
		  "LOOP2: ld r14, -X \n\t"  //load b0~b(d-1)
		  "ld r13, -X \n\t"
		  "ld r12, -X \n\t"
		  "ld r11, -X \n\t"
		  "ld r15, Y+ \n\t"  //load c[j*d+0]
		  "mul r11, r15 \n\t"  //t=0
		  "add r2, r0 \n\t"
		  "adc r3, r1 \n\t"
		  "brcc T01 \n\t"
		  "adc r4, r19 \n\t"
		  "brcc T01 \n\t"
		  "adc r5, r19 \n\t"
		  "adc r6, r19 \n\t"
		  "adc r7, r19 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "T01: mul r12, r15 \n\t"  //t=1
		  "add r3, r0 \n\t"
		  "adc r4, r1 \n\t"
		  "brcc T02 \n\t"
		  "adc r5, r19 \n\t"
		  "brcc T02 \n\t"
		  "adc r6, r19 \n\t"
		  "adc r7, r19 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "T02: mul r13, r15 \n\t"  //t=2
		  "add r4, r0 \n\t"
		  "adc r5, r1 \n\t"
		  "brcc T03 \n\t"
		  "adc r6, r19 \n\t"
		  "brcc T03 \n\t"
		  "adc r7, r19 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "T03: mul r14, r15 \n\t"  //t=3
		  "add r5, r0 \n\t"
		  "adc r6, r1 \n\t"
		  "brcc T04 \n\t"
		  "adc r7, r19 \n\t"
		  "brcc T04 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "T04: ld r15, Y+ \n\t"  //load c[j*d+1]
		  "mul r11, r15 \n\t" //t=0, b0*c
		  "add r3, r0 \n\t"
		  "adc r4, r1 \n\t"
		  "brcc T11 \n\t"
		  "adc r5, r19 \n\t"
		  "brcc T11 \n\t"
		  "adc r6, r19 \n\t"
		  "adc r7, r19 \n\t"
		  "adc r8, r19 \n\t"
		  "adc r9, r19 \n\t"
		  "adc r10, r19 \n\t"
		  "T11: mul r12, r15 \n\t"  //t=1
		  "add r4, r0 \n\t"
		  "adc r5, r1 \n\t"
		  "brcc T12 \n\t"
		  "adc r6, r19 \n\t"
		  "brcc T12 \n\t"