1/*
2 * Copyright (c) 2007, 2017, Oracle and/or its affiliates. All rights reserved.
3 * Use is subject to license terms.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public License
16 * along with this library; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24/* *********************************************************************
25 *
26 * The Original Code is the elliptic curve math library.
27 *
28 * The Initial Developer of the Original Code is
29 * Sun Microsystems, Inc.
30 * Portions created by the Initial Developer are Copyright (C) 2003
31 * the Initial Developer. All Rights Reserved.
32 *
33 * Contributor(s):
34 * Stephen Fung <fungstep@hotmail.com> and
35 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
36 *
37 * Last Modified Date from the Original Code: May 2017
38 *********************************************************************** */
39
40#ifndef _ECL_PRIV_H
41#define _ECL_PRIV_H
42
43#include "ecl.h"
44#include "mpi.h"
45#include "mplogic.h"
46
47/* MAX_FIELD_SIZE_DIGITS is the maximum size of field element supported */
48/* the following needs to go away... */
49#if defined(MP_USE_LONG_LONG_DIGIT) || defined(MP_USE_LONG_DIGIT)
50#define ECL_SIXTY_FOUR_BIT
51#else
52#define ECL_THIRTY_TWO_BIT
53#endif
54
55#define ECL_CURVE_DIGITS(curve_size_in_bits) \
56 (((curve_size_in_bits)+(sizeof(mp_digit)*8-1))/(sizeof(mp_digit)*8))
57#define ECL_BITS (sizeof(mp_digit)*8)
58#define ECL_MAX_FIELD_SIZE_DIGITS (80/sizeof(mp_digit))
59
60/* Gets the i'th bit in the binary representation of a. If i >= length(a),
61 * then return 0. (The above behaviour differs from mpl_get_bit, which
62 * causes an error if i >= length(a).) */
63#define MP_GET_BIT(a, i) \
64 ((i) >= mpl_significant_bits((a))) ? 0 : mpl_get_bit((a), (i))
65
66#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
67#define MP_ADD_CARRY(a1, a2, s, cin, cout) \
68 { mp_word w; \
69 w = ((mp_word)(cin)) + (a1) + (a2); \
70 s = ACCUM(w); \
71 cout = CARRYOUT(w); }
72
73/* Handle case when carry-in value is zero */
74#define MP_ADD_CARRY_ZERO(a1, a2, s, cout) \
75 MP_ADD_CARRY(a1, a2, s, 0, cout);
76
77#define MP_SUB_BORROW(a1, a2, s, bin, bout) \
78 { mp_word w; \
79 w = ((mp_word)(a1)) - (a2) - (bin); \
80 s = ACCUM(w); \
81 bout = (w >> MP_DIGIT_BIT) & 1; }
82
83#else
84/* NOTE,
85 * cin and cout could be the same variable.
86 * bin and bout could be the same variable.
87 * a1 or a2 and s could be the same variable.
88 * don't trash those outputs until their respective inputs have
89 * been read. */
90#define MP_ADD_CARRY(a1, a2, s, cin, cout) \
91 { mp_digit tmp,sum; \
92 tmp = (a1); \
93 sum = tmp + (a2); \
94 tmp = (sum < tmp); /* detect overflow */ \
95 s = sum += (cin); \
96 cout = tmp + (sum < (cin)); }
97
98/* Handle case when carry-in value is zero */
99#define MP_ADD_CARRY_ZERO(a1, a2, s, cout) \
100 { mp_digit tmp,sum; \
101 tmp = (a1); \
102 sum = tmp + (a2); \
103 tmp = (sum < tmp); /* detect overflow */ \
104 s = sum; \
105 cout = tmp; }
106
107#define MP_SUB_BORROW(a1, a2, s, bin, bout) \
108 { mp_digit tmp; \
109 tmp = (a1); \
110 s = tmp - (a2); \
111 tmp = (s > tmp); /* detect borrow */ \
112 if ((bin) && !s--) tmp++; \
113 bout = tmp; }
114#endif
115
116
117struct GFMethodStr;
118typedef struct GFMethodStr GFMethod;
119struct GFMethodStr {
120 /* Indicates whether the structure was constructed from dynamic memory
121 * or statically created. */
122 int constructed;
123 /* Irreducible that defines the field. For prime fields, this is the
124 * prime p. For binary polynomial fields, this is the bitstring
125 * representation of the irreducible polynomial. */
126 mp_int irr;
127 /* For prime fields, the value irr_arr[0] is the number of bits in the
128 * field. For binary polynomial fields, the irreducible polynomial
129 * f(t) is represented as an array of unsigned int[], where f(t) is
130 * of the form: f(t) = t^p[0] + t^p[1] + ... + t^p[4] where m = p[0]
131 * > p[1] > ... > p[4] = 0. */
132 unsigned int irr_arr[5];
133 /* Field arithmetic methods. All methods (except field_enc and
134 * field_dec) are assumed to take field-encoded parameters and return
135 * field-encoded values. All methods (except field_enc and field_dec)
136 * are required to be implemented. */
137 mp_err (*field_add) (const mp_int *a, const mp_int *b, mp_int *r,
138 const GFMethod *meth);
139 mp_err (*field_neg) (const mp_int *a, mp_int *r, const GFMethod *meth);
140 mp_err (*field_sub) (const mp_int *a, const mp_int *b, mp_int *r,
141 const GFMethod *meth);
142 mp_err (*field_mod) (const mp_int *a, mp_int *r, const GFMethod *meth);
143 mp_err (*field_mul) (const mp_int *a, const mp_int *b, mp_int *r,
144 const GFMethod *meth);
145 mp_err (*field_sqr) (const mp_int *a, mp_int *r, const GFMethod *meth);
146 mp_err (*field_div) (const mp_int *a, const mp_int *b, mp_int *r,
147 const GFMethod *meth);
148 mp_err (*field_enc) (const mp_int *a, mp_int *r, const GFMethod *meth);
149 mp_err (*field_dec) (const mp_int *a, mp_int *r, const GFMethod *meth);
150 /* Extra storage for implementation-specific data. Any memory
151 * allocated to these extra fields will be cleared by extra_free. */
152 void *extra1;
153 void *extra2;
154 void (*extra_free) (GFMethod *meth);
155};
156
157/* Construct generic GFMethods. */
158GFMethod *GFMethod_consGFp(const mp_int *irr);
159GFMethod *GFMethod_consGFp_mont(const mp_int *irr);
160GFMethod *GFMethod_consGF2m(const mp_int *irr,
161 const unsigned int irr_arr[5]);
162/* Free the memory allocated (if any) to a GFMethod object. */
163void GFMethod_free(GFMethod *meth);
164
165struct ECGroupStr {
166 /* Indicates whether the structure was constructed from dynamic memory
167 * or statically created. */
168 int constructed;
169 /* Field definition and arithmetic. */
170 GFMethod *meth;
171 /* Textual representation of curve name, if any. */
172 char *text;
173#ifdef _KERNEL
174 int text_len;
175#endif
176 /* Curve parameters, field-encoded. */
177 mp_int curvea, curveb;
178 /* x and y coordinates of the base point, field-encoded. */
179 mp_int genx, geny;
180 /* Order and cofactor of the base point. */
181 mp_int order;
182 int cofactor;
183 /* Point arithmetic methods. All methods are assumed to take
184 * field-encoded parameters and return field-encoded values. All
185 * methods (except base_point_mul and points_mul) are required to be
186 * implemented. */
187 mp_err (*point_add) (const mp_int *px, const mp_int *py,
188 const mp_int *qx, const mp_int *qy, mp_int *rx,
189 mp_int *ry, const ECGroup *group);
190 mp_err (*point_sub) (const mp_int *px, const mp_int *py,
191 const mp_int *qx, const mp_int *qy, mp_int *rx,
192 mp_int *ry, const ECGroup *group);
193 mp_err (*point_dbl) (const mp_int *px, const mp_int *py, mp_int *rx,
194 mp_int *ry, const ECGroup *group);
195 mp_err (*point_mul) (const mp_int *n, const mp_int *px,
196 const mp_int *py, mp_int *rx, mp_int *ry,
197 const ECGroup *group, int timing);
198 mp_err (*base_point_mul) (const mp_int *n, mp_int *rx, mp_int *ry,
199 const ECGroup *group);
200 mp_err (*points_mul) (const mp_int *k1, const mp_int *k2,
201 const mp_int *px, const mp_int *py, mp_int *rx,
202 mp_int *ry, const ECGroup *group,
203 int timing);
204 mp_err (*validate_point) (const mp_int *px, const mp_int *py, const ECGroup *group);
205 /* Extra storage for implementation-specific data. Any memory
206 * allocated to these extra fields will be cleared by extra_free. */
207 void *extra1;
208 void *extra2;
209 void (*extra_free) (ECGroup *group);
210};
211
212/* Wrapper functions for generic prime field arithmetic. */
213mp_err ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
214 const GFMethod *meth);
215mp_err ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth);
216mp_err ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
217 const GFMethod *meth);
218
219/* fixed length in-line adds. Count is in words */
220mp_err ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,
221 const GFMethod *meth);
222mp_err ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,
223 const GFMethod *meth);
224mp_err ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,
225 const GFMethod *meth);
226mp_err ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,
227 const GFMethod *meth);
228mp_err ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,
229 const GFMethod *meth);
230mp_err ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,
231 const GFMethod *meth);
232mp_err ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,
233 const GFMethod *meth);
234mp_err ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,
235 const GFMethod *meth);
236
237mp_err ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth);
238mp_err ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
239 const GFMethod *meth);
240mp_err ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth);
241mp_err ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
242 const GFMethod *meth);
243/* Wrapper functions for generic binary polynomial field arithmetic. */
244mp_err ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
245 const GFMethod *meth);
246mp_err ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth);
247mp_err ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth);
248mp_err ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
249 const GFMethod *meth);
250mp_err ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth);
251mp_err ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
252 const GFMethod *meth);
253
254/* Montgomery prime field arithmetic. */
255mp_err ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,
256 const GFMethod *meth);
257mp_err ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth);
258mp_err ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,
259 const GFMethod *meth);
260mp_err ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth);
261mp_err ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth);
262void ec_GFp_extra_free_mont(GFMethod *meth);
263
264/* point multiplication */
265mp_err ec_pts_mul_basic(const mp_int *k1, const mp_int *k2,
266 const mp_int *px, const mp_int *py, mp_int *rx,
267 mp_int *ry, const ECGroup *group,
268 int timing);
269mp_err ec_pts_mul_simul_w2(const mp_int *k1, const mp_int *k2,
270 const mp_int *px, const mp_int *py, mp_int *rx,
271 mp_int *ry, const ECGroup *group,
272 int timing);
273
274/* Computes the windowed non-adjacent-form (NAF) of a scalar. Out should
275 * be an array of signed char's to output to, bitsize should be the number
276 * of bits of out, in is the original scalar, and w is the window size.
277 * NAF is discussed in the paper: D. Hankerson, J. Hernandez and A.
278 * Menezes, "Software implementation of elliptic curve cryptography over
279 * binary fields", Proc. CHES 2000. */
280mp_err ec_compute_wNAF(signed char *out, int bitsize, const mp_int *in,
281 int w);
282
283/* Optimized field arithmetic */
284mp_err ec_group_set_gfp192(ECGroup *group, ECCurveName);
285mp_err ec_group_set_gfp224(ECGroup *group, ECCurveName);
286mp_err ec_group_set_gfp256(ECGroup *group, ECCurveName);
287mp_err ec_group_set_gfp384(ECGroup *group, ECCurveName);
288mp_err ec_group_set_gfp521(ECGroup *group, ECCurveName);
289mp_err ec_group_set_gf2m163(ECGroup *group, ECCurveName name);
290mp_err ec_group_set_gf2m193(ECGroup *group, ECCurveName name);
291mp_err ec_group_set_gf2m233(ECGroup *group, ECCurveName name);
292
293/* Optimized floating-point arithmetic */
294#ifdef ECL_USE_FP
295mp_err ec_group_set_secp160r1_fp(ECGroup *group);
296mp_err ec_group_set_nistp192_fp(ECGroup *group);
297mp_err ec_group_set_nistp224_fp(ECGroup *group);
298#endif
299
300#endif /* _ECL_PRIV_H */
301