xref: /titanic_51/usr/src/common/crypto/ecc/ecp_384.c (revision f9fbec18f5b458b560ecf45d3db8e8bd56bf6942)
1*f9fbec18Smcpowers /*
2*f9fbec18Smcpowers  * ***** BEGIN LICENSE BLOCK *****
3*f9fbec18Smcpowers  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4*f9fbec18Smcpowers  *
5*f9fbec18Smcpowers  * The contents of this file are subject to the Mozilla Public License Version
6*f9fbec18Smcpowers  * 1.1 (the "License"); you may not use this file except in compliance with
7*f9fbec18Smcpowers  * the License. You may obtain a copy of the License at
8*f9fbec18Smcpowers  * http://www.mozilla.org/MPL/
9*f9fbec18Smcpowers  *
10*f9fbec18Smcpowers  * Software distributed under the License is distributed on an "AS IS" basis,
11*f9fbec18Smcpowers  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12*f9fbec18Smcpowers  * for the specific language governing rights and limitations under the
13*f9fbec18Smcpowers  * License.
14*f9fbec18Smcpowers  *
15*f9fbec18Smcpowers  * The Original Code is the elliptic curve math library for prime field curves.
16*f9fbec18Smcpowers  *
17*f9fbec18Smcpowers  * The Initial Developer of the Original Code is
18*f9fbec18Smcpowers  * Sun Microsystems, Inc.
19*f9fbec18Smcpowers  * Portions created by the Initial Developer are Copyright (C) 2003
20*f9fbec18Smcpowers  * the Initial Developer. All Rights Reserved.
21*f9fbec18Smcpowers  *
22*f9fbec18Smcpowers  * Contributor(s):
23*f9fbec18Smcpowers  *   Douglas Stebila <douglas@stebila.ca>
24*f9fbec18Smcpowers  *
25*f9fbec18Smcpowers  * Alternatively, the contents of this file may be used under the terms of
26*f9fbec18Smcpowers  * either the GNU General Public License Version 2 or later (the "GPL"), or
27*f9fbec18Smcpowers  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28*f9fbec18Smcpowers  * in which case the provisions of the GPL or the LGPL are applicable instead
29*f9fbec18Smcpowers  * of those above. If you wish to allow use of your version of this file only
30*f9fbec18Smcpowers  * under the terms of either the GPL or the LGPL, and not to allow others to
31*f9fbec18Smcpowers  * use your version of this file under the terms of the MPL, indicate your
32*f9fbec18Smcpowers  * decision by deleting the provisions above and replace them with the notice
33*f9fbec18Smcpowers  * and other provisions required by the GPL or the LGPL. If you do not delete
34*f9fbec18Smcpowers  * the provisions above, a recipient may use your version of this file under
35*f9fbec18Smcpowers  * the terms of any one of the MPL, the GPL or the LGPL.
36*f9fbec18Smcpowers  *
37*f9fbec18Smcpowers  * ***** END LICENSE BLOCK ***** */
38*f9fbec18Smcpowers /*
39*f9fbec18Smcpowers  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
40*f9fbec18Smcpowers  * Use is subject to license terms.
41*f9fbec18Smcpowers  *
42*f9fbec18Smcpowers  * Sun elects to use this software under the MPL license.
43*f9fbec18Smcpowers  */
44*f9fbec18Smcpowers 
45*f9fbec18Smcpowers #pragma ident	"%Z%%M%	%I%	%E% SMI"
46*f9fbec18Smcpowers 
47*f9fbec18Smcpowers #include "ecp.h"
48*f9fbec18Smcpowers #include "mpi.h"
49*f9fbec18Smcpowers #include "mplogic.h"
50*f9fbec18Smcpowers #include "mpi-priv.h"
51*f9fbec18Smcpowers #ifndef _KERNEL
52*f9fbec18Smcpowers #include <stdlib.h>
53*f9fbec18Smcpowers #endif
54*f9fbec18Smcpowers 
55*f9fbec18Smcpowers /* Fast modular reduction for p384 = 2^384 - 2^128 - 2^96 + 2^32 - 1.  a can be r.
56*f9fbec18Smcpowers  * Uses algorithm 2.30 from Hankerson, Menezes, Vanstone. Guide to
57*f9fbec18Smcpowers  * Elliptic Curve Cryptography. */
58*f9fbec18Smcpowers mp_err
59*f9fbec18Smcpowers ec_GFp_nistp384_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
60*f9fbec18Smcpowers {
61*f9fbec18Smcpowers 	mp_err res = MP_OKAY;
62*f9fbec18Smcpowers 	int a_bits = mpl_significant_bits(a);
63*f9fbec18Smcpowers 	int i;
64*f9fbec18Smcpowers 
65*f9fbec18Smcpowers 	/* m1, m2 are statically-allocated mp_int of exactly the size we need */
66*f9fbec18Smcpowers 	mp_int m[10];
67*f9fbec18Smcpowers 
68*f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
69*f9fbec18Smcpowers 	mp_digit s[10][12];
70*f9fbec18Smcpowers 	for (i = 0; i < 10; i++) {
71*f9fbec18Smcpowers 		MP_SIGN(&m[i]) = MP_ZPOS;
72*f9fbec18Smcpowers 		MP_ALLOC(&m[i]) = 12;
73*f9fbec18Smcpowers 		MP_USED(&m[i]) = 12;
74*f9fbec18Smcpowers 		MP_DIGITS(&m[i]) = s[i];
75*f9fbec18Smcpowers 	}
76*f9fbec18Smcpowers #else
77*f9fbec18Smcpowers 	mp_digit s[10][6];
78*f9fbec18Smcpowers 	for (i = 0; i < 10; i++) {
79*f9fbec18Smcpowers 		MP_SIGN(&m[i]) = MP_ZPOS;
80*f9fbec18Smcpowers 		MP_ALLOC(&m[i]) = 6;
81*f9fbec18Smcpowers 		MP_USED(&m[i]) = 6;
82*f9fbec18Smcpowers 		MP_DIGITS(&m[i]) = s[i];
83*f9fbec18Smcpowers 	}
84*f9fbec18Smcpowers #endif
85*f9fbec18Smcpowers 
86*f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
87*f9fbec18Smcpowers 	/* for polynomials larger than twice the field size or polynomials
88*f9fbec18Smcpowers 	 * not using all words, use regular reduction */
89*f9fbec18Smcpowers 	if ((a_bits > 768) || (a_bits <= 736)) {
90*f9fbec18Smcpowers 		MP_CHECKOK(mp_mod(a, &meth->irr, r));
91*f9fbec18Smcpowers 	} else {
92*f9fbec18Smcpowers 		for (i = 0; i < 12; i++) {
93*f9fbec18Smcpowers 			s[0][i] = MP_DIGIT(a, i);
94*f9fbec18Smcpowers 		}
95*f9fbec18Smcpowers 		s[1][0] = 0;
96*f9fbec18Smcpowers 		s[1][1] = 0;
97*f9fbec18Smcpowers 		s[1][2] = 0;
98*f9fbec18Smcpowers 		s[1][3] = 0;
99*f9fbec18Smcpowers 		s[1][4] = MP_DIGIT(a, 21);
100*f9fbec18Smcpowers 		s[1][5] = MP_DIGIT(a, 22);
101*f9fbec18Smcpowers 		s[1][6] = MP_DIGIT(a, 23);
102*f9fbec18Smcpowers 		s[1][7] = 0;
103*f9fbec18Smcpowers 		s[1][8] = 0;
104*f9fbec18Smcpowers 		s[1][9] = 0;
105*f9fbec18Smcpowers 		s[1][10] = 0;
106*f9fbec18Smcpowers 		s[1][11] = 0;
107*f9fbec18Smcpowers 		for (i = 0; i < 12; i++) {
108*f9fbec18Smcpowers 			s[2][i] = MP_DIGIT(a, i+12);
109*f9fbec18Smcpowers 		}
110*f9fbec18Smcpowers 		s[3][0] = MP_DIGIT(a, 21);
111*f9fbec18Smcpowers 		s[3][1] = MP_DIGIT(a, 22);
112*f9fbec18Smcpowers 		s[3][2] = MP_DIGIT(a, 23);
113*f9fbec18Smcpowers 		for (i = 3; i < 12; i++) {
114*f9fbec18Smcpowers 			s[3][i] = MP_DIGIT(a, i+9);
115*f9fbec18Smcpowers 		}
116*f9fbec18Smcpowers 		s[4][0] = 0;
117*f9fbec18Smcpowers 		s[4][1] = MP_DIGIT(a, 23);
118*f9fbec18Smcpowers 		s[4][2] = 0;
119*f9fbec18Smcpowers 		s[4][3] = MP_DIGIT(a, 20);
120*f9fbec18Smcpowers 		for (i = 4; i < 12; i++) {
121*f9fbec18Smcpowers 			s[4][i] = MP_DIGIT(a, i+8);
122*f9fbec18Smcpowers 		}
123*f9fbec18Smcpowers 		s[5][0] = 0;
124*f9fbec18Smcpowers 		s[5][1] = 0;
125*f9fbec18Smcpowers 		s[5][2] = 0;
126*f9fbec18Smcpowers 		s[5][3] = 0;
127*f9fbec18Smcpowers 		s[5][4] = MP_DIGIT(a, 20);
128*f9fbec18Smcpowers 		s[5][5] = MP_DIGIT(a, 21);
129*f9fbec18Smcpowers 		s[5][6] = MP_DIGIT(a, 22);
130*f9fbec18Smcpowers 		s[5][7] = MP_DIGIT(a, 23);
131*f9fbec18Smcpowers 		s[5][8] = 0;
132*f9fbec18Smcpowers 		s[5][9] = 0;
133*f9fbec18Smcpowers 		s[5][10] = 0;
134*f9fbec18Smcpowers 		s[5][11] = 0;
135*f9fbec18Smcpowers 		s[6][0] = MP_DIGIT(a, 20);
136*f9fbec18Smcpowers 		s[6][1] = 0;
137*f9fbec18Smcpowers 		s[6][2] = 0;
138*f9fbec18Smcpowers 		s[6][3] = MP_DIGIT(a, 21);
139*f9fbec18Smcpowers 		s[6][4] = MP_DIGIT(a, 22);
140*f9fbec18Smcpowers 		s[6][5] = MP_DIGIT(a, 23);
141*f9fbec18Smcpowers 		s[6][6] = 0;
142*f9fbec18Smcpowers 		s[6][7] = 0;
143*f9fbec18Smcpowers 		s[6][8] = 0;
144*f9fbec18Smcpowers 		s[6][9] = 0;
145*f9fbec18Smcpowers 		s[6][10] = 0;
146*f9fbec18Smcpowers 		s[6][11] = 0;
147*f9fbec18Smcpowers 		s[7][0] = MP_DIGIT(a, 23);
148*f9fbec18Smcpowers 		for (i = 1; i < 12; i++) {
149*f9fbec18Smcpowers 			s[7][i] = MP_DIGIT(a, i+11);
150*f9fbec18Smcpowers 		}
151*f9fbec18Smcpowers 		s[8][0] = 0;
152*f9fbec18Smcpowers 		s[8][1] = MP_DIGIT(a, 20);
153*f9fbec18Smcpowers 		s[8][2] = MP_DIGIT(a, 21);
154*f9fbec18Smcpowers 		s[8][3] = MP_DIGIT(a, 22);
155*f9fbec18Smcpowers 		s[8][4] = MP_DIGIT(a, 23);
156*f9fbec18Smcpowers 		s[8][5] = 0;
157*f9fbec18Smcpowers 		s[8][6] = 0;
158*f9fbec18Smcpowers 		s[8][7] = 0;
159*f9fbec18Smcpowers 		s[8][8] = 0;
160*f9fbec18Smcpowers 		s[8][9] = 0;
161*f9fbec18Smcpowers 		s[8][10] = 0;
162*f9fbec18Smcpowers 		s[8][11] = 0;
163*f9fbec18Smcpowers 		s[9][0] = 0;
164*f9fbec18Smcpowers 		s[9][1] = 0;
165*f9fbec18Smcpowers 		s[9][2] = 0;
166*f9fbec18Smcpowers 		s[9][3] = MP_DIGIT(a, 23);
167*f9fbec18Smcpowers 		s[9][4] = MP_DIGIT(a, 23);
168*f9fbec18Smcpowers 		s[9][5] = 0;
169*f9fbec18Smcpowers 		s[9][6] = 0;
170*f9fbec18Smcpowers 		s[9][7] = 0;
171*f9fbec18Smcpowers 		s[9][8] = 0;
172*f9fbec18Smcpowers 		s[9][9] = 0;
173*f9fbec18Smcpowers 		s[9][10] = 0;
174*f9fbec18Smcpowers 		s[9][11] = 0;
175*f9fbec18Smcpowers 
176*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(&m[0], &m[1], r));
177*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[1], r));
178*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[2], r));
179*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[3], r));
180*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[4], r));
181*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[5], r));
182*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[6], r));
183*f9fbec18Smcpowers 		MP_CHECKOK(mp_sub(r, &m[7], r));
184*f9fbec18Smcpowers 		MP_CHECKOK(mp_sub(r, &m[8], r));
185*f9fbec18Smcpowers 		MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r));
186*f9fbec18Smcpowers 		s_mp_clamp(r);
187*f9fbec18Smcpowers 	}
188*f9fbec18Smcpowers #else
189*f9fbec18Smcpowers 	/* for polynomials larger than twice the field size or polynomials
190*f9fbec18Smcpowers 	 * not using all words, use regular reduction */
191*f9fbec18Smcpowers 	if ((a_bits > 768) || (a_bits <= 736)) {
192*f9fbec18Smcpowers 		MP_CHECKOK(mp_mod(a, &meth->irr, r));
193*f9fbec18Smcpowers 	} else {
194*f9fbec18Smcpowers 		for (i = 0; i < 6; i++) {
195*f9fbec18Smcpowers 			s[0][i] = MP_DIGIT(a, i);
196*f9fbec18Smcpowers 		}
197*f9fbec18Smcpowers 		s[1][0] = 0;
198*f9fbec18Smcpowers 		s[1][1] = 0;
199*f9fbec18Smcpowers 		s[1][2] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32);
200*f9fbec18Smcpowers 		s[1][3] = MP_DIGIT(a, 11) >> 32;
201*f9fbec18Smcpowers 		s[1][4] = 0;
202*f9fbec18Smcpowers 		s[1][5] = 0;
203*f9fbec18Smcpowers 		for (i = 0; i < 6; i++) {
204*f9fbec18Smcpowers 			s[2][i] = MP_DIGIT(a, i+6);
205*f9fbec18Smcpowers 		}
206*f9fbec18Smcpowers 		s[3][0] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32);
207*f9fbec18Smcpowers 		s[3][1] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32);
208*f9fbec18Smcpowers 		for (i = 2; i < 6; i++) {
209*f9fbec18Smcpowers 			s[3][i] = (MP_DIGIT(a, i+4) >> 32) | (MP_DIGIT(a, i+5) << 32);
210*f9fbec18Smcpowers 		}
211*f9fbec18Smcpowers 		s[4][0] = (MP_DIGIT(a, 11) >> 32) << 32;
212*f9fbec18Smcpowers 		s[4][1] = MP_DIGIT(a, 10) << 32;
213*f9fbec18Smcpowers 		for (i = 2; i < 6; i++) {
214*f9fbec18Smcpowers 			s[4][i] = MP_DIGIT(a, i+4);
215*f9fbec18Smcpowers 		}
216*f9fbec18Smcpowers 		s[5][0] = 0;
217*f9fbec18Smcpowers 		s[5][1] = 0;
218*f9fbec18Smcpowers 		s[5][2] = MP_DIGIT(a, 10);
219*f9fbec18Smcpowers 		s[5][3] = MP_DIGIT(a, 11);
220*f9fbec18Smcpowers 		s[5][4] = 0;
221*f9fbec18Smcpowers 		s[5][5] = 0;
222*f9fbec18Smcpowers 		s[6][0] = (MP_DIGIT(a, 10) << 32) >> 32;
223*f9fbec18Smcpowers 		s[6][1] = (MP_DIGIT(a, 10) >> 32) << 32;
224*f9fbec18Smcpowers 		s[6][2] = MP_DIGIT(a, 11);
225*f9fbec18Smcpowers 		s[6][3] = 0;
226*f9fbec18Smcpowers 		s[6][4] = 0;
227*f9fbec18Smcpowers 		s[6][5] = 0;
228*f9fbec18Smcpowers 		s[7][0] = (MP_DIGIT(a, 11) >> 32) | (MP_DIGIT(a, 6) << 32);
229*f9fbec18Smcpowers 		for (i = 1; i < 6; i++) {
230*f9fbec18Smcpowers 			s[7][i] = (MP_DIGIT(a, i+5) >> 32) | (MP_DIGIT(a, i+6) << 32);
231*f9fbec18Smcpowers 		}
232*f9fbec18Smcpowers 		s[8][0] = MP_DIGIT(a, 10) << 32;
233*f9fbec18Smcpowers 		s[8][1] = (MP_DIGIT(a, 10) >> 32) | (MP_DIGIT(a, 11) << 32);
234*f9fbec18Smcpowers 		s[8][2] = MP_DIGIT(a, 11) >> 32;
235*f9fbec18Smcpowers 		s[8][3] = 0;
236*f9fbec18Smcpowers 		s[8][4] = 0;
237*f9fbec18Smcpowers 		s[8][5] = 0;
238*f9fbec18Smcpowers 		s[9][0] = 0;
239*f9fbec18Smcpowers 		s[9][1] = (MP_DIGIT(a, 11) >> 32) << 32;
240*f9fbec18Smcpowers 		s[9][2] = MP_DIGIT(a, 11) >> 32;
241*f9fbec18Smcpowers 		s[9][3] = 0;
242*f9fbec18Smcpowers 		s[9][4] = 0;
243*f9fbec18Smcpowers 		s[9][5] = 0;
244*f9fbec18Smcpowers 
245*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(&m[0], &m[1], r));
246*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[1], r));
247*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[2], r));
248*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[3], r));
249*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[4], r));
250*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[5], r));
251*f9fbec18Smcpowers 		MP_CHECKOK(mp_add(r, &m[6], r));
252*f9fbec18Smcpowers 		MP_CHECKOK(mp_sub(r, &m[7], r));
253*f9fbec18Smcpowers 		MP_CHECKOK(mp_sub(r, &m[8], r));
254*f9fbec18Smcpowers 		MP_CHECKOK(mp_submod(r, &m[9], &meth->irr, r));
255*f9fbec18Smcpowers 		s_mp_clamp(r);
256*f9fbec18Smcpowers 	}
257*f9fbec18Smcpowers #endif
258*f9fbec18Smcpowers 
259*f9fbec18Smcpowers   CLEANUP:
260*f9fbec18Smcpowers 	return res;
261*f9fbec18Smcpowers }
262*f9fbec18Smcpowers 
263*f9fbec18Smcpowers /* Compute the square of polynomial a, reduce modulo p384. Store the
264*f9fbec18Smcpowers  * result in r.  r could be a.  Uses optimized modular reduction for p384.
265*f9fbec18Smcpowers  */
266*f9fbec18Smcpowers mp_err
267*f9fbec18Smcpowers ec_GFp_nistp384_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
268*f9fbec18Smcpowers {
269*f9fbec18Smcpowers 	mp_err res = MP_OKAY;
270*f9fbec18Smcpowers 
271*f9fbec18Smcpowers 	MP_CHECKOK(mp_sqr(a, r));
272*f9fbec18Smcpowers 	MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth));
273*f9fbec18Smcpowers   CLEANUP:
274*f9fbec18Smcpowers 	return res;
275*f9fbec18Smcpowers }
276*f9fbec18Smcpowers 
277*f9fbec18Smcpowers /* Compute the product of two polynomials a and b, reduce modulo p384.
278*f9fbec18Smcpowers  * Store the result in r.  r could be a or b; a could be b.  Uses
279*f9fbec18Smcpowers  * optimized modular reduction for p384. */
280*f9fbec18Smcpowers mp_err
281*f9fbec18Smcpowers ec_GFp_nistp384_mul(const mp_int *a, const mp_int *b, mp_int *r,
282*f9fbec18Smcpowers 					const GFMethod *meth)
283*f9fbec18Smcpowers {
284*f9fbec18Smcpowers 	mp_err res = MP_OKAY;
285*f9fbec18Smcpowers 
286*f9fbec18Smcpowers 	MP_CHECKOK(mp_mul(a, b, r));
287*f9fbec18Smcpowers 	MP_CHECKOK(ec_GFp_nistp384_mod(r, r, meth));
288*f9fbec18Smcpowers   CLEANUP:
289*f9fbec18Smcpowers 	return res;
290*f9fbec18Smcpowers }
291*f9fbec18Smcpowers 
292*f9fbec18Smcpowers /* Wire in fast field arithmetic and precomputation of base point for
293*f9fbec18Smcpowers  * named curves. */
294*f9fbec18Smcpowers mp_err
295*f9fbec18Smcpowers ec_group_set_gfp384(ECGroup *group, ECCurveName name)
296*f9fbec18Smcpowers {
297*f9fbec18Smcpowers 	if (name == ECCurve_NIST_P384) {
298*f9fbec18Smcpowers 		group->meth->field_mod = &ec_GFp_nistp384_mod;
299*f9fbec18Smcpowers 		group->meth->field_mul = &ec_GFp_nistp384_mul;
300*f9fbec18Smcpowers 		group->meth->field_sqr = &ec_GFp_nistp384_sqr;
301*f9fbec18Smcpowers 	}
302*f9fbec18Smcpowers 	return MP_OKAY;
303*f9fbec18Smcpowers }
304