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 #pragma ident "%Z%%M% %I% %E% SMI"
48
49 #include "ec2.h"
50 #include "mplogic.h"
51 #include "mp_gf2m.h"
52 #ifndef _KERNEL
53 #include <stdlib.h>
54 #endif
55
56 /* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery
57 * projective coordinates. Uses algorithm Mdouble in appendix of Lopez, J.
58 * and Dahab, R. "Fast multiplication on elliptic curves over GF(2^m)
59 * without precomputation". modified to not require precomputation of
60 * c=b^{2^{m-1}}. */
61 static mp_err
gf2m_Mdouble(mp_int * x,mp_int * z,const ECGroup * group,int kmflag)62 gf2m_Mdouble(mp_int *x, mp_int *z, const ECGroup *group, int kmflag)
63 {
64 mp_err res = MP_OKAY;
65 mp_int t1;
66
67 MP_DIGITS(&t1) = 0;
68 MP_CHECKOK(mp_init(&t1, kmflag));
69
70 MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
71 MP_CHECKOK(group->meth->field_sqr(z, &t1, group->meth));
72 MP_CHECKOK(group->meth->field_mul(x, &t1, z, group->meth));
73 MP_CHECKOK(group->meth->field_sqr(x, x, group->meth));
74 MP_CHECKOK(group->meth->field_sqr(&t1, &t1, group->meth));
75 MP_CHECKOK(group->meth->
76 field_mul(&group->curveb, &t1, &t1, group->meth));
77 MP_CHECKOK(group->meth->field_add(x, &t1, x, group->meth));
78
79 CLEANUP:
80 mp_clear(&t1);
81 return res;
82 }
83
84 /* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in
85 * Montgomery projective coordinates. Uses algorithm Madd in appendix of
86 * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
87 * GF(2^m) without precomputation". */
88 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)89 gf2m_Madd(const mp_int *x, mp_int *x1, mp_int *z1, mp_int *x2, mp_int *z2,
90 const ECGroup *group, int kmflag)
91 {
92 mp_err res = MP_OKAY;
93 mp_int t1, t2;
94
95 MP_DIGITS(&t1) = 0;
96 MP_DIGITS(&t2) = 0;
97 MP_CHECKOK(mp_init(&t1, kmflag));
98 MP_CHECKOK(mp_init(&t2, kmflag));
99
100 MP_CHECKOK(mp_copy(x, &t1));
101 MP_CHECKOK(group->meth->field_mul(x1, z2, x1, group->meth));
102 MP_CHECKOK(group->meth->field_mul(z1, x2, z1, group->meth));
103 MP_CHECKOK(group->meth->field_mul(x1, z1, &t2, group->meth));
104 MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
105 MP_CHECKOK(group->meth->field_sqr(z1, z1, group->meth));
106 MP_CHECKOK(group->meth->field_mul(z1, &t1, x1, group->meth));
107 MP_CHECKOK(group->meth->field_add(x1, &t2, x1, group->meth));
108
109 CLEANUP:
110 mp_clear(&t1);
111 mp_clear(&t2);
112 return res;
113 }
114
115 /* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
116 * using Montgomery point multiplication algorithm Mxy() in appendix of
117 * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over
118 * GF(2^m) without precomputation". Returns: 0 on error 1 if return value
119 * should be the point at infinity 2 otherwise */
120 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)121 gf2m_Mxy(const mp_int *x, const mp_int *y, mp_int *x1, mp_int *z1,
122 mp_int *x2, mp_int *z2, const ECGroup *group)
123 {
124 mp_err res = MP_OKAY;
125 int ret = 0;
126 mp_int t3, t4, t5;
127
128 MP_DIGITS(&t3) = 0;
129 MP_DIGITS(&t4) = 0;
130 MP_DIGITS(&t5) = 0;
131 MP_CHECKOK(mp_init(&t3, FLAG(x2)));
132 MP_CHECKOK(mp_init(&t4, FLAG(x2)));
133 MP_CHECKOK(mp_init(&t5, FLAG(x2)));
134
135 if (mp_cmp_z(z1) == 0) {
136 mp_zero(x2);
137 mp_zero(z2);
138 ret = 1;
139 goto CLEANUP;
140 }
141
142 if (mp_cmp_z(z2) == 0) {
143 MP_CHECKOK(mp_copy(x, x2));
144 MP_CHECKOK(group->meth->field_add(x, y, z2, group->meth));
145 ret = 2;
146 goto CLEANUP;
147 }
148
149 MP_CHECKOK(mp_set_int(&t5, 1));
150 if (group->meth->field_enc) {
151 MP_CHECKOK(group->meth->field_enc(&t5, &t5, group->meth));
152 }
153
154 MP_CHECKOK(group->meth->field_mul(z1, z2, &t3, group->meth));
155
156 MP_CHECKOK(group->meth->field_mul(z1, x, z1, group->meth));
157 MP_CHECKOK(group->meth->field_add(z1, x1, z1, group->meth));
158 MP_CHECKOK(group->meth->field_mul(z2, x, z2, group->meth));
159 MP_CHECKOK(group->meth->field_mul(z2, x1, x1, group->meth));
160 MP_CHECKOK(group->meth->field_add(z2, x2, z2, group->meth));
161
162 MP_CHECKOK(group->meth->field_mul(z2, z1, z2, group->meth));
163 MP_CHECKOK(group->meth->field_sqr(x, &t4, group->meth));
164 MP_CHECKOK(group->meth->field_add(&t4, y, &t4, group->meth));
165 MP_CHECKOK(group->meth->field_mul(&t4, &t3, &t4, group->meth));
166 MP_CHECKOK(group->meth->field_add(&t4, z2, &t4, group->meth));
167
168 MP_CHECKOK(group->meth->field_mul(&t3, x, &t3, group->meth));
169 MP_CHECKOK(group->meth->field_div(&t5, &t3, &t3, group->meth));
170 MP_CHECKOK(group->meth->field_mul(&t3, &t4, &t4, group->meth));
171 MP_CHECKOK(group->meth->field_mul(x1, &t3, x2, group->meth));
172 MP_CHECKOK(group->meth->field_add(x2, x, z2, group->meth));
173
174 MP_CHECKOK(group->meth->field_mul(z2, &t4, z2, group->meth));
175 MP_CHECKOK(group->meth->field_add(z2, y, z2, group->meth));
176
177 ret = 2;
178
179 CLEANUP:
180 mp_clear(&t3);
181 mp_clear(&t4);
182 mp_clear(&t5);
183 if (res == MP_OKAY) {
184 return ret;
185 } else {
186 return 0;
187 }
188 }
189
190 /* Computes R = nP based on algorithm 2P of Lopex, J. and Dahab, R. "Fast
191 * multiplication on elliptic curves over GF(2^m) without
192 * precomputation". Elliptic curve points P and R can be identical. Uses
193 * Montgomery projective coordinates. */
194 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)195 ec_GF2m_pt_mul_mont(const mp_int *n, const mp_int *px, const mp_int *py,
196 mp_int *rx, mp_int *ry, const ECGroup *group)
197 {
198 mp_err res = MP_OKAY;
199 mp_int x1, x2, z1, z2;
200 int i, j;
201 mp_digit top_bit, mask;
202
203 MP_DIGITS(&x1) = 0;
204 MP_DIGITS(&x2) = 0;
205 MP_DIGITS(&z1) = 0;
206 MP_DIGITS(&z2) = 0;
207 MP_CHECKOK(mp_init(&x1, FLAG(n)));
208 MP_CHECKOK(mp_init(&x2, FLAG(n)));
209 MP_CHECKOK(mp_init(&z1, FLAG(n)));
210 MP_CHECKOK(mp_init(&z2, FLAG(n)));
211
212 /* if result should be point at infinity */
213 if ((mp_cmp_z(n) == 0) || (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES)) {
214 MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
215 goto CLEANUP;
216 }
217
218 MP_CHECKOK(mp_copy(px, &x1)); /* x1 = px */
219 MP_CHECKOK(mp_set_int(&z1, 1)); /* z1 = 1 */
220 MP_CHECKOK(group->meth->field_sqr(&x1, &z2, group->meth)); /* z2 =
221 * x1^2 =
222 * px^2 */
223 MP_CHECKOK(group->meth->field_sqr(&z2, &x2, group->meth));
224 MP_CHECKOK(group->meth->field_add(&x2, &group->curveb, &x2, group->meth)); /* x2
225 * =
226 * px^4
227 * +
228 * b
229 */
230
231 /* find top-most bit and go one past it */
232 i = MP_USED(n) - 1;
233 j = MP_DIGIT_BIT - 1;
234 top_bit = 1;
235 top_bit <<= MP_DIGIT_BIT - 1;
236 mask = top_bit;
237 while (!(MP_DIGITS(n)[i] & mask)) {
238 mask >>= 1;
239 j--;
240 }
241 mask >>= 1;
242 j--;
243
244 /* if top most bit was at word break, go to next word */
245 if (!mask) {
246 i--;
247 j = MP_DIGIT_BIT - 1;
248 mask = top_bit;
249 }
250
251 for (; i >= 0; i--) {
252 for (; j >= 0; j--) {
253 if (MP_DIGITS(n)[i] & mask) {
254 MP_CHECKOK(gf2m_Madd(px, &x1, &z1, &x2, &z2, group, FLAG(n)));
255 MP_CHECKOK(gf2m_Mdouble(&x2, &z2, group, FLAG(n)));
256 } else {
257 MP_CHECKOK(gf2m_Madd(px, &x2, &z2, &x1, &z1, group, FLAG(n)));
258 MP_CHECKOK(gf2m_Mdouble(&x1, &z1, group, FLAG(n)));
259 }
260 mask >>= 1;
261 }
262 j = MP_DIGIT_BIT - 1;
263 mask = top_bit;
264 }
265
266 /* convert out of "projective" coordinates */
267 i = gf2m_Mxy(px, py, &x1, &z1, &x2, &z2, group);
268 if (i == 0) {
269 res = MP_BADARG;
270 goto CLEANUP;
271 } else if (i == 1) {
272 MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
273 } else {
274 MP_CHECKOK(mp_copy(&x2, rx));
275 MP_CHECKOK(mp_copy(&z2, ry));
276 }
277
278 CLEANUP:
279 mp_clear(&x1);
280 mp_clear(&x2);
281 mp_clear(&z1);
282 mp_clear(&z2);
283 return res;
284 }
285