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 GNUTLS_LIB_NETTLE_ECC_NETTLE_ECC_INTERNAL_H_INCLUDED 35 #define GNUTLS_LIB_NETTLE_ECC_NETTLE_ECC_INTERNAL_H_INCLUDED 36 37 #include <nettle/nettle-types.h> 38 #include <nettle/bignum.h> 39 #include <nettle/ecc-curve.h> 40 #include "gmp-glue.h" 41 42 /* Name mangling */ 43 #define ecc_pp1_redc _gnutls_nettle_ecc_ecc_pp1_redc 44 #define ecc_pm1_redc _gnutls_nettle_ecc_ecc_pm1_redc 45 #define ecc_mod_add _gnutls_nettle_ecc_ecc_mod_add 46 #define ecc_mod_sub _gnutls_nettle_ecc_ecc_mod_sub 47 #define ecc_mod_mul_1 _gnutls_nettle_ecc_ecc_mod_mul_1 48 #define ecc_mod_addmul_1 _gnutls_nettle_ecc_ecc_mod_addmul_1 49 #define ecc_mod_submul_1 _gnutls_nettle_ecc_ecc_mod_submul_1 50 #define ecc_mod_mul _gnutls_nettle_ecc_ecc_mod_mul 51 #define ecc_mod_sqr _gnutls_nettle_ecc_ecc_mod_sqr 52 #define ecc_mod_mul_canonical _gnutls_nettle_ecc_ecc_mod_mul_canonical 53 #define ecc_mod_random _gnutls_nettle_ecc_ecc_mod_random 54 #define ecc_mod _gnutls_nettle_ecc_ecc_mod 55 #define ecc_mod_inv _gnutls_nettle_ecc_ecc_mod_inv 56 #define ecc_hash _gnutls_nettle_ecc_ecc_hash 57 #define gost_hash _gnutls_nettle_ecc_gost_hash 58 #define ecc_a_to_j _gnutls_nettle_ecc_ecc_a_to_j 59 #define ecc_j_to_a _gnutls_nettle_ecc_ecc_j_to_a 60 #define ecc_eh_to_a _gnutls_nettle_ecc_ecc_eh_to_a 61 #define ecc_dup_jj _gnutls_nettle_ecc_ecc_dup_jj 62 #define ecc_add_jja _gnutls_nettle_ecc_ecc_add_jja 63 #define ecc_add_jjj _gnutls_nettle_ecc_ecc_add_jjj 64 #define ecc_dup_eh _gnutls_nettle_ecc_ecc_dup_eh 65 #define ecc_add_eh _gnutls_nettle_ecc_ecc_add_eh 66 #define ecc_add_ehh _gnutls_nettle_ecc_ecc_add_ehh 67 #define ecc_dup_th _gnutls_nettle_ecc_ecc_dup_th 68 #define ecc_add_th _gnutls_nettle_ecc_ecc_add_th 69 #define ecc_add_thh _gnutls_nettle_ecc_ecc_add_thh 70 #define ecc_mul_g _gnutls_nettle_ecc_ecc_mul_g 71 #define ecc_mul_a _gnutls_nettle_ecc_ecc_mul_a 72 #define ecc_mul_g_eh _gnutls_nettle_ecc_ecc_mul_g_eh 73 #define ecc_mul_a_eh _gnutls_nettle_ecc_ecc_mul_a_eh 74 #define ecc_mul_m _gnutls_nettle_ecc_ecc_mul_m 75 #define cnd_copy _gnutls_nettle_ecc_cnd_copy 76 #define sec_add_1 _gnutls_nettle_ecc_sec_add_1 77 #define sec_sub_1 _gnutls_nettle_ecc_sec_sub_1 78 #define sec_tabselect _gnutls_nettle_ecc_sec_tabselect 79 #define sec_modinv _gnutls_nettle_ecc_sec_modinv 80 #define curve25519_eh_to_x _gnutls_nettle_ecc_curve25519_eh_to_x 81 #define curve448_eh_to_x _gnutls_nettle_ecc_curve448_eh_to_x 82 83 #define _nettle__secp_192r1 _gnutls_nettle_ecc__secp_192r1 84 extern const struct ecc_curve _nettle_secp_192r1; 85 #define _nettle__secp_224r1 _gnutls_nettle_ecc__secp_224r1 86 extern const struct ecc_curve _nettle_secp_224r1; 87 #define _nettle__secp_256r1 _gnutls_nettle_ecc__secp_256r1 88 extern const struct ecc_curve _nettle_secp_256r1; 89 #define _nettle__secp_384r1 _gnutls_nettle_ecc__secp_384r1 90 extern const struct ecc_curve _nettle_secp_384r1; 91 #define _nettle__secp_521r1 _gnutls_nettle_ecc__secp_521r1 92 extern const struct ecc_curve _nettle_secp_521r1; 93 94 /* Keep this structure internal for now. It's misnamed (since it's 95 really implementing the equivalent twisted Edwards curve, with 96 different coordinates). And we're not quite ready to provide 97 general ecc operations over an arbitrary type of curve. */ 98 #define _nettle__curve25519 _gnutls_nettle_ecc__curve25519 99 extern const struct ecc_curve _nettle_curve25519; 100 #define _nettle__curve448 _gnutls_nettle_ecc__curve448 101 extern const struct ecc_curve _nettle_curve448; 102 103 /* GOST curves, visible with underscore prefix for now */ 104 #define _nettle__gost_gc256b _gnutls_nettle_ecc__gost_gc256b 105 extern const struct ecc_curve _nettle_gost_gc256b; 106 #define _nettle__gost_gc512a _gnutls_nettle_ecc__gost_gc512a 107 extern const struct ecc_curve _nettle_gost_gc512a; 108 109 #define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS) 110 111 /* Window size for ecc_mul_a. Using 4 bits seems like a good choice, 112 for both Intel x86_64 and ARM Cortex A9. For the larger curves, of 113 384 and 521 bits, we could improve speed by a few percent if we go 114 up to 5 bits, but I don't think that's worth doubling the 115 storage. */ 116 #define ECC_MUL_A_WBITS 4 117 /* And for ecc_mul_a_eh */ 118 #define ECC_MUL_A_EH_WBITS 4 119 120 struct ecc_modulo; 121 122 /* Reduces from 2*ecc->size to ecc->size. */ 123 /* Required to return a result < 2q. This property is inherited by 124 mod_mul and mod_sqr. */ 125 typedef void ecc_mod_func (const struct ecc_modulo *m, mp_limb_t *rp); 126 127 typedef void ecc_mod_inv_func (const struct ecc_modulo *m, 128 mp_limb_t *vp, const mp_limb_t *ap, 129 mp_limb_t *scratch); 130 131 /* Computes the square root of (u/v) (mod p) */ 132 typedef int ecc_mod_sqrt_func (const struct ecc_modulo *m, 133 mp_limb_t *rp, 134 const mp_limb_t *up, const mp_limb_t *vp, 135 mp_limb_t *scratch); 136 137 typedef void ecc_add_func (const struct ecc_curve *ecc, 138 mp_limb_t *r, 139 const mp_limb_t *p, const mp_limb_t *q, 140 mp_limb_t *scratch); 141 142 typedef void ecc_dup_func (const struct ecc_curve *ecc, 143 mp_limb_t *r, const mp_limb_t *p, 144 mp_limb_t *scratch); 145 146 typedef void ecc_mul_g_func (const struct ecc_curve *ecc, mp_limb_t *r, 147 const mp_limb_t *np, mp_limb_t *scratch); 148 149 typedef void ecc_mul_func (const struct ecc_curve *ecc, 150 mp_limb_t *r, 151 const mp_limb_t *np, const mp_limb_t *p, 152 mp_limb_t *scratch); 153 154 typedef void ecc_h_to_a_func (const struct ecc_curve *ecc, 155 int flags, 156 mp_limb_t *r, const mp_limb_t *p, 157 mp_limb_t *scratch); 158 159 struct ecc_modulo 160 { 161 unsigned short bit_size; 162 unsigned short size; 163 unsigned short B_size; 164 unsigned short redc_size; 165 unsigned short invert_itch; 166 unsigned short sqrt_itch; 167 168 const mp_limb_t *m; 169 /* B^size mod m. Expected to have at least 32 leading zeros 170 (equality for secp_256r1). */ 171 const mp_limb_t *B; 172 /* 2^{bit_size} - m, same value as above, but shifted. */ 173 const mp_limb_t *B_shifted; 174 /* m +/- 1, for redc, excluding redc_size low limbs. */ 175 const mp_limb_t *redc_mpm1; 176 /* (m+1)/2 */ 177 const mp_limb_t *mp1h; 178 179 ecc_mod_func *mod; 180 ecc_mod_func *reduce; 181 ecc_mod_inv_func *invert; 182 ecc_mod_sqrt_func *sqrt; 183 }; 184 185 /* Represents an elliptic curve of the form 186 187 y^2 = x^3 - 3x + b (mod p) 188 */ 189 struct ecc_curve 190 { 191 /* The prime p. */ 192 struct ecc_modulo p; 193 /* Group order. FIXME: Currently, many functions rely on q.size == 194 p.size. This has to change for radix-51 implementation of 195 curve25519 mod p arithmetic. */ 196 struct ecc_modulo q; 197 198 unsigned short use_redc; 199 unsigned short pippenger_k; 200 unsigned short pippenger_c; 201 202 unsigned short add_hh_itch; 203 unsigned short add_hhh_itch; 204 unsigned short dup_itch; 205 unsigned short mul_itch; 206 unsigned short mul_g_itch; 207 unsigned short h_to_a_itch; 208 209 ecc_add_func *add_hh; 210 ecc_add_func *add_hhh; 211 ecc_dup_func *dup; 212 ecc_mul_func *mul; 213 ecc_mul_g_func *mul_g; 214 ecc_h_to_a_func *h_to_a; 215 216 /* Curve constant */ 217 const mp_limb_t *b; 218 219 /* For redc, same as B mod p, otherwise 1. */ 220 const mp_limb_t *unit; 221 222 /* Tables for multiplying by the generator, size determined by k and 223 c. The first 2^c entries are defined by 224 225 T[ j_0 + j_1 2 + ... + j_{c-1} 2^{c-1} ] 226 = j_0 g + j_1 2^k g + ... + j_{c-1} 2^{k(c-1)} g 227 228 The following entries differ by powers of 2^{kc}, 229 230 T[i] = 2^{kc} T[i-2^c] 231 */ 232 const mp_limb_t *pippenger_table; 233 }; 234 235 /* In-place reduction. */ 236 ecc_mod_func ecc_mod; 237 ecc_mod_func ecc_pp1_redc; 238 ecc_mod_func ecc_pm1_redc; 239 240 ecc_mod_inv_func ecc_mod_inv; 241 242 void 243 ecc_mod_add (const struct ecc_modulo *m, mp_limb_t *rp, 244 const mp_limb_t *ap, const mp_limb_t *bp); 245 void 246 ecc_mod_sub (const struct ecc_modulo *m, mp_limb_t *rp, 247 const mp_limb_t *ap, const mp_limb_t *bp); 248 249 void 250 ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, 251 const mp_limb_t *ap, const mp_limb_t b); 252 253 void 254 ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, 255 const mp_limb_t *ap, mp_limb_t b); 256 void 257 ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, 258 const mp_limb_t *ap, mp_limb_t b); 259 260 /* The mul and sqr functions need 2*m->size limbs at rp */ 261 void 262 ecc_mod_mul (const struct ecc_modulo *m, mp_limb_t *rp, 263 const mp_limb_t *ap, const mp_limb_t *bp); 264 265 void 266 ecc_mod_sqr (const struct ecc_modulo *m, mp_limb_t *rp, 267 const mp_limb_t *ap); 268 269 /* mul function produces a canonical result, 0 <= R < M, needs 2*m->size limbs 270 * at rp. 271 */ 272 void 273 ecc_mod_mul_canonical (const struct ecc_modulo *m, mp_limb_t *rp, 274 const mp_limb_t *ap, const mp_limb_t *bp); 275 276 /* mod q operations. */ 277 void 278 ecc_mod_random (const struct ecc_modulo *m, mp_limb_t *xp, 279 void *ctx, nettle_random_func *random, mp_limb_t *scratch); 280 281 void 282 ecc_hash (const struct ecc_modulo *m, 283 mp_limb_t *hp, 284 size_t length, const uint8_t *digest); 285 286 void 287 gost_hash (const struct ecc_modulo *m, 288 mp_limb_t *hp, 289 size_t length, const uint8_t *digest); 290 291 /* Converts a point P in affine coordinates into a point R in jacobian 292 coordinates. */ 293 void 294 ecc_a_to_j (const struct ecc_curve *ecc, 295 mp_limb_t *r, const mp_limb_t *p); 296 297 /* Converts a point P in jacobian coordinates into a point R in affine 298 coordinates. If op == 1, produce x coordinate only. If op == 2, 299 produce the x coordinate only, and also reduce it modulo q. */ 300 void 301 ecc_j_to_a (const struct ecc_curve *ecc, 302 int op, 303 mp_limb_t *r, const mp_limb_t *p, 304 mp_limb_t *scratch); 305 306 /* Converts a point P in homogeneous coordinates on an Edwards curve 307 to affine coordinates. Meaning of op is the same as for 308 ecc_j_to_a. */ 309 void 310 ecc_eh_to_a (const struct ecc_curve *ecc, 311 int op, 312 mp_limb_t *r, const mp_limb_t *p, 313 mp_limb_t *scratch); 314 315 /* Group operations */ 316 317 /* Point doubling, with jacobian input and output. Corner cases: 318 Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ 319 void 320 ecc_dup_jj (const struct ecc_curve *ecc, 321 mp_limb_t *r, const mp_limb_t *p, 322 mp_limb_t *scratch); 323 324 /* Point addition, with jacobian output, one jacobian input and one 325 affine input. Corner cases: Fails for the cases 326 327 P = Q != 0 Duplication of non-zero point 328 P = 0, Q != 0 or P != 0, Q = 0 One input zero 329 330 Correctly gives R = 0 if P = Q = 0 or P = -Q. */ 331 void 332 ecc_add_jja (const struct ecc_curve *ecc, 333 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 334 mp_limb_t *scratch); 335 336 /* Point addition with Jacobian input and output. */ 337 void 338 ecc_add_jjj (const struct ecc_curve *ecc, 339 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 340 mp_limb_t *scratch); 341 342 /* Point doubling on a twisted Edwards curve, with homogeneous 343 cooordinates. */ 344 void 345 ecc_dup_eh (const struct ecc_curve *ecc, 346 mp_limb_t *r, const mp_limb_t *p, 347 mp_limb_t *scratch); 348 349 void 350 ecc_add_eh (const struct ecc_curve *ecc, 351 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 352 mp_limb_t *scratch); 353 354 void 355 ecc_add_ehh (const struct ecc_curve *ecc, 356 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 357 mp_limb_t *scratch); 358 359 void 360 ecc_dup_th (const struct ecc_curve *ecc, 361 mp_limb_t *r, const mp_limb_t *p, 362 mp_limb_t *scratch); 363 364 void 365 ecc_add_th (const struct ecc_curve *ecc, 366 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 367 mp_limb_t *scratch); 368 369 void 370 ecc_add_thh (const struct ecc_curve *ecc, 371 mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, 372 mp_limb_t *scratch); 373 374 /* Computes N * the group generator. N is an array of ecc_size() 375 limbs. It must be in the range 0 < N < group order, then R != 0, 376 and the algorithm can work without any intermediate values getting 377 to zero. */ 378 void 379 ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r, 380 const mp_limb_t *np, mp_limb_t *scratch); 381 382 /* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a 383 non-zero point on the curve, in affine coordinates. Output R is a 384 non-zero point, in Jacobian coordinates. */ 385 void 386 ecc_mul_a (const struct ecc_curve *ecc, 387 mp_limb_t *r, 388 const mp_limb_t *np, const mp_limb_t *p, 389 mp_limb_t *scratch); 390 391 void 392 ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r, 393 const mp_limb_t *np, mp_limb_t *scratch); 394 395 void 396 ecc_mul_a_eh (const struct ecc_curve *ecc, 397 mp_limb_t *r, 398 const mp_limb_t *np, const mp_limb_t *p, 399 mp_limb_t *scratch); 400 401 void 402 ecc_mul_m (const struct ecc_modulo *m, 403 mp_limb_t a24, 404 unsigned bit_low, unsigned bit_high, 405 mp_limb_t *qx, const uint8_t *n, const mp_limb_t *px, 406 mp_limb_t *scratch); 407 408 void 409 cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n); 410 411 mp_limb_t 412 sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b); 413 414 mp_limb_t 415 sec_sub_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b); 416 417 void 418 sec_tabselect (mp_limb_t *rp, mp_size_t rn, 419 const mp_limb_t *table, unsigned tn, 420 unsigned k); 421 422 void 423 curve25519_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, 424 mp_limb_t *scratch); 425 426 void 427 curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, 428 mp_limb_t *scratch); 429 430 /* Current scratch needs: */ 431 #define ECC_MOD_INV_ITCH(size) (2*(size)) 432 #define ECC_J_TO_A_ITCH(size) (5*(size)) 433 #define ECC_EH_TO_A_ITCH(size, inv) (2*(size)+(inv)) 434 #define ECC_DUP_JJ_ITCH(size) (5*(size)) 435 #define ECC_DUP_EH_ITCH(size) (5*(size)) 436 #define ECC_DUP_TH_ITCH(size) (5*(size)) 437 #define ECC_ADD_JJA_ITCH(size) (6*(size)) 438 #define ECC_ADD_JJJ_ITCH(size) (8*(size)) 439 #define ECC_ADD_EH_ITCH(size) (6*(size)) 440 #define ECC_ADD_EHH_ITCH(size) (7*(size)) 441 #define ECC_ADD_TH_ITCH(size) (6*(size)) 442 #define ECC_ADD_THH_ITCH(size) (7*(size)) 443 #define ECC_MUL_G_ITCH(size) (9*(size)) 444 #define ECC_MUL_G_EH_ITCH(size) (9*(size)) 445 #if ECC_MUL_A_WBITS == 0 446 #define ECC_MUL_A_ITCH(size) (12*(size)) 447 #else 448 #define ECC_MUL_A_ITCH(size) \ 449 (((3 << ECC_MUL_A_WBITS) + 11) * (size)) 450 #endif 451 #if ECC_MUL_A_EH_WBITS == 0 452 #define ECC_MUL_A_EH_ITCH(size) (12*(size)) 453 #else 454 #define ECC_MUL_A_EH_ITCH(size) \ 455 (((3 << ECC_MUL_A_EH_WBITS) + 10) * (size)) 456 #endif 457 #define ECC_MUL_M_ITCH(size) (11*(size)) 458 #define ECC_ECDSA_SIGN_ITCH(size) (12*(size)) 459 #define ECC_GOSTDSA_SIGN_ITCH(size) (12*(size)) 460 #define ECC_MOD_RANDOM_ITCH(size) (size) 461 #define ECC_HASH_ITCH(size) (1+(size)) 462 463 #endif /* GNUTLS_LIB_NETTLE_ECC_NETTLE_ECC_INTERNAL_H_INCLUDED */ 464