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 Tate pairing 17 /*! \file */ 18 19 #include "epid/member/tiny/math/pairing.h" 20 #include "epid/member/tiny/math/efq2.h" 21 #include "epid/member/tiny/math/fq.h" 22 #include "epid/member/tiny/math/fq12.h" 23 #include "epid/member/tiny/math/fq2.h" 24 #include "epid/member/tiny/math/mathtypes.h" 25 #include "epid/member/tiny/math/vli.h" 26 27 static const VeryLargeInt epid_e = {{0xf2788803, 0x7886dcf9, 0x2dc401c0, 28 0xd77a10ff, 0x27bd9b6f, 0x367ba865, 29 0xaaaa2822, 0x2aaaaaaa}}; 30 static const VeryLargeInt epid_t = {{0x30B0A801, 0x6882F5C0, 0, 0, 0, 0, 0, 0}}; 31 static const Fq2Elem epid_xi = { 32 {{{0x00000002, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 33 0x00000000, 0x00000000}}}, 34 {{{0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 35 0x00000000, 0x00000000}}}}; 36 static const int neg = 1; 37 38 void PairingInit(PairingState* state) { 39 int i; 40 Fq2Exp(&state->g[0][0], &epid_xi, &epid_e); 41 for (i = 1; i < 5; i++) { 42 Fq2Mul(&state->g[0][i], &state->g[0][i - 1], &state->g[0][0]); 43 } 44 for (i = 0; i < 5; i++) { 45 FqSquare(&state->g[1][i].x0, &state->g[0][i].x0); 46 FqSquare(&state->g[1][i].x1, &state->g[0][i].x1); 47 FqAdd(&state->g[1][i].x0, &state->g[1][i].x0, &state->g[1][i].x1); 48 FqClear(&state->g[1][i].x1); 49 Fq2Mul(&state->g[2][i], &state->g[0][i], &state->g[1][i]); 50 } 51 } 52 53 static void piOp(EccPointFq2* Qout, EccPointFq2 const* Qin, int e, 54 PairingState const* scratch) { 55 if (e == 1) { 56 Fq2Conj(&Qout->x, &Qin->x); 57 Fq2Conj(&Qout->y, &Qin->y); 58 } else { 59 Fq2Cp(&Qout->x, &Qin->x); 60 Fq2Cp(&Qout->y, &Qin->y); 61 } 62 Fq2Mul(&Qout->x, &Qout->x, &scratch->g[e - 1][1]); 63 Fq2Mul(&Qout->y, &Qout->y, &scratch->g[e - 1][2]); 64 } 65 66 /* 67 * Computes the Frobenius endomorphism Pout = Pin^(p^e) 68 */ 69 static void frob_op(Fq12Elem* Pout, Fq12Elem const* Pin, int e, 70 PairingState const* state) { 71 if (e == 1 || e == 3) { 72 Fq2Conj(&Pout->z0.y0, &Pin->z0.y0); 73 Fq2Conj(&Pout->z1.y0, &Pin->z1.y0); 74 Fq2Conj(&Pout->z0.y1, &Pin->z0.y1); 75 Fq2Conj(&Pout->z1.y1, &Pin->z1.y1); 76 Fq2Conj(&Pout->z0.y2, &Pin->z0.y2); 77 Fq2Conj(&Pout->z1.y2, &Pin->z1.y2); 78 } else { 79 Fq2Cp(&Pout->z0.y0, &Pin->z0.y0); 80 Fq2Cp(&Pout->z1.y0, &Pin->z1.y0); 81 Fq2Cp(&Pout->z0.y1, &Pin->z0.y1); 82 Fq2Cp(&Pout->z1.y1, &Pin->z1.y1); 83 Fq2Cp(&Pout->z0.y2, &Pin->z0.y2); 84 Fq2Cp(&Pout->z1.y2, &Pin->z1.y2); 85 } 86 Fq2Mul(&Pout->z1.y0, &Pout->z1.y0, &state->g[e - 1][0]); 87 Fq2Mul(&Pout->z0.y1, &Pout->z0.y1, &state->g[e - 1][1]); 88 Fq2Mul(&Pout->z1.y1, &Pout->z1.y1, &state->g[e - 1][2]); 89 Fq2Mul(&Pout->z0.y2, &Pout->z0.y2, &state->g[e - 1][3]); 90 Fq2Mul(&Pout->z1.y2, &Pout->z1.y2, &state->g[e - 1][4]); 91 } 92 93 static void finalExp(Fq12Elem* f, PairingState const* state) { 94 Fq12Elem t3; 95 Fq12Elem t2; 96 Fq12Elem t1; 97 Fq12Elem t0; 98 99 Fq12Conj(&t1, f); 100 Fq12Inv(&t2, f); 101 Fq12Mul(f, &t1, &t2); 102 frob_op(&t2, f, 2, state); 103 Fq12Mul(f, f, &t2); 104 Fq12ExpCyc(&t1, f, &epid_t); 105 if (neg) { 106 Fq12Conj(&t1, &t1); 107 } 108 Fq12ExpCyc(&t3, &t1, &epid_t); 109 if (neg) { 110 Fq12Conj(&t3, &t3); 111 } 112 Fq12ExpCyc(&t0, &t3, &epid_t); 113 if (neg) { 114 Fq12Conj(&t0, &t0); 115 } 116 frob_op(&t2, &t0, 1, state); 117 Fq12Mul(&t2, &t2, &t0); 118 Fq12Conj(&t2, &t2); 119 Fq12SqCyc(&t0, &t2); 120 frob_op(&t2, &t3, 1, state); 121 Fq12Mul(&t2, &t2, &t1); 122 Fq12Conj(&t2, &t2); 123 Fq12Mul(&t0, &t0, &t2); 124 Fq12Conj(&t2, &t3); 125 Fq12Mul(&t0, &t0, &t2); 126 frob_op(&t1, &t1, 1, state); 127 Fq12Conj(&t1, &t1); 128 Fq12Mul(&t1, &t1, &t2); 129 Fq12Mul(&t1, &t1, &t0); 130 frob_op(&t2, &t3, 2, state); 131 Fq12Mul(&t0, &t0, &t2); 132 Fq12SqCyc(&t1, &t1); 133 Fq12Mul(&t1, &t1, &t0); 134 Fq12SqCyc(&t1, &t1); 135 Fq12Conj(&t2, f); 136 Fq12Mul(&t0, &t1, &t2); 137 frob_op(&t2, f, 1, state); 138 Fq12Mul(&t1, &t1, &t2); 139 frob_op(&t2, f, 2, state); 140 Fq12Mul(&t1, &t1, &t2); 141 frob_op(&t2, f, 3, state); 142 Fq12Mul(&t1, &t1, &t2); 143 Fq12SqCyc(&t0, &t0); 144 Fq12Mul(f, &t1, &t0); 145 } 146 147 static void pair_tangent(Fq12Elem* f, Fq2Elem* X, Fq2Elem* Y, Fq2Elem* Z, 148 Fq2Elem* Z2, EccPointFq const* P) { 149 Fq2Mul(&f->z0.y0, X, X); 150 Fq2Add(&f->z0.y2, &f->z0.y0, &f->z0.y0); 151 Fq2Add(&f->z0.y2, &f->z0.y2, &f->z0.y0); 152 Fq2Add(&f->z1.y1, X, &f->z0.y2); 153 Fq2Mul(&f->z1.y1, &f->z1.y1, &f->z1.y1); 154 Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z0.y0); 155 Fq2Mul(&f->z0.y1, Y, Y); 156 Fq2Add(&f->z1.y0, &f->z0.y1, X); 157 Fq2Mul(&f->z1.y0, &f->z1.y0, &f->z1.y0); 158 Fq2Sub(&f->z1.y0, &f->z1.y0, &f->z0.y0); 159 Fq2Mul(&f->z0.y0, &f->z0.y1, &f->z0.y1); 160 Fq2Sub(&f->z1.y0, &f->z1.y0, &f->z0.y0); 161 Fq2Add(&f->z1.y0, &f->z1.y0, &f->z1.y0); 162 Fq2Mul(&f->z1.y2, &f->z0.y2, &f->z0.y2); 163 Fq2Add(Z, Y, Z); 164 Fq2Mul(Z, Z, Z); 165 Fq2Sub(Z, Z, &f->z0.y1); 166 Fq2Sub(Z, Z, Z2); 167 Fq2Add(&f->z0.y1, &f->z0.y1, &f->z0.y1); 168 Fq2Add(&f->z0.y1, &f->z0.y1, &f->z0.y1); 169 Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z1.y2); 170 Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z0.y1); 171 Fq2Sub(X, &f->z1.y2, &f->z1.y0); 172 Fq2Sub(X, X, &f->z1.y0); 173 Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0); 174 Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0); 175 Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0); 176 Fq2Sub(Y, &f->z1.y0, X); 177 Fq2Mul(Y, Y, &f->z0.y2); 178 Fq2Sub(Y, Y, &f->z0.y0); 179 Fq2Mul(&f->z1.y0, &f->z0.y2, Z2); 180 Fq2Neg(&f->z1.y0, &f->z1.y0); 181 Fq2Add(&f->z1.y0, &f->z1.y0, &f->z1.y0); 182 Fq2MulScalar(&f->z1.y0, &f->z1.y0, &P->x); 183 Fq2Mul(&f->z0.y0, Z, Z2); 184 Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0); 185 Fq2MulScalar(&f->z0.y0, &f->z0.y0, &P->y); 186 Fq2Mul(Z2, Z, Z); 187 Fq2Clear(&f->z0.y1); 188 Fq2Clear(&f->z0.y2); 189 Fq2Clear(&f->z1.y2); 190 Fq2Square(Z2, Z); 191 } 192 193 static void pair_line(Fq12Elem* f, Fq2Elem* X, Fq2Elem* Y, Fq2Elem* Z, 194 Fq2Elem* Z2, EccPointFq const* P, EccPointFq2 const* Q) { 195 Fq2Mul(&f->z0.y1, &Q->x, Z2); 196 Fq2Add(&f->z1.y0, &Q->y, Z); 197 Fq2Mul(&f->z1.y0, &f->z1.y0, &f->z1.y0); 198 Fq2Square(&f->z0.y0, &Q->y); 199 Fq2Sub(&f->z1.y0, &f->z1.y0, &f->z0.y0); 200 Fq2Sub(&f->z1.y0, &f->z1.y0, Z2); 201 Fq2Mul(&f->z1.y0, &f->z1.y0, Z2); 202 Fq2Sub(&f->z0.y1, &f->z0.y1, X); 203 Fq2Mul(&f->z0.y2, &f->z0.y1, &f->z0.y1); 204 Fq2Add(Z, Z, &f->z0.y1); 205 Fq2Square(Z, Z); 206 Fq2Sub(Z, Z, Z2); 207 Fq2Sub(Z, Z, &f->z0.y2); 208 Fq2Mul(Z2, Z, Z); 209 Fq2Add(&f->z1.y2, &Q->y, Z); 210 Fq2Mul(&f->z1.y2, &f->z1.y2, &f->z1.y2); 211 Fq2Sub(&f->z1.y2, &f->z1.y2, &f->z0.y0); 212 Fq2Sub(&f->z1.y2, &f->z1.y2, Z2); 213 Fq2Sub(&f->z1.y0, &f->z1.y0, Y); 214 Fq2Sub(&f->z1.y0, &f->z1.y0, Y); 215 Fq2Mul(&f->z1.y1, &f->z1.y0, &Q->x); 216 Fq2Add(&f->z1.y1, &f->z1.y1, &f->z1.y1); 217 Fq2Sub(&f->z1.y1, &f->z1.y1, &f->z1.y2); 218 Fq2Add(&f->z0.y2, &f->z0.y2, &f->z0.y2); 219 Fq2Add(&f->z0.y2, &f->z0.y2, &f->z0.y2); 220 Fq2Mul(&f->z0.y1, &f->z0.y2, &f->z0.y1); 221 Fq2Mul(&f->z0.y2, X, &f->z0.y2); 222 Fq2Mul(X, &f->z1.y0, &f->z1.y0); 223 Fq2Sub(X, X, &f->z0.y1); 224 Fq2Sub(X, X, &f->z0.y2); 225 Fq2Sub(X, X, &f->z0.y2); 226 Fq2Sub(&f->z0.y2, &f->z0.y2, X); 227 Fq2Mul(&f->z0.y2, &f->z0.y2, &f->z1.y0); 228 Fq2Mul(&f->z0.y1, Y, &f->z0.y1); 229 Fq2Add(&f->z0.y1, &f->z0.y1, &f->z0.y1); 230 Fq2Sub(Y, &f->z0.y2, &f->z0.y1); 231 Fq2MulScalar(&f->z0.y0, Z, &P->y); 232 Fq2Add(&f->z0.y0, &f->z0.y0, &f->z0.y0); 233 Fq2Neg(&f->z1.y0, &f->z1.y0); 234 Fq2MulScalar(&f->z1.y0, &f->z1.y0, &P->x); 235 Fq2Add(&f->z1.y0, &f->z1.y0, &f->z1.y0); 236 Fq2Clear(&f->z0.y1); 237 Fq2Clear(&f->z0.y2); 238 Fq2Clear(&f->z1.y2); 239 } 240 241 void PairingCompute(Fq12Elem* d, EccPointFq const* P, EccPointFq2 const* Q, 242 PairingState const* state) { 243 Fq2Elem X; 244 Fq2Elem Y; 245 Fq2Elem Z; 246 Fq2Elem Z2; 247 EccPointFq2 Qp; 248 Fq12Elem f; 249 VeryLargeInt s; 250 const VeryLargeInt two = {{2}}; 251 uint32_t i; 252 253 VliAdd(&s, &epid_t, &epid_t); // s = 2*t 254 VliAdd(&s, &s, &epid_t); // s = 3*t 255 VliAdd(&s, &s, &s); // s = 6*t 256 if (neg) { 257 VliSub(&s, &s, &two); 258 } else { 259 VliAdd(&s, &s, &two); 260 } 261 Fq2Cp(&X, &Q->x); 262 Fq2Cp(&Y, &Q->y); 263 Fq2Set(&Z, 1); 264 Fq2Set(&Z2, 1); 265 Fq12Set(d, 1); 266 267 Fq12Clear(&f); 268 // s has 66 bits, 0 through 65, so starting point is bit 64 269 i = 65; 270 while (i > 0) { 271 i -= 1; 272 pair_tangent(&f, &X, &Y, &Z, &Z2, P); 273 Fq12Square(d, d); 274 Fq12MulSpecial(d, d, &f); 275 if (VliTestBit(&s, i)) { 276 pair_line(&f, &X, &Y, &Z, &Z2, P, Q); 277 Fq12MulSpecial(d, d, &f); 278 } 279 } 280 if (neg) { 281 Fq2Neg(&Y, &Y); 282 Fq12Conj(d, d); 283 } 284 piOp(&Qp, Q, 1, state); 285 pair_line(&f, &X, &Y, &Z, &Z2, P, &Qp); 286 Fq12MulSpecial(d, d, &f); 287 piOp(&Qp, Q, 2, state); 288 Fq2Neg(&Qp.y, &Qp.y); 289 pair_line(&f, &X, &Y, &Z, &Z2, P, &Qp); 290 Fq12MulSpecial(d, d, &f); 291 finalExp(d, state); 292 // s doesn't have secret information; no need to clear it. 293 Fq12Clear(&f); 294 Fq2Clear(&X); 295 Fq2Clear(&Y); 296 Fq2Clear(&Z); 297 Fq2Clear(&Z2); 298 Fq2Clear(&Qp.x); 299 Fq2Clear(&Qp.y); 300 } 301
