Satya Calloji | 444a8da | 2015-03-06 10:38:22 -0800 | [diff] [blame^] | 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 | |