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 Fq12 math 17 /*! \file */ 18 19 #include "epid/member/tiny/math/fq12.h" 20 21 #include "epid/member/tiny/math/fq.h" 22 #include "epid/member/tiny/math/fq2.h" 23 #include "epid/member/tiny/math/fq6.h" 24 #include "epid/member/tiny/math/mathtypes.h" 25 #include "epid/member/tiny/math/vli.h" 26 #include "epid/member/tiny/stdlib/tiny_stdlib.h" 27 28 static void Fq12MulScalar(Fq12Elem* result, Fq12Elem const* left, 29 Fq6Elem const* right) { 30 Fq6Mul(&result->z0, &left->z0, right); 31 Fq6Mul(&result->z1, &left->z1, right); 32 } 33 34 static void Fq4Square(Fq2Elem* out0, Fq2Elem* out1, Fq2Elem const* in0, 35 Fq2Elem const* in1) { 36 Fq2Elem tmp; 37 Fq2Elem* temp = &tmp; 38 Fq2Square(temp, in1); 39 Fq2Add(out1, in0, in1); 40 Fq2Square(out0, in0); 41 Fq2Square(out1, out1); 42 Fq2Sub(out1, out1, temp); 43 Fq2Sub(out1, out1, out0); 44 Fq2MulXi(temp, temp); 45 Fq2Add(out0, out0, temp); 46 } 47 48 static void Fq12CondSet(Fq12Elem* result, Fq12Elem const* true_val, 49 Fq12Elem const* false_val, int truth_val) { 50 Fq6CondSet(&result->z0, &true_val->z0, &false_val->z0, truth_val); 51 Fq6CondSet(&result->z1, &true_val->z1, &false_val->z1, truth_val); 52 } 53 54 void Fq12Add(Fq12Elem* result, Fq12Elem const* left, Fq12Elem const* right) { 55 Fq6Add(&result->z0, &left->z0, &right->z0); 56 Fq6Add(&result->z1, &left->z1, &right->z1); 57 } 58 59 void Fq12Sub(Fq12Elem* result, Fq12Elem const* left, Fq12Elem const* right) { 60 Fq6Sub(&result->z0, &left->z0, &right->z0); 61 Fq6Sub(&result->z1, &left->z1, &right->z1); 62 } 63 64 void Fq12Square(Fq12Elem* result, Fq12Elem const* in) { 65 Fq6Elem tmpa; 66 Fq6Elem* temp_a = &tmpa; 67 Fq6Square(temp_a, &in->z1); 68 Fq6Add(&result->z1, &in->z0, &in->z1); 69 Fq6Square(&result->z0, &in->z0); 70 Fq6Square(&result->z1, &result->z1); 71 Fq6Sub(&result->z1, &result->z1, (&result->z0)); 72 Fq6Sub(&result->z1, &result->z1, temp_a); 73 Fq6MulV(temp_a, temp_a); 74 Fq6Add((&result->z0), (&result->z0), temp_a); 75 } 76 77 void Fq12Mul(Fq12Elem* result, Fq12Elem const* left, Fq12Elem const* right) { 78 Fq6Elem A; 79 Fq6Elem B; 80 Fq6Elem* t0 = &A; 81 Fq6Elem* t1 = &B; 82 83 Fq6Add(t0, &left->z0, &left->z1); 84 Fq6Add(t1, &right->z0, &right->z1); 85 Fq6Mul(t0, t0, t1); 86 Fq6Mul(&result->z0, &left->z0, &right->z0); 87 Fq6Sub(t0, t0, &result->z0); 88 Fq6Mul(t1, &left->z1, &right->z1); 89 Fq6Sub(&result->z1, t0, t1); 90 Fq6MulV(t1, t1); 91 Fq6Add(&result->z0, &result->z0, t1); 92 } 93 94 void Fq12Inv(Fq12Elem* result, Fq12Elem const* in) { 95 Fq12Elem tmp3; 96 Fq12Elem tmp4; 97 Fq12Elem* const temp3 = &tmp3; 98 Fq12Elem* const temp4 = &tmp4; 99 Fq12Conj(temp3, in); 100 Fq12Mul(temp4, temp3, in); 101 Fq6Inv(&temp4->z0, &temp4->z0); 102 Fq12MulScalar(result, temp3, &temp4->z0); 103 } 104 105 void Fq12Neg(Fq12Elem* result, Fq12Elem const* in) { 106 Fq6Neg(&result->z0, &in->z0); 107 Fq6Neg(&result->z1, &in->z1); 108 } 109 110 void Fq12Set(Fq12Elem* result, uint32_t val) { 111 Fq12Clear(result); 112 FqSet(&(*result).z0.y0.x0, val); 113 } 114 115 void Fq12Exp(Fq12Elem* result, Fq12Elem const* base, VeryLargeInt const* exp) { 116 int i; 117 Fq12Elem tmp, tmp2, *const temp = &tmp, *const temp2 = &tmp2; 118 Fq12Clear(temp); 119 temp->z0.y0.x0.limbs.word[0]++; 120 for (i = NUM_ECC_DIGITS * 32 - 1; i >= 0; i--) { 121 Fq12Square(temp, temp); 122 Fq12Mul(temp2, temp, base); 123 124 Fq12CondSet(temp, temp2, temp, 125 (int)((exp->word[i / 32] >> (i & 31)) & (0x1))); 126 } 127 Fq12Cp(result, temp); 128 } 129 130 void Fq12MultiExp(Fq12Elem* result, Fq12Elem const* base0, 131 VeryLargeInt const* exp0, Fq12Elem const* base1, 132 VeryLargeInt const* exp1, Fq12Elem const* base2, 133 VeryLargeInt const* exp2, Fq12Elem const* base3, 134 VeryLargeInt const* exp3) { 135 Fq12Elem tmp; 136 Fq12Exp(result, base0, exp0); 137 Fq12Exp(&tmp, base1, exp1); 138 Fq12Mul(result, result, &tmp); 139 Fq12Exp(&tmp, base2, exp2); 140 Fq12Mul(result, result, &tmp); 141 Fq12Exp(&tmp, base3, exp3); 142 Fq12Mul(result, result, &tmp); 143 } 144 145 int Fq12Eq(Fq12Elem const* left, Fq12Elem const* right) { 146 return Fq6Eq(&left->z0, &right->z0) && Fq6Eq(&left->z0, &right->z0); 147 } 148 149 void Fq12Conj(Fq12Elem* result, Fq12Elem const* in) { 150 Fq6Cp(&result->z0, &in->z0); 151 Fq6Neg(&result->z1, &in->z1); 152 } 153 154 void Fq12ExpCyc(Fq12Elem* result, Fq12Elem const* in, VeryLargeInt const* t) { 155 int i = 0; 156 Fq12Elem ac; 157 Fq12Elem* const acc = ∾ 158 Fq12Cp(acc, in); 159 Fq12Cp(result, in); 160 161 for (i = 61; i >= 0; i--) { 162 Fq12SqCyc(result, result); 163 164 if (VliTestBit(t, (uint32_t)i)) { 165 Fq12Mul(result, result, acc); 166 } 167 } 168 } 169 170 void Fq12SqCyc(Fq12Elem* result, Fq12Elem const* in) { 171 Fq2Elem const* a0 = &(in->z0).y0; 172 Fq2Elem const* a1 = &(in->z1).y0; 173 Fq2Elem const* a2 = &(in->z0).y1; 174 Fq2Elem const* a3 = &(in->z1).y1; 175 Fq2Elem const* a4 = &(in->z0).y2; 176 Fq2Elem const* a5 = &(in->z1).y2; 177 Fq2Elem* e0 = &(result->z0).y0; 178 Fq2Elem* e1 = &(result->z1).y0; 179 Fq2Elem* e2 = &(result->z0).y1; 180 Fq2Elem* e3 = &(result->z1).y1; 181 Fq2Elem* e4 = &(result->z0).y2; 182 Fq2Elem* e5 = &(result->z1).y2; 183 Fq2Elem tmp1; 184 Fq2Elem tmp2; 185 Fq2Elem tmp3; 186 Fq2Elem tmp4; 187 Fq2Elem* temp1 = &tmp1; 188 Fq2Elem* temp2 = &tmp2; 189 Fq2Elem* temp3 = &tmp3; 190 Fq2Elem* temp4 = &tmp4; 191 192 Fq4Square(temp1, temp2, a0, a3); // t00,t11 = sq(a0,a3) 193 Fq2Add(e0, a0, a0); // e0 = 3*t00 - 2*a0 194 Fq2Sub(e0, temp1, e0); 195 Fq2Add(e0, temp1, e0); 196 Fq2Add(e0, temp1, e0); 197 Fq2Add(e3, a3, a3); // e3 = 3*t11 - 2*a3 198 Fq2Add(e3, temp2, e3); 199 Fq2Add(e3, temp2, e3); 200 Fq2Add(e3, temp2, e3); 201 202 Fq4Square(temp1, temp2, a2, a5); // t02, t10 = sq(a2,a5) 203 Fq2MulXi(temp2, temp2); 204 Fq4Square(temp3, temp4, a1, a4); // t01, t12 = sq(a1,a4) 205 206 Fq2Add(e4, a4, a4); 207 Fq2Sub(e4, temp1, e4); 208 Fq2Add(e4, temp1, e4); 209 Fq2Add(e4, temp1, e4); 210 Fq2Add(e1, a1, a1); 211 Fq2Add(e1, temp2, e1); 212 Fq2Add(e1, temp2, e1); 213 Fq2Add(e1, temp2, e1); 214 215 Fq2Add(e2, a2, a2); 216 Fq2Sub(e2, temp3, e2); 217 Fq2Add(e2, temp3, e2); 218 Fq2Add(e2, temp3, e2); 219 Fq2Add(e5, a5, a5); 220 Fq2Add(e5, temp4, e5); 221 Fq2Add(e5, temp4, e5); 222 Fq2Add(e5, temp4, e5); 223 } 224 225 void Fq12MulSpecial(Fq12Elem* result, Fq12Elem const* left, 226 Fq12Elem const* right) { 227 Fq2Elem T3; 228 Fq2Elem* t3 = &T3; 229 Fq2Elem const* b0 = &(right->z0.y0); 230 Fq2Elem const* b1 = &right->z1.y0; 231 Fq2Elem const* b3 = &right->z1.y1; 232 Fq6Elem T0; 233 Fq6Elem T1; 234 Fq6Elem T2; 235 Fq6Elem* t0 = &T0; 236 Fq6Elem* t1 = &T1; 237 Fq6Elem* t2 = &T2; 238 Fq6Elem const* a0 = &left->z0; 239 Fq6Elem const* a1 = &left->z1; 240 Fq6Elem* r0 = &result->z0; 241 Fq6Elem* r1 = &result->z1; 242 243 #if defined(DEBUG) 244 // validate algorithm precondition 245 if (!Fq2IsZero(&right->z0.y1) || !Fq2IsZero(&right->z0.y2) || 246 !Fq2IsZero(&right->z1.y2)) { 247 memset(&result, 0xff, sizeof(result)); 248 return; 249 } 250 #endif // defined(DEBUG) 251 252 Fq6Add(t0, a0, a1); 253 Fq2Add(t3, b0, b1); 254 Fq6MulScalar(t0, t0, t3); 255 256 Fq6MulScalar(t2, a1, b3); 257 Fq6MulV(t2, t2); 258 259 Fq6MulScalar(t1, a1, b1); 260 Fq6Sub(t0, t0, t1); 261 Fq6Add(t2, t2, t1); 262 Fq6MulV(t2, t2); 263 264 Fq6MulScalar(t1, a0, b0); 265 Fq6Add(t2, t2, t1); 266 Fq6Sub(t0, t0, t1); 267 268 Fq6MulScalar(t1, a0, b3); 269 Fq6MulV(t1, t1); 270 Fq6Add(r1, t1, t0); 271 Fq6Cp(r0, t2); 272 } 273 274 void Fq12Cp(Fq12Elem* result, Fq12Elem const* in) { 275 Fq6Cp(&result->z0, &in->z0); 276 Fq6Cp(&result->z1, &in->z1); 277 } 278 279 void Fq12Clear(Fq12Elem* result) { 280 Fq6Clear(&result->z0); 281 Fq6Clear(&result->z1); 282 } 283
