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