1*55fea89dSDan Cross /*
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.
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 * Stephen Fung <fungstep@hotmail.com> and
24f9fbec18Smcpowers * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
25f9fbec18Smcpowers *
26f9fbec18Smcpowers * Alternatively, the contents of this file may be used under the terms of
27f9fbec18Smcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
28f9fbec18Smcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29f9fbec18Smcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
30f9fbec18Smcpowers * of those above. If you wish to allow use of your version of this file only
31f9fbec18Smcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
32f9fbec18Smcpowers * use your version of this file under the terms of the MPL, indicate your
33f9fbec18Smcpowers * decision by deleting the provisions above and replace them with the notice
34f9fbec18Smcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
35f9fbec18Smcpowers * the provisions above, a recipient may use your version of this file under
36f9fbec18Smcpowers * the terms of any one of the MPL, the GPL or the LGPL.
37f9fbec18Smcpowers *
38f9fbec18Smcpowers * ***** END LICENSE BLOCK ***** */
39f9fbec18Smcpowers /*
40f9fbec18Smcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
41f9fbec18Smcpowers * Use is subject to license terms.
42f9fbec18Smcpowers *
43f9fbec18Smcpowers * Sun elects to use this software under the MPL license.
44f9fbec18Smcpowers */
45f9fbec18Smcpowers
46f9fbec18Smcpowers #include "mpi.h"
47f9fbec18Smcpowers #include "mp_gf2m.h"
48f9fbec18Smcpowers #include "ecl-priv.h"
49f9fbec18Smcpowers #include "mpi-priv.h"
50f9fbec18Smcpowers #ifndef _KERNEL
51f9fbec18Smcpowers #include <stdlib.h>
52f9fbec18Smcpowers #endif
53f9fbec18Smcpowers
54f9fbec18Smcpowers /* Allocate memory for a new GFMethod object. */
55f9fbec18Smcpowers GFMethod *
GFMethod_new(int kmflag)56f9fbec18Smcpowers GFMethod_new(int kmflag)
57f9fbec18Smcpowers {
58f9fbec18Smcpowers mp_err res = MP_OKAY;
59f9fbec18Smcpowers GFMethod *meth;
60f9fbec18Smcpowers #ifdef _KERNEL
61f9fbec18Smcpowers meth = (GFMethod *) kmem_alloc(sizeof(GFMethod), kmflag);
62f9fbec18Smcpowers #else
63f9fbec18Smcpowers meth = (GFMethod *) malloc(sizeof(GFMethod));
64f9fbec18Smcpowers if (meth == NULL)
65f9fbec18Smcpowers return NULL;
66f9fbec18Smcpowers #endif
67f9fbec18Smcpowers meth->constructed = MP_YES;
68f9fbec18Smcpowers MP_DIGITS(&meth->irr) = 0;
69f9fbec18Smcpowers meth->extra_free = NULL;
70f9fbec18Smcpowers MP_CHECKOK(mp_init(&meth->irr, kmflag));
71f9fbec18Smcpowers
72f9fbec18Smcpowers CLEANUP:
73f9fbec18Smcpowers if (res != MP_OKAY) {
74f9fbec18Smcpowers GFMethod_free(meth);
75f9fbec18Smcpowers return NULL;
76f9fbec18Smcpowers }
77f9fbec18Smcpowers return meth;
78f9fbec18Smcpowers }
79f9fbec18Smcpowers
80f9fbec18Smcpowers /* Construct a generic GFMethod for arithmetic over prime fields with
81f9fbec18Smcpowers * irreducible irr. */
82f9fbec18Smcpowers GFMethod *
GFMethod_consGFp(const mp_int * irr)83f9fbec18Smcpowers GFMethod_consGFp(const mp_int *irr)
84f9fbec18Smcpowers {
85f9fbec18Smcpowers mp_err res = MP_OKAY;
86f9fbec18Smcpowers GFMethod *meth = NULL;
87f9fbec18Smcpowers
88f9fbec18Smcpowers meth = GFMethod_new(FLAG(irr));
89f9fbec18Smcpowers if (meth == NULL)
90f9fbec18Smcpowers return NULL;
91f9fbec18Smcpowers
92f9fbec18Smcpowers MP_CHECKOK(mp_copy(irr, &meth->irr));
93f9fbec18Smcpowers meth->irr_arr[0] = mpl_significant_bits(irr);
94f9fbec18Smcpowers meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] =
95f9fbec18Smcpowers meth->irr_arr[4] = 0;
96f9fbec18Smcpowers switch(MP_USED(&meth->irr)) {
97f9fbec18Smcpowers /* maybe we need 1 and 2 words here as well?*/
98f9fbec18Smcpowers case 3:
99f9fbec18Smcpowers meth->field_add = &ec_GFp_add_3;
100f9fbec18Smcpowers meth->field_sub = &ec_GFp_sub_3;
101f9fbec18Smcpowers break;
102f9fbec18Smcpowers case 4:
103f9fbec18Smcpowers meth->field_add = &ec_GFp_add_4;
104f9fbec18Smcpowers meth->field_sub = &ec_GFp_sub_4;
105f9fbec18Smcpowers break;
106f9fbec18Smcpowers case 5:
107f9fbec18Smcpowers meth->field_add = &ec_GFp_add_5;
108f9fbec18Smcpowers meth->field_sub = &ec_GFp_sub_5;
109f9fbec18Smcpowers break;
110f9fbec18Smcpowers case 6:
111f9fbec18Smcpowers meth->field_add = &ec_GFp_add_6;
112f9fbec18Smcpowers meth->field_sub = &ec_GFp_sub_6;
113f9fbec18Smcpowers break;
114f9fbec18Smcpowers default:
115f9fbec18Smcpowers meth->field_add = &ec_GFp_add;
116f9fbec18Smcpowers meth->field_sub = &ec_GFp_sub;
117f9fbec18Smcpowers }
118f9fbec18Smcpowers meth->field_neg = &ec_GFp_neg;
119f9fbec18Smcpowers meth->field_mod = &ec_GFp_mod;
120f9fbec18Smcpowers meth->field_mul = &ec_GFp_mul;
121f9fbec18Smcpowers meth->field_sqr = &ec_GFp_sqr;
122f9fbec18Smcpowers meth->field_div = &ec_GFp_div;
123f9fbec18Smcpowers meth->field_enc = NULL;
124f9fbec18Smcpowers meth->field_dec = NULL;
125f9fbec18Smcpowers meth->extra1 = NULL;
126f9fbec18Smcpowers meth->extra2 = NULL;
127f9fbec18Smcpowers meth->extra_free = NULL;
128f9fbec18Smcpowers
129f9fbec18Smcpowers CLEANUP:
130f9fbec18Smcpowers if (res != MP_OKAY) {
131f9fbec18Smcpowers GFMethod_free(meth);
132f9fbec18Smcpowers return NULL;
133f9fbec18Smcpowers }
134f9fbec18Smcpowers return meth;
135f9fbec18Smcpowers }
136f9fbec18Smcpowers
137f9fbec18Smcpowers /* Construct a generic GFMethod for arithmetic over binary polynomial
138f9fbec18Smcpowers * fields with irreducible irr that has array representation irr_arr (see
139*55fea89dSDan Cross * ecl-priv.h for description of the representation). If irr_arr is NULL,
140f9fbec18Smcpowers * then it is constructed from the bitstring representation. */
141f9fbec18Smcpowers GFMethod *
GFMethod_consGF2m(const mp_int * irr,const unsigned int irr_arr[5])142f9fbec18Smcpowers GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5])
143f9fbec18Smcpowers {
144f9fbec18Smcpowers mp_err res = MP_OKAY;
145f9fbec18Smcpowers int ret;
146f9fbec18Smcpowers GFMethod *meth = NULL;
147f9fbec18Smcpowers
148f9fbec18Smcpowers meth = GFMethod_new(FLAG(irr));
149f9fbec18Smcpowers if (meth == NULL)
150f9fbec18Smcpowers return NULL;
151f9fbec18Smcpowers
152f9fbec18Smcpowers MP_CHECKOK(mp_copy(irr, &meth->irr));
153f9fbec18Smcpowers if (irr_arr != NULL) {
154f9fbec18Smcpowers /* Irreducible polynomials are either trinomials or pentanomials. */
155f9fbec18Smcpowers meth->irr_arr[0] = irr_arr[0];
156f9fbec18Smcpowers meth->irr_arr[1] = irr_arr[1];
157f9fbec18Smcpowers meth->irr_arr[2] = irr_arr[2];
158f9fbec18Smcpowers if (irr_arr[2] > 0) {
159f9fbec18Smcpowers meth->irr_arr[3] = irr_arr[3];
160f9fbec18Smcpowers meth->irr_arr[4] = irr_arr[4];
161f9fbec18Smcpowers } else {
162f9fbec18Smcpowers meth->irr_arr[3] = meth->irr_arr[4] = 0;
163f9fbec18Smcpowers }
164f9fbec18Smcpowers } else {
165f9fbec18Smcpowers ret = mp_bpoly2arr(irr, meth->irr_arr, 5);
166f9fbec18Smcpowers /* Irreducible polynomials are either trinomials or pentanomials. */
167f9fbec18Smcpowers if ((ret != 5) && (ret != 3)) {
168f9fbec18Smcpowers res = MP_UNDEF;
169f9fbec18Smcpowers goto CLEANUP;
170f9fbec18Smcpowers }
171f9fbec18Smcpowers }
172f9fbec18Smcpowers meth->field_add = &ec_GF2m_add;
173f9fbec18Smcpowers meth->field_neg = &ec_GF2m_neg;
174f9fbec18Smcpowers meth->field_sub = &ec_GF2m_add;
175f9fbec18Smcpowers meth->field_mod = &ec_GF2m_mod;
176f9fbec18Smcpowers meth->field_mul = &ec_GF2m_mul;
177f9fbec18Smcpowers meth->field_sqr = &ec_GF2m_sqr;
178f9fbec18Smcpowers meth->field_div = &ec_GF2m_div;
179f9fbec18Smcpowers meth->field_enc = NULL;
180f9fbec18Smcpowers meth->field_dec = NULL;
181f9fbec18Smcpowers meth->extra1 = NULL;
182f9fbec18Smcpowers meth->extra2 = NULL;
183f9fbec18Smcpowers meth->extra_free = NULL;
184f9fbec18Smcpowers
185f9fbec18Smcpowers CLEANUP:
186f9fbec18Smcpowers if (res != MP_OKAY) {
187f9fbec18Smcpowers GFMethod_free(meth);
188f9fbec18Smcpowers return NULL;
189f9fbec18Smcpowers }
190f9fbec18Smcpowers return meth;
191f9fbec18Smcpowers }
192f9fbec18Smcpowers
193f9fbec18Smcpowers /* Free the memory allocated (if any) to a GFMethod object. */
194f9fbec18Smcpowers void
GFMethod_free(GFMethod * meth)195f9fbec18Smcpowers GFMethod_free(GFMethod *meth)
196f9fbec18Smcpowers {
197f9fbec18Smcpowers if (meth == NULL)
198f9fbec18Smcpowers return;
199f9fbec18Smcpowers if (meth->constructed == MP_NO)
200f9fbec18Smcpowers return;
201f9fbec18Smcpowers mp_clear(&meth->irr);
202f9fbec18Smcpowers if (meth->extra_free != NULL)
203f9fbec18Smcpowers meth->extra_free(meth);
204f9fbec18Smcpowers #ifdef _KERNEL
205f9fbec18Smcpowers kmem_free(meth, sizeof(GFMethod));
206f9fbec18Smcpowers #else
207f9fbec18Smcpowers free(meth);
208f9fbec18Smcpowers #endif
209f9fbec18Smcpowers }
210f9fbec18Smcpowers
211f9fbec18Smcpowers /* Wrapper functions for generic prime field arithmetic. */
212f9fbec18Smcpowers
213f9fbec18Smcpowers /* Add two field elements. Assumes that 0 <= a, b < meth->irr */
214f9fbec18Smcpowers mp_err
ec_GFp_add(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)215f9fbec18Smcpowers ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
216f9fbec18Smcpowers const GFMethod *meth)
217f9fbec18Smcpowers {
218f9fbec18Smcpowers /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */
219f9fbec18Smcpowers mp_err res;
220f9fbec18Smcpowers
221f9fbec18Smcpowers if ((res = mp_add(a, b, r)) != MP_OKAY) {
222f9fbec18Smcpowers return res;
223f9fbec18Smcpowers }
224f9fbec18Smcpowers if (mp_cmp(r, &meth->irr) >= 0) {
225f9fbec18Smcpowers return mp_sub(r, &meth->irr, r);
226f9fbec18Smcpowers }
227f9fbec18Smcpowers return res;
228f9fbec18Smcpowers }
229f9fbec18Smcpowers
230f9fbec18Smcpowers /* Negates a field element. Assumes that 0 <= a < meth->irr */
231f9fbec18Smcpowers mp_err
ec_GFp_neg(const mp_int * a,mp_int * r,const GFMethod * meth)232f9fbec18Smcpowers ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
233f9fbec18Smcpowers {
234f9fbec18Smcpowers /* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */
235f9fbec18Smcpowers
236f9fbec18Smcpowers if (mp_cmp_z(a) == 0) {
237f9fbec18Smcpowers mp_zero(r);
238f9fbec18Smcpowers return MP_OKAY;
239f9fbec18Smcpowers }
240f9fbec18Smcpowers return mp_sub(&meth->irr, a, r);
241f9fbec18Smcpowers }
242f9fbec18Smcpowers
243f9fbec18Smcpowers /* Subtracts two field elements. Assumes that 0 <= a, b < meth->irr */
244f9fbec18Smcpowers mp_err
ec_GFp_sub(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)245f9fbec18Smcpowers ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
246f9fbec18Smcpowers const GFMethod *meth)
247f9fbec18Smcpowers {
248f9fbec18Smcpowers mp_err res = MP_OKAY;
249f9fbec18Smcpowers
250f9fbec18Smcpowers /* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */
251f9fbec18Smcpowers res = mp_sub(a, b, r);
252f9fbec18Smcpowers if (res == MP_RANGE) {
253f9fbec18Smcpowers MP_CHECKOK(mp_sub(b, a, r));
254f9fbec18Smcpowers if (mp_cmp_z(r) < 0) {
255f9fbec18Smcpowers MP_CHECKOK(mp_add(r, &meth->irr, r));
256f9fbec18Smcpowers }
257f9fbec18Smcpowers MP_CHECKOK(ec_GFp_neg(r, r, meth));
258f9fbec18Smcpowers }
259f9fbec18Smcpowers if (mp_cmp_z(r) < 0) {
260f9fbec18Smcpowers MP_CHECKOK(mp_add(r, &meth->irr, r));
261f9fbec18Smcpowers }
262f9fbec18Smcpowers CLEANUP:
263f9fbec18Smcpowers return res;
264f9fbec18Smcpowers }
265*55fea89dSDan Cross /*
266f9fbec18Smcpowers * Inline adds for small curve lengths.
267f9fbec18Smcpowers */
268f9fbec18Smcpowers /* 3 words */
269f9fbec18Smcpowers mp_err
ec_GFp_add_3(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)270*55fea89dSDan Cross ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,
271f9fbec18Smcpowers const GFMethod *meth)
272f9fbec18Smcpowers {
273f9fbec18Smcpowers mp_err res = MP_OKAY;
274f9fbec18Smcpowers mp_digit a0 = 0, a1 = 0, a2 = 0;
275f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0;
276f9fbec18Smcpowers mp_digit carry;
277f9fbec18Smcpowers
278f9fbec18Smcpowers switch(MP_USED(a)) {
279f9fbec18Smcpowers case 3:
280f9fbec18Smcpowers a2 = MP_DIGIT(a,2);
28138a641c5SToomas Soome /* FALLTHROUGH */
282f9fbec18Smcpowers case 2:
283f9fbec18Smcpowers a1 = MP_DIGIT(a,1);
28438a641c5SToomas Soome /* FALLTHROUGH */
285f9fbec18Smcpowers case 1:
286f9fbec18Smcpowers a0 = MP_DIGIT(a,0);
287f9fbec18Smcpowers }
288f9fbec18Smcpowers switch(MP_USED(b)) {
289f9fbec18Smcpowers case 3:
290f9fbec18Smcpowers r2 = MP_DIGIT(b,2);
29138a641c5SToomas Soome /* FALLTHROUGH */
292f9fbec18Smcpowers case 2:
293f9fbec18Smcpowers r1 = MP_DIGIT(b,1);
29438a641c5SToomas Soome /* FALLTHROUGH */
295f9fbec18Smcpowers case 1:
296f9fbec18Smcpowers r0 = MP_DIGIT(b,0);
297f9fbec18Smcpowers }
298f9fbec18Smcpowers
299f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
300f9fbec18Smcpowers MP_ADD_CARRY(a0, r0, r0, 0, carry);
301f9fbec18Smcpowers MP_ADD_CARRY(a1, r1, r1, carry, carry);
302f9fbec18Smcpowers MP_ADD_CARRY(a2, r2, r2, carry, carry);
303f9fbec18Smcpowers #else
304f9fbec18Smcpowers __asm__ (
305f9fbec18Smcpowers "xorq %3,%3 \n\t"
306f9fbec18Smcpowers "addq %4,%0 \n\t"
307f9fbec18Smcpowers "adcq %5,%1 \n\t"
308f9fbec18Smcpowers "adcq %6,%2 \n\t"
309f9fbec18Smcpowers "adcq $0,%3 \n\t"
310f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
311f9fbec18Smcpowers : "r" (a0), "r" (a1), "r" (a2),
312f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2)
313f9fbec18Smcpowers : "%cc" );
314f9fbec18Smcpowers #endif
315f9fbec18Smcpowers
316f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 3));
317f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
318f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
319f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
320f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
321f9fbec18Smcpowers MP_USED(r) = 3;
322f9fbec18Smcpowers
323*55fea89dSDan Cross /* Do quick 'subract' if we've gone over
324f9fbec18Smcpowers * (add the 2's complement of the curve field) */
325f9fbec18Smcpowers a2 = MP_DIGIT(&meth->irr,2);
326f9fbec18Smcpowers if (carry || r2 > a2 ||
327f9fbec18Smcpowers ((r2 == a2) && mp_cmp(r,&meth->irr) != MP_LT)) {
328f9fbec18Smcpowers a1 = MP_DIGIT(&meth->irr,1);
329f9fbec18Smcpowers a0 = MP_DIGIT(&meth->irr,0);
330f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
331f9fbec18Smcpowers MP_SUB_BORROW(r0, a0, r0, 0, carry);
332f9fbec18Smcpowers MP_SUB_BORROW(r1, a1, r1, carry, carry);
333f9fbec18Smcpowers MP_SUB_BORROW(r2, a2, r2, carry, carry);
334f9fbec18Smcpowers #else
335f9fbec18Smcpowers __asm__ (
336f9fbec18Smcpowers "subq %3,%0 \n\t"
337f9fbec18Smcpowers "sbbq %4,%1 \n\t"
338f9fbec18Smcpowers "sbbq %5,%2 \n\t"
339f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2)
340f9fbec18Smcpowers : "r" (a0), "r" (a1), "r" (a2),
341f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2)
342f9fbec18Smcpowers : "%cc" );
343f9fbec18Smcpowers #endif
344f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
345f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
346f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
347f9fbec18Smcpowers }
348*55fea89dSDan Cross
349f9fbec18Smcpowers s_mp_clamp(r);
350f9fbec18Smcpowers
351f9fbec18Smcpowers CLEANUP:
352f9fbec18Smcpowers return res;
353f9fbec18Smcpowers }
354f9fbec18Smcpowers
355f9fbec18Smcpowers /* 4 words */
356f9fbec18Smcpowers mp_err
ec_GFp_add_4(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)357*55fea89dSDan Cross ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,
358f9fbec18Smcpowers const GFMethod *meth)
359f9fbec18Smcpowers {
360f9fbec18Smcpowers mp_err res = MP_OKAY;
361f9fbec18Smcpowers mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0;
362f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
363f9fbec18Smcpowers mp_digit carry;
364f9fbec18Smcpowers
365f9fbec18Smcpowers switch(MP_USED(a)) {
366f9fbec18Smcpowers case 4:
367f9fbec18Smcpowers a3 = MP_DIGIT(a,3);
36838a641c5SToomas Soome /* FALLTHROUGH */
369f9fbec18Smcpowers case 3:
370f9fbec18Smcpowers a2 = MP_DIGIT(a,2);
37138a641c5SToomas Soome /* FALLTHROUGH */
372f9fbec18Smcpowers case 2:
373f9fbec18Smcpowers a1 = MP_DIGIT(a,1);
37438a641c5SToomas Soome /* FALLTHROUGH */
375f9fbec18Smcpowers case 1:
376f9fbec18Smcpowers a0 = MP_DIGIT(a,0);
377f9fbec18Smcpowers }
378f9fbec18Smcpowers switch(MP_USED(b)) {
379f9fbec18Smcpowers case 4:
380f9fbec18Smcpowers r3 = MP_DIGIT(b,3);
38138a641c5SToomas Soome /* FALLTHROUGH */
382f9fbec18Smcpowers case 3:
383f9fbec18Smcpowers r2 = MP_DIGIT(b,2);
38438a641c5SToomas Soome /* FALLTHROUGH */
385f9fbec18Smcpowers case 2:
386f9fbec18Smcpowers r1 = MP_DIGIT(b,1);
38738a641c5SToomas Soome /* FALLTHROUGH */
388f9fbec18Smcpowers case 1:
389f9fbec18Smcpowers r0 = MP_DIGIT(b,0);
390f9fbec18Smcpowers }
391f9fbec18Smcpowers
392f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
393f9fbec18Smcpowers MP_ADD_CARRY(a0, r0, r0, 0, carry);
394f9fbec18Smcpowers MP_ADD_CARRY(a1, r1, r1, carry, carry);
395f9fbec18Smcpowers MP_ADD_CARRY(a2, r2, r2, carry, carry);
396f9fbec18Smcpowers MP_ADD_CARRY(a3, r3, r3, carry, carry);
397f9fbec18Smcpowers #else
398f9fbec18Smcpowers __asm__ (
399f9fbec18Smcpowers "xorq %4,%4 \n\t"
400f9fbec18Smcpowers "addq %5,%0 \n\t"
401f9fbec18Smcpowers "adcq %6,%1 \n\t"
402f9fbec18Smcpowers "adcq %7,%2 \n\t"
403f9fbec18Smcpowers "adcq %8,%3 \n\t"
404f9fbec18Smcpowers "adcq $0,%4 \n\t"
405f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry)
406f9fbec18Smcpowers : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
407f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2), "3" (r3)
408f9fbec18Smcpowers : "%cc" );
409f9fbec18Smcpowers #endif
410f9fbec18Smcpowers
411f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 4));
412f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
413f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
414f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
415f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
416f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
417f9fbec18Smcpowers MP_USED(r) = 4;
418f9fbec18Smcpowers
419*55fea89dSDan Cross /* Do quick 'subract' if we've gone over
420f9fbec18Smcpowers * (add the 2's complement of the curve field) */
421f9fbec18Smcpowers a3 = MP_DIGIT(&meth->irr,3);
422f9fbec18Smcpowers if (carry || r3 > a3 ||
423f9fbec18Smcpowers ((r3 == a3) && mp_cmp(r,&meth->irr) != MP_LT)) {
424f9fbec18Smcpowers a2 = MP_DIGIT(&meth->irr,2);
425f9fbec18Smcpowers a1 = MP_DIGIT(&meth->irr,1);
426f9fbec18Smcpowers a0 = MP_DIGIT(&meth->irr,0);
427f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
428f9fbec18Smcpowers MP_SUB_BORROW(r0, a0, r0, 0, carry);
429f9fbec18Smcpowers MP_SUB_BORROW(r1, a1, r1, carry, carry);
430f9fbec18Smcpowers MP_SUB_BORROW(r2, a2, r2, carry, carry);
431f9fbec18Smcpowers MP_SUB_BORROW(r3, a3, r3, carry, carry);
432f9fbec18Smcpowers #else
433f9fbec18Smcpowers __asm__ (
434f9fbec18Smcpowers "subq %4,%0 \n\t"
435f9fbec18Smcpowers "sbbq %5,%1 \n\t"
436f9fbec18Smcpowers "sbbq %6,%2 \n\t"
437f9fbec18Smcpowers "sbbq %7,%3 \n\t"
438f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
439f9fbec18Smcpowers : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
440f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2), "3" (r3)
441f9fbec18Smcpowers : "%cc" );
442f9fbec18Smcpowers #endif
443f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
444f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
445f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
446f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
447f9fbec18Smcpowers }
448*55fea89dSDan Cross
449f9fbec18Smcpowers s_mp_clamp(r);
450f9fbec18Smcpowers
451f9fbec18Smcpowers CLEANUP:
452f9fbec18Smcpowers return res;
453f9fbec18Smcpowers }
454f9fbec18Smcpowers
455f9fbec18Smcpowers /* 5 words */
456f9fbec18Smcpowers mp_err
ec_GFp_add_5(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)457*55fea89dSDan Cross ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,
458f9fbec18Smcpowers const GFMethod *meth)
459f9fbec18Smcpowers {
460f9fbec18Smcpowers mp_err res = MP_OKAY;
461f9fbec18Smcpowers mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0;
462f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
463f9fbec18Smcpowers mp_digit carry;
464f9fbec18Smcpowers
465f9fbec18Smcpowers switch(MP_USED(a)) {
466f9fbec18Smcpowers case 5:
467f9fbec18Smcpowers a4 = MP_DIGIT(a,4);
46838a641c5SToomas Soome /* FALLTHROUGH */
469f9fbec18Smcpowers case 4:
470f9fbec18Smcpowers a3 = MP_DIGIT(a,3);
47138a641c5SToomas Soome /* FALLTHROUGH */
472f9fbec18Smcpowers case 3:
473f9fbec18Smcpowers a2 = MP_DIGIT(a,2);
47438a641c5SToomas Soome /* FALLTHROUGH */
475f9fbec18Smcpowers case 2:
476f9fbec18Smcpowers a1 = MP_DIGIT(a,1);
47738a641c5SToomas Soome /* FALLTHROUGH */
478f9fbec18Smcpowers case 1:
479f9fbec18Smcpowers a0 = MP_DIGIT(a,0);
480f9fbec18Smcpowers }
481f9fbec18Smcpowers switch(MP_USED(b)) {
482f9fbec18Smcpowers case 5:
483f9fbec18Smcpowers r4 = MP_DIGIT(b,4);
48438a641c5SToomas Soome /* FALLTHROUGH */
485f9fbec18Smcpowers case 4:
486f9fbec18Smcpowers r3 = MP_DIGIT(b,3);
48738a641c5SToomas Soome /* FALLTHROUGH */
488f9fbec18Smcpowers case 3:
489f9fbec18Smcpowers r2 = MP_DIGIT(b,2);
49038a641c5SToomas Soome /* FALLTHROUGH */
491f9fbec18Smcpowers case 2:
492f9fbec18Smcpowers r1 = MP_DIGIT(b,1);
49338a641c5SToomas Soome /* FALLTHROUGH */
494f9fbec18Smcpowers case 1:
495f9fbec18Smcpowers r0 = MP_DIGIT(b,0);
496f9fbec18Smcpowers }
497f9fbec18Smcpowers
498f9fbec18Smcpowers MP_ADD_CARRY(a0, r0, r0, 0, carry);
499f9fbec18Smcpowers MP_ADD_CARRY(a1, r1, r1, carry, carry);
500f9fbec18Smcpowers MP_ADD_CARRY(a2, r2, r2, carry, carry);
501f9fbec18Smcpowers MP_ADD_CARRY(a3, r3, r3, carry, carry);
502f9fbec18Smcpowers MP_ADD_CARRY(a4, r4, r4, carry, carry);
503f9fbec18Smcpowers
504f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 5));
505f9fbec18Smcpowers MP_DIGIT(r, 4) = r4;
506f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
507f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
508f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
509f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
510f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
511f9fbec18Smcpowers MP_USED(r) = 5;
512f9fbec18Smcpowers
513*55fea89dSDan Cross /* Do quick 'subract' if we've gone over
514f9fbec18Smcpowers * (add the 2's complement of the curve field) */
515f9fbec18Smcpowers a4 = MP_DIGIT(&meth->irr,4);
516f9fbec18Smcpowers if (carry || r4 > a4 ||
517f9fbec18Smcpowers ((r4 == a4) && mp_cmp(r,&meth->irr) != MP_LT)) {
518f9fbec18Smcpowers a3 = MP_DIGIT(&meth->irr,3);
519f9fbec18Smcpowers a2 = MP_DIGIT(&meth->irr,2);
520f9fbec18Smcpowers a1 = MP_DIGIT(&meth->irr,1);
521f9fbec18Smcpowers a0 = MP_DIGIT(&meth->irr,0);
522f9fbec18Smcpowers MP_SUB_BORROW(r0, a0, r0, 0, carry);
523f9fbec18Smcpowers MP_SUB_BORROW(r1, a1, r1, carry, carry);
524f9fbec18Smcpowers MP_SUB_BORROW(r2, a2, r2, carry, carry);
525f9fbec18Smcpowers MP_SUB_BORROW(r3, a3, r3, carry, carry);
526f9fbec18Smcpowers MP_SUB_BORROW(r4, a4, r4, carry, carry);
527f9fbec18Smcpowers MP_DIGIT(r, 4) = r4;
528f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
529f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
530f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
531f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
532f9fbec18Smcpowers }
533*55fea89dSDan Cross
534f9fbec18Smcpowers s_mp_clamp(r);
535f9fbec18Smcpowers
536f9fbec18Smcpowers CLEANUP:
537f9fbec18Smcpowers return res;
538f9fbec18Smcpowers }
539f9fbec18Smcpowers
540f9fbec18Smcpowers /* 6 words */
541f9fbec18Smcpowers mp_err
ec_GFp_add_6(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)542*55fea89dSDan Cross ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,
543f9fbec18Smcpowers const GFMethod *meth)
544f9fbec18Smcpowers {
545f9fbec18Smcpowers mp_err res = MP_OKAY;
546f9fbec18Smcpowers mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0;
547f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
548f9fbec18Smcpowers mp_digit carry;
549f9fbec18Smcpowers
550f9fbec18Smcpowers switch(MP_USED(a)) {
551f9fbec18Smcpowers case 6:
552f9fbec18Smcpowers a5 = MP_DIGIT(a,5);
55338a641c5SToomas Soome /* FALLTHROUGH */
554f9fbec18Smcpowers case 5:
555f9fbec18Smcpowers a4 = MP_DIGIT(a,4);
55638a641c5SToomas Soome /* FALLTHROUGH */
557f9fbec18Smcpowers case 4:
558f9fbec18Smcpowers a3 = MP_DIGIT(a,3);
55938a641c5SToomas Soome /* FALLTHROUGH */
560f9fbec18Smcpowers case 3:
561f9fbec18Smcpowers a2 = MP_DIGIT(a,2);
56238a641c5SToomas Soome /* FALLTHROUGH */
563f9fbec18Smcpowers case 2:
564f9fbec18Smcpowers a1 = MP_DIGIT(a,1);
56538a641c5SToomas Soome /* FALLTHROUGH */
566f9fbec18Smcpowers case 1:
567f9fbec18Smcpowers a0 = MP_DIGIT(a,0);
568f9fbec18Smcpowers }
569f9fbec18Smcpowers switch(MP_USED(b)) {
570f9fbec18Smcpowers case 6:
571f9fbec18Smcpowers r5 = MP_DIGIT(b,5);
57238a641c5SToomas Soome /* FALLTHROUGH */
573f9fbec18Smcpowers case 5:
574f9fbec18Smcpowers r4 = MP_DIGIT(b,4);
57538a641c5SToomas Soome /* FALLTHROUGH */
576f9fbec18Smcpowers case 4:
577f9fbec18Smcpowers r3 = MP_DIGIT(b,3);
57838a641c5SToomas Soome /* FALLTHROUGH */
579f9fbec18Smcpowers case 3:
580f9fbec18Smcpowers r2 = MP_DIGIT(b,2);
58138a641c5SToomas Soome /* FALLTHROUGH */
582f9fbec18Smcpowers case 2:
583f9fbec18Smcpowers r1 = MP_DIGIT(b,1);
58438a641c5SToomas Soome /* FALLTHROUGH */
585f9fbec18Smcpowers case 1:
586f9fbec18Smcpowers r0 = MP_DIGIT(b,0);
587f9fbec18Smcpowers }
588f9fbec18Smcpowers
589f9fbec18Smcpowers MP_ADD_CARRY(a0, r0, r0, 0, carry);
590f9fbec18Smcpowers MP_ADD_CARRY(a1, r1, r1, carry, carry);
591f9fbec18Smcpowers MP_ADD_CARRY(a2, r2, r2, carry, carry);
592f9fbec18Smcpowers MP_ADD_CARRY(a3, r3, r3, carry, carry);
593f9fbec18Smcpowers MP_ADD_CARRY(a4, r4, r4, carry, carry);
594f9fbec18Smcpowers MP_ADD_CARRY(a5, r5, r5, carry, carry);
595f9fbec18Smcpowers
596f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 6));
597f9fbec18Smcpowers MP_DIGIT(r, 5) = r5;
598f9fbec18Smcpowers MP_DIGIT(r, 4) = r4;
599f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
600f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
601f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
602f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
603f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
604f9fbec18Smcpowers MP_USED(r) = 6;
605f9fbec18Smcpowers
606*55fea89dSDan Cross /* Do quick 'subract' if we've gone over
607f9fbec18Smcpowers * (add the 2's complement of the curve field) */
608f9fbec18Smcpowers a5 = MP_DIGIT(&meth->irr,5);
609f9fbec18Smcpowers if (carry || r5 > a5 ||
610f9fbec18Smcpowers ((r5 == a5) && mp_cmp(r,&meth->irr) != MP_LT)) {
611f9fbec18Smcpowers a4 = MP_DIGIT(&meth->irr,4);
612f9fbec18Smcpowers a3 = MP_DIGIT(&meth->irr,3);
613f9fbec18Smcpowers a2 = MP_DIGIT(&meth->irr,2);
614f9fbec18Smcpowers a1 = MP_DIGIT(&meth->irr,1);
615f9fbec18Smcpowers a0 = MP_DIGIT(&meth->irr,0);
616f9fbec18Smcpowers MP_SUB_BORROW(r0, a0, r0, 0, carry);
617f9fbec18Smcpowers MP_SUB_BORROW(r1, a1, r1, carry, carry);
618f9fbec18Smcpowers MP_SUB_BORROW(r2, a2, r2, carry, carry);
619f9fbec18Smcpowers MP_SUB_BORROW(r3, a3, r3, carry, carry);
620f9fbec18Smcpowers MP_SUB_BORROW(r4, a4, r4, carry, carry);
621f9fbec18Smcpowers MP_SUB_BORROW(r5, a5, r5, carry, carry);
622f9fbec18Smcpowers MP_DIGIT(r, 5) = r5;
623f9fbec18Smcpowers MP_DIGIT(r, 4) = r4;
624f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
625f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
626f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
627f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
628f9fbec18Smcpowers }
629*55fea89dSDan Cross
630f9fbec18Smcpowers s_mp_clamp(r);
631f9fbec18Smcpowers
632f9fbec18Smcpowers CLEANUP:
633f9fbec18Smcpowers return res;
634f9fbec18Smcpowers }
635f9fbec18Smcpowers
636f9fbec18Smcpowers /*
637f9fbec18Smcpowers * The following subraction functions do in-line subractions based
638f9fbec18Smcpowers * on our curve size.
639f9fbec18Smcpowers *
640f9fbec18Smcpowers * ... 3 words
641f9fbec18Smcpowers */
642f9fbec18Smcpowers mp_err
ec_GFp_sub_3(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)643*55fea89dSDan Cross ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,
644f9fbec18Smcpowers const GFMethod *meth)
645f9fbec18Smcpowers {
646f9fbec18Smcpowers mp_err res = MP_OKAY;
647f9fbec18Smcpowers mp_digit b0 = 0, b1 = 0, b2 = 0;
648f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0;
649f9fbec18Smcpowers mp_digit borrow;
650f9fbec18Smcpowers
651f9fbec18Smcpowers switch(MP_USED(a)) {
652f9fbec18Smcpowers case 3:
653f9fbec18Smcpowers r2 = MP_DIGIT(a,2);
65438a641c5SToomas Soome /* FALLTHROUGH */
655f9fbec18Smcpowers case 2:
656f9fbec18Smcpowers r1 = MP_DIGIT(a,1);
65738a641c5SToomas Soome /* FALLTHROUGH */
658f9fbec18Smcpowers case 1:
659f9fbec18Smcpowers r0 = MP_DIGIT(a,0);
660f9fbec18Smcpowers }
661f9fbec18Smcpowers switch(MP_USED(b)) {
662f9fbec18Smcpowers case 3:
663f9fbec18Smcpowers b2 = MP_DIGIT(b,2);
66438a641c5SToomas Soome /* FALLTHROUGH */
665f9fbec18Smcpowers case 2:
666f9fbec18Smcpowers b1 = MP_DIGIT(b,1);
66738a641c5SToomas Soome /* FALLTHROUGH */
668f9fbec18Smcpowers case 1:
669f9fbec18Smcpowers b0 = MP_DIGIT(b,0);
670f9fbec18Smcpowers }
671f9fbec18Smcpowers
672f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
673f9fbec18Smcpowers MP_SUB_BORROW(r0, b0, r0, 0, borrow);
674f9fbec18Smcpowers MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
675f9fbec18Smcpowers MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
676f9fbec18Smcpowers #else
677f9fbec18Smcpowers __asm__ (
678f9fbec18Smcpowers "xorq %3,%3 \n\t"
679f9fbec18Smcpowers "subq %4,%0 \n\t"
680f9fbec18Smcpowers "sbbq %5,%1 \n\t"
681f9fbec18Smcpowers "sbbq %6,%2 \n\t"
682f9fbec18Smcpowers "adcq $0,%3 \n\t"
683f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r" (borrow)
684*55fea89dSDan Cross : "r" (b0), "r" (b1), "r" (b2),
685f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2)
686f9fbec18Smcpowers : "%cc" );
687f9fbec18Smcpowers #endif
688f9fbec18Smcpowers
689f9fbec18Smcpowers /* Do quick 'add' if we've gone under 0
690f9fbec18Smcpowers * (subtract the 2's complement of the curve field) */
691f9fbec18Smcpowers if (borrow) {
692f9fbec18Smcpowers b2 = MP_DIGIT(&meth->irr,2);
693f9fbec18Smcpowers b1 = MP_DIGIT(&meth->irr,1);
694f9fbec18Smcpowers b0 = MP_DIGIT(&meth->irr,0);
695f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
696f9fbec18Smcpowers MP_ADD_CARRY(b0, r0, r0, 0, borrow);
697f9fbec18Smcpowers MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
698f9fbec18Smcpowers MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
699f9fbec18Smcpowers #else
700f9fbec18Smcpowers __asm__ (
701f9fbec18Smcpowers "addq %3,%0 \n\t"
702f9fbec18Smcpowers "adcq %4,%1 \n\t"
703f9fbec18Smcpowers "adcq %5,%2 \n\t"
704f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2)
705f9fbec18Smcpowers : "r" (b0), "r" (b1), "r" (b2),
706f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2)
707f9fbec18Smcpowers : "%cc" );
708f9fbec18Smcpowers #endif
709f9fbec18Smcpowers }
710f9fbec18Smcpowers
711f9fbec18Smcpowers #ifdef MPI_AMD64_ADD
712f9fbec18Smcpowers /* compiler fakeout? */
713*55fea89dSDan Cross if ((r2 == b0) && (r1 == b0) && (r0 == b0)) {
714f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 4));
715*55fea89dSDan Cross }
716f9fbec18Smcpowers #endif
717f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 3));
718f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
719f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
720f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
721f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
722f9fbec18Smcpowers MP_USED(r) = 3;
723f9fbec18Smcpowers s_mp_clamp(r);
724f9fbec18Smcpowers
725f9fbec18Smcpowers CLEANUP:
726f9fbec18Smcpowers return res;
727f9fbec18Smcpowers }
728f9fbec18Smcpowers
729f9fbec18Smcpowers /* 4 words */
730f9fbec18Smcpowers mp_err
ec_GFp_sub_4(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)731*55fea89dSDan Cross ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,
732f9fbec18Smcpowers const GFMethod *meth)
733f9fbec18Smcpowers {
734f9fbec18Smcpowers mp_err res = MP_OKAY;
735f9fbec18Smcpowers mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0;
736f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
737f9fbec18Smcpowers mp_digit borrow;
738f9fbec18Smcpowers
739f9fbec18Smcpowers switch(MP_USED(a)) {
740f9fbec18Smcpowers case 4:
741f9fbec18Smcpowers r3 = MP_DIGIT(a,3);
74238a641c5SToomas Soome /* FALLTHROUGH */
743f9fbec18Smcpowers case 3:
744f9fbec18Smcpowers r2 = MP_DIGIT(a,2);
74538a641c5SToomas Soome /* FALLTHROUGH */
746f9fbec18Smcpowers case 2:
747f9fbec18Smcpowers r1 = MP_DIGIT(a,1);
74838a641c5SToomas Soome /* FALLTHROUGH */
749f9fbec18Smcpowers case 1:
750f9fbec18Smcpowers r0 = MP_DIGIT(a,0);
751f9fbec18Smcpowers }
752f9fbec18Smcpowers switch(MP_USED(b)) {
753f9fbec18Smcpowers case 4:
754f9fbec18Smcpowers b3 = MP_DIGIT(b,3);
75538a641c5SToomas Soome /* FALLTHROUGH */
756f9fbec18Smcpowers case 3:
757f9fbec18Smcpowers b2 = MP_DIGIT(b,2);
75838a641c5SToomas Soome /* FALLTHROUGH */
759f9fbec18Smcpowers case 2:
760f9fbec18Smcpowers b1 = MP_DIGIT(b,1);
76138a641c5SToomas Soome /* FALLTHROUGH */
762f9fbec18Smcpowers case 1:
763f9fbec18Smcpowers b0 = MP_DIGIT(b,0);
764f9fbec18Smcpowers }
765f9fbec18Smcpowers
766f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
767f9fbec18Smcpowers MP_SUB_BORROW(r0, b0, r0, 0, borrow);
768f9fbec18Smcpowers MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
769f9fbec18Smcpowers MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
770f9fbec18Smcpowers MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
771f9fbec18Smcpowers #else
772f9fbec18Smcpowers __asm__ (
773f9fbec18Smcpowers "xorq %4,%4 \n\t"
774f9fbec18Smcpowers "subq %5,%0 \n\t"
775f9fbec18Smcpowers "sbbq %6,%1 \n\t"
776f9fbec18Smcpowers "sbbq %7,%2 \n\t"
777f9fbec18Smcpowers "sbbq %8,%3 \n\t"
778f9fbec18Smcpowers "adcq $0,%4 \n\t"
779f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r" (borrow)
780f9fbec18Smcpowers : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
781f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2), "3" (r3)
782f9fbec18Smcpowers : "%cc" );
783f9fbec18Smcpowers #endif
784f9fbec18Smcpowers
785f9fbec18Smcpowers /* Do quick 'add' if we've gone under 0
786f9fbec18Smcpowers * (subtract the 2's complement of the curve field) */
787f9fbec18Smcpowers if (borrow) {
788f9fbec18Smcpowers b3 = MP_DIGIT(&meth->irr,3);
789f9fbec18Smcpowers b2 = MP_DIGIT(&meth->irr,2);
790f9fbec18Smcpowers b1 = MP_DIGIT(&meth->irr,1);
791f9fbec18Smcpowers b0 = MP_DIGIT(&meth->irr,0);
792f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
793f9fbec18Smcpowers MP_ADD_CARRY(b0, r0, r0, 0, borrow);
794f9fbec18Smcpowers MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
795f9fbec18Smcpowers MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
796f9fbec18Smcpowers MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
797f9fbec18Smcpowers #else
798f9fbec18Smcpowers __asm__ (
799f9fbec18Smcpowers "addq %4,%0 \n\t"
800f9fbec18Smcpowers "adcq %5,%1 \n\t"
801f9fbec18Smcpowers "adcq %6,%2 \n\t"
802f9fbec18Smcpowers "adcq %7,%3 \n\t"
803f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
804f9fbec18Smcpowers : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
805f9fbec18Smcpowers "0" (r0), "1" (r1), "2" (r2), "3" (r3)
806f9fbec18Smcpowers : "%cc" );
807f9fbec18Smcpowers #endif
808f9fbec18Smcpowers }
809f9fbec18Smcpowers #ifdef MPI_AMD64_ADD
810f9fbec18Smcpowers /* compiler fakeout? */
811*55fea89dSDan Cross if ((r3 == b0) && (r1 == b0) && (r0 == b0)) {
812f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 4));
813*55fea89dSDan Cross }
814f9fbec18Smcpowers #endif
815f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 4));
816f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
817f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
818f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
819f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
820f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
821f9fbec18Smcpowers MP_USED(r) = 4;
822f9fbec18Smcpowers s_mp_clamp(r);
823f9fbec18Smcpowers
824f9fbec18Smcpowers CLEANUP:
825f9fbec18Smcpowers return res;
826f9fbec18Smcpowers }
827f9fbec18Smcpowers
828f9fbec18Smcpowers /* 5 words */
829f9fbec18Smcpowers mp_err
ec_GFp_sub_5(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)830*55fea89dSDan Cross ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,
831f9fbec18Smcpowers const GFMethod *meth)
832f9fbec18Smcpowers {
833f9fbec18Smcpowers mp_err res = MP_OKAY;
834f9fbec18Smcpowers mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0;
835f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
836f9fbec18Smcpowers mp_digit borrow;
837f9fbec18Smcpowers
838f9fbec18Smcpowers switch(MP_USED(a)) {
839f9fbec18Smcpowers case 5:
840f9fbec18Smcpowers r4 = MP_DIGIT(a,4);
84138a641c5SToomas Soome /* FALLTHROUGH */
842f9fbec18Smcpowers case 4:
843f9fbec18Smcpowers r3 = MP_DIGIT(a,3);
84438a641c5SToomas Soome /* FALLTHROUGH */
845f9fbec18Smcpowers case 3:
846f9fbec18Smcpowers r2 = MP_DIGIT(a,2);
84738a641c5SToomas Soome /* FALLTHROUGH */
848f9fbec18Smcpowers case 2:
849f9fbec18Smcpowers r1 = MP_DIGIT(a,1);
85038a641c5SToomas Soome /* FALLTHROUGH */
851f9fbec18Smcpowers case 1:
852f9fbec18Smcpowers r0 = MP_DIGIT(a,0);
853f9fbec18Smcpowers }
854f9fbec18Smcpowers switch(MP_USED(b)) {
855f9fbec18Smcpowers case 5:
856f9fbec18Smcpowers b4 = MP_DIGIT(b,4);
85738a641c5SToomas Soome /* FALLTHROUGH */
858f9fbec18Smcpowers case 4:
859f9fbec18Smcpowers b3 = MP_DIGIT(b,3);
86038a641c5SToomas Soome /* FALLTHROUGH */
861f9fbec18Smcpowers case 3:
862f9fbec18Smcpowers b2 = MP_DIGIT(b,2);
86338a641c5SToomas Soome /* FALLTHROUGH */
864f9fbec18Smcpowers case 2:
865f9fbec18Smcpowers b1 = MP_DIGIT(b,1);
86638a641c5SToomas Soome /* FALLTHROUGH */
867f9fbec18Smcpowers case 1:
868f9fbec18Smcpowers b0 = MP_DIGIT(b,0);
869f9fbec18Smcpowers }
870f9fbec18Smcpowers
871f9fbec18Smcpowers MP_SUB_BORROW(r0, b0, r0, 0, borrow);
872f9fbec18Smcpowers MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
873f9fbec18Smcpowers MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
874f9fbec18Smcpowers MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
875f9fbec18Smcpowers MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
876f9fbec18Smcpowers
877f9fbec18Smcpowers /* Do quick 'add' if we've gone under 0
878f9fbec18Smcpowers * (subtract the 2's complement of the curve field) */
879f9fbec18Smcpowers if (borrow) {
880f9fbec18Smcpowers b4 = MP_DIGIT(&meth->irr,4);
881f9fbec18Smcpowers b3 = MP_DIGIT(&meth->irr,3);
882f9fbec18Smcpowers b2 = MP_DIGIT(&meth->irr,2);
883f9fbec18Smcpowers b1 = MP_DIGIT(&meth->irr,1);
884f9fbec18Smcpowers b0 = MP_DIGIT(&meth->irr,0);
885f9fbec18Smcpowers MP_ADD_CARRY(b0, r0, r0, 0, borrow);
886f9fbec18Smcpowers MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
887f9fbec18Smcpowers MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
888f9fbec18Smcpowers MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
889f9fbec18Smcpowers }
890f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 5));
891f9fbec18Smcpowers MP_DIGIT(r, 4) = r4;
892f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
893f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
894f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
895f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
896f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
897f9fbec18Smcpowers MP_USED(r) = 5;
898f9fbec18Smcpowers s_mp_clamp(r);
899f9fbec18Smcpowers
900f9fbec18Smcpowers CLEANUP:
901f9fbec18Smcpowers return res;
902f9fbec18Smcpowers }
903f9fbec18Smcpowers
904f9fbec18Smcpowers /* 6 words */
905f9fbec18Smcpowers mp_err
ec_GFp_sub_6(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)906*55fea89dSDan Cross ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,
907f9fbec18Smcpowers const GFMethod *meth)
908f9fbec18Smcpowers {
909f9fbec18Smcpowers mp_err res = MP_OKAY;
910f9fbec18Smcpowers mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0;
911f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
912f9fbec18Smcpowers mp_digit borrow;
913f9fbec18Smcpowers
914f9fbec18Smcpowers switch(MP_USED(a)) {
915f9fbec18Smcpowers case 6:
916f9fbec18Smcpowers r5 = MP_DIGIT(a,5);
91738a641c5SToomas Soome /* FALLTHROUGH */
918f9fbec18Smcpowers case 5:
919f9fbec18Smcpowers r4 = MP_DIGIT(a,4);
92038a641c5SToomas Soome /* FALLTHROUGH */
921f9fbec18Smcpowers case 4:
922f9fbec18Smcpowers r3 = MP_DIGIT(a,3);
92338a641c5SToomas Soome /* FALLTHROUGH */
924f9fbec18Smcpowers case 3:
925f9fbec18Smcpowers r2 = MP_DIGIT(a,2);
92638a641c5SToomas Soome /* FALLTHROUGH */
927f9fbec18Smcpowers case 2:
928f9fbec18Smcpowers r1 = MP_DIGIT(a,1);
92938a641c5SToomas Soome /* FALLTHROUGH */
930f9fbec18Smcpowers case 1:
931f9fbec18Smcpowers r0 = MP_DIGIT(a,0);
932f9fbec18Smcpowers }
933f9fbec18Smcpowers switch(MP_USED(b)) {
934f9fbec18Smcpowers case 6:
935f9fbec18Smcpowers b5 = MP_DIGIT(b,5);
93638a641c5SToomas Soome /* FALLTHROUGH */
937f9fbec18Smcpowers case 5:
938f9fbec18Smcpowers b4 = MP_DIGIT(b,4);
93938a641c5SToomas Soome /* FALLTHROUGH */
940f9fbec18Smcpowers case 4:
941f9fbec18Smcpowers b3 = MP_DIGIT(b,3);
94238a641c5SToomas Soome /* FALLTHROUGH */
943f9fbec18Smcpowers case 3:
944f9fbec18Smcpowers b2 = MP_DIGIT(b,2);
94538a641c5SToomas Soome /* FALLTHROUGH */
946f9fbec18Smcpowers case 2:
947f9fbec18Smcpowers b1 = MP_DIGIT(b,1);
94838a641c5SToomas Soome /* FALLTHROUGH */
949f9fbec18Smcpowers case 1:
950f9fbec18Smcpowers b0 = MP_DIGIT(b,0);
951f9fbec18Smcpowers }
952f9fbec18Smcpowers
953f9fbec18Smcpowers MP_SUB_BORROW(r0, b0, r0, 0, borrow);
954f9fbec18Smcpowers MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
955f9fbec18Smcpowers MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
956f9fbec18Smcpowers MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
957f9fbec18Smcpowers MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
958f9fbec18Smcpowers MP_SUB_BORROW(r5, b5, r5, borrow, borrow);
959f9fbec18Smcpowers
960f9fbec18Smcpowers /* Do quick 'add' if we've gone under 0
961f9fbec18Smcpowers * (subtract the 2's complement of the curve field) */
962f9fbec18Smcpowers if (borrow) {
963f9fbec18Smcpowers b5 = MP_DIGIT(&meth->irr,5);
964f9fbec18Smcpowers b4 = MP_DIGIT(&meth->irr,4);
965f9fbec18Smcpowers b3 = MP_DIGIT(&meth->irr,3);
966f9fbec18Smcpowers b2 = MP_DIGIT(&meth->irr,2);
967f9fbec18Smcpowers b1 = MP_DIGIT(&meth->irr,1);
968f9fbec18Smcpowers b0 = MP_DIGIT(&meth->irr,0);
969f9fbec18Smcpowers MP_ADD_CARRY(b0, r0, r0, 0, borrow);
970f9fbec18Smcpowers MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
971f9fbec18Smcpowers MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
972f9fbec18Smcpowers MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
973f9fbec18Smcpowers MP_ADD_CARRY(b4, r4, r4, borrow, borrow);
974f9fbec18Smcpowers }
975f9fbec18Smcpowers
976f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 6));
977f9fbec18Smcpowers MP_DIGIT(r, 5) = r5;
978f9fbec18Smcpowers MP_DIGIT(r, 4) = r4;
979f9fbec18Smcpowers MP_DIGIT(r, 3) = r3;
980f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
981f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
982f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
983f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
984f9fbec18Smcpowers MP_USED(r) = 6;
985f9fbec18Smcpowers s_mp_clamp(r);
986f9fbec18Smcpowers
987f9fbec18Smcpowers CLEANUP:
988f9fbec18Smcpowers return res;
989f9fbec18Smcpowers }
990f9fbec18Smcpowers
991f9fbec18Smcpowers
992f9fbec18Smcpowers /* Reduces an integer to a field element. */
993f9fbec18Smcpowers mp_err
ec_GFp_mod(const mp_int * a,mp_int * r,const GFMethod * meth)994f9fbec18Smcpowers ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
995f9fbec18Smcpowers {
996f9fbec18Smcpowers return mp_mod(a, &meth->irr, r);
997f9fbec18Smcpowers }
998f9fbec18Smcpowers
999f9fbec18Smcpowers /* Multiplies two field elements. */
1000f9fbec18Smcpowers mp_err
ec_GFp_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1001f9fbec18Smcpowers ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
1002f9fbec18Smcpowers const GFMethod *meth)
1003f9fbec18Smcpowers {
1004f9fbec18Smcpowers return mp_mulmod(a, b, &meth->irr, r);
1005f9fbec18Smcpowers }
1006f9fbec18Smcpowers
1007f9fbec18Smcpowers /* Squares a field element. */
1008f9fbec18Smcpowers mp_err
ec_GFp_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)1009f9fbec18Smcpowers ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
1010f9fbec18Smcpowers {
1011f9fbec18Smcpowers return mp_sqrmod(a, &meth->irr, r);
1012f9fbec18Smcpowers }
1013f9fbec18Smcpowers
1014f9fbec18Smcpowers /* Divides two field elements. If a is NULL, then returns the inverse of
1015f9fbec18Smcpowers * b. */
1016f9fbec18Smcpowers mp_err
ec_GFp_div(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1017f9fbec18Smcpowers ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
1018f9fbec18Smcpowers const GFMethod *meth)
1019f9fbec18Smcpowers {
1020f9fbec18Smcpowers mp_err res = MP_OKAY;
1021f9fbec18Smcpowers mp_int t;
1022f9fbec18Smcpowers
1023f9fbec18Smcpowers /* If a is NULL, then return the inverse of b, otherwise return a/b. */
1024f9fbec18Smcpowers if (a == NULL) {
1025f9fbec18Smcpowers return mp_invmod(b, &meth->irr, r);
1026f9fbec18Smcpowers } else {
1027*55fea89dSDan Cross /* MPI doesn't support divmod, so we implement it using invmod and
1028f9fbec18Smcpowers * mulmod. */
1029f9fbec18Smcpowers MP_CHECKOK(mp_init(&t, FLAG(b)));
1030f9fbec18Smcpowers MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
1031f9fbec18Smcpowers MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r));
1032f9fbec18Smcpowers CLEANUP:
1033f9fbec18Smcpowers mp_clear(&t);
1034f9fbec18Smcpowers return res;
1035f9fbec18Smcpowers }
1036f9fbec18Smcpowers }
1037f9fbec18Smcpowers
1038f9fbec18Smcpowers /* Wrapper functions for generic binary polynomial field arithmetic. */
1039f9fbec18Smcpowers
1040f9fbec18Smcpowers /* Adds two field elements. */
1041f9fbec18Smcpowers mp_err
ec_GF2m_add(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1042f9fbec18Smcpowers ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
1043f9fbec18Smcpowers const GFMethod *meth)
1044f9fbec18Smcpowers {
1045f9fbec18Smcpowers return mp_badd(a, b, r);
1046f9fbec18Smcpowers }
1047f9fbec18Smcpowers
1048f9fbec18Smcpowers /* Negates a field element. Note that for binary polynomial fields, the
1049f9fbec18Smcpowers * negation of a field element is the field element itself. */
1050f9fbec18Smcpowers mp_err
ec_GF2m_neg(const mp_int * a,mp_int * r,const GFMethod * meth)1051f9fbec18Smcpowers ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
1052f9fbec18Smcpowers {
1053f9fbec18Smcpowers if (a == r) {
1054f9fbec18Smcpowers return MP_OKAY;
1055f9fbec18Smcpowers } else {
1056f9fbec18Smcpowers return mp_copy(a, r);
1057f9fbec18Smcpowers }
1058f9fbec18Smcpowers }
1059f9fbec18Smcpowers
1060f9fbec18Smcpowers /* Reduces a binary polynomial to a field element. */
1061f9fbec18Smcpowers mp_err
ec_GF2m_mod(const mp_int * a,mp_int * r,const GFMethod * meth)1062f9fbec18Smcpowers ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
1063f9fbec18Smcpowers {
1064f9fbec18Smcpowers return mp_bmod(a, meth->irr_arr, r);
1065f9fbec18Smcpowers }
1066f9fbec18Smcpowers
1067f9fbec18Smcpowers /* Multiplies two field elements. */
1068f9fbec18Smcpowers mp_err
ec_GF2m_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1069f9fbec18Smcpowers ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
1070f9fbec18Smcpowers const GFMethod *meth)
1071f9fbec18Smcpowers {
1072f9fbec18Smcpowers return mp_bmulmod(a, b, meth->irr_arr, r);
1073f9fbec18Smcpowers }
1074f9fbec18Smcpowers
1075f9fbec18Smcpowers /* Squares a field element. */
1076f9fbec18Smcpowers mp_err
ec_GF2m_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)1077f9fbec18Smcpowers ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
1078f9fbec18Smcpowers {
1079f9fbec18Smcpowers return mp_bsqrmod(a, meth->irr_arr, r);
1080f9fbec18Smcpowers }
1081f9fbec18Smcpowers
1082f9fbec18Smcpowers /* Divides two field elements. If a is NULL, then returns the inverse of
1083f9fbec18Smcpowers * b. */
1084f9fbec18Smcpowers mp_err
ec_GF2m_div(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)1085f9fbec18Smcpowers ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
1086f9fbec18Smcpowers const GFMethod *meth)
1087f9fbec18Smcpowers {
1088f9fbec18Smcpowers mp_err res = MP_OKAY;
1089f9fbec18Smcpowers mp_int t;
1090f9fbec18Smcpowers
1091f9fbec18Smcpowers /* If a is NULL, then return the inverse of b, otherwise return a/b. */
1092f9fbec18Smcpowers if (a == NULL) {
1093f9fbec18Smcpowers /* The GF(2^m) portion of MPI doesn't support invmod, so we
1094f9fbec18Smcpowers * compute 1/b. */
1095f9fbec18Smcpowers MP_CHECKOK(mp_init(&t, FLAG(b)));
1096f9fbec18Smcpowers MP_CHECKOK(mp_set_int(&t, 1));
1097f9fbec18Smcpowers MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r));
1098f9fbec18Smcpowers CLEANUP:
1099f9fbec18Smcpowers mp_clear(&t);
1100f9fbec18Smcpowers return res;
1101f9fbec18Smcpowers } else {
1102f9fbec18Smcpowers return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r);
1103f9fbec18Smcpowers }
1104f9fbec18Smcpowers }
1105