1 /*
2 * Copyright (c) 2013, Kenneth MacKay
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
18 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26 #ifndef _CRYPTO_ECC_H
27 #define _CRYPTO_ECC_H
28
29 #include <crypto/ecc_curve.h>
30 #include <linux/unaligned.h>
31
32 /* One digit is u64 qword. */
33 #define ECC_CURVE_NIST_P192_DIGITS 3
34 #define ECC_CURVE_NIST_P256_DIGITS 4
35 #define ECC_CURVE_NIST_P384_DIGITS 6
36 #define ECC_CURVE_NIST_P521_DIGITS 9
37 #define ECC_MAX_DIGITS DIV_ROUND_UP(521, 64) /* NIST P521 */
38
39 #define ECC_DIGITS_TO_BYTES_SHIFT 3
40
41 #define ECC_MAX_BYTES (ECC_MAX_DIGITS << ECC_DIGITS_TO_BYTES_SHIFT)
42
43 #define ECC_POINT_INIT(x, y, ndigits) (struct ecc_point) { x, y, ndigits }
44
45 /**
46 * ecc_swap_digits() - Copy ndigits from big endian array to native array
47 * @in: Input array
48 * @out: Output array
49 * @ndigits: Number of digits to copy
50 */
ecc_swap_digits(const void * in,u64 * out,unsigned int ndigits)51 static inline void ecc_swap_digits(const void *in, u64 *out, unsigned int ndigits)
52 {
53 const __be64 *src = (__force __be64 *)in;
54 int i;
55
56 for (i = 0; i < ndigits; i++)
57 out[i] = get_unaligned_be64(&src[ndigits - 1 - i]);
58 }
59
60 /**
61 * ecc_digits_from_bytes() - Create ndigits-sized digits array from byte array
62 * @in: Input byte array
63 * @nbytes Size of input byte array
64 * @out Output digits array
65 * @ndigits: Number of digits to create from byte array
66 *
67 * The first byte in the input byte array is expected to hold the most
68 * significant bits of the large integer.
69 */
70 void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes,
71 u64 *out, unsigned int ndigits);
72
73 /**
74 * ecc_is_key_valid() - Validate a given ECDH private key
75 *
76 * @curve_id: id representing the curve to use
77 * @ndigits: curve's number of digits
78 * @private_key: private key to be used for the given curve
79 * @private_key_len: private key length
80 *
81 * Returns 0 if the key is acceptable, a negative value otherwise
82 */
83 int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
84 const u64 *private_key, unsigned int private_key_len);
85
86 /**
87 * ecc_gen_privkey() - Generates an ECC private key.
88 * The private key is a random integer in the range 0 < random < n, where n is a
89 * prime that is the order of the cyclic subgroup generated by the distinguished
90 * point G.
91 * @curve_id: id representing the curve to use
92 * @ndigits: curve number of digits
93 * @private_key: buffer for storing the generated private key
94 *
95 * Returns 0 if the private key was generated successfully, a negative value
96 * if an error occurred.
97 */
98 int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits,
99 u64 *private_key);
100
101 /**
102 * ecc_make_pub_key() - Compute an ECC public key
103 *
104 * @curve_id: id representing the curve to use
105 * @ndigits: curve's number of digits
106 * @private_key: pregenerated private key for the given curve
107 * @public_key: buffer for storing the generated public key
108 *
109 * Returns 0 if the public key was generated successfully, a negative value
110 * if an error occurred.
111 */
112 int ecc_make_pub_key(const unsigned int curve_id, unsigned int ndigits,
113 const u64 *private_key, u64 *public_key);
114
115 /**
116 * crypto_ecdh_shared_secret() - Compute a shared secret
117 *
118 * @curve_id: id representing the curve to use
119 * @ndigits: curve's number of digits
120 * @private_key: private key of part A
121 * @public_key: public key of counterpart B
122 * @secret: buffer for storing the calculated shared secret
123 *
124 * Note: It is recommended that you hash the result of crypto_ecdh_shared_secret
125 * before using it for symmetric encryption or HMAC.
126 *
127 * Returns 0 if the shared secret was generated successfully, a negative value
128 * if an error occurred.
129 */
130 int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
131 const u64 *private_key, const u64 *public_key,
132 u64 *secret);
133
134 /**
135 * ecc_is_pubkey_valid_partial() - Partial public key validation
136 *
137 * @curve: elliptic curve domain parameters
138 * @pk: public key as a point
139 *
140 * Valdiate public key according to SP800-56A section 5.6.2.3.4 ECC Partial
141 * Public-Key Validation Routine.
142 *
143 * Note: There is no check that the public key is in the correct elliptic curve
144 * subgroup.
145 *
146 * Return: 0 if validation is successful, -EINVAL if validation is failed.
147 */
148 int ecc_is_pubkey_valid_partial(const struct ecc_curve *curve,
149 struct ecc_point *pk);
150
151 /**
152 * ecc_is_pubkey_valid_full() - Full public key validation
153 *
154 * @curve: elliptic curve domain parameters
155 * @pk: public key as a point
156 *
157 * Valdiate public key according to SP800-56A section 5.6.2.3.3 ECC Full
158 * Public-Key Validation Routine.
159 *
160 * Return: 0 if validation is successful, -EINVAL if validation is failed.
161 */
162 int ecc_is_pubkey_valid_full(const struct ecc_curve *curve,
163 struct ecc_point *pk);
164
165 /**
166 * vli_is_zero() - Determine is vli is zero
167 *
168 * @vli: vli to check.
169 * @ndigits: length of the @vli
170 */
171 bool vli_is_zero(const u64 *vli, unsigned int ndigits);
172
173 /**
174 * vli_cmp() - compare left and right vlis
175 *
176 * @left: vli
177 * @right: vli
178 * @ndigits: length of both vlis
179 *
180 * Returns sign of @left - @right, i.e. -1 if @left < @right,
181 * 0 if @left == @right, 1 if @left > @right.
182 */
183 int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits);
184
185 /**
186 * vli_sub() - Subtracts right from left
187 *
188 * @result: where to write result
189 * @left: vli
190 * @right vli
191 * @ndigits: length of all vlis
192 *
193 * Note: can modify in-place.
194 *
195 * Return: carry bit.
196 */
197 u64 vli_sub(u64 *result, const u64 *left, const u64 *right,
198 unsigned int ndigits);
199
200 /**
201 * vli_from_be64() - Load vli from big-endian u64 array
202 *
203 * @dest: destination vli
204 * @src: source array of u64 BE values
205 * @ndigits: length of both vli and array
206 */
207 void vli_from_be64(u64 *dest, const void *src, unsigned int ndigits);
208
209 /**
210 * vli_from_le64() - Load vli from little-endian u64 array
211 *
212 * @dest: destination vli
213 * @src: source array of u64 LE values
214 * @ndigits: length of both vli and array
215 */
216 void vli_from_le64(u64 *dest, const void *src, unsigned int ndigits);
217
218 /**
219 * vli_mod_inv() - Modular inversion
220 *
221 * @result: where to write vli number
222 * @input: vli value to operate on
223 * @mod: modulus
224 * @ndigits: length of all vlis
225 */
226 void vli_mod_inv(u64 *result, const u64 *input, const u64 *mod,
227 unsigned int ndigits);
228
229 /**
230 * vli_mod_mult_slow() - Modular multiplication
231 *
232 * @result: where to write result value
233 * @left: vli number to multiply with @right
234 * @right: vli number to multiply with @left
235 * @mod: modulus
236 * @ndigits: length of all vlis
237 *
238 * Note: Assumes that mod is big enough curve order.
239 */
240 void vli_mod_mult_slow(u64 *result, const u64 *left, const u64 *right,
241 const u64 *mod, unsigned int ndigits);
242
243 /**
244 * vli_num_bits() - Counts the number of bits required for vli.
245 *
246 * @vli: vli to check.
247 * @ndigits: Length of the @vli
248 *
249 * Return: The number of bits required to represent @vli.
250 */
251 unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits);
252
253 /**
254 * ecc_aloc_point() - Allocate ECC point.
255 *
256 * @ndigits: Length of vlis in u64 qwords.
257 *
258 * Return: Pointer to the allocated point or NULL if allocation failed.
259 */
260 struct ecc_point *ecc_alloc_point(unsigned int ndigits);
261
262 /**
263 * ecc_free_point() - Free ECC point.
264 *
265 * @p: The point to free.
266 */
267 void ecc_free_point(struct ecc_point *p);
268
269 /**
270 * ecc_point_is_zero() - Check if point is zero.
271 *
272 * @p: Point to check for zero.
273 *
274 * Return: true if point is the point at infinity, false otherwise.
275 */
276 bool ecc_point_is_zero(const struct ecc_point *point);
277
278 /**
279 * ecc_point_mult_shamir() - Add two points multiplied by scalars
280 *
281 * @result: resulting point
282 * @x: scalar to multiply with @p
283 * @p: point to multiply with @x
284 * @y: scalar to multiply with @q
285 * @q: point to multiply with @y
286 * @curve: curve
287 *
288 * Returns result = x * p + x * q over the curve.
289 * This works faster than two multiplications and addition.
290 */
291 void ecc_point_mult_shamir(const struct ecc_point *result,
292 const u64 *x, const struct ecc_point *p,
293 const u64 *y, const struct ecc_point *q,
294 const struct ecc_curve *curve);
295
296 #endif
297