1 /* ecc-internal.h 2 3 Copyright (C) 2013, 2014 Niels Möller 4 5 This file is part of GNU Nettle. 6 7 GNU Nettle is free software: you can redistribute it and/or 8 modify it under the terms of either: 9 10 * the GNU Lesser General Public License as published by the Free 11 Software Foundation; either version 3 of the License, or (at your 12 option) any later version. 13 14 or 15 16 * the GNU General Public License as published by the Free 17 Software Foundation; either version 2 of the License, or (at your 18 option) any later version. 19 20 or both in parallel, as here. 21 22 GNU Nettle is distributed in the hope that it will be useful, 23 but WITHOUT ANY WARRANTY; without even the implied warranty of 24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 25 General Public License for more details. 26 27 You should have received copies of the GNU General Public License and 28 the GNU Lesser General Public License along with this program. If 29 not, see http://www.gnu.org/licenses/. 30 */ 31 32 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ 33 34 #ifndef NETTLE_ECC_INTERNAL_H_INCLUDED 35 #define NETTLE_ECC_INTERNAL_H_INCLUDED 36 37 #include "nettle-types.h" 38 #include "bignum.h" 39 #include "ecc-curve.h" 40 #include "gmp-glue.h" 41 42 /* Name mangling */ 43 #define ecc_pp1_redc _nettle_ecc_pp1_redc 44 #define ecc_pm1_redc _nettle_ecc_pm1_redc 45 #define ecc_mod_add _nettle_ecc_mod_add 46 #define ecc_mod_sub _nettle_ecc_mod_sub 47 #define ecc_mod_mul_1 _nettle_ecc_mod_mul_1 48 #define ecc_mod_addmul_1 _nettle_ecc_mod_addmul_1 49 #define ecc_mod_submul_1 _nettle_ecc_mod_submul_1 50 #define ecc_mod_mul _nettle_ecc_mod_mul 51 #define ecc_mod_sqr _nettle_ecc_mod_sqr 52 #define ecc_mod_random _nettle_ecc_mod_random 53 #define ecc_mod _nettle_ecc_mod 54 #define ecc_mod_inv _nettle_ecc_mod_inv 55 #define ecc_hash _nettle_ecc_hash 56 #define ecc_a_to_j _nettle_ecc_a_to_j 57 #define ecc_j_to_a _nettle_ecc_j_to_a 58 #define ecc_eh_to_a _nettle_ecc_eh_to_a 59 #define ecc_dup_jj _nettle_ecc_dup_jj 60 #define ecc_add_jja _nettle_ecc_add_jja 61 #define ecc_add_jjj _nettle_ecc_add_jjj 62 #define ecc_dup_eh _nettle_ecc_dup_eh 63 #define ecc_add_eh _nettle_ecc_add_eh 64 #define ecc_add_ehh _nettle_ecc_add_ehh 65 #define ecc_mul_g _nettle_ecc_mul_g 66 #define ecc_mul_a _nettle_ecc_mul_a 67 #define ecc_mul_g_eh _nettle_ecc_mul_g_eh 68 #define ecc_mul_a_eh _nettle_ecc_mul_a_eh 69 #define cnd_copy _nettle_cnd_copy 70 #define sec_add_1 _nettle_sec_add_1 71 #define sec_sub_1 _nettle_sec_sub_1 72 #define sec_tabselect _nettle_sec_tabselect 73 #define sec_modinv _nettle_sec_modinv 74 #define curve25519_eh_to_x _nettle_curve25519_eh_to_x 75 76 extern const struct ecc_curve _nettle_secp_192r1; 77 extern const struct ecc_curve _nettle_secp_224r1; 78 extern const struct ecc_curve _nettle_secp_256r1; 79 extern const struct ecc_curve _nettle_secp_384r1; 80 extern const struct ecc_curve _nettle_secp_521r1; 81 82 /* Keep this structure internal for now. It's misnamed (since it's 83 really implementing the equivalent twisted Edwards curve, with 84 different coordinates). And we're not quite ready to provide 85 general ecc operations over an arbitrary type of curve. */ 86 extern const struct ecc_curve _nettle_curve25519; 87 88 #define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS) 89 90 /* Window size for ecc_mul_a. Using 4 bits seems like a good choice, 91 for both Intel x86_64 and ARM Cortex A9. For the larger curves, of 92 384 and 521 bits, we could improve speed by a few percent if we go 93 up to 5 bits, but I don't think that's worth doubling the 94 storage. */ 95 #define ECC_MUL_A_WBITS 4 96 /* And for ecc_mul_a_eh */ 97 #define ECC_MUL_A_EH_WBITS 4 98 99 struct ecc_modulo; 100 101 /* Reduces from 2*ecc->size to ecc->size. */ 102 /* Required to return a result < 2q. This property is inherited by 103 mod_mul and mod_sqr. */ 104 typedef void ecc_mod_func (const struct ecc_modulo *m, mp_limb_t *rp); 105 106 typedef void ecc_mod_inv_func (const struct ecc_modulo *m, 107 mp_limb_t *vp, const mp_limb_t *ap, 108 mp_limb_t *scratch); 109 110 /* Computes the square root of (u/v) (mod p) */ 111 typedef int ecc_mod_sqrt_func (const struct ecc_modulo *m, 112 mp_limb_t *rp, 113 const mp_limb_t *up, const mp_limb_t *vp, 114 mp_limb_t *scratch); 115 116 typedef void ecc_add_func (const struct ecc_curve *ecc, 117 mp_limb_t *r, 118 const mp_limb_t *p, const mp_limb_t *q, 119 mp_limb_t *scratch); 120 121 typedef void ecc_mul_g_func (const struct ecc_curve *ecc, mp_limb_t *r, 122 const mp_limb_t *np, mp_limb_t *scratch); 123 124 typedef void ecc_mul_func (const struct ecc_curve *ecc, 125 mp_limb_t *r, 126 const mp_limb_t *np, const mp_limb_t *p, 127 mp_limb_t *scratch); 128 129 typedef void ecc_h_to_a_func (const struct ecc_curve *ecc, 130 int flags, 131 mp_limb_t *r, const mp_limb_t *p, 132 mp_limb_t *scratch); 133 134 struct ecc_modulo 135 { 136 unsigned short bit_size; 137 unsigned short size; 138 unsigned short B_size; 139 unsigned short redc_size; 140 unsigned short invert_itch; 141 unsigned short sqrt_itch; 142 143 const mp_limb_t *m; 144 /* B^size mod m. Expected to have at least 32 leading zeros 145 (equality for secp_256r1). */ 146 const mp_limb_t *B; 147 /* 2^{bit_size} - p, same value as above, but shifted. */ 148 const mp_limb_t *B_shifted; 149 /* m +/- 1, for redc, excluding redc_size low limbs. */ 150 const mp_limb_t *redc_mpm1; 151 /* (m+1)/2 */ 152 const mp_limb_t *mp1h; 153 154 ecc_mod_func *mod; 155 ecc_mod_func *reduce; 156 ecc_mod_inv_func *invert; 157 ecc_mod_sqrt_func *sqrt; 158 }; 159 160 /* Represents an elliptic curve of the form 161 162 y^2 = x^3 - 3x + b (mod p) 163 */ 164 struct ecc_curve 165 { 166 /* The prime p. */ 167 struct ecc_modulo p; 168 /* Group order. FIXME: Currently, many fucntions rely on q.size == 169 p.size. This has to change for radix-51 implementation of 170 curve25519 mod p arithmetic. */ 171 struct ecc_modulo q; 172 173 unsigned short use_redc; 174 unsigned short pippenger_k; 175 unsigned short pippenger_c; 176 177 unsigned short add_hhh_itch; 178 unsigned short mul_itch; 179 unsigned short mul_g_itch; 180 unsigned short h_to_a_itch; 181 182 ecc_add_func *add_hhh; 183 ecc_mul_func *mul; 184 ecc_mul_g_func *mul_g; 185 ecc_h_to_a_func *h_to_a; 186 187 /* Curve constant */ 188 const mp_limb_t *b; 189 /* Generator, x coordinate followed by y (affine coordinates). 190 Currently used only by the test suite. */ 191 const mp_limb_t *g; 192 /* If non-NULL, the constant needed for transformation to the 193 equivalent Edwards curve. */ 194 const mp_limb_t *edwards_root; 195 196 /* For redc, same as B mod p, otherwise 1. */ 197 const mp_limb_t *unit; 198 199 /* Tables for multiplying by the generator, size determined by k and 200 c. The first 2^c entries are defined by 201 202 T[ j_0 + j_1 2 + ... + j_{c-1} 2^{c-1} ] 203 = j_0 g + j_1 2^k g + ... + j_{c-1} 2^{k(c-1)} g 204 205 The following entries differ by powers of 2^{kc}, 206 207 T[i] = 2^{kc} T[i-2^c] 208 */ 209 const mp_limb_t *pippenger_table; 210 }; 211 212 /* In-place reduction. */ 213 ecc_mod_func ecc_mod; 214 ecc_mod_func ecc_pp1_redc; 215 ecc_mod_func ecc_pm1_redc; 216 217 ecc_mod_inv_func ecc_mod_inv; 218 219 void 220 ecc_mod_add (const struct ecc_modulo *m, mp_limb_t *rp, 221 const mp_limb_t *ap, const mp_limb_t *bp); 222 void 223 ecc_mod_sub (const struct ecc_modulo *m, mp_limb_t *rp, 224 const mp_limb_t *ap, const mp_limb_t *bp); 225 226 void 227 ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, 228 const mp_limb_t *ap, const mp_limb_t b); 229 230 void 231 ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, 232 const mp_limb_t *ap, mp_limb_t b); 233 void 234 ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, 235 const mp_limb_t *ap, mp_limb_t b); 236 237 /* NOTE: mul and sqr needs 2*ecc->size limbs at rp */ 238 void 239 ecc_mod_mul (const struct ecc_modulo *m, mp_limb_t *rp, 240 const mp_limb_t *ap, const mp_limb_t *bp); 241 242 void 243 ecc_mod_sqr (const struct ecc_modulo *m, mp_limb_t *rp, 244 const mp_limb_t *ap); 245 246 #define ecc_modp_add(ecc, r, a, b) \ 247 ecc_mod_add (&(ecc)->p, (r), (a), (b)) 248 #define ecc_modp_sub(ecc, r, a, b) \ 249 ecc_mod_sub (&(ecc)->p, (r), (a), (b)) 250 #define ecc_modp_mul_1(ecc, r, a, b) \ 251 ecc_mod_mul_1 (&(ecc)->p, (r), (a), (b)) 252 #define ecc_modp_addmul_1(ecc, r, a, b) \ 253 ecc_mod_addmul_1 (&(ecc)->p, (r), (a), (b)) 254 #define ecc_modp_submul_1(ecc, r, a, b) \ 255 ecc_mod_submul_1 (&(ecc)->p, (r), (a), (b)) 256 #define ecc_modp_mul(ecc, r, a, b) \ 257 ecc_mod_mul (&(ecc)->p, (r), (a), (b)) 258 #define ecc_modp_sqr(ecc, r, a) \ 259 ecc_mod_sqr (&(ecc)->p, (r), (a)) 260 261 #define ecc_modq_add(ecc, r, a, b) \ 262 ecc_mod_add (&(ecc)->q, (r), (a), (b)) 263 #define ecc_modq_mul(ecc, r, a, b) \ 264 ecc_mod_mul (&(ecc)->q, (r), (a), (b)) 265 266 /* mod q operations. */ 267 void 268 ecc_mod_random (const struct ecc_modulo *m, mp_limb_t *xp, 269 void *ctx, nettle_random_func *random, mp_limb_t *scratch); 270 271 void 272 ecc_hash (const struct ecc_modulo *m, 273 mp_limb_t *hp, 274 size_t length, const uint8_t *digest); 275 276 /* Converts a point P in affine coordinates into a point R in jacobian 277 coordinates. */ 278 void 279 ecc_a_to_j (const struct ecc_curve *ecc, 280 mp_limb_t *r, const mp_limb_t *p); 281 282 /* Converts a point P in jacobian coordinates into a point R in affine 283 coordinates. If op == 1, produce x coordinate only. If op == 2, 284 produce the x coordiante only, and in also it modulo q. FIXME: For 285 the public interface, have separate for the three cases, and use 286 this flag argument only for the internal ecc->h_to_a function. */ 287 void 288 ecc_j_to_a (const struct ecc_curve *ecc, 289 int op, 290 mp_limb_t *r, const mp_limb_t *p, 291 mp_limb_t *scratch); 292 293 /* Converts a point P on an Edwards curve to affine coordinates on 294 the corresponding Montgomery curve. */ 295 void 296 ecc_eh_to_a (const struct ecc_curve *ecc, 297 int op, 298 mp_limb_t *r, const mp_limb_t *p, 299 mp_limb_t *scratch); 300 301 /* Group operations */ 302 303 /* Point doubling, with jacobian input and output. Corner cases: 304 Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ 305 void 306 ecc_dup_jj (const struct ecc_curve *ecc, 307 mp_limb_t *r, const mp_limb_t *p, 308 mp_limb_t *scratch); 309 310 /* Point addition, with jacobian output, one jacobian input and one 311 affine input. Corner cases: Fails for the cases 312 313 P = Q != 0 Duplication of non-zero point 314 P = 0, Q != 0 or P != 0, Q = 0 One input zero 315 316 Correctly gives R = 0 if P = Q = 0 or P = -Q. */ 317 void 318 ecc_add_jja (const struct ecc_curve *ecc, 319 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 320 mp_limb_t *scratch); 321 322 /* Point addition with Jacobian input and output. */ 323 void 324 ecc_add_jjj (const struct ecc_curve *ecc, 325 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 326 mp_limb_t *scratch); 327 328 /* Point doubling on an Edwards curve, with homogeneous 329 cooordinates. */ 330 void 331 ecc_dup_eh (const struct ecc_curve *ecc, 332 mp_limb_t *r, const mp_limb_t *p, 333 mp_limb_t *scratch); 334 335 void 336 ecc_add_eh (const struct ecc_curve *ecc, 337 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 338 mp_limb_t *scratch); 339 340 void 341 ecc_add_ehh (const struct ecc_curve *ecc, 342 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 343 mp_limb_t *scratch); 344 345 /* Computes N * the group generator. N is an array of ecc_size() 346 limbs. It must be in the range 0 < N < group order, then R != 0, 347 and the algorithm can work without any intermediate values getting 348 to zero. */ 349 void 350 ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r, 351 const mp_limb_t *np, mp_limb_t *scratch); 352 353 /* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a 354 non-zero point on the curve, in affine coordinates. Output R is a 355 non-zero point, in Jacobian coordinates. */ 356 void 357 ecc_mul_a (const struct ecc_curve *ecc, 358 mp_limb_t *r, 359 const mp_limb_t *np, const mp_limb_t *p, 360 mp_limb_t *scratch); 361 362 void 363 ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r, 364 const mp_limb_t *np, mp_limb_t *scratch); 365 366 void 367 ecc_mul_a_eh (const struct ecc_curve *ecc, 368 mp_limb_t *r, 369 const mp_limb_t *np, const mp_limb_t *p, 370 mp_limb_t *scratch); 371 372 void 373 cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n); 374 375 mp_limb_t 376 sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b); 377 378 mp_limb_t 379 sec_sub_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b); 380 381 void 382 sec_tabselect (mp_limb_t *rp, mp_size_t rn, 383 const mp_limb_t *table, unsigned tn, 384 unsigned k); 385 386 void 387 curve25519_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, 388 mp_limb_t *scratch); 389 390 /* Current scratch needs: */ 391 #define ECC_MOD_INV_ITCH(size) (2*(size)) 392 #define ECC_J_TO_A_ITCH(size) (5*(size)) 393 #define ECC_EH_TO_A_ITCH(size, inv) (2*(size)+(inv)) 394 #define ECC_DUP_JJ_ITCH(size) (5*(size)) 395 #define ECC_DUP_EH_ITCH(size) (5*(size)) 396 #define ECC_ADD_JJA_ITCH(size) (6*(size)) 397 #define ECC_ADD_JJJ_ITCH(size) (8*(size)) 398 #define ECC_ADD_EH_ITCH(size) (6*(size)) 399 #define ECC_ADD_EHH_ITCH(size) (7*(size)) 400 #define ECC_MUL_G_ITCH(size) (9*(size)) 401 #define ECC_MUL_G_EH_ITCH(size) (9*(size)) 402 #if ECC_MUL_A_WBITS == 0 403 #define ECC_MUL_A_ITCH(size) (12*(size)) 404 #else 405 #define ECC_MUL_A_ITCH(size) \ 406 (((3 << ECC_MUL_A_WBITS) + 11) * (size)) 407 #endif 408 #if ECC_MUL_A_EH_WBITS == 0 409 #define ECC_MUL_A_EH_ITCH(size) (13*(size)) 410 #else 411 #define ECC_MUL_A_EH_ITCH(size) \ 412 (((3 << ECC_MUL_A_EH_WBITS) + 10) * (size)) 413 #endif 414 #define ECC_ECDSA_SIGN_ITCH(size) (12*(size)) 415 #define ECC_MOD_RANDOM_ITCH(size) (size) 416 #define ECC_HASH_ITCH(size) (1+(size)) 417 418 #endif /* NETTLE_ECC_INTERNAL_H_INCLUDED */ 419