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^2 support functions
37 * mrzzn2b.c
38 */
39
40 #include <stdlib.h>
41 #include "miracl.h"
42
zzn2_qr(_MIPD_ zzn2 * u)43 BOOL zzn2_qr(_MIPD_ zzn2 *u)
44 {
45 int j;
46 #ifdef MR_OS_THREADS
47 miracl *mr_mip=get_mip();
48 #endif
49
50 if (mr_mip->ERNUM) return FALSE;
51 if (zzn2_iszero(u)) return TRUE;
52 if (size(u->b)==0) return TRUE;
53
54 if (mr_mip->qnr==-1 && size(u->a)==0) return TRUE;
55
56
57 MR_IN(203)
58
59 nres_modmult(_MIPP_ u->b,u->b,mr_mip->w1);
60 if (mr_mip->qnr==-2) nres_modadd(_MIPP_ mr_mip->w1,mr_mip->w1,mr_mip->w1);
61 nres_modmult(_MIPP_ u->a,u->a,mr_mip->w2);
62 nres_modadd(_MIPP_ mr_mip->w1,mr_mip->w2,mr_mip->w1);
63 redc(_MIPP_ mr_mip->w1,mr_mip->w1);
64 j=jack(_MIPP_ mr_mip->w1,mr_mip->modulus);
65
66 MR_OUT
67 if (j==1) return TRUE;
68 return FALSE;
69 }
70
zzn2_sqrt(_MIPD_ zzn2 * u,zzn2 * w)71 BOOL zzn2_sqrt(_MIPD_ zzn2 *u,zzn2 *w)
72 { /* sqrt(a+ib) = sqrt(a+sqrt(a*a-n*b*b)/2)+ib/(2*sqrt(a+sqrt(a*a-n*b*b)/2))
73 where i*i=n */
74 #ifdef MR_OS_THREADS
75 miracl *mr_mip=get_mip();
76 #endif
77 if (mr_mip->ERNUM) return FALSE;
78
79 zzn2_copy(u,w);
80 if (zzn2_iszero(w)) return TRUE;
81
82 MR_IN(204)
83
84 if (size(w->b)==0)
85 {
86 if (!nres_sqroot(_MIPP_ w->a,mr_mip->w15))
87 {
88 nres_negate(_MIPP_ w->a,w->b);
89 zero(w->a);
90 if (mr_mip->qnr==-2) nres_div2(_MIPP_ w->b,w->b);
91 nres_sqroot(_MIPP_ w->b,w->b);
92 }
93 else
94 copy(mr_mip->w15,w->a);
95
96 MR_OUT
97 return TRUE;
98 }
99
100 if (mr_mip->qnr==-1 && size(w->a)==0)
101 {
102 nres_div2(_MIPP_ w->b,w->b);
103 if (nres_sqroot(_MIPP_ w->b,mr_mip->w15))
104 {
105 copy(mr_mip->w15,w->b);
106 copy(w->b,w->a);
107 }
108 else
109 {
110 nres_negate(_MIPP_ w->b,w->b);
111 nres_sqroot(_MIPP_ w->b,w->b);
112 nres_negate(_MIPP_ w->b,w->a);
113 }
114
115 MR_OUT
116 return TRUE;
117 }
118
119 nres_modmult(_MIPP_ w->b,w->b,mr_mip->w7);
120 if (mr_mip->qnr==-2) nres_modadd(_MIPP_ mr_mip->w7,mr_mip->w7,mr_mip->w7);
121 nres_modmult(_MIPP_ w->a,w->a,mr_mip->w1);
122 nres_modadd(_MIPP_ mr_mip->w7,mr_mip->w1,mr_mip->w7);
123
124 if (!nres_sqroot(_MIPP_ mr_mip->w7,mr_mip->w7)) /* s=w7 */
125 {
126 zzn2_zero(w);
127 MR_OUT
128 return FALSE;
129 }
130
131 nres_modadd(_MIPP_ w->a,mr_mip->w7,mr_mip->w15);
132 nres_div2(_MIPP_ mr_mip->w15,mr_mip->w15);
133
134 if (!nres_sqroot(_MIPP_ mr_mip->w15,mr_mip->w15))
135 {
136
137 nres_modsub(_MIPP_ w->a,mr_mip->w7,mr_mip->w15);
138 nres_div2(_MIPP_ mr_mip->w15,mr_mip->w15);
139 if (!nres_sqroot(_MIPP_ mr_mip->w15,mr_mip->w15))
140 {
141 zzn2_zero(w);
142 MR_OUT
143 return FALSE;
144 }
145 }
146
147 copy(mr_mip->w15,w->a);
148 nres_modadd(_MIPP_ mr_mip->w15,mr_mip->w15,mr_mip->w15);
149 nres_moddiv(_MIPP_ w->b,mr_mip->w15,w->b);
150
151 MR_OUT
152 return TRUE;
153 }
154
155 /* y=1/x, z=1/w
156
157 BOOL zzn2_double_inverse(_MIPD_ zzn2 *x,zzn2 *y,zzn2 *w,zzn2 *z)
158 {
159 zzn2 t1,t2;
160 #ifdef MR_OS_THREADS
161 miracl *mr_mip=get_mip();
162 #endif
163 MR_IN(214)
164
165 t1.a=mr_mip->w8;
166 t1.b=mr_mip->w9;
167 t2.a=mr_mip->w10;
168 t2.b=mr_mip->w11;
169
170 zzn2_mul(_MIPP_ x,w,&t1);
171 if (zzn2_iszero(_MIPP_ &t1))
172 {
173 mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
174 MR_OUT
175 return FALSE;
176 }
177 zzn2_inv(_MIPP_ &t1);
178
179 zzn2_mul(_MIPP_ &w,&t1,&t2);
180 zzn2_mul(_MIPP_ &x,&t1,&z);
181 zzn2_copy(&t2,&y);
182
183 MR_OUT
184 return TRUE;
185
186 }
187 */
188
189 /* find w[i]=1/x[i] mod n, for i=0 to m-1 *
190 * x and w MUST be distinct */
191
zzn2_multi_inverse(_MIPD_ int m,zzn2 * x,zzn2 * w)192 BOOL zzn2_multi_inverse(_MIPD_ int m,zzn2 *x,zzn2 *w)
193 {
194 int i;
195 zzn2 t1,t2;
196 #ifdef MR_OS_THREADS
197 miracl *mr_mip=get_mip();
198 #endif
199 if (m==0) return TRUE;
200 if (m<0) return FALSE;
201 MR_IN(214)
202
203 if (x==w)
204 {
205 mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
206 MR_OUT
207 return FALSE;
208 }
209
210 if (m==1)
211 {
212 zzn2_copy(&x[0],&w[0]);
213 zzn2_inv(_MIPP_ &w[0]);
214
215 MR_OUT
216 return TRUE;
217 }
218
219 zzn2_from_int(_MIPP_ 1,&w[0]);
220 zzn2_copy(&x[0],&w[1]);
221
222 for (i=2;i<m;i++)
223 {
224 if (zzn2_isunity(_MIPP_ &x[i-1]))
225 zzn2_copy(&w[i-1],&w[i]);
226 else
227 zzn2_mul(_MIPP_ &w[i-1],&x[i-1],&w[i]);
228 }
229
230 t1.a=mr_mip->w8;
231 t1.b=mr_mip->w9;
232 t2.a=mr_mip->w10;
233 t2.b=mr_mip->w11;
234
235 zzn2_mul(_MIPP_ &w[m-1],&x[m-1],&t1);
236 if (zzn2_iszero(&t1))
237 {
238 mr_berror(_MIPP_ MR_ERR_DIV_BY_ZERO);
239 MR_OUT
240 return FALSE;
241 }
242
243 zzn2_inv(_MIPP_ &t1);
244
245 zzn2_copy(&x[m-1],&t2);
246 zzn2_mul(_MIPP_ &w[m-1],&t1,&w[m-1]);
247
248 for (i=m-2;;i--)
249 {
250 if (i==0)
251 {
252 zzn2_mul(_MIPP_ &t2,&t1,&w[0]);
253 break;
254 }
255 zzn2_mul(_MIPP_ &w[i],&t2,&w[i]);
256 zzn2_mul(_MIPP_ &w[i],&t1,&w[i]);
257 if (!zzn2_isunity(_MIPP_ &x[i])) zzn2_mul(_MIPP_ &t2,&x[i],&t2);
258 }
259
260 MR_OUT
261 return TRUE;
262 }
263
264