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>
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
53*55fea89dSDan Cross /* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be r.
54*55fea89dSDan Cross * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to
55f9fbec18Smcpowers * Elliptic Curve Cryptography. */
56f9fbec18Smcpowers mp_err
ec_GFp_nistp256_mod(const mp_int * a,mp_int * r,const GFMethod * meth)57f9fbec18Smcpowers ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
58f9fbec18Smcpowers {
59f9fbec18Smcpowers mp_err res = MP_OKAY;
60f9fbec18Smcpowers mp_size a_used = MP_USED(a);
61f9fbec18Smcpowers int a_bits = mpl_significant_bits(a);
62f9fbec18Smcpowers mp_digit carry;
63f9fbec18Smcpowers
64f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
65f9fbec18Smcpowers mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0;
66f9fbec18Smcpowers mp_digit r0, r1, r2, r3, r4, r5, r6, r7;
67f9fbec18Smcpowers int r8; /* must be a signed value ! */
68f9fbec18Smcpowers #else
69f9fbec18Smcpowers mp_digit a4=0, a5=0, a6=0, a7=0;
70f9fbec18Smcpowers mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l;
71f9fbec18Smcpowers mp_digit r0, r1, r2, r3;
72f9fbec18Smcpowers int r4; /* must be a signed value ! */
73f9fbec18Smcpowers #endif
74*55fea89dSDan Cross /* for polynomials larger than twice the field size
75f9fbec18Smcpowers * use regular reduction */
76f9fbec18Smcpowers if (a_bits < 256) {
77f9fbec18Smcpowers if (a == r) return MP_OKAY;
78f9fbec18Smcpowers return mp_copy(a,r);
79f9fbec18Smcpowers }
80f9fbec18Smcpowers if (a_bits > 512) {
81f9fbec18Smcpowers MP_CHECKOK(mp_mod(a, &meth->irr, r));
82f9fbec18Smcpowers } else {
83f9fbec18Smcpowers
84f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
85f9fbec18Smcpowers switch (a_used) {
86f9fbec18Smcpowers case 16:
87f9fbec18Smcpowers a15 = MP_DIGIT(a,15);
8838a641c5SToomas Soome /* FALLTHROUGH */
89f9fbec18Smcpowers case 15:
90f9fbec18Smcpowers a14 = MP_DIGIT(a,14);
9138a641c5SToomas Soome /* FALLTHROUGH */
92f9fbec18Smcpowers case 14:
93f9fbec18Smcpowers a13 = MP_DIGIT(a,13);
9438a641c5SToomas Soome /* FALLTHROUGH */
95f9fbec18Smcpowers case 13:
96f9fbec18Smcpowers a12 = MP_DIGIT(a,12);
9738a641c5SToomas Soome /* FALLTHROUGH */
98f9fbec18Smcpowers case 12:
99f9fbec18Smcpowers a11 = MP_DIGIT(a,11);
10038a641c5SToomas Soome /* FALLTHROUGH */
101f9fbec18Smcpowers case 11:
102f9fbec18Smcpowers a10 = MP_DIGIT(a,10);
10338a641c5SToomas Soome /* FALLTHROUGH */
104f9fbec18Smcpowers case 10:
105f9fbec18Smcpowers a9 = MP_DIGIT(a,9);
10638a641c5SToomas Soome /* FALLTHROUGH */
107f9fbec18Smcpowers case 9:
108f9fbec18Smcpowers a8 = MP_DIGIT(a,8);
109f9fbec18Smcpowers }
110f9fbec18Smcpowers
111f9fbec18Smcpowers r0 = MP_DIGIT(a,0);
112f9fbec18Smcpowers r1 = MP_DIGIT(a,1);
113f9fbec18Smcpowers r2 = MP_DIGIT(a,2);
114f9fbec18Smcpowers r3 = MP_DIGIT(a,3);
115f9fbec18Smcpowers r4 = MP_DIGIT(a,4);
116f9fbec18Smcpowers r5 = MP_DIGIT(a,5);
117f9fbec18Smcpowers r6 = MP_DIGIT(a,6);
118f9fbec18Smcpowers r7 = MP_DIGIT(a,7);
119f9fbec18Smcpowers
120f9fbec18Smcpowers /* sum 1 */
121f9fbec18Smcpowers MP_ADD_CARRY(r3, a11, r3, 0, carry);
122f9fbec18Smcpowers MP_ADD_CARRY(r4, a12, r4, carry, carry);
123f9fbec18Smcpowers MP_ADD_CARRY(r5, a13, r5, carry, carry);
124f9fbec18Smcpowers MP_ADD_CARRY(r6, a14, r6, carry, carry);
125f9fbec18Smcpowers MP_ADD_CARRY(r7, a15, r7, carry, carry);
126f9fbec18Smcpowers r8 = carry;
127f9fbec18Smcpowers MP_ADD_CARRY(r3, a11, r3, 0, carry);
128f9fbec18Smcpowers MP_ADD_CARRY(r4, a12, r4, carry, carry);
129f9fbec18Smcpowers MP_ADD_CARRY(r5, a13, r5, carry, carry);
130f9fbec18Smcpowers MP_ADD_CARRY(r6, a14, r6, carry, carry);
131f9fbec18Smcpowers MP_ADD_CARRY(r7, a15, r7, carry, carry);
132f9fbec18Smcpowers r8 += carry;
133f9fbec18Smcpowers /* sum 2 */
134f9fbec18Smcpowers MP_ADD_CARRY(r3, a12, r3, 0, carry);
135f9fbec18Smcpowers MP_ADD_CARRY(r4, a13, r4, carry, carry);
136f9fbec18Smcpowers MP_ADD_CARRY(r5, a14, r5, carry, carry);
137f9fbec18Smcpowers MP_ADD_CARRY(r6, a15, r6, carry, carry);
138f9fbec18Smcpowers MP_ADD_CARRY(r7, 0, r7, carry, carry);
139f9fbec18Smcpowers r8 += carry;
140f9fbec18Smcpowers /* combine last bottom of sum 3 with second sum 2 */
141f9fbec18Smcpowers MP_ADD_CARRY(r0, a8, r0, 0, carry);
142f9fbec18Smcpowers MP_ADD_CARRY(r1, a9, r1, carry, carry);
143f9fbec18Smcpowers MP_ADD_CARRY(r2, a10, r2, carry, carry);
144f9fbec18Smcpowers MP_ADD_CARRY(r3, a12, r3, carry, carry);
145f9fbec18Smcpowers MP_ADD_CARRY(r4, a13, r4, carry, carry);
146f9fbec18Smcpowers MP_ADD_CARRY(r5, a14, r5, carry, carry);
147f9fbec18Smcpowers MP_ADD_CARRY(r6, a15, r6, carry, carry);
148f9fbec18Smcpowers MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */
149f9fbec18Smcpowers r8 += carry;
150f9fbec18Smcpowers /* sum 3 (rest of it)*/
151f9fbec18Smcpowers MP_ADD_CARRY(r6, a14, r6, 0, carry);
152f9fbec18Smcpowers MP_ADD_CARRY(r7, 0, r7, carry, carry);
153f9fbec18Smcpowers r8 += carry;
154f9fbec18Smcpowers /* sum 4 (rest of it)*/
155f9fbec18Smcpowers MP_ADD_CARRY(r0, a9, r0, 0, carry);
156f9fbec18Smcpowers MP_ADD_CARRY(r1, a10, r1, carry, carry);
157f9fbec18Smcpowers MP_ADD_CARRY(r2, a11, r2, carry, carry);
158f9fbec18Smcpowers MP_ADD_CARRY(r3, a13, r3, carry, carry);
159f9fbec18Smcpowers MP_ADD_CARRY(r4, a14, r4, carry, carry);
160f9fbec18Smcpowers MP_ADD_CARRY(r5, a15, r5, carry, carry);
161f9fbec18Smcpowers MP_ADD_CARRY(r6, a13, r6, carry, carry);
162f9fbec18Smcpowers MP_ADD_CARRY(r7, a8, r7, carry, carry);
163f9fbec18Smcpowers r8 += carry;
164f9fbec18Smcpowers /* diff 5 */
165f9fbec18Smcpowers MP_SUB_BORROW(r0, a11, r0, 0, carry);
166f9fbec18Smcpowers MP_SUB_BORROW(r1, a12, r1, carry, carry);
167f9fbec18Smcpowers MP_SUB_BORROW(r2, a13, r2, carry, carry);
168f9fbec18Smcpowers MP_SUB_BORROW(r3, 0, r3, carry, carry);
169f9fbec18Smcpowers MP_SUB_BORROW(r4, 0, r4, carry, carry);
170f9fbec18Smcpowers MP_SUB_BORROW(r5, 0, r5, carry, carry);
171f9fbec18Smcpowers MP_SUB_BORROW(r6, a8, r6, carry, carry);
172f9fbec18Smcpowers MP_SUB_BORROW(r7, a10, r7, carry, carry);
173f9fbec18Smcpowers r8 -= carry;
174f9fbec18Smcpowers /* diff 6 */
175f9fbec18Smcpowers MP_SUB_BORROW(r0, a12, r0, 0, carry);
176f9fbec18Smcpowers MP_SUB_BORROW(r1, a13, r1, carry, carry);
177f9fbec18Smcpowers MP_SUB_BORROW(r2, a14, r2, carry, carry);
178f9fbec18Smcpowers MP_SUB_BORROW(r3, a15, r3, carry, carry);
179f9fbec18Smcpowers MP_SUB_BORROW(r4, 0, r4, carry, carry);
180f9fbec18Smcpowers MP_SUB_BORROW(r5, 0, r5, carry, carry);
181f9fbec18Smcpowers MP_SUB_BORROW(r6, a9, r6, carry, carry);
182f9fbec18Smcpowers MP_SUB_BORROW(r7, a11, r7, carry, carry);
183f9fbec18Smcpowers r8 -= carry;
184f9fbec18Smcpowers /* diff 7 */
185f9fbec18Smcpowers MP_SUB_BORROW(r0, a13, r0, 0, carry);
186f9fbec18Smcpowers MP_SUB_BORROW(r1, a14, r1, carry, carry);
187f9fbec18Smcpowers MP_SUB_BORROW(r2, a15, r2, carry, carry);
188f9fbec18Smcpowers MP_SUB_BORROW(r3, a8, r3, carry, carry);
189f9fbec18Smcpowers MP_SUB_BORROW(r4, a9, r4, carry, carry);
190f9fbec18Smcpowers MP_SUB_BORROW(r5, a10, r5, carry, carry);
191f9fbec18Smcpowers MP_SUB_BORROW(r6, 0, r6, carry, carry);
192f9fbec18Smcpowers MP_SUB_BORROW(r7, a12, r7, carry, carry);
193f9fbec18Smcpowers r8 -= carry;
194f9fbec18Smcpowers /* diff 8 */
195f9fbec18Smcpowers MP_SUB_BORROW(r0, a14, r0, 0, carry);
196f9fbec18Smcpowers MP_SUB_BORROW(r1, a15, r1, carry, carry);
197f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry);
198f9fbec18Smcpowers MP_SUB_BORROW(r3, a9, r3, carry, carry);
199f9fbec18Smcpowers MP_SUB_BORROW(r4, a10, r4, carry, carry);
200f9fbec18Smcpowers MP_SUB_BORROW(r5, a11, r5, carry, carry);
201f9fbec18Smcpowers MP_SUB_BORROW(r6, 0, r6, carry, carry);
202f9fbec18Smcpowers MP_SUB_BORROW(r7, a13, r7, carry, carry);
203f9fbec18Smcpowers r8 -= carry;
204f9fbec18Smcpowers
205f9fbec18Smcpowers /* reduce the overflows */
206f9fbec18Smcpowers while (r8 > 0) {
207f9fbec18Smcpowers mp_digit r8_d = r8;
208f9fbec18Smcpowers MP_ADD_CARRY(r0, r8_d, r0, 0, carry);
209f9fbec18Smcpowers MP_ADD_CARRY(r1, 0, r1, carry, carry);
210f9fbec18Smcpowers MP_ADD_CARRY(r2, 0, r2, carry, carry);
211f9fbec18Smcpowers MP_ADD_CARRY(r3, -r8_d, r3, carry, carry);
212f9fbec18Smcpowers MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry);
213f9fbec18Smcpowers MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry);
214f9fbec18Smcpowers MP_ADD_CARRY(r6, -(r8_d+1), r6, carry, carry);
215f9fbec18Smcpowers MP_ADD_CARRY(r7, (r8_d-1), r7, carry, carry);
216f9fbec18Smcpowers r8 = carry;
217f9fbec18Smcpowers }
218f9fbec18Smcpowers
219f9fbec18Smcpowers /* reduce the underflows */
220f9fbec18Smcpowers while (r8 < 0) {
221f9fbec18Smcpowers mp_digit r8_d = -r8;
222f9fbec18Smcpowers MP_SUB_BORROW(r0, r8_d, r0, 0, carry);
223f9fbec18Smcpowers MP_SUB_BORROW(r1, 0, r1, carry, carry);
224f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry);
225f9fbec18Smcpowers MP_SUB_BORROW(r3, -r8_d, r3, carry, carry);
226f9fbec18Smcpowers MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry);
227f9fbec18Smcpowers MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry);
228f9fbec18Smcpowers MP_SUB_BORROW(r6, -(r8_d+1), r6, carry, carry);
229f9fbec18Smcpowers MP_SUB_BORROW(r7, (r8_d-1), r7, carry, carry);
230f9fbec18Smcpowers r8 = -carry;
231f9fbec18Smcpowers }
232f9fbec18Smcpowers if (a != r) {
233f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r,8));
234f9fbec18Smcpowers }
235f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
236f9fbec18Smcpowers MP_USED(r) = 8;
237f9fbec18Smcpowers
238f9fbec18Smcpowers MP_DIGIT(r,7) = r7;
239f9fbec18Smcpowers MP_DIGIT(r,6) = r6;
240f9fbec18Smcpowers MP_DIGIT(r,5) = r5;
241f9fbec18Smcpowers MP_DIGIT(r,4) = r4;
242f9fbec18Smcpowers MP_DIGIT(r,3) = r3;
243f9fbec18Smcpowers MP_DIGIT(r,2) = r2;
244f9fbec18Smcpowers MP_DIGIT(r,1) = r1;
245f9fbec18Smcpowers MP_DIGIT(r,0) = r0;
246f9fbec18Smcpowers
247f9fbec18Smcpowers /* final reduction if necessary */
248f9fbec18Smcpowers if ((r7 == MP_DIGIT_MAX) &&
249f9fbec18Smcpowers ((r6 > 1) || ((r6 == 1) &&
250*55fea89dSDan Cross (r5 || r4 || r3 ||
251f9fbec18Smcpowers ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX)
252f9fbec18Smcpowers && (r0 == MP_DIGIT_MAX)))))) {
253f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r));
254f9fbec18Smcpowers }
255f9fbec18Smcpowers #ifdef notdef
256*55fea89dSDan Cross
257f9fbec18Smcpowers
258f9fbec18Smcpowers /* smooth the negatives */
259f9fbec18Smcpowers while (MP_SIGN(r) != MP_ZPOS) {
260f9fbec18Smcpowers MP_CHECKOK(mp_add(r, &meth->irr, r));
261f9fbec18Smcpowers }
262f9fbec18Smcpowers while (MP_USED(r) > 8) {
263f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r));
264f9fbec18Smcpowers }
265f9fbec18Smcpowers
266f9fbec18Smcpowers /* final reduction if necessary */
267f9fbec18Smcpowers if (MP_DIGIT(r,7) >= MP_DIGIT(&meth->irr,7)) {
268f9fbec18Smcpowers if (mp_cmp(r,&meth->irr) != MP_LT) {
269f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r));
270f9fbec18Smcpowers }
271f9fbec18Smcpowers }
272f9fbec18Smcpowers #endif
273f9fbec18Smcpowers s_mp_clamp(r);
274f9fbec18Smcpowers #else
275f9fbec18Smcpowers switch (a_used) {
276f9fbec18Smcpowers case 8:
277f9fbec18Smcpowers a7 = MP_DIGIT(a,7);
27838a641c5SToomas Soome /* FALLTHROUGH */
279f9fbec18Smcpowers case 7:
280f9fbec18Smcpowers a6 = MP_DIGIT(a,6);
28138a641c5SToomas Soome /* FALLTHROUGH */
282f9fbec18Smcpowers case 6:
283f9fbec18Smcpowers a5 = MP_DIGIT(a,5);
28438a641c5SToomas Soome /* FALLTHROUGH */
285f9fbec18Smcpowers case 5:
286f9fbec18Smcpowers a4 = MP_DIGIT(a,4);
287f9fbec18Smcpowers }
288f9fbec18Smcpowers a7l = a7 << 32;
289f9fbec18Smcpowers a7h = a7 >> 32;
290f9fbec18Smcpowers a6l = a6 << 32;
291f9fbec18Smcpowers a6h = a6 >> 32;
292f9fbec18Smcpowers a5l = a5 << 32;
293f9fbec18Smcpowers a5h = a5 >> 32;
294f9fbec18Smcpowers a4l = a4 << 32;
295f9fbec18Smcpowers a4h = a4 >> 32;
296f9fbec18Smcpowers r3 = MP_DIGIT(a,3);
297f9fbec18Smcpowers r2 = MP_DIGIT(a,2);
298f9fbec18Smcpowers r1 = MP_DIGIT(a,1);
299f9fbec18Smcpowers r0 = MP_DIGIT(a,0);
300f9fbec18Smcpowers
301f9fbec18Smcpowers /* sum 1 */
302f9fbec18Smcpowers MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry);
303f9fbec18Smcpowers MP_ADD_CARRY(r2, a6, r2, carry, carry);
304f9fbec18Smcpowers MP_ADD_CARRY(r3, a7, r3, carry, carry);
305f9fbec18Smcpowers r4 = carry;
306f9fbec18Smcpowers MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry);
307f9fbec18Smcpowers MP_ADD_CARRY(r2, a6, r2, carry, carry);
308f9fbec18Smcpowers MP_ADD_CARRY(r3, a7, r3, carry, carry);
309f9fbec18Smcpowers r4 += carry;
310f9fbec18Smcpowers /* sum 2 */
311f9fbec18Smcpowers MP_ADD_CARRY(r1, a6l, r1, 0, carry);
312f9fbec18Smcpowers MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
313f9fbec18Smcpowers MP_ADD_CARRY(r3, a7h, r3, carry, carry);
314f9fbec18Smcpowers r4 += carry;
315f9fbec18Smcpowers MP_ADD_CARRY(r1, a6l, r1, 0, carry);
316f9fbec18Smcpowers MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
317f9fbec18Smcpowers MP_ADD_CARRY(r3, a7h, r3, carry, carry);
318f9fbec18Smcpowers r4 += carry;
319f9fbec18Smcpowers
320f9fbec18Smcpowers /* sum 3 */
321f9fbec18Smcpowers MP_ADD_CARRY(r0, a4, r0, 0, carry);
322f9fbec18Smcpowers MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry);
323f9fbec18Smcpowers MP_ADD_CARRY(r2, 0, r2, carry, carry);
324f9fbec18Smcpowers MP_ADD_CARRY(r3, a7, r3, carry, carry);
325f9fbec18Smcpowers r4 += carry;
326f9fbec18Smcpowers /* sum 4 */
327f9fbec18Smcpowers MP_ADD_CARRY(r0, a4h | a5l, r0, 0, carry);
328f9fbec18Smcpowers MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry);
329f9fbec18Smcpowers MP_ADD_CARRY(r2, a7, r2, carry, carry);
330f9fbec18Smcpowers MP_ADD_CARRY(r3, a6h | a4l, r3, carry, carry);
331f9fbec18Smcpowers r4 += carry;
332f9fbec18Smcpowers /* diff 5 */
333f9fbec18Smcpowers MP_SUB_BORROW(r0, a5h | a6l, r0, 0, carry);
334f9fbec18Smcpowers MP_SUB_BORROW(r1, a6h, r1, carry, carry);
335f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry);
336f9fbec18Smcpowers MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry);
337f9fbec18Smcpowers r4 -= carry;
338f9fbec18Smcpowers /* diff 6 */
339f9fbec18Smcpowers MP_SUB_BORROW(r0, a6, r0, 0, carry);
340f9fbec18Smcpowers MP_SUB_BORROW(r1, a7, r1, carry, carry);
341f9fbec18Smcpowers MP_SUB_BORROW(r2, 0, r2, carry, carry);
342f9fbec18Smcpowers MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry);
343f9fbec18Smcpowers r4 -= carry;
344f9fbec18Smcpowers /* diff 7 */
345f9fbec18Smcpowers MP_SUB_BORROW(r0, a6h|a7l, r0, 0, carry);
346f9fbec18Smcpowers MP_SUB_BORROW(r1, a7h|a4l, r1, carry, carry);
347f9fbec18Smcpowers MP_SUB_BORROW(r2, a4h|a5l, r2, carry, carry);
348f9fbec18Smcpowers MP_SUB_BORROW(r3, a6l, r3, carry, carry);
349f9fbec18Smcpowers r4 -= carry;
350f9fbec18Smcpowers /* diff 8 */
351f9fbec18Smcpowers MP_SUB_BORROW(r0, a7, r0, 0, carry);
352f9fbec18Smcpowers MP_SUB_BORROW(r1, a4h<<32, r1, carry, carry);
353f9fbec18Smcpowers MP_SUB_BORROW(r2, a5, r2, carry, carry);
354f9fbec18Smcpowers MP_SUB_BORROW(r3, a6h<<32, r3, carry, carry);
355f9fbec18Smcpowers r4 -= carry;
356f9fbec18Smcpowers
357f9fbec18Smcpowers /* reduce the overflows */
358f9fbec18Smcpowers while (r4 > 0) {
359f9fbec18Smcpowers mp_digit r4_long = r4;
360f9fbec18Smcpowers mp_digit r4l = (r4_long << 32);
361f9fbec18Smcpowers MP_ADD_CARRY(r0, r4_long, r0, 0, carry);
362f9fbec18Smcpowers MP_ADD_CARRY(r1, -r4l, r1, carry, carry);
363f9fbec18Smcpowers MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry);
364f9fbec18Smcpowers MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry);
365f9fbec18Smcpowers r4 = carry;
366f9fbec18Smcpowers }
367f9fbec18Smcpowers
368f9fbec18Smcpowers /* reduce the underflows */
369f9fbec18Smcpowers while (r4 < 0) {
370f9fbec18Smcpowers mp_digit r4_long = -r4;
371f9fbec18Smcpowers mp_digit r4l = (r4_long << 32);
372f9fbec18Smcpowers MP_SUB_BORROW(r0, r4_long, r0, 0, carry);
373f9fbec18Smcpowers MP_SUB_BORROW(r1, -r4l, r1, carry, carry);
374f9fbec18Smcpowers MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry);
375f9fbec18Smcpowers MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry);
376f9fbec18Smcpowers r4 = -carry;
377f9fbec18Smcpowers }
378f9fbec18Smcpowers
379f9fbec18Smcpowers if (a != r) {
380f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r,4));
381f9fbec18Smcpowers }
382f9fbec18Smcpowers MP_SIGN(r) = MP_ZPOS;
383f9fbec18Smcpowers MP_USED(r) = 4;
384f9fbec18Smcpowers
385f9fbec18Smcpowers MP_DIGIT(r,3) = r3;
386f9fbec18Smcpowers MP_DIGIT(r,2) = r2;
387f9fbec18Smcpowers MP_DIGIT(r,1) = r1;
388f9fbec18Smcpowers MP_DIGIT(r,0) = r0;
389f9fbec18Smcpowers
390f9fbec18Smcpowers /* final reduction if necessary */
391f9fbec18Smcpowers if ((r3 > 0xFFFFFFFF00000001ULL) ||
392*55fea89dSDan Cross ((r3 == 0xFFFFFFFF00000001ULL) &&
393*55fea89dSDan Cross (r2 || (r1 >> 32)||
394f9fbec18Smcpowers (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) {
395f9fbec18Smcpowers /* very rare, just use mp_sub */
396f9fbec18Smcpowers MP_CHECKOK(mp_sub(r, &meth->irr, r));
397f9fbec18Smcpowers }
398*55fea89dSDan Cross
399f9fbec18Smcpowers s_mp_clamp(r);
400f9fbec18Smcpowers #endif
401f9fbec18Smcpowers }
402f9fbec18Smcpowers
403f9fbec18Smcpowers CLEANUP:
404f9fbec18Smcpowers return res;
405f9fbec18Smcpowers }
406f9fbec18Smcpowers
407f9fbec18Smcpowers /* Compute the square of polynomial a, reduce modulo p256. Store the
408*55fea89dSDan Cross * result in r. r could be a. Uses optimized modular reduction for p256.
409f9fbec18Smcpowers */
410f9fbec18Smcpowers mp_err
ec_GFp_nistp256_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)411f9fbec18Smcpowers ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
412f9fbec18Smcpowers {
413f9fbec18Smcpowers mp_err res = MP_OKAY;
414f9fbec18Smcpowers
415f9fbec18Smcpowers MP_CHECKOK(mp_sqr(a, r));
416f9fbec18Smcpowers MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
417f9fbec18Smcpowers CLEANUP:
418f9fbec18Smcpowers return res;
419f9fbec18Smcpowers }
420f9fbec18Smcpowers
421f9fbec18Smcpowers /* Compute the product of two polynomials a and b, reduce modulo p256.
422f9fbec18Smcpowers * Store the result in r. r could be a or b; a could be b. Uses
423f9fbec18Smcpowers * optimized modular reduction for p256. */
424f9fbec18Smcpowers mp_err
ec_GFp_nistp256_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)425f9fbec18Smcpowers ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r,
426f9fbec18Smcpowers const GFMethod *meth)
427f9fbec18Smcpowers {
428f9fbec18Smcpowers mp_err res = MP_OKAY;
429f9fbec18Smcpowers
430f9fbec18Smcpowers MP_CHECKOK(mp_mul(a, b, r));
431f9fbec18Smcpowers MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
432f9fbec18Smcpowers CLEANUP:
433f9fbec18Smcpowers return res;
434f9fbec18Smcpowers }
435f9fbec18Smcpowers
436f9fbec18Smcpowers /* Wire in fast field arithmetic and precomputation of base point for
437f9fbec18Smcpowers * named curves. */
438f9fbec18Smcpowers mp_err
ec_group_set_gfp256(ECGroup * group,ECCurveName name)439f9fbec18Smcpowers ec_group_set_gfp256(ECGroup *group, ECCurveName name)
440f9fbec18Smcpowers {
441f9fbec18Smcpowers if (name == ECCurve_NIST_P256) {
442f9fbec18Smcpowers group->meth->field_mod = &ec_GFp_nistp256_mod;
443f9fbec18Smcpowers group->meth->field_mul = &ec_GFp_nistp256_mul;
444f9fbec18Smcpowers group->meth->field_sqr = &ec_GFp_nistp256_sqr;
445f9fbec18Smcpowers }
446f9fbec18Smcpowers return MP_OKAY;
447f9fbec18Smcpowers }
448