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 for prime 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 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
24f9fbec18Smcpowers *
25f9fbec18Smcpowers * Alternatively, the contents of this file may be used under the terms of
26f9fbec18Smcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
27f9fbec18Smcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28f9fbec18Smcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
29f9fbec18Smcpowers * of those above. If you wish to allow use of your version of this file only
30f9fbec18Smcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
31f9fbec18Smcpowers * use your version of this file under the terms of the MPL, indicate your
32f9fbec18Smcpowers * decision by deleting the provisions above and replace them with the notice
33f9fbec18Smcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
34f9fbec18Smcpowers * the provisions above, a recipient may use your version of this file under
35f9fbec18Smcpowers * the terms of any one of the MPL, the GPL or the LGPL.
36f9fbec18Smcpowers *
37f9fbec18Smcpowers * ***** END LICENSE BLOCK ***** */
38f9fbec18Smcpowers /*
39f9fbec18Smcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
40f9fbec18Smcpowers * Use is subject to license terms.
41f9fbec18Smcpowers *
42f9fbec18Smcpowers * Sun elects to use this software under the MPL license.
43f9fbec18Smcpowers */
44f9fbec18Smcpowers
45f9fbec18Smcpowers #include "ecp.h"
46f9fbec18Smcpowers #include "mpi.h"
47f9fbec18Smcpowers #include "mplogic.h"
48f9fbec18Smcpowers #include "mpi-priv.h"
49f9fbec18Smcpowers #ifndef _KERNEL
50f9fbec18Smcpowers #include <stdlib.h>
51f9fbec18Smcpowers #endif
52f9fbec18Smcpowers
53f9fbec18Smcpowers #define ECP192_DIGITS ECL_CURVE_DIGITS(192)
54f9fbec18Smcpowers
55f9fbec18Smcpowers /* Fast modular reduction for p192 = 2^192 - 2^64 - 1. a can be r. Uses
56f9fbec18Smcpowers * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software
57f9fbec18Smcpowers * Implementation of the NIST Elliptic Curves over Prime Fields. */
58f9fbec18Smcpowers mp_err
ec_GFp_nistp192_mod(const mp_int * a,mp_int * r,const GFMethod * meth)59f9fbec18Smcpowers ec_GFp_nistp192_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
60f9fbec18Smcpowers {
61f9fbec18Smcpowers mp_err res = MP_OKAY;
62f9fbec18Smcpowers mp_size a_used = MP_USED(a);
63f9fbec18Smcpowers mp_digit r3;
64*55fea89dSDan Cross #ifndef MPI_AMD64_ADD
65f9fbec18Smcpowers mp_digit carry;
66f9fbec18Smcpowers #endif
67f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
68f9fbec18Smcpowers mp_digit a5a = 0, a5b = 0, a4a = 0, a4b = 0, a3a = 0, a3b = 0;
69f9fbec18Smcpowers mp_digit r0a, r0b, r1a, r1b, r2a, r2b;
70f9fbec18Smcpowers #else
71f9fbec18Smcpowers mp_digit a5 = 0, a4 = 0, a3 = 0;
72f9fbec18Smcpowers mp_digit r0, r1, r2;
73f9fbec18Smcpowers #endif
74f9fbec18Smcpowers
75f9fbec18Smcpowers /* reduction not needed if a is not larger than field size */
76f9fbec18Smcpowers if (a_used < ECP192_DIGITS) {
77f9fbec18Smcpowers if (a == r) {
78f9fbec18Smcpowers return MP_OKAY;
79f9fbec18Smcpowers }
80f9fbec18Smcpowers return mp_copy(a, r);
81f9fbec18Smcpowers }
82f9fbec18Smcpowers
83f9fbec18Smcpowers /* for polynomials larger than twice the field size, use regular
84f9fbec18Smcpowers * reduction */
85f9fbec18Smcpowers if (a_used > ECP192_DIGITS*2) {
86f9fbec18Smcpowers MP_CHECKOK(mp_mod(a, &meth->irr, r));
87f9fbec18Smcpowers } else {
88f9fbec18Smcpowers /* copy out upper words of a */
89f9fbec18Smcpowers
90f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
91f9fbec18Smcpowers
92f9fbec18Smcpowers /* in all the math below,
93f9fbec18Smcpowers * nXb is most signifiant, nXa is least significant */
94f9fbec18Smcpowers switch (a_used) {
95f9fbec18Smcpowers case 12:
96f9fbec18Smcpowers a5b = MP_DIGIT(a, 11);
9738a641c5SToomas Soome /* FALLTHROUGH */
98f9fbec18Smcpowers case 11:
99f9fbec18Smcpowers a5a = MP_DIGIT(a, 10);
10038a641c5SToomas Soome /* FALLTHROUGH */
101f9fbec18Smcpowers case 10:
102f9fbec18Smcpowers a4b = MP_DIGIT(a, 9);
10338a641c5SToomas Soome /* FALLTHROUGH */
104f9fbec18Smcpowers case 9:
105f9fbec18Smcpowers a4a = MP_DIGIT(a, 8);
10638a641c5SToomas Soome /* FALLTHROUGH */
107f9fbec18Smcpowers case 8:
108f9fbec18Smcpowers a3b = MP_DIGIT(a, 7);
10938a641c5SToomas Soome /* FALLTHROUGH */
110f9fbec18Smcpowers case 7:
111f9fbec18Smcpowers a3a = MP_DIGIT(a, 6);
112f9fbec18Smcpowers }
113f9fbec18Smcpowers
114f9fbec18Smcpowers
115f9fbec18Smcpowers r2b= MP_DIGIT(a, 5);
116f9fbec18Smcpowers r2a= MP_DIGIT(a, 4);
117f9fbec18Smcpowers r1b = MP_DIGIT(a, 3);
118f9fbec18Smcpowers r1a = MP_DIGIT(a, 2);
119f9fbec18Smcpowers r0b = MP_DIGIT(a, 1);
120f9fbec18Smcpowers r0a = MP_DIGIT(a, 0);
121f9fbec18Smcpowers
122f9fbec18Smcpowers /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */
123f9fbec18Smcpowers MP_ADD_CARRY(r0a, a3a, r0a, 0, carry);
124f9fbec18Smcpowers MP_ADD_CARRY(r0b, a3b, r0b, carry, carry);
125f9fbec18Smcpowers MP_ADD_CARRY(r1a, a3a, r1a, carry, carry);
126f9fbec18Smcpowers MP_ADD_CARRY(r1b, a3b, r1b, carry, carry);
127f9fbec18Smcpowers MP_ADD_CARRY(r2a, a4a, r2a, carry, carry);
128f9fbec18Smcpowers MP_ADD_CARRY(r2b, a4b, r2b, carry, carry);
129f9fbec18Smcpowers r3 = carry; carry = 0;
130f9fbec18Smcpowers MP_ADD_CARRY(r0a, a5a, r0a, 0, carry);
131f9fbec18Smcpowers MP_ADD_CARRY(r0b, a5b, r0b, carry, carry);
132f9fbec18Smcpowers MP_ADD_CARRY(r1a, a5a, r1a, carry, carry);
133f9fbec18Smcpowers MP_ADD_CARRY(r1b, a5b, r1b, carry, carry);
134f9fbec18Smcpowers MP_ADD_CARRY(r2a, a5a, r2a, carry, carry);
135f9fbec18Smcpowers MP_ADD_CARRY(r2b, a5b, r2b, carry, carry);
136*55fea89dSDan Cross r3 += carry;
137f9fbec18Smcpowers MP_ADD_CARRY(r1a, a4a, r1a, 0, carry);
138f9fbec18Smcpowers MP_ADD_CARRY(r1b, a4b, r1b, carry, carry);
139f9fbec18Smcpowers MP_ADD_CARRY(r2a, 0, r2a, carry, carry);
140f9fbec18Smcpowers MP_ADD_CARRY(r2b, 0, r2b, carry, carry);
141f9fbec18Smcpowers r3 += carry;
142f9fbec18Smcpowers
143f9fbec18Smcpowers /* reduce out the carry */
144f9fbec18Smcpowers while (r3) {
145f9fbec18Smcpowers MP_ADD_CARRY(r0a, r3, r0a, 0, carry);
146f9fbec18Smcpowers MP_ADD_CARRY(r0b, 0, r0b, carry, carry);
147f9fbec18Smcpowers MP_ADD_CARRY(r1a, r3, r1a, carry, carry);
148f9fbec18Smcpowers MP_ADD_CARRY(r1b, 0, r1b, carry, carry);
149f9fbec18Smcpowers MP_ADD_CARRY(r2a, 0, r2a, carry, carry);
150f9fbec18Smcpowers MP_ADD_CARRY(r2b, 0, r2b, carry, carry);
151f9fbec18Smcpowers r3 = carry;
152f9fbec18Smcpowers }
153f9fbec18Smcpowers
154f9fbec18Smcpowers /* check for final reduction */
155f9fbec18Smcpowers /*
156f9fbec18Smcpowers * our field is 0xffffffffffffffff, 0xfffffffffffffffe,
157f9fbec18Smcpowers * 0xffffffffffffffff. That means we can only be over and need
158*55fea89dSDan Cross * one more reduction
159*55fea89dSDan Cross * if r2 == 0xffffffffffffffffff (same as r2+1 == 0)
160f9fbec18Smcpowers * and
161f9fbec18Smcpowers * r1 == 0xffffffffffffffffff or
162f9fbec18Smcpowers * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff
163*55fea89dSDan Cross * In all cases, we subtract the field (or add the 2's
164f9fbec18Smcpowers * complement value (1,1,0)). (r0, r1, r2)
165f9fbec18Smcpowers */
166*55fea89dSDan Cross if (((r2b == 0xffffffff) && (r2a == 0xffffffff)
167f9fbec18Smcpowers && (r1b == 0xffffffff) ) &&
168*55fea89dSDan Cross ((r1a == 0xffffffff) ||
169f9fbec18Smcpowers (r1a == 0xfffffffe) && (r0a == 0xffffffff) &&
170f9fbec18Smcpowers (r0b == 0xffffffff)) ) {
171f9fbec18Smcpowers /* do a quick subtract */
172f9fbec18Smcpowers MP_ADD_CARRY(r0a, 1, r0a, 0, carry);
173f9fbec18Smcpowers r0b += carry;
174f9fbec18Smcpowers r1a = r1b = r2a = r2b = 0;
175f9fbec18Smcpowers }
176f9fbec18Smcpowers
177f9fbec18Smcpowers /* set the lower words of r */
178f9fbec18Smcpowers if (a != r) {
179f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 6));
180f9fbec18Smcpowers }
181f9fbec18Smcpowers MP_DIGIT(r, 5) = r2b;
182f9fbec18Smcpowers MP_DIGIT(r, 4) = r2a;
183f9fbec18Smcpowers MP_DIGIT(r, 3) = r1b;
184f9fbec18Smcpowers MP_DIGIT(r, 2) = r1a;
185f9fbec18Smcpowers MP_DIGIT(r, 1) = r0b;
186f9fbec18Smcpowers MP_DIGIT(r, 0) = r0a;
187f9fbec18Smcpowers MP_USED(r) = 6;
188f9fbec18Smcpowers #else
189f9fbec18Smcpowers switch (a_used) {
190f9fbec18Smcpowers case 6:
191f9fbec18Smcpowers a5 = MP_DIGIT(a, 5);
19238a641c5SToomas Soome /* FALLTHROUGH */
193f9fbec18Smcpowers case 5:
194f9fbec18Smcpowers a4 = MP_DIGIT(a, 4);
19538a641c5SToomas Soome /* FALLTHROUGH */
196f9fbec18Smcpowers case 4:
197f9fbec18Smcpowers a3 = MP_DIGIT(a, 3);
198f9fbec18Smcpowers }
199f9fbec18Smcpowers
200f9fbec18Smcpowers r2 = MP_DIGIT(a, 2);
201f9fbec18Smcpowers r1 = MP_DIGIT(a, 1);
202f9fbec18Smcpowers r0 = MP_DIGIT(a, 0);
203f9fbec18Smcpowers
204f9fbec18Smcpowers /* implement r = (a2,a1,a0)+(a5,a5,a5)+(a4,a4,0)+(0,a3,a3) */
205*55fea89dSDan Cross #ifndef MPI_AMD64_ADD
206f9fbec18Smcpowers MP_ADD_CARRY(r0, a3, r0, 0, carry);
207f9fbec18Smcpowers MP_ADD_CARRY(r1, a3, r1, carry, carry);
208f9fbec18Smcpowers MP_ADD_CARRY(r2, a4, r2, carry, carry);
209*55fea89dSDan Cross r3 = carry;
210f9fbec18Smcpowers MP_ADD_CARRY(r0, a5, r0, 0, carry);
211f9fbec18Smcpowers MP_ADD_CARRY(r1, a5, r1, carry, carry);
212f9fbec18Smcpowers MP_ADD_CARRY(r2, a5, r2, carry, carry);
213*55fea89dSDan Cross r3 += carry;
214f9fbec18Smcpowers MP_ADD_CARRY(r1, a4, r1, 0, carry);
215f9fbec18Smcpowers MP_ADD_CARRY(r2, 0, r2, carry, carry);
216f9fbec18Smcpowers r3 += carry;
217f9fbec18Smcpowers
218*55fea89dSDan Cross #else
219f9fbec18Smcpowers r2 = MP_DIGIT(a, 2);
220f9fbec18Smcpowers r1 = MP_DIGIT(a, 1);
221f9fbec18Smcpowers r0 = MP_DIGIT(a, 0);
222f9fbec18Smcpowers
223f9fbec18Smcpowers /* set the lower words of r */
224f9fbec18Smcpowers __asm__ (
225f9fbec18Smcpowers "xorq %3,%3 \n\t"
226f9fbec18Smcpowers "addq %4,%0 \n\t"
227f9fbec18Smcpowers "adcq %4,%1 \n\t"
228f9fbec18Smcpowers "adcq %5,%2 \n\t"
229f9fbec18Smcpowers "adcq $0,%3 \n\t"
230f9fbec18Smcpowers "addq %6,%0 \n\t"
231f9fbec18Smcpowers "adcq %6,%1 \n\t"
232f9fbec18Smcpowers "adcq %6,%2 \n\t"
233f9fbec18Smcpowers "adcq $0,%3 \n\t"
234f9fbec18Smcpowers "addq %5,%1 \n\t"
235f9fbec18Smcpowers "adcq $0,%2 \n\t"
236f9fbec18Smcpowers "adcq $0,%3 \n\t"
237*55fea89dSDan Cross : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3),
238f9fbec18Smcpowers "=r"(a4), "=r"(a5)
239*55fea89dSDan Cross : "0" (r0), "1" (r1), "2" (r2), "3" (r3),
240f9fbec18Smcpowers "4" (a3), "5" (a4), "6"(a5)
241f9fbec18Smcpowers : "%cc" );
242*55fea89dSDan Cross #endif
243f9fbec18Smcpowers
244f9fbec18Smcpowers /* reduce out the carry */
245f9fbec18Smcpowers while (r3) {
246f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
247f9fbec18Smcpowers MP_ADD_CARRY(r0, r3, r0, 0, carry);
248f9fbec18Smcpowers MP_ADD_CARRY(r1, r3, r1, carry, carry);
249f9fbec18Smcpowers MP_ADD_CARRY(r2, 0, r2, carry, carry);
250f9fbec18Smcpowers r3 = carry;
251f9fbec18Smcpowers #else
252f9fbec18Smcpowers a3=r3;
253f9fbec18Smcpowers __asm__ (
254f9fbec18Smcpowers "xorq %3,%3 \n\t"
255f9fbec18Smcpowers "addq %4,%0 \n\t"
256f9fbec18Smcpowers "adcq %4,%1 \n\t"
257f9fbec18Smcpowers "adcq $0,%2 \n\t"
258f9fbec18Smcpowers "adcq $0,%3 \n\t"
259f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(a3)
260f9fbec18Smcpowers : "0" (r0), "1" (r1), "2" (r2), "3" (r3), "4"(a3)
261f9fbec18Smcpowers : "%cc" );
262f9fbec18Smcpowers #endif
263f9fbec18Smcpowers }
264f9fbec18Smcpowers
265f9fbec18Smcpowers /* check for final reduction */
266f9fbec18Smcpowers /*
267f9fbec18Smcpowers * our field is 0xffffffffffffffff, 0xfffffffffffffffe,
268f9fbec18Smcpowers * 0xffffffffffffffff. That means we can only be over and need
269*55fea89dSDan Cross * one more reduction
270*55fea89dSDan Cross * if r2 == 0xffffffffffffffffff (same as r2+1 == 0)
271f9fbec18Smcpowers * and
272f9fbec18Smcpowers * r1 == 0xffffffffffffffffff or
273f9fbec18Smcpowers * r1 == 0xfffffffffffffffffe and r0 = 0xfffffffffffffffff
274*55fea89dSDan Cross * In all cases, we subtract the field (or add the 2's
275f9fbec18Smcpowers * complement value (1,1,0)). (r0, r1, r2)
276f9fbec18Smcpowers */
277f9fbec18Smcpowers if (r3 || ((r2 == MP_DIGIT_MAX) &&
278*55fea89dSDan Cross ((r1 == MP_DIGIT_MAX) ||
279f9fbec18Smcpowers ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) {
280f9fbec18Smcpowers /* do a quick subtract */
281f9fbec18Smcpowers r0++;
282f9fbec18Smcpowers r1 = r2 = 0;
283f9fbec18Smcpowers }
284f9fbec18Smcpowers /* set the lower words of r */
285f9fbec18Smcpowers if (a != r) {
286f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 3));
287f9fbec18Smcpowers }
288f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
289f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
290f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
291f9fbec18Smcpowers MP_USED(r) = 3;
292f9fbec18Smcpowers #endif
293f9fbec18Smcpowers }
294f9fbec18Smcpowers
295f9fbec18Smcpowers CLEANUP:
296f9fbec18Smcpowers return res;
297f9fbec18Smcpowers }
298f9fbec18Smcpowers
299f9fbec18Smcpowers #ifndef ECL_THIRTY_TWO_BIT
300f9fbec18Smcpowers /* Compute the sum of 192 bit curves. Do the work in-line since the
301f9fbec18Smcpowers * number of words are so small, we don't want to overhead of mp function
302*55fea89dSDan Cross * calls. Uses optimized modular reduction for p192.
303f9fbec18Smcpowers */
304f9fbec18Smcpowers mp_err
ec_GFp_nistp192_add(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)305*55fea89dSDan Cross ec_GFp_nistp192_add(const mp_int *a, const mp_int *b, mp_int *r,
306f9fbec18Smcpowers const GFMethod *meth)
307f9fbec18Smcpowers {
308f9fbec18Smcpowers mp_err res = MP_OKAY;
309f9fbec18Smcpowers mp_digit a0 = 0, a1 = 0, a2 = 0;
310f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0;
311f9fbec18Smcpowers mp_digit carry;
312f9fbec18Smcpowers
313f9fbec18Smcpowers switch(MP_USED(a)) {
314f9fbec18Smcpowers case 3:
315f9fbec18Smcpowers a2 = MP_DIGIT(a,2);
31638a641c5SToomas Soome /* FALLTHROUGH */
317f9fbec18Smcpowers case 2:
318f9fbec18Smcpowers a1 = MP_DIGIT(a,1);
31938a641c5SToomas Soome /* FALLTHROUGH */
320f9fbec18Smcpowers case 1:
321f9fbec18Smcpowers a0 = MP_DIGIT(a,0);
322f9fbec18Smcpowers }
323f9fbec18Smcpowers switch(MP_USED(b)) {
324f9fbec18Smcpowers case 3:
325f9fbec18Smcpowers r2 = MP_DIGIT(b,2);
32638a641c5SToomas Soome /* FALLTHROUGH */
327f9fbec18Smcpowers case 2:
328f9fbec18Smcpowers r1 = MP_DIGIT(b,1);
32938a641c5SToomas Soome /* FALLTHROUGH */
330f9fbec18Smcpowers case 1:
331f9fbec18Smcpowers r0 = MP_DIGIT(b,0);
332f9fbec18Smcpowers }
333f9fbec18Smcpowers
334f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
335f9fbec18Smcpowers MP_ADD_CARRY(a0, r0, r0, 0, carry);
336f9fbec18Smcpowers MP_ADD_CARRY(a1, r1, r1, carry, carry);
337f9fbec18Smcpowers MP_ADD_CARRY(a2, r2, r2, carry, carry);
338f9fbec18Smcpowers #else
339f9fbec18Smcpowers __asm__ (
340f9fbec18Smcpowers "xorq %3,%3 \n\t"
341f9fbec18Smcpowers "addq %4,%0 \n\t"
342f9fbec18Smcpowers "adcq %5,%1 \n\t"
343f9fbec18Smcpowers "adcq %6,%2 \n\t"
344f9fbec18Smcpowers "adcq $0,%3 \n\t"
345f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
346*55fea89dSDan Cross : "r" (a0), "r" (a1), "r" (a2), "0" (r0),
347f9fbec18Smcpowers "1" (r1), "2" (r2)
348f9fbec18Smcpowers : "%cc" );
349f9fbec18Smcpowers #endif
350f9fbec18Smcpowers
351*55fea89dSDan Cross /* Do quick 'subract' if we've gone over
352f9fbec18Smcpowers * (add the 2's complement of the curve field) */
353f9fbec18Smcpowers if (carry || ((r2 == MP_DIGIT_MAX) &&
354*55fea89dSDan Cross ((r1 == MP_DIGIT_MAX) ||
355f9fbec18Smcpowers ((r1 == (MP_DIGIT_MAX-1)) && (r0 == MP_DIGIT_MAX))))) {
356f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
357f9fbec18Smcpowers MP_ADD_CARRY(r0, 1, r0, 0, carry);
358f9fbec18Smcpowers MP_ADD_CARRY(r1, 1, r1, carry, carry);
359f9fbec18Smcpowers MP_ADD_CARRY(r2, 0, r2, carry, carry);
360f9fbec18Smcpowers #else
361f9fbec18Smcpowers __asm__ (
362f9fbec18Smcpowers "addq $1,%0 \n\t"
363f9fbec18Smcpowers "adcq $1,%1 \n\t"
364f9fbec18Smcpowers "adcq $0,%2 \n\t"
365f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2)
366f9fbec18Smcpowers : "0" (r0), "1" (r1), "2" (r2)
367f9fbec18Smcpowers : "%cc" );
368f9fbec18Smcpowers #endif
369f9fbec18Smcpowers }
370f9fbec18Smcpowers
371*55fea89dSDan Cross
372f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 3));
373f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
374f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
375f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
376f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
377f9fbec18Smcpowers MP_USED(r) = 3;
378f9fbec18Smcpowers s_mp_clamp(r);
379f9fbec18Smcpowers
380f9fbec18Smcpowers
381f9fbec18Smcpowers CLEANUP:
382f9fbec18Smcpowers return res;
383f9fbec18Smcpowers }
384f9fbec18Smcpowers
385f9fbec18Smcpowers /* Compute the diff of 192 bit curves. Do the work in-line since the
386f9fbec18Smcpowers * number of words are so small, we don't want to overhead of mp function
387*55fea89dSDan Cross * calls. Uses optimized modular reduction for p192.
388f9fbec18Smcpowers */
389f9fbec18Smcpowers mp_err
ec_GFp_nistp192_sub(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)390*55fea89dSDan Cross ec_GFp_nistp192_sub(const mp_int *a, const mp_int *b, mp_int *r,
391f9fbec18Smcpowers const GFMethod *meth)
392f9fbec18Smcpowers {
393f9fbec18Smcpowers mp_err res = MP_OKAY;
394f9fbec18Smcpowers mp_digit b0 = 0, b1 = 0, b2 = 0;
395f9fbec18Smcpowers mp_digit r0 = 0, r1 = 0, r2 = 0;
396f9fbec18Smcpowers mp_digit borrow;
397f9fbec18Smcpowers
398f9fbec18Smcpowers switch(MP_USED(a)) {
399f9fbec18Smcpowers case 3:
400f9fbec18Smcpowers r2 = MP_DIGIT(a,2);
40138a641c5SToomas Soome /* FALLTHROUGH */
402f9fbec18Smcpowers case 2:
403f9fbec18Smcpowers r1 = MP_DIGIT(a,1);
40438a641c5SToomas Soome /* FALLTHROUGH */
405f9fbec18Smcpowers case 1:
406f9fbec18Smcpowers r0 = MP_DIGIT(a,0);
407f9fbec18Smcpowers }
408f9fbec18Smcpowers
409f9fbec18Smcpowers switch(MP_USED(b)) {
410f9fbec18Smcpowers case 3:
411f9fbec18Smcpowers b2 = MP_DIGIT(b,2);
41238a641c5SToomas Soome /* FALLTHROUGH */
413f9fbec18Smcpowers case 2:
414f9fbec18Smcpowers b1 = MP_DIGIT(b,1);
41538a641c5SToomas Soome /* FALLTHROUGH */
416f9fbec18Smcpowers case 1:
417f9fbec18Smcpowers b0 = MP_DIGIT(b,0);
418f9fbec18Smcpowers }
419f9fbec18Smcpowers
420f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
421f9fbec18Smcpowers MP_SUB_BORROW(r0, b0, r0, 0, borrow);
422f9fbec18Smcpowers MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
423f9fbec18Smcpowers MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
424f9fbec18Smcpowers #else
425f9fbec18Smcpowers __asm__ (
426f9fbec18Smcpowers "xorq %3,%3 \n\t"
427f9fbec18Smcpowers "subq %4,%0 \n\t"
428f9fbec18Smcpowers "sbbq %5,%1 \n\t"
429f9fbec18Smcpowers "sbbq %6,%2 \n\t"
430f9fbec18Smcpowers "adcq $0,%3 \n\t"
431f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(borrow)
432*55fea89dSDan Cross : "r" (b0), "r" (b1), "r" (b2), "0" (r0),
433f9fbec18Smcpowers "1" (r1), "2" (r2)
434f9fbec18Smcpowers : "%cc" );
435f9fbec18Smcpowers #endif
436f9fbec18Smcpowers
437f9fbec18Smcpowers /* Do quick 'add' if we've gone under 0
438f9fbec18Smcpowers * (subtract the 2's complement of the curve field) */
439f9fbec18Smcpowers if (borrow) {
440f9fbec18Smcpowers #ifndef MPI_AMD64_ADD
441f9fbec18Smcpowers MP_SUB_BORROW(r0, 1, r0, 0, borrow);
442f9fbec18Smcpowers MP_SUB_BORROW(r1, 1, r1, borrow, borrow);
443f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, borrow, borrow);
444f9fbec18Smcpowers #else
445f9fbec18Smcpowers __asm__ (
446f9fbec18Smcpowers "subq $1,%0 \n\t"
447f9fbec18Smcpowers "sbbq $1,%1 \n\t"
448f9fbec18Smcpowers "sbbq $0,%2 \n\t"
449f9fbec18Smcpowers : "=r"(r0), "=r"(r1), "=r"(r2)
450f9fbec18Smcpowers : "0" (r0), "1" (r1), "2" (r2)
451f9fbec18Smcpowers : "%cc" );
452f9fbec18Smcpowers #endif
453f9fbec18Smcpowers }
454f9fbec18Smcpowers
455f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 3));
456f9fbec18Smcpowers MP_DIGIT(r, 2) = r2;
457f9fbec18Smcpowers MP_DIGIT(r, 1) = r1;
458f9fbec18Smcpowers MP_DIGIT(r, 0) = r0;
459f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
460f9fbec18Smcpowers MP_USED(r) = 3;
461f9fbec18Smcpowers s_mp_clamp(r);
462f9fbec18Smcpowers
463f9fbec18Smcpowers CLEANUP:
464f9fbec18Smcpowers return res;
465f9fbec18Smcpowers }
466f9fbec18Smcpowers
467f9fbec18Smcpowers #endif
468f9fbec18Smcpowers
469f9fbec18Smcpowers /* Compute the square of polynomial a, reduce modulo p192. Store the
470*55fea89dSDan Cross * result in r. r could be a. Uses optimized modular reduction for p192.
471f9fbec18Smcpowers */
472f9fbec18Smcpowers mp_err
ec_GFp_nistp192_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)473f9fbec18Smcpowers ec_GFp_nistp192_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
474f9fbec18Smcpowers {
475f9fbec18Smcpowers mp_err res = MP_OKAY;
476f9fbec18Smcpowers
477f9fbec18Smcpowers MP_CHECKOK(mp_sqr(a, r));
478f9fbec18Smcpowers MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
479f9fbec18Smcpowers CLEANUP:
480f9fbec18Smcpowers return res;
481f9fbec18Smcpowers }
482f9fbec18Smcpowers
483f9fbec18Smcpowers /* Compute the product of two polynomials a and b, reduce modulo p192.
484f9fbec18Smcpowers * Store the result in r. r could be a or b; a could be b. Uses
485f9fbec18Smcpowers * optimized modular reduction for p192. */
486f9fbec18Smcpowers mp_err
ec_GFp_nistp192_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)487f9fbec18Smcpowers ec_GFp_nistp192_mul(const mp_int *a, const mp_int *b, mp_int *r,
488f9fbec18Smcpowers const GFMethod *meth)
489f9fbec18Smcpowers {
490f9fbec18Smcpowers mp_err res = MP_OKAY;
491f9fbec18Smcpowers
492f9fbec18Smcpowers MP_CHECKOK(mp_mul(a, b, r));
493f9fbec18Smcpowers MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
494f9fbec18Smcpowers CLEANUP:
495f9fbec18Smcpowers return res;
496f9fbec18Smcpowers }
497f9fbec18Smcpowers
498f9fbec18Smcpowers /* Divides two field elements. If a is NULL, then returns the inverse of
499f9fbec18Smcpowers * b. */
500f9fbec18Smcpowers mp_err
ec_GFp_nistp192_div(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)501f9fbec18Smcpowers ec_GFp_nistp192_div(const mp_int *a, const mp_int *b, mp_int *r,
502f9fbec18Smcpowers const GFMethod *meth)
503f9fbec18Smcpowers {
504f9fbec18Smcpowers mp_err res = MP_OKAY;
505f9fbec18Smcpowers mp_int t;
506f9fbec18Smcpowers
507f9fbec18Smcpowers /* If a is NULL, then return the inverse of b, otherwise return a/b. */
508f9fbec18Smcpowers if (a == NULL) {
509f9fbec18Smcpowers return mp_invmod(b, &meth->irr, r);
510f9fbec18Smcpowers } else {
511*55fea89dSDan Cross /* MPI doesn't support divmod, so we implement it using invmod and
512f9fbec18Smcpowers * mulmod. */
513f9fbec18Smcpowers MP_CHECKOK(mp_init(&t, FLAG(b)));
514f9fbec18Smcpowers MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
515f9fbec18Smcpowers MP_CHECKOK(mp_mul(a, &t, r));
516f9fbec18Smcpowers MP_CHECKOK(ec_GFp_nistp192_mod(r, r, meth));
517f9fbec18Smcpowers CLEANUP:
518f9fbec18Smcpowers mp_clear(&t);
519f9fbec18Smcpowers return res;
520f9fbec18Smcpowers }
521f9fbec18Smcpowers }
522f9fbec18Smcpowers
523f9fbec18Smcpowers /* Wire in fast field arithmetic and precomputation of base point for
524f9fbec18Smcpowers * named curves. */
525f9fbec18Smcpowers mp_err
ec_group_set_gfp192(ECGroup * group,ECCurveName name)526f9fbec18Smcpowers ec_group_set_gfp192(ECGroup *group, ECCurveName name)
527f9fbec18Smcpowers {
528f9fbec18Smcpowers if (name == ECCurve_NIST_P192) {
529f9fbec18Smcpowers group->meth->field_mod = &ec_GFp_nistp192_mod;
530f9fbec18Smcpowers group->meth->field_mul = &ec_GFp_nistp192_mul;
531f9fbec18Smcpowers group->meth->field_sqr = &ec_GFp_nistp192_sqr;
532f9fbec18Smcpowers group->meth->field_div = &ec_GFp_nistp192_div;
533f9fbec18Smcpowers #ifndef ECL_THIRTY_TWO_BIT
534f9fbec18Smcpowers group->meth->field_add = &ec_GFp_nistp192_add;
535f9fbec18Smcpowers group->meth->field_sub = &ec_GFp_nistp192_sub;
536f9fbec18Smcpowers #endif
537f9fbec18Smcpowers }
538f9fbec18Smcpowers return MP_OKAY;
539f9fbec18Smcpowers }
540