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 263
