1/* ecc.c - Elliptic Curve Cryptography 2 Copyright (C) 2007, 2008, 2010, 2011 Free Software Foundation, Inc. 3 4 This file is part of Libgcrypt. 5 6 Libgcrypt is free software; you can redistribute it and/or modify 7 it under the terms of the GNU Lesser General Public License as 8 published by the Free Software Foundation; either version 2.1 of 9 the License, or (at your option) any later version. 10 11 Libgcrypt is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU Lesser General Public License for more details. 15 16 You should have received a copy of the GNU Lesser General Public 17 License along with this program; if not, write to the Free Software 18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19 USA. */ 20 21/* This code is originally based on the Patch 0.1.6 for the gnupg 22 1.4.x branch as retrieved on 2007-03-21 from 23 http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2 24 The original authors are: 25 Written by 26 Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>, 27 Ramiro Moreno Chiral <ramiro at eup.udl.es> 28 Maintainers 29 Sergi Blanch i Torne 30 Ramiro Moreno Chiral 31 Mikael Mylnikov (mmr) 32 For use in Libgcrypt the code has been heavily modified and cleaned 33 up. In fact there is not much left of the orginally code except for 34 some variable names and the text book implementaion of the sign and 35 verification algorithms. The arithmetic functions have entirely 36 been rewritten and moved to mpi/ec.c. 37 38 ECDH encrypt and decrypt code written by Andrey Jivsov, 39*/ 40 41 42/* TODO: 43 44 - If we support point compression we need to uncompress before 45 computing the keygrip 46 47 - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a 48 special case in mpi_powm or check whether mpi_mulm is faster. 49 50 - Decide whether we should hide the mpi_point_t definition. 51*/ 52 53 54#include <config.h> 55#include <stdio.h> 56#include <stdlib.h> 57#include <string.h> 58 59#include "g10lib.h" 60#include "mpi.h" 61#include "cipher.h" 62 63/* Definition of a curve. */ 64typedef struct 65{ 66 gcry_mpi_t p; /* Prime specifying the field GF(p). */ 67 gcry_mpi_t a; /* First coefficient of the Weierstrass equation. */ 68 gcry_mpi_t b; /* Second coefficient of the Weierstrass equation. */ 69 mpi_point_t G; /* Base point (generator). */ 70 gcry_mpi_t n; /* Order of G. */ 71 const char *name; /* Name of curve or NULL. */ 72} elliptic_curve_t; 73 74 75typedef struct 76{ 77 elliptic_curve_t E; 78 mpi_point_t Q; /* Q = [d]G */ 79} ECC_public_key; 80 81typedef struct 82{ 83 elliptic_curve_t E; 84 mpi_point_t Q; 85 gcry_mpi_t d; 86} ECC_secret_key; 87 88 89/* This tables defines aliases for curve names. */ 90static const struct 91{ 92 const char *name; /* Our name. */ 93 const char *other; /* Other name. */ 94} curve_aliases[] = 95 { 96 { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID */ 97 { "NIST P-192", "prime192v1" }, /* X9.62 name. */ 98 { "NIST P-192", "secp192r1" }, /* SECP name. */ 99 100 { "NIST P-224", "secp224r1" }, 101 { "NIST P-224", "1.3.132.0.33" }, /* SECP OID. */ 102 103 { "NIST P-256", "1.2.840.10045.3.1.7" }, /* From NIST SP 800-78-1. */ 104 { "NIST P-256", "prime256v1" }, 105 { "NIST P-256", "secp256r1" }, 106 107 { "NIST P-384", "secp384r1" }, 108 { "NIST P-384", "1.3.132.0.34" }, 109 110 { "NIST P-521", "secp521r1" }, 111 { "NIST P-521", "1.3.132.0.35" }, 112 113 { "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.1" }, 114 { "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.3" }, 115 { "brainpoolP224r1", "1.3.36.3.3.2.8.1.1.5" }, 116 { "brainpoolP256r1", "1.3.36.3.3.2.8.1.1.7" }, 117 { "brainpoolP320r1", "1.3.36.3.3.2.8.1.1.9" }, 118 { "brainpoolP384r1", "1.3.36.3.3.2.8.1.1.11"}, 119 { "brainpoolP512r1", "1.3.36.3.3.2.8.1.1.13"}, 120 121 { NULL, NULL} 122 }; 123 124typedef struct { 125 const char *desc; /* Description of the curve. */ 126 unsigned int nbits; /* Number of bits. */ 127 unsigned int fips:1; /* True if this is a FIPS140-2 approved curve. */ 128 const char *p; /* Order of the prime field. */ 129 const char *a, *b; /* The coefficients. */ 130 const char *n; /* The order of the base point. */ 131 const char *g_x, *g_y; /* Base point. */ 132} ecc_domain_parms_t; 133 134/* This static table defines all available curves. */ 135static const ecc_domain_parms_t domain_parms[] = 136 { 137 { 138 "NIST P-192", 192, 1, 139 "0xfffffffffffffffffffffffffffffffeffffffffffffffff", 140 "0xfffffffffffffffffffffffffffffffefffffffffffffffc", 141 "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", 142 "0xffffffffffffffffffffffff99def836146bc9b1b4d22831", 143 144 "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", 145 "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811" 146 }, 147 { 148 "NIST P-224", 224, 1, 149 "0xffffffffffffffffffffffffffffffff000000000000000000000001", 150 "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe", 151 "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", 152 "0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" , 153 154 "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", 155 "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34" 156 }, 157 { 158 "NIST P-256", 256, 1, 159 "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 160 "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 161 "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 162 "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 163 164 "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 165 "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5" 166 }, 167 { 168 "NIST P-384", 384, 1, 169 "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" 170 "ffffffff0000000000000000ffffffff", 171 "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" 172 "ffffffff0000000000000000fffffffc", 173 "0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a" 174 "c656398d8a2ed19d2a85c8edd3ec2aef", 175 "0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf" 176 "581a0db248b0a77aecec196accc52973", 177 178 "0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a38" 179 "5502f25dbf55296c3a545e3872760ab7", 180 "0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0" 181 "0a60b1ce1d7e819d7a431d7c90ea0e5f" 182 }, 183 { 184 "NIST P-521", 521, 1, 185 "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" 186 "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 187 "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" 188 "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc", 189 "0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef10" 190 "9e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 191 "0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" 192 "ffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409", 193 194 "0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3d" 195 "baa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 196 "0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e6" 197 "62c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650" 198 }, 199 200 { "brainpoolP160r1", 160, 0, 201 "0xe95e4a5f737059dc60dfc7ad95b3d8139515620f", 202 "0x340e7be2a280eb74e2be61bada745d97e8f7c300", 203 "0x1e589a8595423412134faa2dbdec95c8d8675e58", 204 "0xe95e4a5f737059dc60df5991d45029409e60fc09", 205 "0xbed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3", 206 "0x1667cb477a1a8ec338f94741669c976316da6321" 207 }, 208 209 { "brainpoolP192r1", 192, 0, 210 "0xc302f41d932a36cda7a3463093d18db78fce476de1a86297", 211 "0x6a91174076b1e0e19c39c031fe8685c1cae040e5c69a28ef", 212 "0x469a28ef7c28cca3dc721d044f4496bcca7ef4146fbf25c9", 213 "0xc302f41d932a36cda7a3462f9e9e916b5be8f1029ac4acc1", 214 "0xc0a0647eaab6a48753b033c56cb0f0900a2f5c4853375fd6", 215 "0x14b690866abd5bb88b5f4828c1490002e6773fa2fa299b8f" 216 }, 217 218 { "brainpoolP224r1", 224, 0, 219 "0xd7c134aa264366862a18302575d1d787b09f075797da89f57ec8c0ff", 220 "0x68a5e62ca9ce6c1c299803a6c1530b514e182ad8b0042a59cad29f43", 221 "0x2580f63ccfe44138870713b1a92369e33e2135d266dbb372386c400b", 222 "0xd7c134aa264366862a18302575d0fb98d116bc4b6ddebca3a5a7939f", 223 "0x0d9029ad2c7e5cf4340823b2a87dc68c9e4ce3174c1e6efdee12c07d", 224 "0x58aa56f772c0726f24c6b89e4ecdac24354b9e99caa3f6d3761402cd" 225 }, 226 227 { "brainpoolP256r1", 256, 0, 228 "0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377", 229 "0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9", 230 "0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6", 231 "0xa9fb57dba1eea9bc3e660a909d838d718c397aa3b561a6f7901e0e82974856a7", 232 "0x8bd2aeb9cb7e57cb2c4b482ffc81b7afb9de27e1e3bd23c23a4453bd9ace3262", 233 "0x547ef835c3dac4fd97f8461a14611dc9c27745132ded8e545c1d54c72f046997" 234 }, 235 236 { "brainpoolP320r1", 320, 0, 237 "0xd35e472036bc4fb7e13c785ed201e065f98fcfa6f6f40def4f92b9ec7893ec28" 238 "fcd412b1f1b32e27", 239 "0x3ee30b568fbab0f883ccebd46d3f3bb8a2a73513f5eb79da66190eb085ffa9f4" 240 "92f375a97d860eb4", 241 "0x520883949dfdbc42d3ad198640688a6fe13f41349554b49acc31dccd88453981" 242 "6f5eb4ac8fb1f1a6", 243 "0xd35e472036bc4fb7e13c785ed201e065f98fcfa5b68f12a32d482ec7ee8658e9" 244 "8691555b44c59311", 245 "0x43bd7e9afb53d8b85289bcc48ee5bfe6f20137d10a087eb6e7871e2a10a599c7" 246 "10af8d0d39e20611", 247 "0x14fdd05545ec1cc8ab4093247f77275e0743ffed117182eaa9c77877aaac6ac7" 248 "d35245d1692e8ee1" 249 }, 250 251 { "brainpoolP384r1", 384, 0, 252 "0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b412b1da197fb71123" 253 "acd3a729901d1a71874700133107ec53", 254 "0x7bc382c63d8c150c3c72080ace05afa0c2bea28e4fb22787139165efba91f90f" 255 "8aa5814a503ad4eb04a8c7dd22ce2826", 256 "0x04a8c7dd22ce28268b39b55416f0447c2fb77de107dcd2a62e880ea53eeb62d5" 257 "7cb4390295dbc9943ab78696fa504c11", 258 "0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b31f166e6cac0425a7" 259 "cf3ab6af6b7fc3103b883202e9046565", 260 "0x1d1c64f068cf45ffa2a63a81b7c13f6b8847a3e77ef14fe3db7fcafe0cbd10e8" 261 "e826e03436d646aaef87b2e247d4af1e", 262 "0x8abe1d7520f9c2a45cb1eb8e95cfd55262b70b29feec5864e19c054ff9912928" 263 "0e4646217791811142820341263c5315" 264 }, 265 266 { "brainpoolP512r1", 512, 0, 267 "0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330871" 268 "7d4d9b009bc66842aecda12ae6a380e62881ff2f2d82c68528aa6056583a48f3", 269 "0x7830a3318b603b89e2327145ac234cc594cbdd8d3df91610a83441caea9863bc" 270 "2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a72bf2c7b9e7c1ac4d77fc94ca", 271 "0x3df91610a83441caea9863bc2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a7" 272 "2bf2c7b9e7c1ac4d77fc94cadc083e67984050b75ebae5dd2809bd638016f723", 273 "0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330870" 274 "553e5c414ca92619418661197fac10471db1d381085ddaddb58796829ca90069", 275 "0x81aee4bdd82ed9645a21322e9c4c6a9385ed9f70b5d916c1b43b62eef4d0098e" 276 "ff3b1f78e2d0d48d50d1687b93b97d5f7c6d5047406a5e688b352209bcb9f822", 277 "0x7dde385d566332ecc0eabfa9cf7822fdf209f70024a57b1aa000c55b881f8111" 278 "b2dcde494a5f485e5bca4bd88a2763aed1ca2b2fa8f0540678cd1e0f3ad80892" 279 }, 280 281 { NULL, 0, 0, NULL, NULL, NULL, NULL } 282 }; 283 284 285/* Registered progress function and its callback value. */ 286static void (*progress_cb) (void *, const char*, int, int, int); 287static void *progress_cb_data; 288 289 290#define point_init(a) _gcry_mpi_ec_point_init ((a)) 291#define point_free(a) _gcry_mpi_ec_point_free ((a)) 292 293 294 295/* Local prototypes. */ 296static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level); 297static void test_keys (ECC_secret_key * sk, unsigned int nbits); 298static int check_secret_key (ECC_secret_key * sk); 299static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey, 300 gcry_mpi_t r, gcry_mpi_t s); 301static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey, 302 gcry_mpi_t r, gcry_mpi_t s); 303 304 305static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base); 306 307 308 309 310void 311_gcry_register_pk_ecc_progress (void (*cb) (void *, const char *, 312 int, int, int), 313 void *cb_data) 314{ 315 progress_cb = cb; 316 progress_cb_data = cb_data; 317} 318 319/* static void */ 320/* progress (int c) */ 321/* { */ 322/* if (progress_cb) */ 323/* progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */ 324/* } */ 325 326 327 328 329/* Set the value from S into D. */ 330static void 331point_set (mpi_point_t *d, mpi_point_t *s) 332{ 333 mpi_set (d->x, s->x); 334 mpi_set (d->y, s->y); 335 mpi_set (d->z, s->z); 336} 337 338 339/* 340 * Release a curve object. 341 */ 342static void 343curve_free (elliptic_curve_t *E) 344{ 345 mpi_free (E->p); E->p = NULL; 346 mpi_free (E->a); E->a = NULL; 347 mpi_free (E->b); E->b = NULL; 348 point_free (&E->G); 349 mpi_free (E->n); E->n = NULL; 350} 351 352 353/* 354 * Return a copy of a curve object. 355 */ 356static elliptic_curve_t 357curve_copy (elliptic_curve_t E) 358{ 359 elliptic_curve_t R; 360 361 R.p = mpi_copy (E.p); 362 R.a = mpi_copy (E.a); 363 R.b = mpi_copy (E.b); 364 point_init (&R.G); 365 point_set (&R.G, &E.G); 366 R.n = mpi_copy (E.n); 367 368 return R; 369} 370 371 372/* Helper to scan a hex string. */ 373static gcry_mpi_t 374scanval (const char *string) 375{ 376 gpg_error_t err; 377 gcry_mpi_t val; 378 379 err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL); 380 if (err) 381 log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err)); 382 return val; 383} 384 385 386 387 388 389/**************** 390 * Solve the right side of the equation that defines a curve. 391 */ 392static gcry_mpi_t 393gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base) 394{ 395 gcry_mpi_t three, x_3, axb, y; 396 397 three = mpi_alloc_set_ui (3); 398 x_3 = mpi_new (0); 399 axb = mpi_new (0); 400 y = mpi_new (0); 401 402 mpi_powm (x_3, x, three, base->p); 403 mpi_mulm (axb, base->a, x, base->p); 404 mpi_addm (axb, axb, base->b, base->p); 405 mpi_addm (y, x_3, axb, base->p); 406 407 mpi_free (x_3); 408 mpi_free (axb); 409 mpi_free (three); 410 return y; /* The quadratic value of the coordinate if it exist. */ 411} 412 413 414/* Generate a random secret scalar k with an order of p 415 416 At the beginning this was identical to the code is in elgamal.c. 417 Later imporved by mmr. Further simplified by wk. */ 418static gcry_mpi_t 419gen_k (gcry_mpi_t p, int security_level) 420{ 421 gcry_mpi_t k; 422 unsigned int nbits; 423 424 nbits = mpi_get_nbits (p); 425 k = mpi_snew (nbits); 426 if (DBG_CIPHER) 427 log_debug ("choosing a random k of %u bits at seclevel %d\n", 428 nbits, security_level); 429 430 gcry_mpi_randomize (k, nbits, security_level); 431 432 mpi_mod (k, k, p); /* k = k mod p */ 433 434 return k; 435} 436 437 438/* Generate the crypto system setup. This function takes the NAME of 439 a curve or the desired number of bits and stores at R_CURVE the 440 parameters of the named curve or those of a suitable curve. The 441 chosen number of bits is stored on R_NBITS. */ 442static gpg_err_code_t 443fill_in_curve (unsigned int nbits, const char *name, 444 elliptic_curve_t *curve, unsigned int *r_nbits) 445{ 446 int idx, aliasno; 447 const char *resname = NULL; /* Set to a found curve name. */ 448 449 if (name) 450 { 451 /* First check our native curves. */ 452 for (idx = 0; domain_parms[idx].desc; idx++) 453 if (!strcmp (name, domain_parms[idx].desc)) 454 { 455 resname = domain_parms[idx].desc; 456 break; 457 } 458 /* If not found consult the alias table. */ 459 if (!domain_parms[idx].desc) 460 { 461 for (aliasno = 0; curve_aliases[aliasno].name; aliasno++) 462 if (!strcmp (name, curve_aliases[aliasno].other)) 463 break; 464 if (curve_aliases[aliasno].name) 465 { 466 for (idx = 0; domain_parms[idx].desc; idx++) 467 if (!strcmp (curve_aliases[aliasno].name, 468 domain_parms[idx].desc)) 469 { 470 resname = domain_parms[idx].desc; 471 break; 472 } 473 } 474 } 475 } 476 else 477 { 478 for (idx = 0; domain_parms[idx].desc; idx++) 479 if (nbits == domain_parms[idx].nbits) 480 break; 481 } 482 if (!domain_parms[idx].desc) 483 return GPG_ERR_INV_VALUE; 484 485 /* In fips mode we only support NIST curves. Note that it is 486 possible to bypass this check by specifying the curve parameters 487 directly. */ 488 if (fips_mode () && !domain_parms[idx].fips ) 489 return GPG_ERR_NOT_SUPPORTED; 490 491 *r_nbits = domain_parms[idx].nbits; 492 curve->p = scanval (domain_parms[idx].p); 493 curve->a = scanval (domain_parms[idx].a); 494 curve->b = scanval (domain_parms[idx].b); 495 curve->n = scanval (domain_parms[idx].n); 496 curve->G.x = scanval (domain_parms[idx].g_x); 497 curve->G.y = scanval (domain_parms[idx].g_y); 498 curve->G.z = mpi_alloc_set_ui (1); 499 curve->name = resname; 500 501 return 0; 502} 503 504 505/* 506 * First obtain the setup. Over the finite field randomize an scalar 507 * secret value, and calculate the public point. 508 */ 509static gpg_err_code_t 510generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name, 511 int transient_key, 512 gcry_mpi_t g_x, gcry_mpi_t g_y, 513 gcry_mpi_t q_x, gcry_mpi_t q_y, 514 const char **r_usedcurve) 515{ 516 gpg_err_code_t err; 517 elliptic_curve_t E; 518 gcry_mpi_t d; 519 mpi_point_t Q; 520 mpi_ec_t ctx; 521 gcry_random_level_t random_level; 522 523 *r_usedcurve = NULL; 524 525 err = fill_in_curve (nbits, name, &E, &nbits); 526 if (err) 527 return err; 528 529 if (DBG_CIPHER) 530 { 531 log_mpidump ("ecgen curve p", E.p); 532 log_mpidump ("ecgen curve a", E.a); 533 log_mpidump ("ecgen curve b", E.b); 534 log_mpidump ("ecgen curve n", E.n); 535 log_mpidump ("ecgen curve Gx", E.G.x); 536 log_mpidump ("ecgen curve Gy", E.G.y); 537 log_mpidump ("ecgen curve Gz", E.G.z); 538 if (E.name) 539 log_debug ("ecgen curve used: %s\n", E.name); 540 } 541 542 random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM; 543 d = gen_k (E.n, random_level); 544 545 /* Compute Q. */ 546 point_init (&Q); 547 ctx = _gcry_mpi_ec_init (E.p, E.a); 548 _gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx); 549 550 /* Copy the stuff to the key structures. */ 551 sk->E.p = mpi_copy (E.p); 552 sk->E.a = mpi_copy (E.a); 553 sk->E.b = mpi_copy (E.b); 554 point_init (&sk->E.G); 555 point_set (&sk->E.G, &E.G); 556 sk->E.n = mpi_copy (E.n); 557 point_init (&sk->Q); 558 point_set (&sk->Q, &Q); 559 sk->d = mpi_copy (d); 560 /* We also return copies of G and Q in affine coordinates if 561 requested. */ 562 if (g_x && g_y) 563 { 564 if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx)) 565 log_fatal ("ecgen: Failed to get affine coordinates\n"); 566 } 567 if (q_x && q_y) 568 { 569 if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx)) 570 log_fatal ("ecgen: Failed to get affine coordinates\n"); 571 } 572 _gcry_mpi_ec_free (ctx); 573 574 point_free (&Q); 575 mpi_free (d); 576 577 *r_usedcurve = E.name; 578 curve_free (&E); 579 580 /* Now we can test our keys (this should never fail!). */ 581 test_keys (sk, nbits - 64); 582 583 return 0; 584} 585 586 587/* 588 * To verify correct skey it use a random information. 589 * First, encrypt and decrypt this dummy value, 590 * test if the information is recuperated. 591 * Second, test with the sign and verify functions. 592 */ 593static void 594test_keys (ECC_secret_key *sk, unsigned int nbits) 595{ 596 ECC_public_key pk; 597 gcry_mpi_t test = mpi_new (nbits); 598 mpi_point_t R_; 599 gcry_mpi_t c = mpi_new (nbits); 600 gcry_mpi_t out = mpi_new (nbits); 601 gcry_mpi_t r = mpi_new (nbits); 602 gcry_mpi_t s = mpi_new (nbits); 603 604 if (DBG_CIPHER) 605 log_debug ("Testing key.\n"); 606 607 point_init (&R_); 608 609 pk.E = curve_copy (sk->E); 610 point_init (&pk.Q); 611 point_set (&pk.Q, &sk->Q); 612 613 gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM); 614 615 if (sign (test, sk, r, s) ) 616 log_fatal ("ECDSA operation: sign failed\n"); 617 618 if (verify (test, &pk, r, s)) 619 { 620 log_fatal ("ECDSA operation: sign, verify failed\n"); 621 } 622 623 if (DBG_CIPHER) 624 log_debug ("ECDSA operation: sign, verify ok.\n"); 625 626 point_free (&pk.Q); 627 curve_free (&pk.E); 628 629 point_free (&R_); 630 mpi_free (s); 631 mpi_free (r); 632 mpi_free (out); 633 mpi_free (c); 634 mpi_free (test); 635} 636 637 638/* 639 * To check the validity of the value, recalculate the correspondence 640 * between the public value and the secret one. 641 */ 642static int 643check_secret_key (ECC_secret_key * sk) 644{ 645 mpi_point_t Q; 646 gcry_mpi_t y_2, y2 = mpi_alloc (0); 647 mpi_ec_t ctx; 648 649 /* ?primarity test of 'p' */ 650 /* (...) //!! */ 651 /* G in E(F_p) */ 652 y_2 = gen_y_2 (sk->E.G.x, &sk->E); /* y^2=x^3+a*x+b */ 653 mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p); /* y^2=y*y */ 654 if (mpi_cmp (y_2, y2)) 655 { 656 if (DBG_CIPHER) 657 log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n"); 658 return (1); 659 } 660 /* G != PaI */ 661 if (!mpi_cmp_ui (sk->E.G.z, 0)) 662 { 663 if (DBG_CIPHER) 664 log_debug ("Bad check: 'G' cannot be Point at Infinity!\n"); 665 return (1); 666 } 667 668 point_init (&Q); 669 ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a); 670 _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx); 671 if (mpi_cmp_ui (Q.z, 0)) 672 { 673 if (DBG_CIPHER) 674 log_debug ("check_secret_key: E is not a curve of order n\n"); 675 point_free (&Q); 676 _gcry_mpi_ec_free (ctx); 677 return 1; 678 } 679 /* pubkey cannot be PaI */ 680 if (!mpi_cmp_ui (sk->Q.z, 0)) 681 { 682 if (DBG_CIPHER) 683 log_debug ("Bad check: Q can not be a Point at Infinity!\n"); 684 _gcry_mpi_ec_free (ctx); 685 return (1); 686 } 687 /* pubkey = [d]G over E */ 688 _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx); 689 if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z)) 690 { 691 if (DBG_CIPHER) 692 log_debug 693 ("Bad check: There is NO correspondence between 'd' and 'Q'!\n"); 694 _gcry_mpi_ec_free (ctx); 695 return (1); 696 } 697 _gcry_mpi_ec_free (ctx); 698 point_free (&Q); 699 return 0; 700} 701 702 703/* 704 * Return the signature struct (r,s) from the message hash. The caller 705 * must have allocated R and S. 706 */ 707static gpg_err_code_t 708sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s) 709{ 710 gpg_err_code_t err = 0; 711 gcry_mpi_t k, dr, sum, k_1, x; 712 mpi_point_t I; 713 mpi_ec_t ctx; 714 715 if (DBG_CIPHER) 716 log_mpidump ("ecdsa sign hash ", input ); 717 718 k = NULL; 719 dr = mpi_alloc (0); 720 sum = mpi_alloc (0); 721 k_1 = mpi_alloc (0); 722 x = mpi_alloc (0); 723 point_init (&I); 724 725 mpi_set_ui (s, 0); 726 mpi_set_ui (r, 0); 727 728 ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a); 729 730 while (!mpi_cmp_ui (s, 0)) /* s == 0 */ 731 { 732 while (!mpi_cmp_ui (r, 0)) /* r == 0 */ 733 { 734 /* Note, that we are guaranteed to enter this loop at least 735 once because r has been intialized to 0. We can't use a 736 do_while because we want to keep the value of R even if S 737 has to be recomputed. */ 738 mpi_free (k); 739 k = gen_k (skey->E.n, GCRY_STRONG_RANDOM); 740 _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); 741 if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx)) 742 { 743 if (DBG_CIPHER) 744 log_debug ("ecc sign: Failed to get affine coordinates\n"); 745 err = GPG_ERR_BAD_SIGNATURE; 746 goto leave; 747 } 748 mpi_mod (r, x, skey->E.n); /* r = x mod n */ 749 } 750 mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */ 751 mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n */ 752 mpi_invm (k_1, k, skey->E.n); /* k_1 = k^(-1) mod n */ 753 mpi_mulm (s, k_1, sum, skey->E.n); /* s = k^(-1)*(hash+(d*r)) mod n */ 754 } 755 756 if (DBG_CIPHER) 757 { 758 log_mpidump ("ecdsa sign result r ", r); 759 log_mpidump ("ecdsa sign result s ", s); 760 } 761 762 leave: 763 _gcry_mpi_ec_free (ctx); 764 point_free (&I); 765 mpi_free (x); 766 mpi_free (k_1); 767 mpi_free (sum); 768 mpi_free (dr); 769 mpi_free (k); 770 771 return err; 772} 773 774 775/* 776 * Check if R and S verifies INPUT. 777 */ 778static gpg_err_code_t 779verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s) 780{ 781 gpg_err_code_t err = 0; 782 gcry_mpi_t h, h1, h2, x, y; 783 mpi_point_t Q, Q1, Q2; 784 mpi_ec_t ctx; 785 786 if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) ) 787 return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */ 788 if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) ) 789 return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */ 790 791 h = mpi_alloc (0); 792 h1 = mpi_alloc (0); 793 h2 = mpi_alloc (0); 794 x = mpi_alloc (0); 795 y = mpi_alloc (0); 796 point_init (&Q); 797 point_init (&Q1); 798 point_init (&Q2); 799 800 ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a); 801 802 /* h = s^(-1) (mod n) */ 803 mpi_invm (h, s, pkey->E.n); 804/* log_mpidump (" h", h); */ 805 /* h1 = hash * s^(-1) (mod n) */ 806 mpi_mulm (h1, input, h, pkey->E.n); 807/* log_mpidump (" h1", h1); */ 808 /* Q1 = [ hash * s^(-1) ]G */ 809 _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx); 810/* log_mpidump ("Q1.x", Q1.x); */ 811/* log_mpidump ("Q1.y", Q1.y); */ 812/* log_mpidump ("Q1.z", Q1.z); */ 813 /* h2 = r * s^(-1) (mod n) */ 814 mpi_mulm (h2, r, h, pkey->E.n); 815/* log_mpidump (" h2", h2); */ 816 /* Q2 = [ r * s^(-1) ]Q */ 817 _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx); 818/* log_mpidump ("Q2.x", Q2.x); */ 819/* log_mpidump ("Q2.y", Q2.y); */ 820/* log_mpidump ("Q2.z", Q2.z); */ 821 /* Q = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */ 822 _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx); 823/* log_mpidump (" Q.x", Q.x); */ 824/* log_mpidump (" Q.y", Q.y); */ 825/* log_mpidump (" Q.z", Q.z); */ 826 827 if (!mpi_cmp_ui (Q.z, 0)) 828 { 829 if (DBG_CIPHER) 830 log_debug ("ecc verify: Rejected\n"); 831 err = GPG_ERR_BAD_SIGNATURE; 832 goto leave; 833 } 834 if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx)) 835 { 836 if (DBG_CIPHER) 837 log_debug ("ecc verify: Failed to get affine coordinates\n"); 838 err = GPG_ERR_BAD_SIGNATURE; 839 goto leave; 840 } 841 mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */ 842 if (mpi_cmp (x, r)) /* x != r */ 843 { 844 if (DBG_CIPHER) 845 { 846 log_mpidump (" x", x); 847 log_mpidump (" y", y); 848 log_mpidump (" r", r); 849 log_mpidump (" s", s); 850 log_debug ("ecc verify: Not verified\n"); 851 } 852 err = GPG_ERR_BAD_SIGNATURE; 853 goto leave; 854 } 855 if (DBG_CIPHER) 856 log_debug ("ecc verify: Accepted\n"); 857 858 leave: 859 _gcry_mpi_ec_free (ctx); 860 point_free (&Q2); 861 point_free (&Q1); 862 point_free (&Q); 863 mpi_free (y); 864 mpi_free (x); 865 mpi_free (h2); 866 mpi_free (h1); 867 mpi_free (h); 868 return err; 869} 870 871 872 873/********************************************* 874 ************** interface ****************** 875 *********************************************/ 876static gcry_mpi_t 877ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p) 878{ 879 gpg_error_t err; 880 int pbytes = (mpi_get_nbits (p)+7)/8; 881 size_t n; 882 unsigned char *buf, *ptr; 883 gcry_mpi_t result; 884 885 buf = gcry_xmalloc ( 1 + 2*pbytes ); 886 *buf = 04; /* Uncompressed point. */ 887 ptr = buf+1; 888 err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x); 889 if (err) 890 log_fatal ("mpi_print failed: %s\n", gpg_strerror (err)); 891 if (n < pbytes) 892 { 893 memmove (ptr+(pbytes-n), ptr, n); 894 memset (ptr, 0, (pbytes-n)); 895 } 896 ptr += pbytes; 897 err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y); 898 if (err) 899 log_fatal ("mpi_print failed: %s\n", gpg_strerror (err)); 900 if (n < pbytes) 901 { 902 memmove (ptr+(pbytes-n), ptr, n); 903 memset (ptr, 0, (pbytes-n)); 904 } 905 906 err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL); 907 if (err) 908 log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err)); 909 gcry_free (buf); 910 911 return result; 912} 913 914 915/* RESULT must have been initialized and is set on success to the 916 point given by VALUE. */ 917static gcry_error_t 918os2ec (mpi_point_t *result, gcry_mpi_t value) 919{ 920 gcry_error_t err; 921 size_t n; 922 unsigned char *buf; 923 gcry_mpi_t x, y; 924 925 n = (mpi_get_nbits (value)+7)/8; 926 buf = gcry_xmalloc (n); 927 err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value); 928 if (err) 929 { 930 gcry_free (buf); 931 return err; 932 } 933 if (n < 1) 934 { 935 gcry_free (buf); 936 return GPG_ERR_INV_OBJ; 937 } 938 if (*buf != 4) 939 { 940 gcry_free (buf); 941 return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression. */ 942 } 943 if ( ((n-1)%2) ) 944 { 945 gcry_free (buf); 946 return GPG_ERR_INV_OBJ; 947 } 948 n = (n-1)/2; 949 err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL); 950 if (err) 951 { 952 gcry_free (buf); 953 return err; 954 } 955 err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL); 956 gcry_free (buf); 957 if (err) 958 { 959 mpi_free (x); 960 return err; 961 } 962 963 mpi_set (result->x, x); 964 mpi_set (result->y, y); 965 mpi_set_ui (result->z, 1); 966 967 mpi_free (x); 968 mpi_free (y); 969 970 return 0; 971} 972 973 974/* Extended version of ecc_generate. */ 975static gcry_err_code_t 976ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue, 977 const gcry_sexp_t genparms, 978 gcry_mpi_t *skey, gcry_mpi_t **retfactors, 979 gcry_sexp_t *r_extrainfo) 980{ 981 gpg_err_code_t ec; 982 ECC_secret_key sk; 983 gcry_mpi_t g_x, g_y, q_x, q_y; 984 char *curve_name = NULL; 985 gcry_sexp_t l1; 986 int transient_key = 0; 987 const char *usedcurve = NULL; 988 989 (void)algo; 990 (void)evalue; 991 992 if (genparms) 993 { 994 /* Parse the optional "curve" parameter. */ 995 l1 = gcry_sexp_find_token (genparms, "curve", 0); 996 if (l1) 997 { 998 curve_name = _gcry_sexp_nth_string (l1, 1); 999 gcry_sexp_release (l1); 1000 if (!curve_name) 1001 return GPG_ERR_INV_OBJ; /* No curve name or value too large. */ 1002 } 1003 1004 /* Parse the optional transient-key flag. */ 1005 l1 = gcry_sexp_find_token (genparms, "transient-key", 0); 1006 if (l1) 1007 { 1008 transient_key = 1; 1009 gcry_sexp_release (l1); 1010 } 1011 } 1012 1013 /* NBITS is required if no curve name has been given. */ 1014 if (!nbits && !curve_name) 1015 return GPG_ERR_NO_OBJ; /* No NBITS parameter. */ 1016 1017 g_x = mpi_new (0); 1018 g_y = mpi_new (0); 1019 q_x = mpi_new (0); 1020 q_y = mpi_new (0); 1021 ec = generate_key (&sk, nbits, curve_name, transient_key, g_x, g_y, q_x, q_y, 1022 &usedcurve); 1023 gcry_free (curve_name); 1024 if (ec) 1025 return ec; 1026 if (usedcurve) /* Fixme: No error return checking. */ 1027 gcry_sexp_build (r_extrainfo, NULL, "(curve %s)", usedcurve); 1028 1029 skey[0] = sk.E.p; 1030 skey[1] = sk.E.a; 1031 skey[2] = sk.E.b; 1032 skey[3] = ec2os (g_x, g_y, sk.E.p); 1033 skey[4] = sk.E.n; 1034 skey[5] = ec2os (q_x, q_y, sk.E.p); 1035 skey[6] = sk.d; 1036 1037 mpi_free (g_x); 1038 mpi_free (g_y); 1039 mpi_free (q_x); 1040 mpi_free (q_y); 1041 1042 point_free (&sk.E.G); 1043 point_free (&sk.Q); 1044 1045 /* Make an empty list of factors. */ 1046 *retfactors = gcry_calloc ( 1, sizeof **retfactors ); 1047 if (!*retfactors) 1048 return gpg_err_code_from_syserror (); /* Fixme: relase mem? */ 1049 1050 if (DBG_CIPHER) 1051 { 1052 log_mpidump ("ecgen result p", skey[0]); 1053 log_mpidump ("ecgen result a", skey[1]); 1054 log_mpidump ("ecgen result b", skey[2]); 1055 log_mpidump ("ecgen result G", skey[3]); 1056 log_mpidump ("ecgen result n", skey[4]); 1057 log_mpidump ("ecgen result Q", skey[5]); 1058 log_mpidump ("ecgen result d", skey[6]); 1059 } 1060 1061 return 0; 1062} 1063 1064 1065static gcry_err_code_t 1066ecc_generate (int algo, unsigned int nbits, unsigned long evalue, 1067 gcry_mpi_t *skey, gcry_mpi_t **retfactors) 1068{ 1069 (void)evalue; 1070 return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL); 1071} 1072 1073 1074/* Return the parameters of the curve NAME in an MPI array. */ 1075static gcry_err_code_t 1076ecc_get_param (const char *name, gcry_mpi_t *pkey) 1077{ 1078 gpg_err_code_t err; 1079 unsigned int nbits; 1080 elliptic_curve_t E; 1081 mpi_ec_t ctx; 1082 gcry_mpi_t g_x, g_y; 1083 1084 err = fill_in_curve (0, name, &E, &nbits); 1085 if (err) 1086 return err; 1087 1088 g_x = mpi_new (0); 1089 g_y = mpi_new (0); 1090 ctx = _gcry_mpi_ec_init (E.p, E.a); 1091 if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx)) 1092 log_fatal ("ecc get param: Failed to get affine coordinates\n"); 1093 _gcry_mpi_ec_free (ctx); 1094 point_free (&E.G); 1095 1096 pkey[0] = E.p; 1097 pkey[1] = E.a; 1098 pkey[2] = E.b; 1099 pkey[3] = ec2os (g_x, g_y, E.p); 1100 pkey[4] = E.n; 1101 pkey[5] = NULL; 1102 1103 mpi_free (g_x); 1104 mpi_free (g_y); 1105 1106 return 0; 1107} 1108 1109 1110/* Return the parameters of the curve NAME as an S-expression. */ 1111static gcry_sexp_t 1112ecc_get_param_sexp (const char *name) 1113{ 1114 gcry_mpi_t pkey[6]; 1115 gcry_sexp_t result; 1116 int i; 1117 1118 if (ecc_get_param (name, pkey)) 1119 return NULL; 1120 1121 if (gcry_sexp_build (&result, NULL, 1122 "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)))", 1123 pkey[0], pkey[1], pkey[2], pkey[3], pkey[4])) 1124 result = NULL; 1125 1126 for (i=0; pkey[i]; i++) 1127 gcry_mpi_release (pkey[i]); 1128 1129 return result; 1130} 1131 1132 1133/* Return the name matching the parameters in PKEY. */ 1134static const char * 1135ecc_get_curve (gcry_mpi_t *pkey, int iterator, unsigned int *r_nbits) 1136{ 1137 gpg_err_code_t err; 1138 elliptic_curve_t E; 1139 int idx; 1140 gcry_mpi_t tmp; 1141 const char *result = NULL; 1142 1143 if (r_nbits) 1144 *r_nbits = 0; 1145 1146 if (!pkey) 1147 { 1148 idx = iterator; 1149 if (idx >= 0 && idx < DIM (domain_parms)) 1150 { 1151 result = domain_parms[idx].desc; 1152 if (r_nbits) 1153 *r_nbits = domain_parms[idx].nbits; 1154 } 1155 return result; 1156 } 1157 1158 if (!pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4]) 1159 return NULL; 1160 1161 E.p = pkey[0]; 1162 E.a = pkey[1]; 1163 E.b = pkey[2]; 1164 point_init (&E.G); 1165 err = os2ec (&E.G, pkey[3]); 1166 if (err) 1167 { 1168 point_free (&E.G); 1169 return NULL; 1170 } 1171 E.n = pkey[4]; 1172 1173 for (idx = 0; domain_parms[idx].desc; idx++) 1174 { 1175 tmp = scanval (domain_parms[idx].p); 1176 if (!mpi_cmp (tmp, E.p)) 1177 { 1178 mpi_free (tmp); 1179 tmp = scanval (domain_parms[idx].a); 1180 if (!mpi_cmp (tmp, E.a)) 1181 { 1182 mpi_free (tmp); 1183 tmp = scanval (domain_parms[idx].b); 1184 if (!mpi_cmp (tmp, E.b)) 1185 { 1186 mpi_free (tmp); 1187 tmp = scanval (domain_parms[idx].n); 1188 if (!mpi_cmp (tmp, E.n)) 1189 { 1190 mpi_free (tmp); 1191 tmp = scanval (domain_parms[idx].g_x); 1192 if (!mpi_cmp (tmp, E.G.x)) 1193 { 1194 mpi_free (tmp); 1195 tmp = scanval (domain_parms[idx].g_y); 1196 if (!mpi_cmp (tmp, E.G.y)) 1197 { 1198 result = domain_parms[idx].desc; 1199 if (r_nbits) 1200 *r_nbits = domain_parms[idx].nbits; 1201 break; 1202 } 1203 } 1204 } 1205 } 1206 } 1207 } 1208 mpi_free (tmp); 1209 } 1210 1211 point_free (&E.G); 1212 1213 return result; 1214} 1215 1216 1217static gcry_err_code_t 1218ecc_check_secret_key (int algo, gcry_mpi_t *skey) 1219{ 1220 gpg_err_code_t err; 1221 ECC_secret_key sk; 1222 1223 (void)algo; 1224 1225 /* FIXME: This check looks a bit fishy: Now long is the array? */ 1226 if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5] 1227 || !skey[6]) 1228 return GPG_ERR_BAD_MPI; 1229 1230 sk.E.p = skey[0]; 1231 sk.E.a = skey[1]; 1232 sk.E.b = skey[2]; 1233 point_init (&sk.E.G); 1234 err = os2ec (&sk.E.G, skey[3]); 1235 if (err) 1236 { 1237 point_free (&sk.E.G); 1238 return err; 1239 } 1240 sk.E.n = skey[4]; 1241 point_init (&sk.Q); 1242 err = os2ec (&sk.Q, skey[5]); 1243 if (err) 1244 { 1245 point_free (&sk.E.G); 1246 point_free (&sk.Q); 1247 return err; 1248 } 1249 1250 sk.d = skey[6]; 1251 1252 if (check_secret_key (&sk)) 1253 { 1254 point_free (&sk.E.G); 1255 point_free (&sk.Q); 1256 return GPG_ERR_BAD_SECKEY; 1257 } 1258 point_free (&sk.E.G); 1259 point_free (&sk.Q); 1260 return 0; 1261} 1262 1263 1264static gcry_err_code_t 1265ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey) 1266{ 1267 gpg_err_code_t err; 1268 ECC_secret_key sk; 1269 1270 (void)algo; 1271 1272 if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] 1273 || !skey[5] || !skey[6] ) 1274 return GPG_ERR_BAD_MPI; 1275 1276 sk.E.p = skey[0]; 1277 sk.E.a = skey[1]; 1278 sk.E.b = skey[2]; 1279 point_init (&sk.E.G); 1280 err = os2ec (&sk.E.G, skey[3]); 1281 if (err) 1282 { 1283 point_free (&sk.E.G); 1284 return err; 1285 } 1286 sk.E.n = skey[4]; 1287 point_init (&sk.Q); 1288 err = os2ec (&sk.Q, skey[5]); 1289 if (err) 1290 { 1291 point_free (&sk.E.G); 1292 point_free (&sk.Q); 1293 return err; 1294 } 1295 sk.d = skey[6]; 1296 1297 resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p)); 1298 resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p)); 1299 err = sign (data, &sk, resarr[0], resarr[1]); 1300 if (err) 1301 { 1302 mpi_free (resarr[0]); 1303 mpi_free (resarr[1]); 1304 resarr[0] = NULL; /* Mark array as released. */ 1305 } 1306 point_free (&sk.E.G); 1307 point_free (&sk.Q); 1308 return err; 1309} 1310 1311 1312static gcry_err_code_t 1313ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey, 1314 int (*cmp)(void *, gcry_mpi_t), void *opaquev) 1315{ 1316 gpg_err_code_t err; 1317 ECC_public_key pk; 1318 1319 (void)algo; 1320 (void)cmp; 1321 (void)opaquev; 1322 1323 if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2] 1324 || !pkey[3] || !pkey[4] || !pkey[5] ) 1325 return GPG_ERR_BAD_MPI; 1326 1327 pk.E.p = pkey[0]; 1328 pk.E.a = pkey[1]; 1329 pk.E.b = pkey[2]; 1330 point_init (&pk.E.G); 1331 err = os2ec (&pk.E.G, pkey[3]); 1332 if (err) 1333 { 1334 point_free (&pk.E.G); 1335 return err; 1336 } 1337 pk.E.n = pkey[4]; 1338 point_init (&pk.Q); 1339 err = os2ec (&pk.Q, pkey[5]); 1340 if (err) 1341 { 1342 point_free (&pk.E.G); 1343 point_free (&pk.Q); 1344 return err; 1345 } 1346 1347 err = verify (hash, &pk, data[0], data[1]); 1348 1349 point_free (&pk.E.G); 1350 point_free (&pk.Q); 1351 return err; 1352} 1353 1354 1355/* ecdh raw is classic 2-round DH protocol published in 1976. 1356 * 1357 * Overview of ecc_encrypt_raw and ecc_decrypt_raw. 1358 * 1359 * As with any PK operation, encrypt version uses a public key and 1360 * decrypt -- private. 1361 * 1362 * Symbols used below: 1363 * G - field generator point 1364 * d - private long-term scalar 1365 * dG - public long-term key 1366 * k - ephemeral scalar 1367 * kG - ephemeral public key 1368 * dkG - shared secret 1369 * 1370 * ecc_encrypt_raw description: 1371 * input: 1372 * data[0] : private scalar (k) 1373 * output: 1374 * result[0] : shared point (kdG) 1375 * result[1] : generated ephemeral public key (kG) 1376 * 1377 * ecc_decrypt_raw description: 1378 * input: 1379 * data[0] : a point kG (ephemeral public key) 1380 * output: 1381 * result[0] : shared point (kdG) 1382 */ 1383static gcry_err_code_t 1384ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k, 1385 gcry_mpi_t *pkey, int flags) 1386{ 1387 ECC_public_key pk; 1388 mpi_ec_t ctx; 1389 gcry_mpi_t result[2]; 1390 int err; 1391 1392 (void)algo; 1393 (void)flags; 1394 1395 if (!k 1396 || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] || !pkey[5]) 1397 return GPG_ERR_BAD_MPI; 1398 1399 pk.E.p = pkey[0]; 1400 pk.E.a = pkey[1]; 1401 pk.E.b = pkey[2]; 1402 point_init (&pk.E.G); 1403 err = os2ec (&pk.E.G, pkey[3]); 1404 if (err) 1405 { 1406 point_free (&pk.E.G); 1407 return err; 1408 } 1409 pk.E.n = pkey[4]; 1410 point_init (&pk.Q); 1411 err = os2ec (&pk.Q, pkey[5]); 1412 if (err) 1413 { 1414 point_free (&pk.E.G); 1415 point_free (&pk.Q); 1416 return err; 1417 } 1418 1419 ctx = _gcry_mpi_ec_init (pk.E.p, pk.E.a); 1420 1421 /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */ 1422 { 1423 mpi_point_t R; /* Result that we return. */ 1424 gcry_mpi_t x, y; 1425 1426 x = mpi_new (0); 1427 y = mpi_new (0); 1428 1429 point_init (&R); 1430 1431 /* R = kQ <=> R = kdG */ 1432 _gcry_mpi_ec_mul_point (&R, k, &pk.Q, ctx); 1433 1434 if (_gcry_mpi_ec_get_affine (x, y, &R, ctx)) 1435 log_fatal ("ecdh: Failed to get affine coordinates for kdG\n"); 1436 1437 result[0] = ec2os (x, y, pk.E.p); 1438 1439 /* R = kG */ 1440 _gcry_mpi_ec_mul_point (&R, k, &pk.E.G, ctx); 1441 1442 if (_gcry_mpi_ec_get_affine (x, y, &R, ctx)) 1443 log_fatal ("ecdh: Failed to get affine coordinates for kG\n"); 1444 1445 result[1] = ec2os (x, y, pk.E.p); 1446 1447 mpi_free (x); 1448 mpi_free (y); 1449 1450 point_free (&R); 1451 } 1452 1453 _gcry_mpi_ec_free (ctx); 1454 point_free (&pk.E.G); 1455 point_free (&pk.Q); 1456 1457 if (!result[0] || !result[1]) 1458 { 1459 mpi_free (result[0]); 1460 mpi_free (result[1]); 1461 return GPG_ERR_ENOMEM; 1462 } 1463 1464 /* Success. */ 1465 resarr[0] = result[0]; 1466 resarr[1] = result[1]; 1467 1468 return 0; 1469} 1470 1471/* input: 1472 * data[0] : a point kG (ephemeral public key) 1473 * output: 1474 * resaddr[0] : shared point kdG 1475 * 1476 * see ecc_encrypt_raw for details. 1477 */ 1478static gcry_err_code_t 1479ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data, 1480 gcry_mpi_t *skey, int flags) 1481{ 1482 ECC_secret_key sk; 1483 mpi_point_t R; /* Result that we return. */ 1484 mpi_point_t kG; 1485 mpi_ec_t ctx; 1486 gcry_mpi_t r; 1487 int err; 1488 1489 (void)algo; 1490 (void)flags; 1491 1492 *result = NULL; 1493 1494 if (!data || !data[0] 1495 || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] 1496 || !skey[5] || !skey[6] ) 1497 return GPG_ERR_BAD_MPI; 1498 1499 point_init (&kG); 1500 err = os2ec (&kG, data[0]); 1501 if (err) 1502 { 1503 point_free (&kG); 1504 return err; 1505 } 1506 1507 1508 sk.E.p = skey[0]; 1509 sk.E.a = skey[1]; 1510 sk.E.b = skey[2]; 1511 point_init (&sk.E.G); 1512 err = os2ec (&sk.E.G, skey[3]); 1513 if (err) 1514 { 1515 point_free (&kG); 1516 point_free (&sk.E.G); 1517 return err; 1518 } 1519 sk.E.n = skey[4]; 1520 point_init (&sk.Q); 1521 err = os2ec (&sk.Q, skey[5]); 1522 if (err) 1523 { 1524 point_free (&kG); 1525 point_free (&sk.E.G); 1526 point_free (&sk.Q); 1527 return err; 1528 } 1529 sk.d = skey[6]; 1530 1531 ctx = _gcry_mpi_ec_init (sk.E.p, sk.E.a); 1532 1533 /* R = dkG */ 1534 point_init (&R); 1535 _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx); 1536 1537 point_free (&kG); 1538 1539 /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so: */ 1540 { 1541 gcry_mpi_t x, y; 1542 1543 x = mpi_new (0); 1544 y = mpi_new (0); 1545 1546 if (_gcry_mpi_ec_get_affine (x, y, &R, ctx)) 1547 log_fatal ("ecdh: Failed to get affine coordinates\n"); 1548 1549 r = ec2os (x, y, sk.E.p); 1550 mpi_free (x); 1551 mpi_free (y); 1552 } 1553 1554 point_free (&R); 1555 _gcry_mpi_ec_free (ctx); 1556 point_free (&kG); 1557 point_free (&sk.E.G); 1558 point_free (&sk.Q); 1559 1560 if (!r) 1561 return GPG_ERR_ENOMEM; 1562 1563 /* Success. */ 1564 1565 *result = r; 1566 1567 return 0; 1568} 1569 1570 1571static unsigned int 1572ecc_get_nbits (int algo, gcry_mpi_t *pkey) 1573{ 1574 (void)algo; 1575 1576 return mpi_get_nbits (pkey[0]); 1577} 1578 1579 1580/* See rsa.c for a description of this function. */ 1581static gpg_err_code_t 1582compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam) 1583{ 1584#define N_COMPONENTS 6 1585 static const char names[N_COMPONENTS+1] = "pabgnq"; 1586 gpg_err_code_t ec = 0; 1587 gcry_sexp_t l1; 1588 gcry_mpi_t values[N_COMPONENTS]; 1589 int idx; 1590 1591 /* Clear the values for easier error cleanup. */ 1592 for (idx=0; idx < N_COMPONENTS; idx++) 1593 values[idx] = NULL; 1594 1595 /* Fill values with all provided parameters. */ 1596 for (idx=0; idx < N_COMPONENTS; idx++) 1597 { 1598 l1 = gcry_sexp_find_token (keyparam, names+idx, 1); 1599 if (l1) 1600 { 1601 values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG); 1602 gcry_sexp_release (l1); 1603 if (!values[idx]) 1604 { 1605 ec = GPG_ERR_INV_OBJ; 1606 goto leave; 1607 } 1608 } 1609 } 1610 1611 /* Check whether a curve parameter is available and use that to fill 1612 in missing values. */ 1613 l1 = gcry_sexp_find_token (keyparam, "curve", 5); 1614 if (l1) 1615 { 1616 char *curve; 1617 gcry_mpi_t tmpvalues[N_COMPONENTS]; 1618 1619 for (idx = 0; idx < N_COMPONENTS; idx++) 1620 tmpvalues[idx] = NULL; 1621 1622 curve = _gcry_sexp_nth_string (l1, 1); 1623 gcry_sexp_release (l1); 1624 if (!curve) 1625 { 1626 ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */ 1627 goto leave; 1628 } 1629 ec = ecc_get_param (curve, tmpvalues); 1630 gcry_free (curve); 1631 if (ec) 1632 goto leave; 1633 1634 for (idx = 0; idx < N_COMPONENTS; idx++) 1635 { 1636 if (!values[idx]) 1637 values[idx] = tmpvalues[idx]; 1638 else 1639 mpi_free (tmpvalues[idx]); 1640 } 1641 } 1642 1643 /* Check that all parameters are known and normalize all MPIs (that 1644 should not be required but we use an internal function later and 1645 thus we better make 100% sure that they are normalized). */ 1646 for (idx = 0; idx < N_COMPONENTS; idx++) 1647 if (!values[idx]) 1648 { 1649 ec = GPG_ERR_NO_OBJ; 1650 goto leave; 1651 } 1652 else 1653 _gcry_mpi_normalize (values[idx]); 1654 1655 /* Hash them all. */ 1656 for (idx = 0; idx < N_COMPONENTS; idx++) 1657 { 1658 char buf[30]; 1659 unsigned char *rawmpi; 1660 unsigned int rawmpilen; 1661 1662 rawmpi = _gcry_mpi_get_buffer (values[idx], &rawmpilen, NULL); 1663 if (!rawmpi) 1664 { 1665 ec = gpg_err_code_from_syserror (); 1666 goto leave; 1667 } 1668 snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen); 1669 gcry_md_write (md, buf, strlen (buf)); 1670 gcry_md_write (md, rawmpi, rawmpilen); 1671 gcry_md_write (md, ")", 1); 1672 gcry_free (rawmpi); 1673 } 1674 1675 leave: 1676 for (idx = 0; idx < N_COMPONENTS; idx++) 1677 _gcry_mpi_release (values[idx]); 1678 1679 return ec; 1680#undef N_COMPONENTS 1681} 1682 1683 1684 1685 1686 1687/* 1688 Self-test section. 1689 */ 1690 1691 1692static gpg_err_code_t 1693selftests_ecdsa (selftest_report_func_t report) 1694{ 1695 const char *what; 1696 const char *errtxt; 1697 1698 what = "low-level"; 1699 errtxt = NULL; /*selftest ();*/ 1700 if (errtxt) 1701 goto failed; 1702 1703 /* FIXME: need more tests. */ 1704 1705 return 0; /* Succeeded. */ 1706 1707 failed: 1708 if (report) 1709 report ("pubkey", GCRY_PK_ECDSA, what, errtxt); 1710 return GPG_ERR_SELFTEST_FAILED; 1711} 1712 1713 1714/* Run a full self-test for ALGO and return 0 on success. */ 1715static gpg_err_code_t 1716run_selftests (int algo, int extended, selftest_report_func_t report) 1717{ 1718 gpg_err_code_t ec; 1719 1720 (void)extended; 1721 1722 switch (algo) 1723 { 1724 case GCRY_PK_ECDSA: 1725 ec = selftests_ecdsa (report); 1726 break; 1727 default: 1728 ec = GPG_ERR_PUBKEY_ALGO; 1729 break; 1730 1731 } 1732 return ec; 1733} 1734 1735 1736 1737 1738static const char *ecdsa_names[] = 1739 { 1740 "ecdsa", 1741 "ecc", 1742 NULL, 1743 }; 1744static const char *ecdh_names[] = 1745 { 1746 "ecdh", 1747 "ecc", 1748 NULL, 1749 }; 1750 1751gcry_pk_spec_t _gcry_pubkey_spec_ecdsa = 1752 { 1753 "ECDSA", ecdsa_names, 1754 "pabgnq", "pabgnqd", "", "rs", "pabgnq", 1755 GCRY_PK_USAGE_SIGN, 1756 ecc_generate, 1757 ecc_check_secret_key, 1758 NULL, 1759 NULL, 1760 ecc_sign, 1761 ecc_verify, 1762 ecc_get_nbits 1763 }; 1764 1765gcry_pk_spec_t _gcry_pubkey_spec_ecdh = 1766 { 1767 "ECDH", ecdh_names, 1768 "pabgnq", "pabgnqd", "se", "", "pabgnq", 1769 GCRY_PK_USAGE_ENCR, 1770 ecc_generate, 1771 ecc_check_secret_key, 1772 ecc_encrypt_raw, 1773 ecc_decrypt_raw, 1774 NULL, 1775 NULL, 1776 ecc_get_nbits 1777 }; 1778 1779 1780pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa = 1781 { 1782 run_selftests, 1783 ecc_generate_ext, 1784 compute_keygrip, 1785 ecc_get_param, 1786 ecc_get_curve, 1787 ecc_get_param_sexp 1788 }; 1789