1 /*############################################################################ 2 # Copyright 2017 Intel Corporation 3 # 4 # Licensed under the Apache License, Version 2.0 (the "License"); 5 # you may not use this file except in compliance with the License. 6 # You may obtain a copy of the License at 7 # 8 # http://www.apache.org/licenses/LICENSE-2.0 9 # 10 # Unless required by applicable law or agreed to in writing, software 11 # distributed under the License is distributed on an "AS IS" BASIS, 12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 # See the License for the specific language governing permissions and 14 # limitations under the License. 15 ############################################################################*/ 16 /// Implementation of EFq math 17 /*! \file */ 18 19 #include "epid/member/tiny/math/efq.h" 20 #include "epid/member/tiny/math/fq.h" 21 #include "epid/member/tiny/math/hashwrap.h" 22 #include "epid/member/tiny/math/mathtypes.h" 23 #include "epid/member/tiny/math/serialize.h" 24 #include "epid/member/tiny/math/vli.h" 25 #include "epid/member/tiny/stdlib/tiny_stdlib.h" 26 27 static int EFqMakePoint(EccPointFq* output, FqElem* in) { 28 FqElem fq_sqrt = {0}; 29 FqElem fq_tmp = {0}; 30 FqSet(&fq_tmp, 3); 31 FqSquare(&fq_sqrt, in); 32 FqMul(&fq_sqrt, &fq_sqrt, in); 33 FqAdd(&fq_sqrt, &fq_sqrt, &fq_tmp); 34 if (!FqSqrt(&output->y, &fq_sqrt)) { 35 return 0; 36 } 37 FqCp(&output->x, in); 38 39 return 1; 40 } 41 42 void EFqMulSSCM(EccPointJacobiFq* result, EccPointJacobiFq const* base, 43 FpElem const* exp) { 44 EccPointJacobiFq efqj_1; 45 EccPointJacobiFq efqj_2; 46 47 uint32_t position; 48 EFqInf(&efqj_1); 49 EFqJCp(&efqj_2, base); 50 for (position = 32 * NUM_ECC_DIGITS; position > 0; --position) { 51 EFqDbl(&efqj_1, &efqj_1); 52 EFqAdd(&efqj_2, base, &efqj_1); 53 EFqCondSet(&efqj_1, &efqj_2, &efqj_1, 54 VliTestBit(&(exp->limbs), position - 1)); 55 } 56 EFqJCp(result, &efqj_1); 57 } 58 59 int EFqAffineExp(EccPointFq* result, EccPointFq const* base, 60 FpElem const* exp) { 61 EccPointJacobiFq efqj; 62 EFqFromAffine(&efqj, base); 63 EFqMulSSCM(&efqj, &efqj, exp); 64 return EFqToAffine(result, &efqj); 65 } 66 67 int EFqAffineMultiExp(EccPointFq* result, EccPointFq const* base0, 68 FpElem const* exp0, EccPointFq const* base1, 69 FpElem const* exp1) { 70 EccPointJacobiFq efqj_base0; 71 EccPointJacobiFq efqj_base1; 72 EFqFromAffine(&efqj_base0, base0); 73 EFqFromAffine(&efqj_base1, base1); 74 EFqMultiExp(&efqj_base0, &efqj_base0, exp0, &efqj_base1, exp1); 75 return EFqToAffine(result, &efqj_base0); 76 } 77 78 void EFqMultiExp(EccPointJacobiFq* result, EccPointJacobiFq const* base0, 79 FpElem const* exp0, EccPointJacobiFq const* base1, 80 FpElem const* exp1) { 81 EccPointJacobiFq efqj_base0; 82 EccPointJacobiFq efqj_a; 83 EccPointJacobiFq efqj_b; 84 int i, j; 85 86 EFqAdd(&efqj_base0, base0, base1); 87 EFqInf(&efqj_a); 88 for (i = NUM_ECC_DIGITS - 1; i >= 0; i--) { 89 for (j = 31; j >= 0; j--) { 90 EFqAdd(&efqj_a, &efqj_a, &efqj_a); 91 EFqInf(&efqj_b); 92 EFqJCp(&efqj_b, base0); 93 94 EFqCondSet(&efqj_b, base1, &efqj_b, 95 (int)((exp1->limbs.word[i] >> j) & (0x1))); 96 97 EFqCondSet(&efqj_b, &efqj_base0, &efqj_b, 98 (int)((exp0->limbs.word[i] >> j) & (exp1->limbs.word[i] >> j) & 99 (0x1))); 100 101 EFqAdd(&efqj_b, &efqj_a, &efqj_b); 102 103 EFqCondSet(&efqj_a, &efqj_b, &efqj_a, (int)(((exp0->limbs.word[i] >> j) | 104 (exp1->limbs.word[i] >> j)) & 105 (0x1))); 106 } 107 } 108 EFqJCp(result, &efqj_a); 109 } 110 111 int EFqAffineAdd(EccPointFq* result, EccPointFq const* left, 112 EccPointFq const* right) { 113 EccPointJacobiFq efqj_a; 114 EccPointJacobiFq efqj_b; 115 if (EFqEqAffine(left, right)) return EFqAffineDbl(result, left); 116 117 EFqFromAffine(&efqj_a, left); 118 EFqFromAffine(&efqj_b, right); 119 EFqAdd(&efqj_a, &efqj_a, &efqj_b); 120 121 return EFqToAffine(result, &efqj_a); 122 } 123 124 int EFqAffineDbl(EccPointFq* result, EccPointFq const* in) { 125 EccPointJacobiFq efqj_a; 126 EFqFromAffine(&efqj_a, in); 127 EFqAdd(&efqj_a, &efqj_a, &efqj_a); 128 129 return EFqToAffine(result, &efqj_a); 130 } 131 132 void EFqDbl(EccPointJacobiFq* result, EccPointJacobiFq const* in) { 133 FqElem fq_a; 134 FqElem fq_b; 135 136 FqAdd(&(result->Z), &(in->Z), &(in->Z)); 137 FqMul(&(result->Z), &(result->Z), &(in->Y)); 138 FqSquare(&fq_a, &(in->X)); 139 FqAdd(&fq_b, &fq_a, &fq_a); 140 FqAdd(&fq_b, &fq_b, &fq_a); 141 FqSquare(&fq_a, &(in->Y)); 142 FqAdd(&fq_a, &fq_a, &fq_a); 143 FqSquare(&(result->Y), &fq_a); 144 FqAdd(&(result->Y), &(result->Y), &(result->Y)); 145 FqAdd(&fq_a, &fq_a, &fq_a); 146 FqMul(&fq_a, &fq_a, &(in->X)); 147 FqSquare(&(result->X), &fq_b); 148 FqSub(&(result->X), &(result->X), &fq_a); 149 FqSub(&(result->X), &(result->X), &fq_a); 150 FqSub(&fq_a, &fq_a, &(result->X)); 151 FqMul(&fq_a, &fq_a, &fq_b); 152 FqSub(&(result->Y), &fq_a, &(result->Y)); 153 } 154 155 void EFqAdd(EccPointJacobiFq* result, EccPointJacobiFq const* left, 156 EccPointJacobiFq const* right) { 157 FqElem fq0; 158 FqElem fq1; 159 FqElem fq2; 160 FqElem fq3; 161 FqElem fq4; 162 FqElem fq5; 163 164 if (FqIsZero(&(left->Z))) { 165 EFqJCp(result, right); 166 return; 167 } 168 if (FqIsZero(&(right->Z))) { 169 EFqJCp(result, left); 170 return; 171 } 172 173 FqSquare(&fq2, &(right->Z)); 174 FqSquare(&fq3, &(left->Z)); 175 // P.X * Q.Z^2 176 FqMul(&fq0, &(left->X), &fq2); 177 // Q.X * P.Z^2 178 FqMul(&fq1, &(right->X), &fq3); 179 // Q.X*P.Z^2 - P*X+Q*Z^2 180 FqSub(&fq5, &fq1, &fq0); 181 FqMul(&fq3, &(right->Y), &fq3); 182 // P.Y * Q.Z^3 183 FqMul(&fq3, &(left->Z), &fq3); 184 FqMul(&fq2, &(left->Y), &fq2); 185 // Q.Y * P.Z^3 186 FqMul(&fq2, &(right->Z), &fq2); 187 FqSub(&fq4, &fq3, &fq2); 188 189 if (FqIsZero(&fq5)) { 190 if (FqIsZero(&fq4)) { 191 EFqDbl(result, left); 192 return; 193 } else { 194 EFqInf(result); 195 return; 196 } 197 } 198 FqMul(&(result->Z), &(left->Z), &(right->Z)); 199 FqMul(&(result->Z), &(result->Z), &fq5); 200 // Q.X*P.Z^2 + P*X+Q*Z^2 201 FqAdd(&fq1, &fq0, &fq1); 202 FqMul(&fq2, &fq2, &fq5); 203 FqSquare(&fq5, &fq5); 204 FqMul(&fq1, &fq1, &fq5); 205 FqSquare(&(result->X), &fq4); 206 FqSub(&(result->X), &(result->X), &fq1); 207 FqMul(&fq2, &fq2, &fq5); 208 FqMul(&fq0, &fq0, &fq5); 209 FqSub(&fq0, &fq0, &(result->X)); 210 FqMul(&(result->Y), &fq4, &fq0); 211 FqSub(&(result->Y), &(result->Y), &fq2); 212 } 213 214 int EFqRand(EccPointFq* result, BitSupplier rnd_func, void* rnd_param) { 215 FqElem fq; 216 do { 217 if (!FqRand(&fq, rnd_func, rnd_param)) { 218 return 0; 219 } 220 } while (!EFqMakePoint(result, &fq)); 221 return 1; 222 } 223 224 void EFqSet(EccPointJacobiFq* result, FqElem const* x, FqElem const* y) { 225 FqCp(&result->X, x); 226 FqCp(&result->Y, y); 227 FqSet(&result->Z, 1); 228 } 229 230 int EFqIsInf(EccPointJacobiFq const* in) { 231 return FqIsZero(&in->X) && FqIsZero(&in->Z) && (!FqIsZero(&in->Y)); 232 } 233 234 void EFqFromAffine(EccPointJacobiFq* result, EccPointFq const* in) { 235 FqCp(&result->X, &in->x); 236 FqCp(&result->Y, &in->y); 237 FqSet(&result->Z, 1); 238 } 239 240 int EFqToAffine(EccPointFq* result, EccPointJacobiFq const* in) { 241 FqElem fq_inv; 242 if (EFqIsInf(in)) { 243 return 0; 244 } 245 FqInv(&fq_inv, &in->Z); 246 FqMul(&result->x, &in->X, &fq_inv); 247 FqMul(&result->x, &result->x, &fq_inv); 248 FqMul(&result->y, &in->Y, &fq_inv); 249 FqMul(&result->y, &result->y, &fq_inv); 250 FqMul(&result->y, &result->y, &fq_inv); 251 252 return 1; 253 } 254 255 void EFqNeg(EccPointJacobiFq* result, EccPointJacobiFq const* in) { 256 FqCp(&result->X, &in->X); 257 FqNeg(&result->Y, &in->Y); 258 FqCp(&result->Z, &in->Z); 259 } 260 261 int EFqEq(EccPointJacobiFq const* left, EccPointJacobiFq const* right) { 262 FqElem fq1; 263 FqElem fq2; 264 FqElem fq3; 265 FqElem fq4; 266 if (EFqIsInf(left) && EFqIsInf(right)) { 267 return 1; 268 } 269 if (EFqIsInf(left) || EFqIsInf(right)) { 270 return 0; 271 } 272 // Z1^2 273 FqSquare(&fq1, &left->Z); 274 // Z2^2 275 FqSquare(&fq2, &right->Z); 276 // (Z1^2)*X2 277 FqMul(&fq3, &fq1, &right->X); 278 // (Z2^2)*X1 279 FqMul(&fq4, &fq2, &left->X); 280 // Z1^3 281 FqMul(&fq1, &fq1, &left->Z); 282 // Z2^3 283 FqMul(&fq2, &fq2, &right->Z); 284 // (Z1^3)*Y2 285 FqMul(&fq1, &fq1, &right->Y); 286 // (Z2^3)*Y1 287 FqMul(&fq2, &fq2, &left->Y); 288 // (Z1^2)*X2 == (Z2^2)*X1 && (Z1^3)*Y2 == (Z2^3)*Y1 289 return FqEq(&fq1, &fq2) && FqEq(&fq3, &fq4); 290 } 291 292 int EFqHash(EccPointFq* result, unsigned char const* msg, size_t len, 293 HashAlg hashalg) { 294 tiny_sha hash_context; 295 FqElem three; 296 FqElem tmp; 297 uint32_t hash_salt = 0; 298 uint32_t buf = 0; 299 sha_digest hash_buf; 300 // 1/q in Fq 301 FqElem montgomery_r = { 302 0x512ccfed, 0x2cd6d224, 0xed67f57d, 0xf3239a04, 303 0x118e5b60, 0xb91a0da1, 0x00030f32, 0, 304 }; 305 if ((kSha512 != hashalg) && (kSha256 != hashalg)) { 306 return 0; 307 } 308 FqSet(&three, 3); 309 310 for (hash_salt = 0; hash_salt < 0xFFFFFFFF; ++hash_salt) { 311 tinysha_init(hashalg, &hash_context); 312 313 Uint32Serialize((OctStr32*)&buf, hash_salt); 314 tinysha_update(&hash_context, &buf, sizeof(buf)); 315 tinysha_update(&hash_context, msg, len); 316 317 tinysha_final(hash_buf.digest, &hash_context); 318 319 FqFromHash(&result->x, hash_buf.digest, tinysha_digest_size(&hash_context)); 320 FqSquare(&tmp, &result->x); 321 FqMul(&tmp, &tmp, &result->x); 322 FqAdd(&tmp, &tmp, &three); 323 if (FqSqrt(&result->y, &tmp)) { 324 FqNeg(&tmp, &result->y); 325 // Verify and Non-tiny member use montgomery representation to determine 326 // if negation is needed: this is to be compatible with them 327 FqMul(&montgomery_r, &result->y, &montgomery_r); 328 FqCondSet(&result->y, &tmp, &result->y, montgomery_r.limbs.word[0] & 1); 329 return 1; 330 } 331 } 332 return 0; 333 } 334 335 void EFqCp(EccPointFq* result, EccPointFq const* in) { 336 FqCp(&result->x, &in->x); 337 FqCp(&result->y, &in->y); 338 } 339 340 int EFqEqAffine(EccPointFq const* left, EccPointFq const* right) { 341 return FqEq(&left->x, &right->x) && FqEq(&left->y, &right->y); 342 } 343 344 void EFqCondSet(EccPointJacobiFq* result, EccPointJacobiFq const* true_val, 345 EccPointJacobiFq const* false_val, int truth_val) { 346 FqCondSet(&result->X, &true_val->X, &false_val->X, truth_val); 347 FqCondSet(&result->Y, &true_val->Y, &false_val->Y, truth_val); 348 FqCondSet(&result->Z, &true_val->Z, &false_val->Z, truth_val); 349 } 350 351 void EFqJCp(EccPointJacobiFq* result, EccPointJacobiFq const* in) { 352 FqCp(&result->X, &in->X); 353 FqCp(&result->Y, &in->Y); 354 FqCp(&result->Z, &in->Z); 355 } 356 357 void EFqInf(EccPointJacobiFq* result) { 358 FqSet(&result->X, 0); 359 FqSet(&result->Y, 1); 360 FqSet(&result->Z, 0); 361 } 362 363 int EFqOnCurve(EccPointFq const* in) { 364 // test that Y^2 mod q == (X^3 + a*Z^4*X + b*Z^6) mod q 365 // This simplifies to: Y^2 mod q == (X^3 + 3) mod q 366 // since: Z = 1 367 // a = 0 368 // b = 3 369 FqElem t1; 370 FqElem t2; 371 FqSquare(&t1, &in->x); 372 FqMul(&t2, &in->x, &t1); 373 FqSquare(&t1, &in->y); 374 FqSub(&t1, &t1, &t2); 375 t1.limbs.word[0] -= 3; // check equal to curve b 376 // this operation will not always 377 // result in the same value as T1 - 3 378 // however it will always result in a correct 379 // value for the zero check below 380 return FqIsZero(&t1); 381 } 382 383 int EFqJOnCurve(EccPointJacobiFq const* in) { 384 FqElem fq1; 385 FqElem fq2; 386 387 FqSquare(&fq1, &in->Z); 388 FqSquare(&fq2, &fq1); 389 FqMul(&fq2, &fq2, &fq1); // T2 = Z^6 390 FqAdd(&fq1, &fq2, &fq2); 391 FqAdd(&fq1, &fq1, &fq2); // T1 = 3 * Z^6 392 FqSquare(&fq2, &in->X); 393 FqMul(&fq2, &fq2, &in->X); // T2 = X^3 394 FqAdd(&fq1, &fq1, &fq2); // T1 = X^3 + 3 Z^6 395 FqSquare(&fq2, &in->Y); 396 FqMul(&fq1, &fq1, &in->Z); 397 FqMul(&fq2, &fq2, &in->Z); 398 return FqEq(&fq1, &fq2); // check Y^2 = X^3 + 3 Z^6 399 } 400 401 int EFqJRand(EccPointJacobiFq* result, BitSupplier rnd_func, void* rnd_param) { 402 FqElem fq; 403 do { 404 if (!FqRand(&fq, rnd_func, rnd_param)) { 405 return 0; 406 } 407 } while (!EFqMakePoint((EccPointFq*)result, &fq)); 408 409 FqSet(&result->Z, 1); 410 411 return 1; 412 } 413
