1
2 /***************************************************************************
3 *
4 Copyright 2012 CertiVox IOM Ltd. *
5 *
6 This file is part of CertiVox MIRACL Crypto SDK. *
7 *
8 The CertiVox MIRACL Crypto SDK provides developers with an *
9 extensive and efficient set of cryptographic functions. *
10 For further information about its features and functionalities please *
11 refer to http://www.certivox.com *
12 *
13 * The CertiVox MIRACL Crypto SDK is free software: you can *
14 redistribute it and/or modify it under the terms of the *
15 GNU Affero General Public License as published by the *
16 Free Software Foundation, either version 3 of the License, *
17 or (at your option) any later version. *
18 *
19 * The CertiVox MIRACL Crypto SDK is distributed in the hope *
20 that it will be useful, but WITHOUT ANY WARRANTY; without even the *
21 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *
22 See the GNU Affero General Public License for more details. *
23 *
24 * You should have received a copy of the GNU Affero General Public *
25 License along with CertiVox MIRACL Crypto SDK. *
26 If not, see <http://www.gnu.org/licenses/>. *
27 *
28 You can be released from the requirements of the license by purchasing *
29 a commercial license. Buying such a license is mandatory as soon as you *
30 develop commercial activities involving the CertiVox MIRACL Crypto SDK *
31 without disclosing the source code of your own applications, or shipping *
32 the CertiVox MIRACL Crypto SDK with a closed source product. *
33 *
34 ***************************************************************************/
35 /*
36 * MIRACL F_p^3 support functions
37 * mrzzn3.c
38 *
39 * This code assumes p=1 mod 3
40 * Irreducible polynomial is x^3+cnr
41 *
42 * Did you know that 2 is a cnr iff p cannot be written as x^2+27.y^2 ?
43 */
44
45 #include <stdlib.h>
46 #include "miracl.h"
47
zzn3_iszero(zzn3 * x)48 BOOL zzn3_iszero(zzn3 *x)
49 {
50 if (size(x->a)==0 && size(x->b)==0 && size(x->c)==0) return TRUE;
51 return FALSE;
52 }
53
zzn3_isunity(_MIPD_ zzn3 * x)54 BOOL zzn3_isunity(_MIPD_ zzn3 *x)
55 {
56 #ifdef MR_OS_THREADS
57 miracl *mr_mip=get_mip();
58 #endif
59 if (mr_mip->ERNUM || size(x->b)!=0 || size(x->c)!=0) return FALSE;
60
61 if (compare(x->a,mr_mip->one)==0) return TRUE;
62 return FALSE;
63 }
64
zzn3_compare(zzn3 * x,zzn3 * y)65 BOOL zzn3_compare(zzn3 *x,zzn3 *y)
66 {
67 if (mr_compare(x->a,y->a)==0 && mr_compare(x->b,y->b)==0 && mr_compare(x->c,y->c)==0) return TRUE;
68 return FALSE;
69 }
70
zzn3_from_int(_MIPD_ int i,zzn3 * w)71 void zzn3_from_int(_MIPD_ int i,zzn3 *w)
72 {
73 #ifdef MR_OS_THREADS
74 miracl *mr_mip=get_mip();
75 #endif
76 if (mr_mip->ERNUM) return;
77
78 MR_IN(174)
79 convert(_MIPP_ i,mr_mip->w1);
80 nres(_MIPP_ mr_mip->w1,w->a);
81 zero(w->b); zero(w->c);
82 MR_OUT
83 }
84
zzn3_from_ints(_MIPD_ int i,int j,int k,zzn3 * w)85 void zzn3_from_ints(_MIPD_ int i,int j,int k,zzn3 *w)
86 {
87 #ifdef MR_OS_THREADS
88 miracl *mr_mip=get_mip();
89 #endif
90 if (mr_mip->ERNUM) return;
91
92 MR_IN(175)
93 convert(_MIPP_ i,mr_mip->w1);
94 nres(_MIPP_ mr_mip->w1,w->a);
95 convert(_MIPP_ j,mr_mip->w1);
96 nres(_MIPP_ mr_mip->w1,w->b);
97 convert(_MIPP_ k,mr_mip->w1);
98 nres(_MIPP_ mr_mip->w1,w->c);
99
100 MR_OUT
101 }
102
zzn3_from_zzns(big x,big y,big z,zzn3 * w)103 void zzn3_from_zzns(big x,big y,big z,zzn3 *w)
104 {
105 copy(x,w->a);
106 copy(y,w->b);
107 copy(z,w->c);
108 }
109
zzn3_from_bigs(_MIPD_ big x,big y,big z,zzn3 * w)110 void zzn3_from_bigs(_MIPD_ big x,big y,big z,zzn3 *w)
111 {
112 #ifdef MR_OS_THREADS
113 miracl *mr_mip=get_mip();
114 #endif
115 if (mr_mip->ERNUM) return;
116
117 MR_IN(176)
118 nres(_MIPP_ x,w->a);
119 nres(_MIPP_ y,w->b);
120 nres(_MIPP_ z,w->c);
121 MR_OUT
122 }
123
zzn3_from_zzn(big x,zzn3 * w)124 void zzn3_from_zzn(big x,zzn3 *w)
125 {
126 copy(x,w->a);
127 zero(w->b); zero(w->c);
128 }
129
zzn3_from_zzn_1(big x,zzn3 * w)130 void zzn3_from_zzn_1(big x,zzn3 *w)
131 {
132 copy(x,w->b);
133 zero(w->a); zero(w->c);
134 }
135
zzn3_from_zzn_2(big x,zzn3 * w)136 void zzn3_from_zzn_2(big x,zzn3 *w)
137 {
138 copy(x,w->c);
139 zero(w->a); zero(w->b);
140 }
141
zzn3_from_big(_MIPD_ big x,zzn3 * w)142 void zzn3_from_big(_MIPD_ big x, zzn3 *w)
143 {
144 #ifdef MR_OS_THREADS
145 miracl *mr_mip=get_mip();
146 #endif
147 if (mr_mip->ERNUM) return;
148
149 MR_IN(177)
150 nres(_MIPP_ x,w->a);
151 zero(w->b); zero(w->c);
152 MR_OUT
153 }
154
zzn3_copy(zzn3 * x,zzn3 * w)155 void zzn3_copy(zzn3 *x,zzn3 *w)
156 {
157 if (x==w) return;
158 copy(x->a,w->a);
159 copy(x->b,w->b);
160 copy(x->c,w->c);
161 }
162
zzn3_zero(zzn3 * w)163 void zzn3_zero(zzn3 *w)
164 {
165 zero(w->a);
166 zero(w->b);
167 zero(w->c);
168 }
169
zzn3_negate(_MIPD_ zzn3 * x,zzn3 * w)170 void zzn3_negate(_MIPD_ zzn3 *x,zzn3 *w)
171 {
172 #ifdef MR_OS_THREADS
173 miracl *mr_mip=get_mip();
174 #endif
175 if (mr_mip->ERNUM) return;
176 MR_IN(177)
177 zzn3_copy(x,w);
178 nres_negate(_MIPP_ w->a,w->a);
179 nres_negate(_MIPP_ w->b,w->b);
180 nres_negate(_MIPP_ w->c,w->c);
181 MR_OUT
182 }
183
zzn3_powq(_MIPD_ zzn3 * x,zzn3 * w)184 void zzn3_powq(_MIPD_ zzn3 *x,zzn3 *w)
185 { /* sru - precalculated sixth root of unity */
186 #ifdef MR_OS_THREADS
187 miracl *mr_mip=get_mip();
188 #endif
189 MR_IN(178)
190 zzn3_copy(x,w);
191 nres_modmult(_MIPP_ mr_mip->sru,mr_mip->sru,mr_mip->w1); /* cube root of unity */
192 nres_modmult(_MIPP_ w->b,mr_mip->w1,w->b);
193 nres_modmult(_MIPP_ w->c,mr_mip->w1,w->c);
194 nres_modmult(_MIPP_ w->c,mr_mip->w1,w->c);
195
196 MR_OUT
197 }
198
zzn3_set(_MIPD_ int cnr,big sru)199 void zzn3_set(_MIPD_ int cnr,big sru)
200 {
201 #ifdef MR_OS_THREADS
202 miracl *mr_mip=get_mip();
203 #endif
204 mr_mip->cnr=cnr;
205 nres(_MIPP_ sru,mr_mip->sru);
206 }
207
zzn3_add(_MIPD_ zzn3 * x,zzn3 * y,zzn3 * w)208 void zzn3_add(_MIPD_ zzn3 *x,zzn3 *y,zzn3 *w)
209 {
210 #ifdef MR_OS_THREADS
211 miracl *mr_mip=get_mip();
212 #endif
213 if (mr_mip->ERNUM) return;
214 MR_IN(180)
215 nres_modadd(_MIPP_ x->a,y->a,w->a);
216 nres_modadd(_MIPP_ x->b,y->b,w->b);
217
218 nres_modadd(_MIPP_ x->c,y->c,w->c);
219
220 MR_OUT
221 }
222
zzn3_sadd(_MIPD_ zzn3 * x,big y,zzn3 * w)223 void zzn3_sadd(_MIPD_ zzn3 *x,big y,zzn3 *w)
224 {
225 #ifdef MR_OS_THREADS
226 miracl *mr_mip=get_mip();
227 #endif
228 if (mr_mip->ERNUM) return;
229 MR_IN(181)
230 nres_modadd(_MIPP_ x->a,y,w->a);
231 MR_OUT
232 }
233
zzn3_sub(_MIPD_ zzn3 * x,zzn3 * y,zzn3 * w)234 void zzn3_sub(_MIPD_ zzn3 *x,zzn3 *y,zzn3 *w)
235 {
236 #ifdef MR_OS_THREADS
237 miracl *mr_mip=get_mip();
238 #endif
239 if (mr_mip->ERNUM) return;
240 MR_IN(182)
241 nres_modsub(_MIPP_ x->a,y->a,w->a);
242 nres_modsub(_MIPP_ x->b,y->b,w->b);
243 nres_modsub(_MIPP_ x->c,y->c,w->c);
244 MR_OUT
245 }
246
zzn3_ssub(_MIPD_ zzn3 * x,big y,zzn3 * w)247 void zzn3_ssub(_MIPD_ zzn3 *x,big y,zzn3 *w)
248 {
249 #ifdef MR_OS_THREADS
250 miracl *mr_mip=get_mip();
251 #endif
252 if (mr_mip->ERNUM) return;
253 MR_IN(183)
254 nres_modsub(_MIPP_ x->a,y,w->a);
255 MR_OUT
256 }
257
zzn3_smul(_MIPD_ zzn3 * x,big y,zzn3 * w)258 void zzn3_smul(_MIPD_ zzn3 *x,big y,zzn3 *w)
259 {
260 #ifdef MR_OS_THREADS
261 miracl *mr_mip=get_mip();
262 #endif
263 if (mr_mip->ERNUM) return;
264 MR_IN(184)
265 if (size(x->a)!=0) nres_modmult(_MIPP_ x->a,y,w->a);
266 else zero(w->a);
267 if (size(x->b)!=0) nres_modmult(_MIPP_ x->b,y,w->b);
268 else zero(w->b);
269 if (size(x->c)!=0) nres_modmult(_MIPP_ x->c,y,w->c);
270 else zero(w->c);
271
272 MR_OUT
273 }
274
zzn3_imul(_MIPD_ zzn3 * x,int y,zzn3 * w)275 void zzn3_imul(_MIPD_ zzn3 *x,int y,zzn3 *w)
276 {
277 #ifdef MR_OS_THREADS
278 miracl *mr_mip=get_mip();
279 #endif
280 if (mr_mip->ERNUM) return;
281 MR_IN(185)
282 if (size(x->a)!=0) nres_premult(_MIPP_ x->a,y,w->a);
283 else zero(w->a);
284 if (size(x->b)!=0) nres_premult(_MIPP_ x->b,y,w->b);
285 else zero(w->b);
286 if (size(x->c)!=0) nres_premult(_MIPP_ x->c,y,w->c);
287 else zero(w->c);
288
289 MR_OUT
290 }
291
zzn3_mul(_MIPD_ zzn3 * x,zzn3 * y,zzn3 * w)292 void zzn3_mul(_MIPD_ zzn3 *x,zzn3 *y,zzn3 *w)
293 {
294 #ifdef MR_OS_THREADS
295 miracl *mr_mip=get_mip();
296 #endif
297
298 if (mr_mip->ERNUM) return;
299 MR_IN(186)
300
301 if (x==y)
302 { /* Chung-Hasan SQR2 */
303 nres_modmult(_MIPP_ x->a,x->a,mr_mip->w1);
304 nres_modmult(_MIPP_ x->b,x->c,mr_mip->w2);
305 nres_modadd(_MIPP_ mr_mip->w2,mr_mip->w2,mr_mip->w2);
306 nres_modmult(_MIPP_ x->c,x->c,mr_mip->w3);
307 nres_modmult(_MIPP_ x->a,x->b,mr_mip->w4);
308 nres_modadd(_MIPP_ mr_mip->w4,mr_mip->w4,mr_mip->w4);
309
310 nres_modadd(_MIPP_ x->a,x->b,mr_mip->w5);
311 nres_modadd(_MIPP_ mr_mip->w5,x->c,w->c);
312 nres_modmult(_MIPP_ w->c,w->c,w->c);
313
314 nres_premult(_MIPP_ mr_mip->w2,mr_mip->cnr,w->a);
315 nres_modadd(_MIPP_ mr_mip->w1,w->a,w->a);
316 nres_premult(_MIPP_ mr_mip->w3,mr_mip->cnr,w->b);
317 nres_modadd(_MIPP_ mr_mip->w4,w->b,w->b);
318
319 nres_modsub(_MIPP_ w->c,mr_mip->w1,w->c);
320 nres_modsub(_MIPP_ w->c,mr_mip->w2,w->c);
321 nres_modsub(_MIPP_ w->c,mr_mip->w3,w->c);
322 nres_modsub(_MIPP_ w->c,mr_mip->w4,w->c);
323 }
324 else
325 {
326 nres_modmult(_MIPP_ x->a,y->a,mr_mip->w1); /* Z0 */
327 nres_modmult(_MIPP_ x->b,y->b,mr_mip->w2); /* Z2 */
328 nres_modmult(_MIPP_ x->c,y->c,mr_mip->w3); /* Z4 */
329
330 nres_modadd(_MIPP_ x->a,x->b,mr_mip->w4);
331 nres_modadd(_MIPP_ y->a,y->b,mr_mip->w5);
332 nres_modmult(_MIPP_ mr_mip->w4,mr_mip->w5,mr_mip->w6); /* Z1 */
333 nres_modsub(_MIPP_ mr_mip->w6,mr_mip->w1,mr_mip->w6);
334 nres_modsub(_MIPP_ mr_mip->w6,mr_mip->w2,mr_mip->w6);
335
336 nres_modadd(_MIPP_ x->b,x->c,mr_mip->w4);
337 nres_modadd(_MIPP_ y->b,y->c,mr_mip->w5);
338 nres_modmult(_MIPP_ mr_mip->w4,mr_mip->w5,w->b); /* Z3 */
339
340 nres_modadd(_MIPP_ x->a,x->c,mr_mip->w4);
341 nres_modadd(_MIPP_ y->a,y->c,mr_mip->w5);
342
343 nres_modsub(_MIPP_ w->b,mr_mip->w2,w->b);
344 nres_modsub(_MIPP_ w->b,mr_mip->w3,w->b);
345 nres_premult(_MIPP_ w->b,mr_mip->cnr,w->a);
346
347 nres_modmult(_MIPP_ mr_mip->w4,mr_mip->w5,mr_mip->w4);
348 nres_modadd(_MIPP_ mr_mip->w2,mr_mip->w4,mr_mip->w2);
349 nres_modsub(_MIPP_ mr_mip->w2,mr_mip->w1,mr_mip->w2);
350 nres_modsub(_MIPP_ mr_mip->w2,mr_mip->w3,w->c);
351
352 nres_modadd(_MIPP_ w->a,mr_mip->w1,w->a);
353 nres_premult(_MIPP_ mr_mip->w3,mr_mip->cnr,w->b);
354 nres_modadd(_MIPP_ w->b,mr_mip->w6,w->b);
355 }
356
357 MR_OUT
358 }
359
zzn3_inv(_MIPD_ zzn3 * w)360 void zzn3_inv(_MIPD_ zzn3 *w)
361 {
362 #ifdef MR_OS_THREADS
363 miracl *mr_mip=get_mip();
364 #endif
365 if (mr_mip->ERNUM) return;
366 MR_IN(187)
367
368 nres_modmult(_MIPP_ w->a,w->a,mr_mip->w1);
369 nres_modmult(_MIPP_ w->b,w->c,mr_mip->w2);
370
371 nres_premult(_MIPP_ mr_mip->w2,mr_mip->cnr,mr_mip->w2);
372 nres_modsub(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w3);
373
374 nres_modmult(_MIPP_ w->c,w->c,mr_mip->w1);
375 nres_modmult(_MIPP_ w->a,w->b,mr_mip->w2);
376
377 nres_premult(_MIPP_ mr_mip->w1,mr_mip->cnr,mr_mip->w1);
378 nres_modsub(_MIPP_ mr_mip->w2,mr_mip->w1,mr_mip->w4);
379 nres_negate(_MIPP_ mr_mip->w4,mr_mip->w4);
380
381 nres_modmult(_MIPP_ w->b,w->b,mr_mip->w1);
382 nres_modmult(_MIPP_ w->a,w->c,mr_mip->w2);
383 nres_modsub(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w5);
384
385 nres_modmult(_MIPP_ w->b,mr_mip->w5,mr_mip->w1);
386 nres_modmult(_MIPP_ w->c,mr_mip->w4,mr_mip->w2);
387 nres_modadd(_MIPP_ mr_mip->w2,mr_mip->w1,mr_mip->w2);
388 nres_premult(_MIPP_ mr_mip->w2,mr_mip->cnr,mr_mip->w2);
389 nres_modmult(_MIPP_ w->a,mr_mip->w3,mr_mip->w1);
390 nres_modadd(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w1);
391
392 copy(mr_mip->w3,w->a);
393 copy(mr_mip->w4,w->b);
394 copy(mr_mip->w5,w->c);
395
396 redc(_MIPP_ mr_mip->w1,mr_mip->w6);
397 invmodp(_MIPP_ mr_mip->w6,mr_mip->modulus,mr_mip->w6);
398 nres(_MIPP_ mr_mip->w6,mr_mip->w6);
399
400 nres_modmult(_MIPP_ w->a,mr_mip->w6,w->a);
401 nres_modmult(_MIPP_ w->b,mr_mip->w6,w->b);
402 nres_modmult(_MIPP_ w->c,mr_mip->w6,w->c);
403
404 MR_OUT
405 }
406
407 /* divide zzn3 by 2 */
408
zzn3_div2(_MIPD_ zzn3 * w)409 void zzn3_div2(_MIPD_ zzn3 *w)
410 {
411 #ifdef MR_OS_THREADS
412 miracl *mr_mip=get_mip();
413 #endif
414 if (mr_mip->ERNUM) return;
415 MR_IN(188)
416 copy(w->a,mr_mip->w1);
417 if (remain(_MIPP_ mr_mip->w1,2)!=0)
418 add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
419 subdiv(_MIPP_ mr_mip->w1,2,mr_mip->w1);
420 copy(mr_mip->w1,w->a);
421
422 copy(w->b,mr_mip->w1);
423 if (remain(_MIPP_ mr_mip->w1,2)!=0)
424 add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
425 subdiv(_MIPP_ mr_mip->w1,2,mr_mip->w1);
426 copy(mr_mip->w1,w->b);
427
428 copy(w->c,mr_mip->w1);
429 if (remain(_MIPP_ mr_mip->w1,2)!=0)
430 add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
431 subdiv(_MIPP_ mr_mip->w1,2,mr_mip->w1);
432 copy(mr_mip->w1,w->c);
433
434 MR_OUT
435 }
436
437 /* multiply zzn3 by i */
438
zzn3_timesi(_MIPD_ zzn3 * u)439 void zzn3_timesi(_MIPD_ zzn3 *u)
440 {
441 #ifdef MR_OS_THREADS
442 miracl *mr_mip=get_mip();
443 #endif
444 if (mr_mip->ERNUM) return;
445 MR_IN(189)
446
447 copy(u->a,mr_mip->w1);
448 nres_premult(_MIPP_ u->c,mr_mip->cnr,u->a);
449 copy(u->b,u->c);
450 copy(mr_mip->w1,u->b);
451
452 MR_OUT
453 }
454
455 /* multiply zzn3 by i^2 */
456
zzn3_timesi2(_MIPD_ zzn3 * u)457 void zzn3_timesi2(_MIPD_ zzn3 *u)
458 {
459 #ifdef MR_OS_THREADS
460 miracl *mr_mip=get_mip();
461 #endif
462 if (mr_mip->ERNUM) return;
463 MR_IN(224)
464
465 copy(u->a,mr_mip->w1);
466 nres_premult(_MIPP_ u->b,mr_mip->cnr,u->a);
467 nres_premult(_MIPP_ u->c,mr_mip->cnr,u->b);
468 copy(mr_mip->w1,u->c);
469
470 MR_OUT
471 }
472