1 /*
2 * ***** BEGIN LICENSE BLOCK *****
3 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4 *
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 * http://www.mozilla.org/MPL/
9 *
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
13 * License.
14 *
15 * The Original Code is the elliptic curve math library for binary polynomial field curves.
16 *
17 * The Initial Developer of the Original Code is
18 * Sun Microsystems, Inc.
19 * Portions created by the Initial Developer are Copyright (C) 2003
20 * the Initial Developer. All Rights Reserved.
21 *
22 * Contributor(s):
23 * Sheueling Chang-Shantz <sheueling.chang@sun.com>,
24 * Stephen Fung <fungstep@hotmail.com>, and
25 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories.
26 *
27 * Alternatively, the contents of this file may be used under the terms of
28 * either the GNU General Public License Version 2 or later (the "GPL"), or
29 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30 * in which case the provisions of the GPL or the LGPL are applicable instead
31 * of those above. If you wish to allow use of your version of this file only
32 * under the terms of either the GPL or the LGPL, and not to allow others to
33 * use your version of this file under the terms of the MPL, indicate your
34 * decision by deleting the provisions above and replace them with the notice
35 * and other provisions required by the GPL or the LGPL. If you do not delete
36 * the provisions above, a recipient may use your version of this file under
37 * the terms of any one of the MPL, the GPL or the LGPL.
38 *
39 * ***** END LICENSE BLOCK ***** */
40 /*
41 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
42 * Use is subject to license terms.
43 *
44 * Sun elects to use this software under the MPL license.
45 */
46
47 #include "ec2.h"
48 #include "mplogic.h"
49 #include "mp_gf2m.h"
50 #ifndef _KERNEL
51 #include <stdlib.h>
52 #endif
53
54 /* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery
55 * projective coordinates. Uses algorithm Mdouble in appendix of Lopez, J.
56 * and Dahab, R. "Fast multiplication on elliptic curves over GF(2^m)
57 * without precomputation". modified to not require precomputation of
58 * c=b^{2^{m-1}}. */
59 static mp_err
gf2m_Mdouble(mp_int * x,mp_int * z,const ECGroup * group,int kmflag)60 gf2m_Mdouble(mp_int *x, mp_int *z, const ECGroup *group, int kmflag)
61 {
62 mp_err res = MP_OKAY;
63 mp_int t1;
64
65 MP_DIGITS(&t1) = 0;
66 MP_CHECKOK(mp_init(&t1, kmflag));
67
68 MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
69 MP_CHECKOK(group->meth->field_sqr(z, &t1, group->meth));
70 MP_CHECKOK(group->meth->field_mul(x, &t1, z, group->meth));
71 MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
72 MP_CHECKOK(group->meth->field_sqr(&t1, &t1, group->meth));
73 MP_CHECKOK(group->meth->
74 field_mul(&group->curveb, &t1, &t1, group->meth));
75 MP_CHECKOK(group->meth->field_add(x, &t1, x, group->meth));
76
77 CLEANUP:
78 mp_clear(&t1);
79 return res;
80 }
81
82 /* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in
83 * Montgomery projective coordinates. Uses algorithm Madd in appendix of
84 * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
85 * GF(2^m) without precomputation". */
86 static mp_err
gf2m_Madd(const mp_int * x,mp_int * x1,mp_int * z1,mp_int * x2,mp_int * z2,const ECGroup * group,int kmflag)87 gf2m_Madd(const mp_int *x, mp_int *x1, mp_int *z1, mp_int *x2, mp_int *z2,
88 const ECGroup *group, int kmflag)
89 {
90 mp_err res = MP_OKAY;
91 mp_int t1, t2;
92
93 MP_DIGITS(&t1) = 0;
94 MP_DIGITS(&t2) = 0;
95 MP_CHECKOK(mp_init(&t1, kmflag));
96 MP_CHECKOK(mp_init(&t2, kmflag));
97
98 MP_CHECKOK(mp_copy(x, &t1));
99 MP_CHECKOK(group->meth->field_mul(x1, z2, x1, group->meth));
100 MP_CHECKOK(group->meth->field_mul(z1, x2, z1, group->meth));
101 MP_CHECKOK(group->meth->field_mul(x1, z1, &t2, group->meth));
102 MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
103 MP_CHECKOK(group->meth->field_sqr(z1, z1, group->meth));
104 MP_CHECKOK(group->meth->field_mul(z1, &t1, x1, group->meth));
105 MP_CHECKOK(group->meth->field_add(x1, &t2, x1, group->meth));
106
107 CLEANUP:
108 mp_clear(&t1);
109 mp_clear(&t2);
110 return res;
111 }
112
113 /* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
114 * using Montgomery point multiplication algorithm Mxy() in appendix of
115 * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
116 * GF(2^m) without precomputation". Returns: 0 on error 1 if return value
117 * should be the point at infinity 2 otherwise */
118 static int
gf2m_Mxy(const mp_int * x,const mp_int * y,mp_int * x1,mp_int * z1,mp_int * x2,mp_int * z2,const ECGroup * group)119 gf2m_Mxy(const mp_int *x, const mp_int *y, mp_int *x1, mp_int *z1,
120 mp_int *x2, mp_int *z2, const ECGroup *group)
121 {
122 mp_err res = MP_OKAY;
123 int ret = 0;
124 mp_int t3, t4, t5;
125
126 MP_DIGITS(&t3) = 0;
127 MP_DIGITS(&t4) = 0;
128 MP_DIGITS(&t5) = 0;
129 MP_CHECKOK(mp_init(&t3, FLAG(x2)));
130 MP_CHECKOK(mp_init(&t4, FLAG(x2)));
131 MP_CHECKOK(mp_init(&t5, FLAG(x2)));
132
133 if (mp_cmp_z(z1) == 0) {
134 mp_zero(x2);
135 mp_zero(z2);
136 ret = 1;
137 goto CLEANUP;
138 }
139
140 if (mp_cmp_z(z2) == 0) {
141 MP_CHECKOK(mp_copy(x, x2));
142 MP_CHECKOK(group->meth->field_add(x, y, z2, group->meth));
143 ret = 2;
144 goto CLEANUP;
145 }
146
147 MP_CHECKOK(mp_set_int(&t5, 1));
148 if (group->meth->field_enc) {
149 MP_CHECKOK(group->meth->field_enc(&t5, &t5, group->meth));
150 }
151
152 MP_CHECKOK(group->meth->field_mul(z1, z2, &t3, group->meth));
153
154 MP_CHECKOK(group->meth->field_mul(z1, x, z1, group->meth));
155 MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
156 MP_CHECKOK(group->meth->field_mul(z2, x, z2, group->meth));
157 MP_CHECKOK(group->meth->field_mul(z2, x1, x1, group->meth));
158 MP_CHECKOK(group->meth->field_add(z2, x2, z2, group->meth));
159
160 MP_CHECKOK(group->meth->field_mul(z2, z1, z2, group->meth));
161 MP_CHECKOK(group->meth->field_sqr(x, &t4, group->meth));
162 MP_CHECKOK(group->meth->field_add(&t4, y, &t4, group->meth));
163 MP_CHECKOK(group->meth->field_mul(&t4, &t3, &t4, group->meth));
164 MP_CHECKOK(group->meth->field_add(&t4, z2, &t4, group->meth));
165
166 MP_CHECKOK(group->meth->field_mul(&t3, x, &t3, group->meth));
167 MP_CHECKOK(group->meth->field_div(&t5, &t3, &t3, group->meth));
168 MP_CHECKOK(group->meth->field_mul(&t3, &t4, &t4, group->meth));
169 MP_CHECKOK(group->meth->field_mul(x1, &t3, x2, group->meth));
170 MP_CHECKOK(group->meth->field_add(x2, x, z2, group->meth));
171
172 MP_CHECKOK(group->meth->field_mul(z2, &t4, z2, group->meth));
173 MP_CHECKOK(group->meth->field_add(z2, y, z2, group->meth));
174
175 ret = 2;
176
177 CLEANUP:
178 mp_clear(&t3);
179 mp_clear(&t4);
180 mp_clear(&t5);
181 if (res == MP_OKAY) {
182 return ret;
183 } else {
184 return 0;
185 }
186 }
187
188 /* Computes R = nP based on algorithm 2P of Lopex, J. and Dahab, R. "Fast
189 * multiplication on elliptic curves over GF(2^m) without
190 * precomputation". Elliptic curve points P and R can be identical. Uses
191 * Montgomery projective coordinates. */
192 mp_err
ec_GF2m_pt_mul_mont(const mp_int * n,const mp_int * px,const mp_int * py,mp_int * rx,mp_int * ry,const ECGroup * group)193 ec_GF2m_pt_mul_mont(const mp_int *n, const mp_int *px, const mp_int *py,
194 mp_int *rx, mp_int *ry, const ECGroup *group)
195 {
196 mp_err res = MP_OKAY;
197 mp_int x1, x2, z1, z2;
198 int i, j;
199 mp_digit top_bit, mask;
200
201 MP_DIGITS(&x1) = 0;
202 MP_DIGITS(&x2) = 0;
203 MP_DIGITS(&z1) = 0;
204 MP_DIGITS(&z2) = 0;
205 MP_CHECKOK(mp_init(&x1, FLAG(n)));
206 MP_CHECKOK(mp_init(&x2, FLAG(n)));
207 MP_CHECKOK(mp_init(&z1, FLAG(n)));
208 MP_CHECKOK(mp_init(&z2, FLAG(n)));
209
210 /* if result should be point at infinity */
211 if ((mp_cmp_z(n) == 0) || (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES)) {
212 MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
213 goto CLEANUP;
214 }
215
216 MP_CHECKOK(mp_copy(px, &x1)); /* x1 = px */
217 MP_CHECKOK(mp_set_int(&z1, 1)); /* z1 = 1 */
218 MP_CHECKOK(group->meth->field_sqr(&x1, &z2, group->meth)); /* z2 =
219 * x1^2 =
220 * px^2 */
221 MP_CHECKOK(group->meth->field_sqr(&z2, &x2, group->meth));
222 MP_CHECKOK(group->meth->field_add(&x2, &group->curveb, &x2, group->meth)); /* x2
223 * =
224 * px^4
225 * +
226 * b
227 */
228
229 /* find top-most bit and go one past it */
230 i = MP_USED(n) - 1;
231 j = MP_DIGIT_BIT - 1;
232 top_bit = 1;
233 top_bit <<= MP_DIGIT_BIT - 1;
234 mask = top_bit;
235 while (!(MP_DIGITS(n)[i] & mask)) {
236 mask >>= 1;
237 j--;
238 }
239 mask >>= 1;
240 j--;
241
242 /* if top most bit was at word break, go to next word */
243 if (!mask) {
244 i--;
245 j = MP_DIGIT_BIT - 1;
246 mask = top_bit;
247 }
248
249 for (; i >= 0; i--) {
250 for (; j >= 0; j--) {
251 if (MP_DIGITS(n)[i] & mask) {
252 MP_CHECKOK(gf2m_Madd(px, &x1, &z1, &x2, &z2, group, FLAG(n)));
253 MP_CHECKOK(gf2m_Mdouble(&x2, &z2, group, FLAG(n)));
254 } else {
255 MP_CHECKOK(gf2m_Madd(px, &x2, &z2, &x1, &z1, group, FLAG(n)));
256 MP_CHECKOK(gf2m_Mdouble(&x1, &z1, group, FLAG(n)));
257 }
258 mask >>= 1;
259 }
260 j = MP_DIGIT_BIT - 1;
261 mask = top_bit;
262 }
263
264 /* convert out of "projective" coordinates */
265 i = gf2m_Mxy(px, py, &x1, &z1, &x2, &z2, group);
266 if (i == 0) {
267 res = MP_BADARG;
268 goto CLEANUP;
269 } else if (i == 1) {
270 MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
271 } else {
272 MP_CHECKOK(mp_copy(&x2, rx));
273 MP_CHECKOK(mp_copy(&z2, ry));
274 }
275
276 CLEANUP:
277 mp_clear(&x1);
278 mp_clear(&x2);
279 mp_clear(&z1);
280 mp_clear(&z2);
281 return res;
282 }
283