stack/smp/p_256_ecc_pp.c

   1 /******************************************************************************
   2  *
   3  *  Copyright (C) 2006-2015 Broadcom Corporation
   4  *
   5  *  Licensed under the Apache License, Version 2.0 (the "License");
   6  *  you may not use this file except in compliance with the License.
   7  *  You may obtain a copy of the License at:
   8  *
   9  *  http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  *  Unless required by applicable law or agreed to in writing, software
  12  *  distributed under the License is distributed on an "AS IS" BASIS,
  13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  *  See the License for the specific language governing permissions and
  15  *  limitations under the License.
  16  *
  17  ******************************************************************************/
  18
  19  /******************************************************************************
  20   *
  21   *  This file contains simple pairing algorithms using Elliptic Curve Cryptography for private public key
  22   *
  23   ******************************************************************************/
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include "p_256_ecc_pp.h"
  28 #include "p_256_multprecision.h"
  29
  30 elliptic_curve_t curve;
  31 elliptic_curve_t curve_p256;
  32
  33 static void p_256_init_point(Point *q)
  34 {
  35     memset(q, 0, sizeof(Point));
  36 }
  37
  38 static void p_256_copy_point(Point *q, Point *p)
  39 {
  40     memcpy(q, p, sizeof(Point));
  41 }
  42
  43 // q=2q
  44 static void ECC_Double(Point *q, Point *p, uint32_t keyLength)
  45 {
  46     DWORD t1[KEY_LENGTH_DWORDS_P256];
  47     DWORD t2[KEY_LENGTH_DWORDS_P256];
  48     DWORD t3[KEY_LENGTH_DWORDS_P256];
  49     DWORD *x1;
  50     DWORD *x3;
  51     DWORD *y1;
  52     DWORD *y3;
  53     DWORD *z1;
  54     DWORD *z3;
  55
  56     if (multiprecision_iszero(p->z, keyLength))
  57     {
  58         multiprecision_init(q->z, keyLength);
  59         return;                                     // return infinity
  60     }
  61
  62     x1=p->x; y1=p->y; z1=p->z;
  63     x3=q->x; y3=q->y; z3=q->z;
  64
  65     multiprecision_mersenns_squa_mod(t1, z1, keyLength);  // t1=z1^2
  66     multiprecision_sub_mod(t2, x1, t1, keyLength);  // t2=x1-t1
  67     multiprecision_add_mod(t1, x1, t1, keyLength);  // t1=x1+t1
  68     multiprecision_mersenns_mult_mod(t2, t1, t2, keyLength);  // t2=t2*t1
  69     multiprecision_lshift_mod(t3, t2, keyLength);
  70     multiprecision_add_mod(t2, t3, t2, keyLength);  // t2=3t2
  71
  72     multiprecision_mersenns_mult_mod(z3, y1, z1, keyLength);  // z3=y1*z1
  73     multiprecision_lshift_mod(z3, z3, keyLength);
  74
  75     multiprecision_mersenns_squa_mod(y3, y1, keyLength);  // y3=y1^2
  76     multiprecision_lshift_mod(y3, y3, keyLength);
  77     multiprecision_mersenns_mult_mod(t3, y3, x1, keyLength);  // t3=y3*x1=x1*y1^2
  78     multiprecision_lshift_mod(t3, t3, keyLength);
  79     multiprecision_mersenns_squa_mod(y3, y3, keyLength);  // y3=y3^2=y1^4
  80     multiprecision_lshift_mod(y3, y3, keyLength);
  81
  82     multiprecision_mersenns_squa_mod(x3, t2, keyLength);  // x3=t2^2
  83     multiprecision_lshift_mod(t1, t3, keyLength);                // t1=2t3
  84     multiprecision_sub_mod(x3, x3, t1, keyLength);               // x3=x3-t1
  85     multiprecision_sub_mod(t1, t3, x3, keyLength);               // t1=t3-x3
  86     multiprecision_mersenns_mult_mod(t1, t1, t2, keyLength);  // t1=t1*t2
  87     multiprecision_sub_mod(y3, t1, y3, keyLength);               // y3=t1-y3
  88 }
  89
  90 // q=q+p,     zp must be 1
  91 static void ECC_Add(Point *r, Point *p, Point *q, uint32_t keyLength)
  92 {
  93     DWORD t1[KEY_LENGTH_DWORDS_P256];
  94     DWORD t2[KEY_LENGTH_DWORDS_P256];
  95     DWORD *x1;
  96     DWORD *x2;
  97     DWORD *x3;
  98     DWORD *y1;
  99     DWORD *y2;
 100     DWORD *y3;
 101     DWORD *z1;
 102     DWORD *z2;
 103     DWORD *z3;
 104
 105     x1=p->x; y1=p->y; z1=p->z;
 106     x2=q->x; y2=q->y; z2=q->z;
 107     x3=r->x; y3=r->y; z3=r->z;
 108
 109     // if Q=infinity, return p
 110     if (multiprecision_iszero(z2, keyLength))
 111     {
 112         p_256_copy_point(r, p);
 113         return;
 114     }
 115
 116     // if P=infinity, return q
 117     if (multiprecision_iszero(z1, keyLength))
 118     {
 119         p_256_copy_point(r, q);
 120         return;
 121     }
 122
 123     multiprecision_mersenns_squa_mod(t1, z1, keyLength);      // t1=z1^2
 124     multiprecision_mersenns_mult_mod(t2, z1, t1, keyLength);  // t2=t1*z1
 125     multiprecision_mersenns_mult_mod(t1, x2, t1, keyLength);  // t1=t1*x2
 126     multiprecision_mersenns_mult_mod(t2, y2, t2, keyLength);  // t2=t2*y2
 127
 128     multiprecision_sub_mod(t1, t1, x1, keyLength);  // t1=t1-x1
 129     multiprecision_sub_mod(t2, t2, y1, keyLength);  // t2=t2-y1
 130
 131     if (multiprecision_iszero(t1, keyLength))
 132     {
 133         if (multiprecision_iszero(t2, keyLength))
 134         {
 135             ECC_Double(r, q, keyLength) ;
 136             return;
 137         }
 138         else
 139         {
 140             multiprecision_init(z3, keyLength);
 141             return;                             // return infinity
 142         }
 143     }
 144
 145     multiprecision_mersenns_mult_mod(z3, z1, t1, keyLength);  // z3=z1*t1
 146     multiprecision_mersenns_squa_mod(y3, t1, keyLength);      // t3=t1^2
 147     multiprecision_mersenns_mult_mod(z1, y3, t1, keyLength);  // t4=t3*t1
 148     multiprecision_mersenns_mult_mod(y3, y3, x1, keyLength);  // t3=t3*x1
 149     multiprecision_lshift_mod(t1, y3, keyLength);            // t1=2*t3
 150     multiprecision_mersenns_squa_mod(x3, t2, keyLength);      // x3=t2^2
 151     multiprecision_sub_mod(x3, x3, t1, keyLength);           // x3=x3-t1
 152     multiprecision_sub_mod(x3, x3, z1, keyLength);           // x3=x3-t4
 153     multiprecision_sub_mod(y3, y3, x3, keyLength);           // t3=t3-x3
 154     multiprecision_mersenns_mult_mod(y3, y3, t2, keyLength);  // t3=t3*t2
 155     multiprecision_mersenns_mult_mod(z1, z1, y1, keyLength);  // t4=t4*t1
 156     multiprecision_sub_mod(y3, y3, z1, keyLength);
 157 }
 158
 159 // Computing the Non-Adjacent Form of a positive integer
 160 static void ECC_NAF(uint8_t *naf, uint32_t *NumNAF, DWORD *k, uint32_t keyLength)
 161 {
 162     uint32_t sign;
 163     int i=0;
 164     int j;
 165     uint32_t var;
 166
 167     while ((var = multiprecision_most_signbits(k, keyLength))>=1)
 168     {
 169         if (k[0] & 0x01)  // k is odd
 170         {
 171             sign = (k[0] & 0x03);  // 1 or 3
 172
 173             // k = k-naf[i]
 174             if (sign == 1)
 175                 k[0] = k[0] & 0xFFFFFFFE;
 176             else
 177             {
 178                 k[0] = k[0] + 1;
 179                 if (k[0] == 0)  //overflow
 180                 {
 181                     j = 1;
 182                     do
 183                     {
 184                         k[j]++;
 185                     } while (k[j++]==0);  //overflow
 186                 }
 187             }
 188         }
 189         else
 190             sign = 0;
 191
 192         multiprecision_rshift(k, k, keyLength);
 193         naf[i / 4] |= (sign) << ((i % 4) * 2);
 194         i++;
 195     }
 196
 197     *NumNAF=i;
 198 }
 199
 200 // Binary Non-Adjacent Form for point multiplication
 201 void ECC_PointMult_Bin_NAF(Point *q, Point *p, DWORD *n, uint32_t keyLength)
 202 {
 203     uint32_t sign;
 204     UINT8 naf[256 / 4 +1];
 205     uint32_t NumNaf;
 206     Point minus_p;
 207     Point r;
 208     DWORD *modp;
 209
 210     if (keyLength == KEY_LENGTH_DWORDS_P256)
 211     {
 212         modp = curve_p256.p;
 213     }
 214     else
 215     {
 216         modp = curve.p;
 217     }
 218
 219     p_256_init_point(&r);
 220     multiprecision_init(p->z, keyLength);
 221     p->z[0] = 1;
 222
 223     // initialization
 224     p_256_init_point(q);
 225
 226     // -p
 227     multiprecision_copy(minus_p.x, p->x, keyLength);
 228     multiprecision_sub(minus_p.y, modp, p->y, keyLength);
 229
 230     multiprecision_init(minus_p.z, keyLength);
 231     minus_p.z[0]=1;
 232
 233     // NAF
 234     memset(naf, 0, sizeof(naf));
 235     ECC_NAF(naf, &NumNaf, n, keyLength);
 236
 237     for (int i = NumNaf - 1; i >= 0; i--)
 238     {
 239         p_256_copy_point(&r, q);
 240         ECC_Double(q, &r, keyLength);
 241         sign = (naf[i / 4] >> ((i % 4) * 2)) & 0x03;
 242
 243         if (sign == 1)
 244         {
 245             p_256_copy_point(&r, q);
 246             ECC_Add(q, &r, p, keyLength);
 247         }
 248         else if (sign == 3)
 249         {
 250             p_256_copy_point(&r, q);
 251             ECC_Add(q, &r, &minus_p, keyLength);
 252         }
 253     }
 254
 255     multiprecision_inv_mod(minus_p.x, q->z, keyLength);
 256     multiprecision_mersenns_squa_mod(q->z, minus_p.x, keyLength);
 257     multiprecision_mersenns_mult_mod(q->x, q->x, q->z, keyLength);
 258     multiprecision_mersenns_mult_mod(q->z, q->z, minus_p.x, keyLength);
 259     multiprecision_mersenns_mult_mod(q->y, q->y, q->z, keyLength);
 260 }
 261
 262