stack/smp/p_256_ecc_pp.cc

   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
  22  *  Cryptography for private public key
  23  *
  24  ******************************************************************************/
  25 #include "p_256_ecc_pp.h"
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include "p_256_multprecision.h"
  30
  31 elliptic_curve_t curve;
  32 elliptic_curve_t curve_p256;
  33
  34 static void p_256_init_point(Point* q) { memset(q, 0, sizeof(Point)); }
  35
  36 static void p_256_copy_point(Point* q, Point* p) {
  37   memcpy(q, p, sizeof(Point));
  38 }
  39
  40 // q=2q
  41 static void ECC_Double(Point* q, Point* p, uint32_t keyLength) {
  42   uint32_t t1[KEY_LENGTH_DWORDS_P256];
  43   uint32_t t2[KEY_LENGTH_DWORDS_P256];
  44   uint32_t t3[KEY_LENGTH_DWORDS_P256];
  45   uint32_t* x1;
  46   uint32_t* x3;
  47   uint32_t* y1;
  48   uint32_t* y3;
  49   uint32_t* z1;
  50   uint32_t* z3;
  51
  52   if (multiprecision_iszero(p->z, keyLength)) {
  53     multiprecision_init(q->z, keyLength);
  54     return;  // return infinity
  55   }
  56
  57   x1 = p->x;
  58   y1 = p->y;
  59   z1 = p->z;
  60   x3 = q->x;
  61   y3 = q->y;
  62   z3 = q->z;
  63
  64   multiprecision_mersenns_squa_mod(t1, z1, keyLength);      // t1=z1^2
  65   multiprecision_sub_mod(t2, x1, t1, keyLength);            // t2=x1-t1
  66   multiprecision_add_mod(t1, x1, t1, keyLength);            // t1=x1+t1
  67   multiprecision_mersenns_mult_mod(t2, t1, t2, keyLength);  // t2=t2*t1
  68   multiprecision_lshift_mod(t3, t2, keyLength);
  69   multiprecision_add_mod(t2, t3, t2, keyLength);  // t2=3t2
  70
  71   multiprecision_mersenns_mult_mod(z3, y1, z1, keyLength);  // z3=y1*z1
  72   multiprecision_lshift_mod(z3, z3, keyLength);
  73
  74   multiprecision_mersenns_squa_mod(y3, y1, keyLength);  // y3=y1^2
  75   multiprecision_lshift_mod(y3, y3, keyLength);
  76   multiprecision_mersenns_mult_mod(t3, y3, x1, keyLength);  // t3=y3*x1=x1*y1^2
  77   multiprecision_lshift_mod(t3, t3, keyLength);
  78   multiprecision_mersenns_squa_mod(y3, y3, keyLength);  // y3=y3^2=y1^4
  79   multiprecision_lshift_mod(y3, y3, keyLength);
  80
  81   multiprecision_mersenns_squa_mod(x3, t2, keyLength);      // x3=t2^2
  82   multiprecision_lshift_mod(t1, t3, keyLength);             // t1=2t3
  83   multiprecision_sub_mod(x3, x3, t1, keyLength);            // x3=x3-t1
  84   multiprecision_sub_mod(t1, t3, x3, keyLength);            // t1=t3-x3
  85   multiprecision_mersenns_mult_mod(t1, t1, t2, keyLength);  // t1=t1*t2
  86   multiprecision_sub_mod(y3, t1, y3, keyLength);            // y3=t1-y3
  87 }
  88
  89 // q=q+p,     zp must be 1
  90 static void ECC_Add(Point* r, Point* p, Point* q, uint32_t keyLength) {
  91   uint32_t t1[KEY_LENGTH_DWORDS_P256];
  92   uint32_t t2[KEY_LENGTH_DWORDS_P256];
  93   uint32_t* x1;
  94   uint32_t* x2;
  95   uint32_t* x3;
  96   uint32_t* y1;
  97   uint32_t* y2;
  98   uint32_t* y3;
  99   uint32_t* z1;
 100   uint32_t* z2;
 101   uint32_t* z3;
 102
 103   x1 = p->x;
 104   y1 = p->y;
 105   z1 = p->z;
 106   x2 = q->x;
 107   y2 = q->y;
 108   z2 = q->z;
 109   x3 = r->x;
 110   y3 = r->y;
 111   z3 = r->z;
 112
 113   // if Q=infinity, return p
 114   if (multiprecision_iszero(z2, keyLength)) {
 115     p_256_copy_point(r, p);
 116     return;
 117   }
 118
 119   // if P=infinity, return q
 120   if (multiprecision_iszero(z1, keyLength)) {
 121     p_256_copy_point(r, q);
 122     return;
 123   }
 124
 125   multiprecision_mersenns_squa_mod(t1, z1, keyLength);      // t1=z1^2
 126   multiprecision_mersenns_mult_mod(t2, z1, t1, keyLength);  // t2=t1*z1
 127   multiprecision_mersenns_mult_mod(t1, x2, t1, keyLength);  // t1=t1*x2
 128   multiprecision_mersenns_mult_mod(t2, y2, t2, keyLength);  // t2=t2*y2
 129
 130   multiprecision_sub_mod(t1, t1, x1, keyLength);  // t1=t1-x1
 131   multiprecision_sub_mod(t2, t2, y1, keyLength);  // t2=t2-y1
 132
 133   if (multiprecision_iszero(t1, keyLength)) {
 134     if (multiprecision_iszero(t2, keyLength)) {
 135       ECC_Double(r, q, keyLength);
 136       return;
 137     } else {
 138       multiprecision_init(z3, keyLength);
 139       return;  // return infinity
 140     }
 141   }
 142
 143   multiprecision_mersenns_mult_mod(z3, z1, t1, keyLength);  // z3=z1*t1
 144   multiprecision_mersenns_squa_mod(y3, t1, keyLength);      // t3=t1^2
 145   multiprecision_mersenns_mult_mod(z1, y3, t1, keyLength);  // t4=t3*t1
 146   multiprecision_mersenns_mult_mod(y3, y3, x1, keyLength);  // t3=t3*x1
 147   multiprecision_lshift_mod(t1, y3, keyLength);             // t1=2*t3
 148   multiprecision_mersenns_squa_mod(x3, t2, keyLength);      // x3=t2^2
 149   multiprecision_sub_mod(x3, x3, t1, keyLength);            // x3=x3-t1
 150   multiprecision_sub_mod(x3, x3, z1, keyLength);            // x3=x3-t4
 151   multiprecision_sub_mod(y3, y3, x3, keyLength);            // t3=t3-x3
 152   multiprecision_mersenns_mult_mod(y3, y3, t2, keyLength);  // t3=t3*t2
 153   multiprecision_mersenns_mult_mod(z1, z1, y1, keyLength);  // t4=t4*t1
 154   multiprecision_sub_mod(y3, y3, z1, keyLength);
 155 }
 156
 157 // Computing the Non-Adjacent Form of a positive integer
 158 static void ECC_NAF(uint8_t* naf, uint32_t* NumNAF, uint32_t* k,
 159                     uint32_t keyLength) {
 160   uint32_t sign;
 161   int i = 0;
 162   int j;
 163   uint32_t var;
 164
 165   while ((var = multiprecision_most_signbits(k, keyLength)) >= 1) {
 166     if (k[0] & 0x01)  // k is odd
 167     {
 168       sign = (k[0] & 0x03);  // 1 or 3
 169
 170       // k = k-naf[i]
 171       if (sign == 1)
 172         k[0] = k[0] & 0xFFFFFFFE;
 173       else {
 174         k[0] = k[0] + 1;
 175         if (k[0] == 0)  // overflow
 176         {
 177           j = 1;
 178           do {
 179             k[j]++;
 180           } while (k[j++] == 0);  // overflow
 181         }
 182       }
 183     } else
 184       sign = 0;
 185
 186     multiprecision_rshift(k, k, keyLength);
 187     naf[i / 4] |= (sign) << ((i % 4) * 2);
 188     i++;
 189   }
 190
 191   *NumNAF = i;
 192 }
 193
 194 // Binary Non-Adjacent Form for point multiplication
 195 void ECC_PointMult_Bin_NAF(Point* q, Point* p, uint32_t* n,
 196                            uint32_t keyLength) {
 197   uint32_t sign;
 198   uint8_t naf[256 / 4 + 1];
 199   uint32_t NumNaf;
 200   Point minus_p;
 201   Point r;
 202   uint32_t* modp;
 203
 204   if (keyLength == KEY_LENGTH_DWORDS_P256) {
 205     modp = curve_p256.p;
 206   } else {
 207     modp = curve.p;
 208   }
 209
 210   p_256_init_point(&r);
 211   multiprecision_init(p->z, keyLength);
 212   p->z[0] = 1;
 213
 214   // initialization
 215   p_256_init_point(q);
 216
 217   // -p
 218   multiprecision_copy(minus_p.x, p->x, keyLength);
 219   multiprecision_sub(minus_p.y, modp, p->y, keyLength);
 220
 221   multiprecision_init(minus_p.z, keyLength);
 222   minus_p.z[0] = 1;
 223
 224   // NAF
 225   memset(naf, 0, sizeof(naf));
 226   ECC_NAF(naf, &NumNaf, n, keyLength);
 227
 228   for (int i = NumNaf - 1; i >= 0; i--) {
 229     p_256_copy_point(&r, q);
 230     ECC_Double(q, &r, keyLength);
 231     sign = (naf[i / 4] >> ((i % 4) * 2)) & 0x03;
 232
 233     if (sign == 1) {
 234       p_256_copy_point(&r, q);
 235       ECC_Add(q, &r, p, keyLength);
 236     } else if (sign == 3) {
 237       p_256_copy_point(&r, q);
 238       ECC_Add(q, &r, &minus_p, keyLength);
 239     }
 240   }
 241
 242   multiprecision_inv_mod(minus_p.x, q->z, keyLength);
 243   multiprecision_mersenns_squa_mod(q->z, minus_p.x, keyLength);
 244   multiprecision_mersenns_mult_mod(q->x, q->x, q->z, keyLength);
 245   multiprecision_mersenns_mult_mod(q->z, q->z, minus_p.x, keyLength);
 246   multiprecision_mersenns_mult_mod(q->y, q->y, q->z, keyLength);
 247 }
 248
 249 bool ECC_ValidatePoint(const Point& pt) {
 250   const size_t kl = KEY_LENGTH_DWORDS_P256;
 251   p_256_init_curve(kl);
 252
 253   // Ensure y^2 = x^3 + a*x + b (mod p); a = -3
 254
 255   // y^2 mod p
 256   uint32_t y2_mod[kl] = {0};
 257   multiprecision_mersenns_squa_mod(y2_mod, (uint32_t*)pt.y, kl);
 258
 259   // Right hand side calculation
 260   uint32_t rhs[kl] = {0};
 261   multiprecision_mersenns_squa_mod(rhs, (uint32_t*)pt.x, kl);
 262   uint32_t three[kl] = {0};
 263   three[0] = 3;
 264   multiprecision_sub_mod(rhs, rhs, three, kl);
 265   multiprecision_mersenns_mult_mod(rhs, rhs, (uint32_t*)pt.x, kl);
 266   multiprecision_add_mod(rhs, rhs, curve_p256.b, kl);
 267
 268   return multiprecision_compare(rhs, y2_mod, kl) == 0;
 269 }