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 EFq2 math 17 /*! \file */ 18 19 #include "epid/member/tiny/math/efq2.h" 20 21 #include "epid/member/tiny/math/fq.h" 22 #include "epid/member/tiny/math/fq2.h" 23 #include "epid/member/tiny/math/mathtypes.h" 24 #include "epid/member/tiny/math/vli.h" 25 26 static void EFq2CondSet(EccPointJacobiFq2* result, 27 EccPointJacobiFq2 const* true_val, 28 EccPointJacobiFq2 const* false_val, int truth_val) { 29 Fq2CondSet(&result->X, &true_val->X, &false_val->X, truth_val); 30 Fq2CondSet(&result->Y, &true_val->Y, &false_val->Y, truth_val); 31 Fq2CondSet(&result->Z, &true_val->Z, &false_val->Z, truth_val); 32 } 33 34 static void EFq2Cp(EccPointJacobiFq2* result, EccPointJacobiFq2 const* in) { 35 Fq2Cp(&result->X, &in->X); 36 Fq2Cp(&result->Y, &in->Y); 37 Fq2Cp(&result->Z, &in->Z); 38 } 39 40 static void EFq2Inf(EccPointJacobiFq2* result) { 41 Fq2Set(&result->X, 0); 42 Fq2Set(&result->Y, 1); 43 Fq2Set(&result->Z, 0); 44 } 45 46 int EFq2IsInf(EccPointJacobiFq2 const* in) { 47 return Fq2IsZero(&in->X) && Fq2IsZero(&in->Z) && (!Fq2IsZero(&in->Y)); 48 } 49 50 void EFq2FromAffine(EccPointJacobiFq2* result, EccPointFq2 const* in) { 51 Fq2Cp(&result->X, &in->x); 52 Fq2Cp(&result->Y, &in->y); 53 Fq2Set(&result->Z, 1); 54 } 55 56 int EFq2ToAffine(EccPointFq2* result, EccPointJacobiFq2 const* in) { 57 Fq2Elem inverted_z; 58 if (EFq2IsInf(in)) { 59 return 0; 60 } 61 Fq2Inv(&inverted_z, &in->Z); 62 Fq2Mul(&result->x, &in->X, &inverted_z); 63 Fq2Mul(&result->x, &result->x, &inverted_z); 64 Fq2Mul(&result->y, &in->Y, &inverted_z); 65 Fq2Mul(&result->y, &result->y, &inverted_z); 66 Fq2Mul(&result->y, &result->y, &inverted_z); 67 return 1; 68 } 69 70 void EFq2Dbl(EccPointJacobiFq2* result, EccPointJacobiFq2 const* in) { 71 Fq2Elem a; 72 Fq2Elem b; 73 // Z3 = 2Z1 74 Fq2Add(&(result->Z), &(in->Z), &(in->Z)); 75 // Z3 = 2*Z1*Y1 76 Fq2Mul(&(result->Z), &(result->Z), &(in->Y)); 77 // A = X1^2 78 Fq2Square(&a, &(in->X)); 79 // B = 2(X1^2) 80 Fq2Add(&b, &a, &a); 81 // B = 3(X1^2) 82 Fq2Add(&b, &b, &a); 83 // A = Y1^2 84 Fq2Square(&a, &(in->Y)); 85 // A = 2*(Y1^2) 86 Fq2Add(&a, &a, &a); 87 // Y3 = 4*(Y1^4) 88 Fq2Square(&(result->Y), &a); 89 // Y3 = 8*(Y1^4) 90 Fq2Add(&(result->Y), &(result->Y), &(result->Y)); 91 // A = 4(Y1^2) 92 Fq2Add(&a, &a, &a); 93 // A = 4(Y1^2)*X1 94 Fq2Mul(&a, &a, &(in->X)); 95 // X3 = B^2 96 Fq2Square(&(result->X), &b); 97 // X3 = (B^2) - A 98 Fq2Sub(&(result->X), &(result->X), &a); 99 // X3 = (B^2) - 2A 100 Fq2Sub(&(result->X), &(result->X), &a); 101 // A = A - X3 102 Fq2Sub(&a, &a, &(result->X)); 103 // A = B*(A-X3) 104 Fq2Mul(&a, &a, &b); 105 // Y3 = B*(A-X3) - 8*(Y1^4) 106 Fq2Sub(&(result->Y), &a, &(result->Y)); 107 } 108 109 void EFq2Add(EccPointJacobiFq2* result, EccPointJacobiFq2 const* left, 110 EccPointJacobiFq2 const* right) { 111 Fq2Elem A; 112 Fq2Elem B; 113 Fq2Elem C; 114 Fq2Elem D; 115 Fq2Elem W; 116 Fq2Elem V; 117 118 if (Fq2IsZero(&left->Z)) { 119 // If P = O, set R = Q and return 120 EFq2Cp(result, right); 121 return; 122 } 123 if (Fq2IsZero(&right->Z)) { 124 // If Q = O, set R = P and return. 125 EFq2Cp(result, left); 126 return; 127 } 128 // A = P.X * Q.Z^2 129 Fq2Square(&C, &right->Z); 130 Fq2Mul(&A, &left->X, &C); 131 // B = Q.X * P.Z^2 132 Fq2Square(&D, &left->Z); 133 Fq2Mul(&B, &right->X, &D); 134 // C = P.Y * Q.Z^3 135 Fq2Mul(&C, &right->Z, &C); 136 Fq2Mul(&C, &left->Y, &C); 137 // D = Q.Y * P.Z^3 138 Fq2Mul(&D, &left->Z, &D); 139 Fq2Mul(&D, &right->Y, &D); 140 // W = B - A 141 Fq2Sub(&W, &B, &A); 142 // V = D - C 143 Fq2Sub(&V, &D, &C); 144 if (Fq2IsZero(&W)) { 145 if (Fq2IsZero(&V)) { 146 EFq2Dbl(result, left); 147 return; 148 } else { 149 EFq2Inf(result); 150 return; 151 } 152 } 153 // R.Z = P.Z * Q.Z * W 154 Fq2Mul(&result->Z, &left->Z, &right->Z); 155 Fq2Mul(&result->Z, &result->Z, &W); 156 // R.X = V^2 - (A + B) * W^2 157 Fq2Square(&result->X, &V); 158 Fq2Add(&B, &A, &B); 159 // Before squaring W save (C * W) to use in compitation of R.Y 160 Fq2Mul(&C, &C, &W); 161 Fq2Square(&W, &W); 162 Fq2Mul(&B, &B, &W); 163 Fq2Sub(&result->X, &result->X, &B); 164 // R.Y = V * (A * W^2 - R.X) - C * W^3 165 Fq2Mul(&A, &A, &W); 166 Fq2Sub(&A, &A, &result->X); 167 Fq2Mul(&result->Y, &V, &A); 168 Fq2Mul(&C, &C, &W); 169 Fq2Sub(&result->Y, &result->Y, &C); 170 } 171 172 void EFq2Neg(EccPointJacobiFq2* result, EccPointJacobiFq2 const* in) { 173 Fq2Cp(&result->X, &in->X); 174 Fq2Neg(&result->Y, &in->Y); 175 Fq2Cp(&result->Z, &in->Z); 176 } 177 178 void EFq2MulSSCM(EccPointJacobiFq2* result, EccPointJacobiFq2 const* left, 179 FpElem const* right) { 180 int position; 181 EccPointJacobiFq2 nv; 182 EccPointJacobiFq2 mv; 183 EFq2Inf(&nv); 184 EFq2Cp(&mv, left); 185 for (position = 32 * NUM_ECC_DIGITS - 1; position >= 0; position--) { 186 EFq2Dbl(&nv, &nv); 187 EFq2Add(&mv, left, &nv); 188 EFq2CondSet(&nv, &mv, &nv, 189 (int)(VliTestBit(&right->limbs, (uint32_t)position))); 190 } 191 EFq2Cp(result, &nv); 192 } 193 194 int EFq2Eq(EccPointJacobiFq2 const* left, EccPointJacobiFq2 const* right) { 195 Fq2Elem t1; 196 Fq2Elem t2; 197 Fq2Elem t3; 198 Fq2Elem t4; 199 200 if (EFq2IsInf(left) && EFq2IsInf(right)) { 201 return 1; 202 } 203 // if either left or right equals to inf return 0 204 if (EFq2IsInf(left) || EFq2IsInf(right)) { 205 return 0; 206 } 207 Fq2Square(&t1, &(left->Z)); 208 Fq2Square(&t2, &(right->Z)); 209 Fq2Mul(&t3, &t1, &(right->X)); 210 Fq2Mul(&t4, &t2, &(left->X)); 211 Fq2Mul(&t1, &t1, &(left->Z)); 212 Fq2Mul(&t2, &t2, &(right->Z)); 213 Fq2Mul(&t1, &t1, &(right->Y)); 214 Fq2Mul(&t2, &t2, &(left->Y)); 215 return Fq2Eq(&t1, &t2) && Fq2Eq(&t3, &t4); 216 } 217 218 int EFq2OnCurve(EccPointFq2 const* in) { 219 // test that Y^2 mod q == (X^3 + a*Z^4*X + b'*Z^6) mod q 220 // This simplifies to: Y^2 mod q == (X^3 + b') mod q 221 // since: Z = 1 222 // a = 0 223 // b = 3 224 Fq2Elem t1; 225 Fq2Elem t2; 226 FqElem three; 227 // Fq2xi 228 Fq2Elem bp = {{{{0x00000002, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 229 0x00000000, 0x00000000, 0x00000000}}}, 230 {{{0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 231 0x00000000, 0x00000000, 0x00000000}}}}; 232 Fq2Elem const* x = &in->x; 233 Fq2Elem const* y = &in->y; 234 235 // b' = b * inv(x1) 236 FqSet(&three, 3); 237 Fq2Inv(&bp, &bp); 238 Fq2MulScalar(&bp, &bp, &three); 239 240 // set t2 = X^3 241 Fq2Square(&t1, x); 242 Fq2Mul(&t2, x, &t1); 243 // set t2 = X^3 + b' 244 Fq2Add(&t2, &t2, &bp); 245 246 // set t1 = Y^2 247 Fq2Square(&t1, y); 248 249 // set t1 = Y^2 - (X^3 + b') 250 Fq2Sub(&t1, &t1, &t2); 251 // return if t1 is zero 252 return Fq2IsZero(&t1); 253 } 254
