|
1 /* ********************************************************************* |
|
2 * |
|
3 * Sun elects to have this file available under and governed by the |
|
4 * Mozilla Public License Version 1.1 ("MPL") (see |
|
5 * http://www.mozilla.org/MPL/ for full license text). For the avoidance |
|
6 * of doubt and subject to the following, Sun also elects to allow |
|
7 * licensees to use this file under the MPL, the GNU General Public |
|
8 * License version 2 only or the Lesser General Public License version |
|
9 * 2.1 only. Any references to the "GNU General Public License version 2 |
|
10 * or later" or "GPL" in the following shall be construed to mean the |
|
11 * GNU General Public License version 2 only. Any references to the "GNU |
|
12 * Lesser General Public License version 2.1 or later" or "LGPL" in the |
|
13 * following shall be construed to mean the GNU Lesser General Public |
|
14 * License version 2.1 only. However, the following notice accompanied |
|
15 * the original version of this file: |
|
16 * |
|
17 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 |
|
18 * |
|
19 * The contents of this file are subject to the Mozilla Public License Version |
|
20 * 1.1 (the "License"); you may not use this file except in compliance with |
|
21 * the License. You may obtain a copy of the License at |
|
22 * http://www.mozilla.org/MPL/ |
|
23 * |
|
24 * Software distributed under the License is distributed on an "AS IS" basis, |
|
25 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License |
|
26 * for the specific language governing rights and limitations under the |
|
27 * License. |
|
28 * |
|
29 * The Original Code is the elliptic curve math library for prime field curves. |
|
30 * |
|
31 * The Initial Developer of the Original Code is |
|
32 * Sun Microsystems, Inc. |
|
33 * Portions created by the Initial Developer are Copyright (C) 2003 |
|
34 * the Initial Developer. All Rights Reserved. |
|
35 * |
|
36 * Contributor(s): |
|
37 * Stephen Fung <fungstep@hotmail.com>, Sun Microsystems Laboratories |
|
38 * |
|
39 * Alternatively, the contents of this file may be used under the terms of |
|
40 * either the GNU General Public License Version 2 or later (the "GPL"), or |
|
41 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), |
|
42 * in which case the provisions of the GPL or the LGPL are applicable instead |
|
43 * of those above. If you wish to allow use of your version of this file only |
|
44 * under the terms of either the GPL or the LGPL, and not to allow others to |
|
45 * use your version of this file under the terms of the MPL, indicate your |
|
46 * decision by deleting the provisions above and replace them with the notice |
|
47 * and other provisions required by the GPL or the LGPL. If you do not delete |
|
48 * the provisions above, a recipient may use your version of this file under |
|
49 * the terms of any one of the MPL, the GPL or the LGPL. |
|
50 * |
|
51 *********************************************************************** */ |
|
52 /* |
|
53 * Copyright 2007 Sun Microsystems, Inc. All rights reserved. |
|
54 * Use is subject to license terms. |
|
55 */ |
|
56 |
|
57 #pragma ident "%Z%%M% %I% %E% SMI" |
|
58 |
|
59 #include "ecp.h" |
|
60 #include "ecl-priv.h" |
|
61 #include "mplogic.h" |
|
62 #ifndef _KERNEL |
|
63 #include <stdlib.h> |
|
64 #endif |
|
65 |
|
66 #define MAX_SCRATCH 6 |
|
67 |
|
68 /* Computes R = 2P. Elliptic curve points P and R can be identical. Uses |
|
69 * Modified Jacobian coordinates. |
|
70 * |
|
71 * Assumes input is already field-encoded using field_enc, and returns |
|
72 * output that is still field-encoded. |
|
73 * |
|
74 */ |
|
75 mp_err |
|
76 ec_GFp_pt_dbl_jm(const mp_int *px, const mp_int *py, const mp_int *pz, |
|
77 const mp_int *paz4, mp_int *rx, mp_int *ry, mp_int *rz, |
|
78 mp_int *raz4, mp_int scratch[], const ECGroup *group) |
|
79 { |
|
80 mp_err res = MP_OKAY; |
|
81 mp_int *t0, *t1, *M, *S; |
|
82 |
|
83 t0 = &scratch[0]; |
|
84 t1 = &scratch[1]; |
|
85 M = &scratch[2]; |
|
86 S = &scratch[3]; |
|
87 |
|
88 #if MAX_SCRATCH < 4 |
|
89 #error "Scratch array defined too small " |
|
90 #endif |
|
91 |
|
92 /* Check for point at infinity */ |
|
93 if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) { |
|
94 /* Set r = pt at infinity by setting rz = 0 */ |
|
95 |
|
96 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz)); |
|
97 goto CLEANUP; |
|
98 } |
|
99 |
|
100 /* M = 3 (px^2) + a*(pz^4) */ |
|
101 MP_CHECKOK(group->meth->field_sqr(px, t0, group->meth)); |
|
102 MP_CHECKOK(group->meth->field_add(t0, t0, M, group->meth)); |
|
103 MP_CHECKOK(group->meth->field_add(t0, M, t0, group->meth)); |
|
104 MP_CHECKOK(group->meth->field_add(t0, paz4, M, group->meth)); |
|
105 |
|
106 /* rz = 2 * py * pz */ |
|
107 MP_CHECKOK(group->meth->field_mul(py, pz, S, group->meth)); |
|
108 MP_CHECKOK(group->meth->field_add(S, S, rz, group->meth)); |
|
109 |
|
110 /* t0 = 2y^2 , t1 = 8y^4 */ |
|
111 MP_CHECKOK(group->meth->field_sqr(py, t0, group->meth)); |
|
112 MP_CHECKOK(group->meth->field_add(t0, t0, t0, group->meth)); |
|
113 MP_CHECKOK(group->meth->field_sqr(t0, t1, group->meth)); |
|
114 MP_CHECKOK(group->meth->field_add(t1, t1, t1, group->meth)); |
|
115 |
|
116 /* S = 4 * px * py^2 = 2 * px * t0 */ |
|
117 MP_CHECKOK(group->meth->field_mul(px, t0, S, group->meth)); |
|
118 MP_CHECKOK(group->meth->field_add(S, S, S, group->meth)); |
|
119 |
|
120 |
|
121 /* rx = M^2 - 2S */ |
|
122 MP_CHECKOK(group->meth->field_sqr(M, rx, group->meth)); |
|
123 MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth)); |
|
124 MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth)); |
|
125 |
|
126 /* ry = M * (S - rx) - t1 */ |
|
127 MP_CHECKOK(group->meth->field_sub(S, rx, S, group->meth)); |
|
128 MP_CHECKOK(group->meth->field_mul(S, M, ry, group->meth)); |
|
129 MP_CHECKOK(group->meth->field_sub(ry, t1, ry, group->meth)); |
|
130 |
|
131 /* ra*z^4 = 2*t1*(apz4) */ |
|
132 MP_CHECKOK(group->meth->field_mul(paz4, t1, raz4, group->meth)); |
|
133 MP_CHECKOK(group->meth->field_add(raz4, raz4, raz4, group->meth)); |
|
134 |
|
135 |
|
136 CLEANUP: |
|
137 return res; |
|
138 } |
|
139 |
|
140 /* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is |
|
141 * (qx, qy, 1). Elliptic curve points P, Q, and R can all be identical. |
|
142 * Uses mixed Modified_Jacobian-affine coordinates. Assumes input is |
|
143 * already field-encoded using field_enc, and returns output that is still |
|
144 * field-encoded. */ |
|
145 mp_err |
|
146 ec_GFp_pt_add_jm_aff(const mp_int *px, const mp_int *py, const mp_int *pz, |
|
147 const mp_int *paz4, const mp_int *qx, |
|
148 const mp_int *qy, mp_int *rx, mp_int *ry, mp_int *rz, |
|
149 mp_int *raz4, mp_int scratch[], const ECGroup *group) |
|
150 { |
|
151 mp_err res = MP_OKAY; |
|
152 mp_int *A, *B, *C, *D, *C2, *C3; |
|
153 |
|
154 A = &scratch[0]; |
|
155 B = &scratch[1]; |
|
156 C = &scratch[2]; |
|
157 D = &scratch[3]; |
|
158 C2 = &scratch[4]; |
|
159 C3 = &scratch[5]; |
|
160 |
|
161 #if MAX_SCRATCH < 6 |
|
162 #error "Scratch array defined too small " |
|
163 #endif |
|
164 |
|
165 /* If either P or Q is the point at infinity, then return the other |
|
166 * point */ |
|
167 if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) { |
|
168 MP_CHECKOK(ec_GFp_pt_aff2jac(qx, qy, rx, ry, rz, group)); |
|
169 MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth)); |
|
170 MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth)); |
|
171 MP_CHECKOK(group->meth-> |
|
172 field_mul(raz4, &group->curvea, raz4, group->meth)); |
|
173 goto CLEANUP; |
|
174 } |
|
175 if (ec_GFp_pt_is_inf_aff(qx, qy) == MP_YES) { |
|
176 MP_CHECKOK(mp_copy(px, rx)); |
|
177 MP_CHECKOK(mp_copy(py, ry)); |
|
178 MP_CHECKOK(mp_copy(pz, rz)); |
|
179 MP_CHECKOK(mp_copy(paz4, raz4)); |
|
180 goto CLEANUP; |
|
181 } |
|
182 |
|
183 /* A = qx * pz^2, B = qy * pz^3 */ |
|
184 MP_CHECKOK(group->meth->field_sqr(pz, A, group->meth)); |
|
185 MP_CHECKOK(group->meth->field_mul(A, pz, B, group->meth)); |
|
186 MP_CHECKOK(group->meth->field_mul(A, qx, A, group->meth)); |
|
187 MP_CHECKOK(group->meth->field_mul(B, qy, B, group->meth)); |
|
188 |
|
189 /* C = A - px, D = B - py */ |
|
190 MP_CHECKOK(group->meth->field_sub(A, px, C, group->meth)); |
|
191 MP_CHECKOK(group->meth->field_sub(B, py, D, group->meth)); |
|
192 |
|
193 /* C2 = C^2, C3 = C^3 */ |
|
194 MP_CHECKOK(group->meth->field_sqr(C, C2, group->meth)); |
|
195 MP_CHECKOK(group->meth->field_mul(C, C2, C3, group->meth)); |
|
196 |
|
197 /* rz = pz * C */ |
|
198 MP_CHECKOK(group->meth->field_mul(pz, C, rz, group->meth)); |
|
199 |
|
200 /* C = px * C^2 */ |
|
201 MP_CHECKOK(group->meth->field_mul(px, C2, C, group->meth)); |
|
202 /* A = D^2 */ |
|
203 MP_CHECKOK(group->meth->field_sqr(D, A, group->meth)); |
|
204 |
|
205 /* rx = D^2 - (C^3 + 2 * (px * C^2)) */ |
|
206 MP_CHECKOK(group->meth->field_add(C, C, rx, group->meth)); |
|
207 MP_CHECKOK(group->meth->field_add(C3, rx, rx, group->meth)); |
|
208 MP_CHECKOK(group->meth->field_sub(A, rx, rx, group->meth)); |
|
209 |
|
210 /* C3 = py * C^3 */ |
|
211 MP_CHECKOK(group->meth->field_mul(py, C3, C3, group->meth)); |
|
212 |
|
213 /* ry = D * (px * C^2 - rx) - py * C^3 */ |
|
214 MP_CHECKOK(group->meth->field_sub(C, rx, ry, group->meth)); |
|
215 MP_CHECKOK(group->meth->field_mul(D, ry, ry, group->meth)); |
|
216 MP_CHECKOK(group->meth->field_sub(ry, C3, ry, group->meth)); |
|
217 |
|
218 /* raz4 = a * rz^4 */ |
|
219 MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth)); |
|
220 MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth)); |
|
221 MP_CHECKOK(group->meth-> |
|
222 field_mul(raz4, &group->curvea, raz4, group->meth)); |
|
223 CLEANUP: |
|
224 return res; |
|
225 } |
|
226 |
|
227 /* Computes R = nP where R is (rx, ry) and P is the base point. Elliptic |
|
228 * curve points P and R can be identical. Uses mixed Modified-Jacobian |
|
229 * co-ordinates for doubling and Chudnovsky Jacobian coordinates for |
|
230 * additions. Assumes input is already field-encoded using field_enc, and |
|
231 * returns output that is still field-encoded. Uses 5-bit window NAF |
|
232 * method (algorithm 11) for scalar-point multiplication from Brown, |
|
233 * Hankerson, Lopez, Menezes. Software Implementation of the NIST Elliptic |
|
234 * Curves Over Prime Fields. */ |
|
235 mp_err |
|
236 ec_GFp_pt_mul_jm_wNAF(const mp_int *n, const mp_int *px, const mp_int *py, |
|
237 mp_int *rx, mp_int *ry, const ECGroup *group) |
|
238 { |
|
239 mp_err res = MP_OKAY; |
|
240 mp_int precomp[16][2], rz, tpx, tpy; |
|
241 mp_int raz4; |
|
242 mp_int scratch[MAX_SCRATCH]; |
|
243 signed char *naf = NULL; |
|
244 int i, orderBitSize; |
|
245 |
|
246 MP_DIGITS(&rz) = 0; |
|
247 MP_DIGITS(&raz4) = 0; |
|
248 MP_DIGITS(&tpx) = 0; |
|
249 MP_DIGITS(&tpy) = 0; |
|
250 for (i = 0; i < 16; i++) { |
|
251 MP_DIGITS(&precomp[i][0]) = 0; |
|
252 MP_DIGITS(&precomp[i][1]) = 0; |
|
253 } |
|
254 for (i = 0; i < MAX_SCRATCH; i++) { |
|
255 MP_DIGITS(&scratch[i]) = 0; |
|
256 } |
|
257 |
|
258 ARGCHK(group != NULL, MP_BADARG); |
|
259 ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG); |
|
260 |
|
261 /* initialize precomputation table */ |
|
262 MP_CHECKOK(mp_init(&tpx, FLAG(n))); |
|
263 MP_CHECKOK(mp_init(&tpy, FLAG(n)));; |
|
264 MP_CHECKOK(mp_init(&rz, FLAG(n))); |
|
265 MP_CHECKOK(mp_init(&raz4, FLAG(n))); |
|
266 |
|
267 for (i = 0; i < 16; i++) { |
|
268 MP_CHECKOK(mp_init(&precomp[i][0], FLAG(n))); |
|
269 MP_CHECKOK(mp_init(&precomp[i][1], FLAG(n))); |
|
270 } |
|
271 for (i = 0; i < MAX_SCRATCH; i++) { |
|
272 MP_CHECKOK(mp_init(&scratch[i], FLAG(n))); |
|
273 } |
|
274 |
|
275 /* Set out[8] = P */ |
|
276 MP_CHECKOK(mp_copy(px, &precomp[8][0])); |
|
277 MP_CHECKOK(mp_copy(py, &precomp[8][1])); |
|
278 |
|
279 /* Set (tpx, tpy) = 2P */ |
|
280 MP_CHECKOK(group-> |
|
281 point_dbl(&precomp[8][0], &precomp[8][1], &tpx, &tpy, |
|
282 group)); |
|
283 |
|
284 /* Set 3P, 5P, ..., 15P */ |
|
285 for (i = 8; i < 15; i++) { |
|
286 MP_CHECKOK(group-> |
|
287 point_add(&precomp[i][0], &precomp[i][1], &tpx, &tpy, |
|
288 &precomp[i + 1][0], &precomp[i + 1][1], |
|
289 group)); |
|
290 } |
|
291 |
|
292 /* Set -15P, -13P, ..., -P */ |
|
293 for (i = 0; i < 8; i++) { |
|
294 MP_CHECKOK(mp_copy(&precomp[15 - i][0], &precomp[i][0])); |
|
295 MP_CHECKOK(group->meth-> |
|
296 field_neg(&precomp[15 - i][1], &precomp[i][1], |
|
297 group->meth)); |
|
298 } |
|
299 |
|
300 /* R = inf */ |
|
301 MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz)); |
|
302 |
|
303 orderBitSize = mpl_significant_bits(&group->order); |
|
304 |
|
305 /* Allocate memory for NAF */ |
|
306 #ifdef _KERNEL |
|
307 naf = (signed char *) kmem_alloc((orderBitSize + 1), FLAG(n)); |
|
308 #else |
|
309 naf = (signed char *) malloc(sizeof(signed char) * (orderBitSize + 1)); |
|
310 if (naf == NULL) { |
|
311 res = MP_MEM; |
|
312 goto CLEANUP; |
|
313 } |
|
314 #endif |
|
315 |
|
316 /* Compute 5NAF */ |
|
317 ec_compute_wNAF(naf, orderBitSize, n, 5); |
|
318 |
|
319 /* wNAF method */ |
|
320 for (i = orderBitSize; i >= 0; i--) { |
|
321 /* R = 2R */ |
|
322 ec_GFp_pt_dbl_jm(rx, ry, &rz, &raz4, rx, ry, &rz, |
|
323 &raz4, scratch, group); |
|
324 if (naf[i] != 0) { |
|
325 ec_GFp_pt_add_jm_aff(rx, ry, &rz, &raz4, |
|
326 &precomp[(naf[i] + 15) / 2][0], |
|
327 &precomp[(naf[i] + 15) / 2][1], rx, ry, |
|
328 &rz, &raz4, scratch, group); |
|
329 } |
|
330 } |
|
331 |
|
332 /* convert result S to affine coordinates */ |
|
333 MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, group)); |
|
334 |
|
335 CLEANUP: |
|
336 for (i = 0; i < MAX_SCRATCH; i++) { |
|
337 mp_clear(&scratch[i]); |
|
338 } |
|
339 for (i = 0; i < 16; i++) { |
|
340 mp_clear(&precomp[i][0]); |
|
341 mp_clear(&precomp[i][1]); |
|
342 } |
|
343 mp_clear(&tpx); |
|
344 mp_clear(&tpy); |
|
345 mp_clear(&rz); |
|
346 mp_clear(&raz4); |
|
347 #ifdef _KERNEL |
|
348 kmem_free(naf, (orderBitSize + 1)); |
|
349 #else |
|
350 free(naf); |
|
351 #endif |
|
352 return res; |
|
353 } |