1 /****************************************************************************** 2 * 3 * Copyright 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) { 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)) { 53 multiprecision_init(q->z); 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); // t1=z1^2 65 multiprecision_sub_mod(t2, x1, t1); // t2=x1-t1 66 multiprecision_add_mod(t1, x1, t1); // t1=x1+t1 67 multiprecision_mersenns_mult_mod(t2, t1, t2); // t2=t2*t1 68 multiprecision_lshift_mod(t3, t2); 69 multiprecision_add_mod(t2, t3, t2); // t2=3t2 70 71 multiprecision_mersenns_mult_mod(z3, y1, z1); // z3=y1*z1 72 multiprecision_lshift_mod(z3, z3); 73 74 multiprecision_mersenns_squa_mod(y3, y1); // y3=y1^2 75 multiprecision_lshift_mod(y3, y3); 76 multiprecision_mersenns_mult_mod(t3, y3, x1); // t3=y3*x1=x1*y1^2 77 multiprecision_lshift_mod(t3, t3); 78 multiprecision_mersenns_squa_mod(y3, y3); // y3=y3^2=y1^4 79 multiprecision_lshift_mod(y3, y3); 80 81 multiprecision_mersenns_squa_mod(x3, t2); // x3=t2^2 82 multiprecision_lshift_mod(t1, t3); // t1=2t3 83 multiprecision_sub_mod(x3, x3, t1); // x3=x3-t1 84 multiprecision_sub_mod(t1, t3, x3); // t1=t3-x3 85 multiprecision_mersenns_mult_mod(t1, t1, t2); // t1=t1*t2 86 multiprecision_sub_mod(y3, t1, y3); // y3=t1-y3 87 } 88 89 // q=q+p, zp must be 1 90 static void ECC_Add(Point* r, Point* p, Point* q) { 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)) { 115 p_256_copy_point(r, p); 116 return; 117 } 118 119 // if P=infinity, return q 120 if (multiprecision_iszero(z1)) { 121 p_256_copy_point(r, q); 122 return; 123 } 124 125 multiprecision_mersenns_squa_mod(t1, z1); // t1=z1^2 126 multiprecision_mersenns_mult_mod(t2, z1, t1); // t2=t1*z1 127 multiprecision_mersenns_mult_mod(t1, x2, t1); // t1=t1*x2 128 multiprecision_mersenns_mult_mod(t2, y2, t2); // t2=t2*y2 129 130 multiprecision_sub_mod(t1, t1, x1); // t1=t1-x1 131 multiprecision_sub_mod(t2, t2, y1); // t2=t2-y1 132 133 if (multiprecision_iszero(t1)) { 134 if (multiprecision_iszero(t2)) { 135 ECC_Double(r, q); 136 return; 137 } else { 138 multiprecision_init(z3); 139 return; // return infinity 140 } 141 } 142 143 multiprecision_mersenns_mult_mod(z3, z1, t1); // z3=z1*t1 144 multiprecision_mersenns_squa_mod(y3, t1); // t3=t1^2 145 multiprecision_mersenns_mult_mod(z1, y3, t1); // t4=t3*t1 146 multiprecision_mersenns_mult_mod(y3, y3, x1); // t3=t3*x1 147 multiprecision_lshift_mod(t1, y3); // t1=2*t3 148 multiprecision_mersenns_squa_mod(x3, t2); // x3=t2^2 149 multiprecision_sub_mod(x3, x3, t1); // x3=x3-t1 150 multiprecision_sub_mod(x3, x3, z1); // x3=x3-t4 151 multiprecision_sub_mod(y3, y3, x3); // t3=t3-x3 152 multiprecision_mersenns_mult_mod(y3, y3, t2); // t3=t3*t2 153 multiprecision_mersenns_mult_mod(z1, z1, y1); // t4=t4*t1 154 multiprecision_sub_mod(y3, y3, z1); 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 sign; 160 int i = 0; 161 int j; 162 uint32_t var; 163 164 while ((var = multiprecision_most_signbits(k)) >= 1) { 165 if (k[0] & 0x01) // k is odd 166 { 167 sign = (k[0] & 0x03); // 1 or 3 168 169 // k = k-naf[i] 170 if (sign == 1) 171 k[0] = k[0] & 0xFFFFFFFE; 172 else { 173 k[0] = k[0] + 1; 174 if (k[0] == 0) // overflow 175 { 176 j = 1; 177 do { 178 k[j]++; 179 } while (k[j++] == 0); // overflow 180 } 181 } 182 } else 183 sign = 0; 184 185 multiprecision_rshift(k, k); 186 naf[i / 4] |= (sign) << ((i % 4) * 2); 187 i++; 188 } 189 190 *NumNAF = i; 191 } 192 193 // Binary Non-Adjacent Form for point multiplication 194 void ECC_PointMult_Bin_NAF(Point* q, Point* p, uint32_t* n) { 195 uint32_t sign; 196 uint8_t naf[256 / 4 + 1]; 197 uint32_t NumNaf; 198 Point minus_p; 199 Point r; 200 uint32_t* modp; 201 202 modp = curve_p256.p; 203 204 p_256_init_point(&r); 205 multiprecision_init(p->z); 206 p->z[0] = 1; 207 208 // initialization 209 p_256_init_point(q); 210 211 // -p 212 multiprecision_copy(minus_p.x, p->x); 213 multiprecision_sub(minus_p.y, modp, p->y); 214 215 multiprecision_init(minus_p.z); 216 minus_p.z[0] = 1; 217 218 // NAF 219 memset(naf, 0, sizeof(naf)); 220 ECC_NAF(naf, &NumNaf, n); 221 222 for (int i = NumNaf - 1; i >= 0; i--) { 223 p_256_copy_point(&r, q); 224 ECC_Double(q, &r); 225 sign = (naf[i / 4] >> ((i % 4) * 2)) & 0x03; 226 227 if (sign == 1) { 228 p_256_copy_point(&r, q); 229 ECC_Add(q, &r, p); 230 } else if (sign == 3) { 231 p_256_copy_point(&r, q); 232 ECC_Add(q, &r, &minus_p); 233 } 234 } 235 236 multiprecision_inv_mod(minus_p.x, q->z); 237 multiprecision_mersenns_squa_mod(q->z, minus_p.x); 238 multiprecision_mersenns_mult_mod(q->x, q->x, q->z); 239 multiprecision_mersenns_mult_mod(q->z, q->z, minus_p.x); 240 multiprecision_mersenns_mult_mod(q->y, q->y, q->z); 241 } 242 243 bool ECC_ValidatePoint(const Point& pt) { 244 p_256_init_curve(); 245 246 // Ensure y^2 = x^3 + a*x + b (mod p); a = -3 247 248 // y^2 mod p 249 uint32_t y2_mod[KEY_LENGTH_DWORDS_P256] = {0}; 250 multiprecision_mersenns_squa_mod(y2_mod, (uint32_t*)pt.y); 251 252 // Right hand side calculation 253 uint32_t rhs[KEY_LENGTH_DWORDS_P256] = {0}; 254 multiprecision_mersenns_squa_mod(rhs, (uint32_t*)pt.x); 255 uint32_t three[KEY_LENGTH_DWORDS_P256] = {0}; 256 three[0] = 3; 257 multiprecision_sub_mod(rhs, rhs, three); 258 multiprecision_mersenns_mult_mod(rhs, rhs, (uint32_t*)pt.x); 259 multiprecision_add_mod(rhs, rhs, curve_p256.b); 260 261 return multiprecision_compare(rhs, y2_mod) == 0; 262 } 263