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 int rc = 1; 646 mpi_point_t Q; 647 gcry_mpi_t y_2, y2; 648 mpi_ec_t ctx = NULL; 649 650 point_init (&Q); 651 652 /* ?primarity test of 'p' */ 653 /* (...) //!! */ 654 /* G in E(F_p) */ 655 y_2 = gen_y_2 (sk->E.G.x, &sk->E); /* y^2=x^3+a*x+b */ 656 y2 = mpi_alloc (0); 657 mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p); /* y^2=y*y */ 658 if (mpi_cmp (y_2, y2)) 659 { 660 if (DBG_CIPHER) 661 log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n"); 662 goto leave; 663 } 664 /* G != PaI */ 665 if (!mpi_cmp_ui (sk->E.G.z, 0)) 666 { 667 if (DBG_CIPHER) 668 log_debug ("Bad check: 'G' cannot be Point at Infinity!\n"); 669 goto leave; 670 } 671 672 ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a); 673 674 _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx); 675 if (mpi_cmp_ui (Q.z, 0)) 676 { 677 if (DBG_CIPHER) 678 log_debug ("check_secret_key: E is not a curve of order n\n"); 679 goto leave; 680 } 681 /* pubkey cannot be PaI */ 682 if (!mpi_cmp_ui (sk->Q.z, 0)) 683 { 684 if (DBG_CIPHER) 685 log_debug ("Bad check: Q can not be a Point at Infinity!\n"); 686 goto leave; 687 } 688 /* pubkey = [d]G over E */ 689 _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx); 690 if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z)) 691 { 692 if (DBG_CIPHER) 693 log_debug 694 ("Bad check: There is NO correspondence between 'd' and 'Q'!\n"); 695 goto leave; 696 } 697 rc = 0; /* Okay. */ 698 699 leave: 700 _gcry_mpi_ec_free (ctx); 701 mpi_free (y2); 702 mpi_free (y_2); 703 point_free (&Q); 704 return rc; 705} 706 707 708/* 709 * Return the signature struct (r,s) from the message hash. The caller 710 * must have allocated R and S. 711 */ 712static gpg_err_code_t 713sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s) 714{ 715 gpg_err_code_t err = 0; 716 gcry_mpi_t k, dr, sum, k_1, x; 717 mpi_point_t I; 718 mpi_ec_t ctx; 719 720 if (DBG_CIPHER) 721 log_mpidump ("ecdsa sign hash ", input ); 722 723 k = NULL; 724 dr = mpi_alloc (0); 725 sum = mpi_alloc (0); 726 k_1 = mpi_alloc (0); 727 x = mpi_alloc (0); 728 point_init (&I); 729 730 mpi_set_ui (s, 0); 731 mpi_set_ui (r, 0); 732 733 ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a); 734 735 while (!mpi_cmp_ui (s, 0)) /* s == 0 */ 736 { 737 while (!mpi_cmp_ui (r, 0)) /* r == 0 */ 738 { 739 /* Note, that we are guaranteed to enter this loop at least 740 once because r has been intialized to 0. We can't use a 741 do_while because we want to keep the value of R even if S 742 has to be recomputed. */ 743 mpi_free (k); 744 k = gen_k (skey->E.n, GCRY_STRONG_RANDOM); 745 _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); 746 if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx)) 747 { 748 if (DBG_CIPHER) 749 log_debug ("ecc sign: Failed to get affine coordinates\n"); 750 err = GPG_ERR_BAD_SIGNATURE; 751 goto leave; 752 } 753 mpi_mod (r, x, skey->E.n); /* r = x mod n */ 754 } 755 mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */ 756 mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n */ 757 mpi_invm (k_1, k, skey->E.n); /* k_1 = k^(-1) mod n */ 758 mpi_mulm (s, k_1, sum, skey->E.n); /* s = k^(-1)*(hash+(d*r)) mod n */ 759 } 760 761 if (DBG_CIPHER) 762 { 763 log_mpidump ("ecdsa sign result r ", r); 764 log_mpidump ("ecdsa sign result s ", s); 765 } 766 767 leave: 768 _gcry_mpi_ec_free (ctx); 769 point_free (&I); 770 mpi_free (x); 771 mpi_free (k_1); 772 mpi_free (sum); 773 mpi_free (dr); 774 mpi_free (k); 775 776 return err; 777} 778 779 780/* 781 * Check if R and S verifies INPUT. 782 */ 783static gpg_err_code_t 784verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s) 785{ 786 gpg_err_code_t err = 0; 787 gcry_mpi_t h, h1, h2, x, y; 788 mpi_point_t Q, Q1, Q2; 789 mpi_ec_t ctx; 790 791 if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) ) 792 return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */ 793 if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) ) 794 return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */ 795 796 h = mpi_alloc (0); 797 h1 = mpi_alloc (0); 798 h2 = mpi_alloc (0); 799 x = mpi_alloc (0); 800 y = mpi_alloc (0); 801 point_init (&Q); 802 point_init (&Q1); 803 point_init (&Q2); 804 805 ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a); 806 807 /* h = s^(-1) (mod n) */ 808 mpi_invm (h, s, pkey->E.n); 809/* log_mpidump (" h", h); */ 810 /* h1 = hash * s^(-1) (mod n) */ 811 mpi_mulm (h1, input, h, pkey->E.n); 812/* log_mpidump (" h1", h1); */ 813 /* Q1 = [ hash * s^(-1) ]G */ 814 _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx); 815/* log_mpidump ("Q1.x", Q1.x); */ 816/* log_mpidump ("Q1.y", Q1.y); */ 817/* log_mpidump ("Q1.z", Q1.z); */ 818 /* h2 = r * s^(-1) (mod n) */ 819 mpi_mulm (h2, r, h, pkey->E.n); 820/* log_mpidump (" h2", h2); */ 821 /* Q2 = [ r * s^(-1) ]Q */ 822 _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx); 823/* log_mpidump ("Q2.x", Q2.x); */ 824/* log_mpidump ("Q2.y", Q2.y); */ 825/* log_mpidump ("Q2.z", Q2.z); */ 826 /* Q = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */ 827 _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx); 828/* log_mpidump (" Q.x", Q.x); */ 829/* log_mpidump (" Q.y", Q.y); */ 830/* log_mpidump (" Q.z", Q.z); */ 831 832 if (!mpi_cmp_ui (Q.z, 0)) 833 { 834 if (DBG_CIPHER) 835 log_debug ("ecc verify: Rejected\n"); 836 err = GPG_ERR_BAD_SIGNATURE; 837 goto leave; 838 } 839 if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx)) 840 { 841 if (DBG_CIPHER) 842 log_debug ("ecc verify: Failed to get affine coordinates\n"); 843 err = GPG_ERR_BAD_SIGNATURE; 844 goto leave; 845 } 846 mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */ 847 if (mpi_cmp (x, r)) /* x != r */ 848 { 849 if (DBG_CIPHER) 850 { 851 log_mpidump (" x", x); 852 log_mpidump (" y", y); 853 log_mpidump (" r", r); 854 log_mpidump (" s", s); 855 log_debug ("ecc verify: Not verified\n"); 856 } 857 err = GPG_ERR_BAD_SIGNATURE; 858 goto leave; 859 } 860 if (DBG_CIPHER) 861 log_debug ("ecc verify: Accepted\n"); 862 863 leave: 864 _gcry_mpi_ec_free (ctx); 865 point_free (&Q2); 866 point_free (&Q1); 867 point_free (&Q); 868 mpi_free (y); 869 mpi_free (x); 870 mpi_free (h2); 871 mpi_free (h1); 872 mpi_free (h); 873 return err; 874} 875 876 877 878/********************************************* 879 ************** interface ****************** 880 *********************************************/ 881static gcry_mpi_t 882ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p) 883{ 884 gpg_error_t err; 885 int pbytes = (mpi_get_nbits (p)+7)/8; 886 size_t n; 887 unsigned char *buf, *ptr; 888 gcry_mpi_t result; 889 890 buf = gcry_xmalloc ( 1 + 2*pbytes ); 891 *buf = 04; /* Uncompressed point. */ 892 ptr = buf+1; 893 err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x); 894 if (err) 895 log_fatal ("mpi_print failed: %s\n", gpg_strerror (err)); 896 if (n < pbytes) 897 { 898 memmove (ptr+(pbytes-n), ptr, n); 899 memset (ptr, 0, (pbytes-n)); 900 } 901 ptr += pbytes; 902 err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y); 903 if (err) 904 log_fatal ("mpi_print failed: %s\n", gpg_strerror (err)); 905 if (n < pbytes) 906 { 907 memmove (ptr+(pbytes-n), ptr, n); 908 memset (ptr, 0, (pbytes-n)); 909 } 910 911 err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL); 912 if (err) 913 log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err)); 914 gcry_free (buf); 915 916 return result; 917} 918 919 920/* RESULT must have been initialized and is set on success to the 921 point given by VALUE. */ 922static gcry_error_t 923os2ec (mpi_point_t *result, gcry_mpi_t value) 924{ 925 gcry_error_t err; 926 size_t n; 927 unsigned char *buf; 928 gcry_mpi_t x, y; 929 930 n = (mpi_get_nbits (value)+7)/8; 931 buf = gcry_xmalloc (n); 932 err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value); 933 if (err) 934 { 935 gcry_free (buf); 936 return err; 937 } 938 if (n < 1) 939 { 940 gcry_free (buf); 941 return GPG_ERR_INV_OBJ; 942 } 943 if (*buf != 4) 944 { 945 gcry_free (buf); 946 return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression. */ 947 } 948 if ( ((n-1)%2) ) 949 { 950 gcry_free (buf); 951 return GPG_ERR_INV_OBJ; 952 } 953 n = (n-1)/2; 954 err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL); 955 if (err) 956 { 957 gcry_free (buf); 958 return err; 959 } 960 err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL); 961 gcry_free (buf); 962 if (err) 963 { 964 mpi_free (x); 965 return err; 966 } 967 968 mpi_set (result->x, x); 969 mpi_set (result->y, y); 970 mpi_set_ui (result->z, 1); 971 972 mpi_free (x); 973 mpi_free (y); 974 975 return 0; 976} 977 978 979/* Extended version of ecc_generate. */ 980static gcry_err_code_t 981ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue, 982 const gcry_sexp_t genparms, 983 gcry_mpi_t *skey, gcry_mpi_t **retfactors, 984 gcry_sexp_t *r_extrainfo) 985{ 986 gpg_err_code_t ec; 987 ECC_secret_key sk; 988 gcry_mpi_t g_x, g_y, q_x, q_y; 989 char *curve_name = NULL; 990 gcry_sexp_t l1; 991 int transient_key = 0; 992 const char *usedcurve = NULL; 993 994 (void)algo; 995 (void)evalue; 996 997 if (genparms) 998 { 999 /* Parse the optional "curve" parameter. */ 1000 l1 = gcry_sexp_find_token (genparms, "curve", 0); 1001 if (l1) 1002 { 1003 curve_name = _gcry_sexp_nth_string (l1, 1); 1004 gcry_sexp_release (l1); 1005 if (!curve_name) 1006 return GPG_ERR_INV_OBJ; /* No curve name or value too large. */ 1007 } 1008 1009 /* Parse the optional transient-key flag. */ 1010 l1 = gcry_sexp_find_token (genparms, "transient-key", 0); 1011 if (l1) 1012 { 1013 transient_key = 1; 1014 gcry_sexp_release (l1); 1015 } 1016 } 1017 1018 /* NBITS is required if no curve name has been given. */ 1019 if (!nbits && !curve_name) 1020 return GPG_ERR_NO_OBJ; /* No NBITS parameter. */ 1021 1022 g_x = mpi_new (0); 1023 g_y = mpi_new (0); 1024 q_x = mpi_new (0); 1025 q_y = mpi_new (0); 1026 ec = generate_key (&sk, nbits, curve_name, transient_key, g_x, g_y, q_x, q_y, 1027 &usedcurve); 1028 gcry_free (curve_name); 1029 if (ec) 1030 return ec; 1031 if (usedcurve) /* Fixme: No error return checking. */ 1032 gcry_sexp_build (r_extrainfo, NULL, "(curve %s)", usedcurve); 1033 1034 skey[0] = sk.E.p; 1035 skey[1] = sk.E.a; 1036 skey[2] = sk.E.b; 1037 skey[3] = ec2os (g_x, g_y, sk.E.p); 1038 skey[4] = sk.E.n; 1039 skey[5] = ec2os (q_x, q_y, sk.E.p); 1040 skey[6] = sk.d; 1041 1042 mpi_free (g_x); 1043 mpi_free (g_y); 1044 mpi_free (q_x); 1045 mpi_free (q_y); 1046 1047 point_free (&sk.E.G); 1048 point_free (&sk.Q); 1049 1050 /* Make an empty list of factors. */ 1051 *retfactors = gcry_calloc ( 1, sizeof **retfactors ); 1052 if (!*retfactors) 1053 return gpg_err_code_from_syserror (); /* Fixme: relase mem? */ 1054 1055 if (DBG_CIPHER) 1056 { 1057 log_mpidump ("ecgen result p", skey[0]); 1058 log_mpidump ("ecgen result a", skey[1]); 1059 log_mpidump ("ecgen result b", skey[2]); 1060 log_mpidump ("ecgen result G", skey[3]); 1061 log_mpidump ("ecgen result n", skey[4]); 1062 log_mpidump ("ecgen result Q", skey[5]); 1063 log_mpidump ("ecgen result d", skey[6]); 1064 } 1065 1066 return 0; 1067} 1068 1069 1070static gcry_err_code_t 1071ecc_generate (int algo, unsigned int nbits, unsigned long evalue, 1072 gcry_mpi_t *skey, gcry_mpi_t **retfactors) 1073{ 1074 (void)evalue; 1075 return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL); 1076} 1077 1078 1079/* Return the parameters of the curve NAME in an MPI array. */ 1080static gcry_err_code_t 1081ecc_get_param (const char *name, gcry_mpi_t *pkey) 1082{ 1083 gpg_err_code_t err; 1084 unsigned int nbits; 1085 elliptic_curve_t E; 1086 mpi_ec_t ctx; 1087 gcry_mpi_t g_x, g_y; 1088 1089 err = fill_in_curve (0, name, &E, &nbits); 1090 if (err) 1091 return err; 1092 1093 g_x = mpi_new (0); 1094 g_y = mpi_new (0); 1095 ctx = _gcry_mpi_ec_init (E.p, E.a); 1096 if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx)) 1097 log_fatal ("ecc get param: Failed to get affine coordinates\n"); 1098 _gcry_mpi_ec_free (ctx); 1099 point_free (&E.G); 1100 1101 pkey[0] = E.p; 1102 pkey[1] = E.a; 1103 pkey[2] = E.b; 1104 pkey[3] = ec2os (g_x, g_y, E.p); 1105 pkey[4] = E.n; 1106 pkey[5] = NULL; 1107 1108 mpi_free (g_x); 1109 mpi_free (g_y); 1110 1111 return 0; 1112} 1113 1114 1115/* Return the parameters of the curve NAME as an S-expression. */ 1116static gcry_sexp_t 1117ecc_get_param_sexp (const char *name) 1118{ 1119 gcry_mpi_t pkey[6]; 1120 gcry_sexp_t result; 1121 int i; 1122 1123 if (ecc_get_param (name, pkey)) 1124 return NULL; 1125 1126 if (gcry_sexp_build (&result, NULL, 1127 "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)))", 1128 pkey[0], pkey[1], pkey[2], pkey[3], pkey[4])) 1129 result = NULL; 1130 1131 for (i=0; pkey[i]; i++) 1132 gcry_mpi_release (pkey[i]); 1133 1134 return result; 1135} 1136 1137 1138/* Return the name matching the parameters in PKEY. */ 1139static const char * 1140ecc_get_curve (gcry_mpi_t *pkey, int iterator, unsigned int *r_nbits) 1141{ 1142 gpg_err_code_t err; 1143 elliptic_curve_t E; 1144 int idx; 1145 gcry_mpi_t tmp; 1146 const char *result = NULL; 1147 1148 if (r_nbits) 1149 *r_nbits = 0; 1150 1151 if (!pkey) 1152 { 1153 idx = iterator; 1154 if (idx >= 0 && idx < DIM (domain_parms)) 1155 { 1156 result = domain_parms[idx].desc; 1157 if (r_nbits) 1158 *r_nbits = domain_parms[idx].nbits; 1159 } 1160 return result; 1161 } 1162 1163 if (!pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4]) 1164 return NULL; 1165 1166 E.p = pkey[0]; 1167 E.a = pkey[1]; 1168 E.b = pkey[2]; 1169 point_init (&E.G); 1170 err = os2ec (&E.G, pkey[3]); 1171 if (err) 1172 { 1173 point_free (&E.G); 1174 return NULL; 1175 } 1176 E.n = pkey[4]; 1177 1178 for (idx = 0; domain_parms[idx].desc; idx++) 1179 { 1180 tmp = scanval (domain_parms[idx].p); 1181 if (!mpi_cmp (tmp, E.p)) 1182 { 1183 mpi_free (tmp); 1184 tmp = scanval (domain_parms[idx].a); 1185 if (!mpi_cmp (tmp, E.a)) 1186 { 1187 mpi_free (tmp); 1188 tmp = scanval (domain_parms[idx].b); 1189 if (!mpi_cmp (tmp, E.b)) 1190 { 1191 mpi_free (tmp); 1192 tmp = scanval (domain_parms[idx].n); 1193 if (!mpi_cmp (tmp, E.n)) 1194 { 1195 mpi_free (tmp); 1196 tmp = scanval (domain_parms[idx].g_x); 1197 if (!mpi_cmp (tmp, E.G.x)) 1198 { 1199 mpi_free (tmp); 1200 tmp = scanval (domain_parms[idx].g_y); 1201 if (!mpi_cmp (tmp, E.G.y)) 1202 { 1203 result = domain_parms[idx].desc; 1204 if (r_nbits) 1205 *r_nbits = domain_parms[idx].nbits; 1206 break; 1207 } 1208 } 1209 } 1210 } 1211 } 1212 } 1213 mpi_free (tmp); 1214 } 1215 1216 point_free (&E.G); 1217 1218 return result; 1219} 1220 1221 1222static gcry_err_code_t 1223ecc_check_secret_key (int algo, gcry_mpi_t *skey) 1224{ 1225 gpg_err_code_t err; 1226 ECC_secret_key sk; 1227 1228 (void)algo; 1229 1230 /* FIXME: This check looks a bit fishy: Now long is the array? */ 1231 if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5] 1232 || !skey[6]) 1233 return GPG_ERR_BAD_MPI; 1234 1235 sk.E.p = skey[0]; 1236 sk.E.a = skey[1]; 1237 sk.E.b = skey[2]; 1238 point_init (&sk.E.G); 1239 err = os2ec (&sk.E.G, skey[3]); 1240 if (err) 1241 { 1242 point_free (&sk.E.G); 1243 return err; 1244 } 1245 sk.E.n = skey[4]; 1246 point_init (&sk.Q); 1247 err = os2ec (&sk.Q, skey[5]); 1248 if (err) 1249 { 1250 point_free (&sk.E.G); 1251 point_free (&sk.Q); 1252 return err; 1253 } 1254 1255 sk.d = skey[6]; 1256 1257 if (check_secret_key (&sk)) 1258 { 1259 point_free (&sk.E.G); 1260 point_free (&sk.Q); 1261 return GPG_ERR_BAD_SECKEY; 1262 } 1263 point_free (&sk.E.G); 1264 point_free (&sk.Q); 1265 return 0; 1266} 1267 1268 1269static gcry_err_code_t 1270ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey) 1271{ 1272 gpg_err_code_t err; 1273 ECC_secret_key sk; 1274 1275 (void)algo; 1276 1277 if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] 1278 || !skey[5] || !skey[6] ) 1279 return GPG_ERR_BAD_MPI; 1280 1281 sk.E.p = skey[0]; 1282 sk.E.a = skey[1]; 1283 sk.E.b = skey[2]; 1284 point_init (&sk.E.G); 1285 err = os2ec (&sk.E.G, skey[3]); 1286 if (err) 1287 { 1288 point_free (&sk.E.G); 1289 return err; 1290 } 1291 sk.E.n = skey[4]; 1292 point_init (&sk.Q); 1293 err = os2ec (&sk.Q, skey[5]); 1294 if (err) 1295 { 1296 point_free (&sk.E.G); 1297 point_free (&sk.Q); 1298 return err; 1299 } 1300 sk.d = skey[6]; 1301 1302 resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p)); 1303 resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p)); 1304 err = sign (data, &sk, resarr[0], resarr[1]); 1305 if (err) 1306 { 1307 mpi_free (resarr[0]); 1308 mpi_free (resarr[1]); 1309 resarr[0] = NULL; /* Mark array as released. */ 1310 } 1311 point_free (&sk.E.G); 1312 point_free (&sk.Q); 1313 return err; 1314} 1315 1316 1317static gcry_err_code_t 1318ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey, 1319 int (*cmp)(void *, gcry_mpi_t), void *opaquev) 1320{ 1321 gpg_err_code_t err; 1322 ECC_public_key pk; 1323 1324 (void)algo; 1325 (void)cmp; 1326 (void)opaquev; 1327 1328 if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2] 1329 || !pkey[3] || !pkey[4] || !pkey[5] ) 1330 return GPG_ERR_BAD_MPI; 1331 1332 pk.E.p = pkey[0]; 1333 pk.E.a = pkey[1]; 1334 pk.E.b = pkey[2]; 1335 point_init (&pk.E.G); 1336 err = os2ec (&pk.E.G, pkey[3]); 1337 if (err) 1338 { 1339 point_free (&pk.E.G); 1340 return err; 1341 } 1342 pk.E.n = pkey[4]; 1343 point_init (&pk.Q); 1344 err = os2ec (&pk.Q, pkey[5]); 1345 if (err) 1346 { 1347 point_free (&pk.E.G); 1348 point_free (&pk.Q); 1349 return err; 1350 } 1351 1352 err = verify (hash, &pk, data[0], data[1]); 1353 1354 point_free (&pk.E.G); 1355 point_free (&pk.Q); 1356 return err; 1357} 1358 1359 1360/* ecdh raw is classic 2-round DH protocol published in 1976. 1361 * 1362 * Overview of ecc_encrypt_raw and ecc_decrypt_raw. 1363 * 1364 * As with any PK operation, encrypt version uses a public key and 1365 * decrypt -- private. 1366 * 1367 * Symbols used below: 1368 * G - field generator point 1369 * d - private long-term scalar 1370 * dG - public long-term key 1371 * k - ephemeral scalar 1372 * kG - ephemeral public key 1373 * dkG - shared secret 1374 * 1375 * ecc_encrypt_raw description: 1376 * input: 1377 * data[0] : private scalar (k) 1378 * output: 1379 * result[0] : shared point (kdG) 1380 * result[1] : generated ephemeral public key (kG) 1381 * 1382 * ecc_decrypt_raw description: 1383 * input: 1384 * data[0] : a point kG (ephemeral public key) 1385 * output: 1386 * result[0] : shared point (kdG) 1387 */ 1388static gcry_err_code_t 1389ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k, 1390 gcry_mpi_t *pkey, int flags) 1391{ 1392 ECC_public_key pk; 1393 mpi_ec_t ctx; 1394 gcry_mpi_t result[2]; 1395 int err; 1396 1397 (void)algo; 1398 (void)flags; 1399 1400 if (!k 1401 || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] || !pkey[5]) 1402 return GPG_ERR_BAD_MPI; 1403 1404 pk.E.p = pkey[0]; 1405 pk.E.a = pkey[1]; 1406 pk.E.b = pkey[2]; 1407 point_init (&pk.E.G); 1408 err = os2ec (&pk.E.G, pkey[3]); 1409 if (err) 1410 { 1411 point_free (&pk.E.G); 1412 return err; 1413 } 1414 pk.E.n = pkey[4]; 1415 point_init (&pk.Q); 1416 err = os2ec (&pk.Q, pkey[5]); 1417 if (err) 1418 { 1419 point_free (&pk.E.G); 1420 point_free (&pk.Q); 1421 return err; 1422 } 1423 1424 ctx = _gcry_mpi_ec_init (pk.E.p, pk.E.a); 1425 1426 /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */ 1427 { 1428 mpi_point_t R; /* Result that we return. */ 1429 gcry_mpi_t x, y; 1430 1431 x = mpi_new (0); 1432 y = mpi_new (0); 1433 1434 point_init (&R); 1435 1436 /* R = kQ <=> R = kdG */ 1437 _gcry_mpi_ec_mul_point (&R, k, &pk.Q, ctx); 1438 1439 if (_gcry_mpi_ec_get_affine (x, y, &R, ctx)) 1440 log_fatal ("ecdh: Failed to get affine coordinates for kdG\n"); 1441 1442 result[0] = ec2os (x, y, pk.E.p); 1443 1444 /* R = kG */ 1445 _gcry_mpi_ec_mul_point (&R, k, &pk.E.G, ctx); 1446 1447 if (_gcry_mpi_ec_get_affine (x, y, &R, ctx)) 1448 log_fatal ("ecdh: Failed to get affine coordinates for kG\n"); 1449 1450 result[1] = ec2os (x, y, pk.E.p); 1451 1452 mpi_free (x); 1453 mpi_free (y); 1454 1455 point_free (&R); 1456 } 1457 1458 _gcry_mpi_ec_free (ctx); 1459 point_free (&pk.E.G); 1460 point_free (&pk.Q); 1461 1462 if (!result[0] || !result[1]) 1463 { 1464 mpi_free (result[0]); 1465 mpi_free (result[1]); 1466 return GPG_ERR_ENOMEM; 1467 } 1468 1469 /* Success. */ 1470 resarr[0] = result[0]; 1471 resarr[1] = result[1]; 1472 1473 return 0; 1474} 1475 1476/* input: 1477 * data[0] : a point kG (ephemeral public key) 1478 * output: 1479 * resaddr[0] : shared point kdG 1480 * 1481 * see ecc_encrypt_raw for details. 1482 */ 1483static gcry_err_code_t 1484ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data, 1485 gcry_mpi_t *skey, int flags) 1486{ 1487 ECC_secret_key sk; 1488 mpi_point_t R; /* Result that we return. */ 1489 mpi_point_t kG; 1490 mpi_ec_t ctx; 1491 gcry_mpi_t r; 1492 int err; 1493 1494 (void)algo; 1495 (void)flags; 1496 1497 *result = NULL; 1498 1499 if (!data || !data[0] 1500 || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] 1501 || !skey[5] || !skey[6] ) 1502 return GPG_ERR_BAD_MPI; 1503 1504 point_init (&kG); 1505 err = os2ec (&kG, data[0]); 1506 if (err) 1507 { 1508 point_free (&kG); 1509 return err; 1510 } 1511 1512 1513 sk.E.p = skey[0]; 1514 sk.E.a = skey[1]; 1515 sk.E.b = skey[2]; 1516 point_init (&sk.E.G); 1517 err = os2ec (&sk.E.G, skey[3]); 1518 if (err) 1519 { 1520 point_free (&kG); 1521 point_free (&sk.E.G); 1522 return err; 1523 } 1524 sk.E.n = skey[4]; 1525 point_init (&sk.Q); 1526 err = os2ec (&sk.Q, skey[5]); 1527 if (err) 1528 { 1529 point_free (&kG); 1530 point_free (&sk.E.G); 1531 point_free (&sk.Q); 1532 return err; 1533 } 1534 sk.d = skey[6]; 1535 1536 ctx = _gcry_mpi_ec_init (sk.E.p, sk.E.a); 1537 1538 /* R = dkG */ 1539 point_init (&R); 1540 _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx); 1541 1542 point_free (&kG); 1543 1544 /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so: */ 1545 { 1546 gcry_mpi_t x, y; 1547 1548 x = mpi_new (0); 1549 y = mpi_new (0); 1550 1551 if (_gcry_mpi_ec_get_affine (x, y, &R, ctx)) 1552 log_fatal ("ecdh: Failed to get affine coordinates\n"); 1553 1554 r = ec2os (x, y, sk.E.p); 1555 mpi_free (x); 1556 mpi_free (y); 1557 } 1558 1559 point_free (&R); 1560 _gcry_mpi_ec_free (ctx); 1561 point_free (&kG); 1562 point_free (&sk.E.G); 1563 point_free (&sk.Q); 1564 1565 if (!r) 1566 return GPG_ERR_ENOMEM; 1567 1568 /* Success. */ 1569 1570 *result = r; 1571 1572 return 0; 1573} 1574 1575 1576static unsigned int 1577ecc_get_nbits (int algo, gcry_mpi_t *pkey) 1578{ 1579 (void)algo; 1580 1581 return mpi_get_nbits (pkey[0]); 1582} 1583 1584 1585/* See rsa.c for a description of this function. */ 1586static gpg_err_code_t 1587compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam) 1588{ 1589#define N_COMPONENTS 6 1590 static const char names[N_COMPONENTS+1] = "pabgnq"; 1591 gpg_err_code_t ec = 0; 1592 gcry_sexp_t l1; 1593 gcry_mpi_t values[N_COMPONENTS]; 1594 int idx; 1595 1596 /* Clear the values for easier error cleanup. */ 1597 for (idx=0; idx < N_COMPONENTS; idx++) 1598 values[idx] = NULL; 1599 1600 /* Fill values with all provided parameters. */ 1601 for (idx=0; idx < N_COMPONENTS; idx++) 1602 { 1603 l1 = gcry_sexp_find_token (keyparam, names+idx, 1); 1604 if (l1) 1605 { 1606 values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG); 1607 gcry_sexp_release (l1); 1608 if (!values[idx]) 1609 { 1610 ec = GPG_ERR_INV_OBJ; 1611 goto leave; 1612 } 1613 } 1614 } 1615 1616 /* Check whether a curve parameter is available and use that to fill 1617 in missing values. */ 1618 l1 = gcry_sexp_find_token (keyparam, "curve", 5); 1619 if (l1) 1620 { 1621 char *curve; 1622 gcry_mpi_t tmpvalues[N_COMPONENTS]; 1623 1624 for (idx = 0; idx < N_COMPONENTS; idx++) 1625 tmpvalues[idx] = NULL; 1626 1627 curve = _gcry_sexp_nth_string (l1, 1); 1628 gcry_sexp_release (l1); 1629 if (!curve) 1630 { 1631 ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */ 1632 goto leave; 1633 } 1634 ec = ecc_get_param (curve, tmpvalues); 1635 gcry_free (curve); 1636 if (ec) 1637 goto leave; 1638 1639 for (idx = 0; idx < N_COMPONENTS; idx++) 1640 { 1641 if (!values[idx]) 1642 values[idx] = tmpvalues[idx]; 1643 else 1644 mpi_free (tmpvalues[idx]); 1645 } 1646 } 1647 1648 /* Check that all parameters are known and normalize all MPIs (that 1649 should not be required but we use an internal function later and 1650 thus we better make 100% sure that they are normalized). */ 1651 for (idx = 0; idx < N_COMPONENTS; idx++) 1652 if (!values[idx]) 1653 { 1654 ec = GPG_ERR_NO_OBJ; 1655 goto leave; 1656 } 1657 else 1658 _gcry_mpi_normalize (values[idx]); 1659 1660 /* Hash them all. */ 1661 for (idx = 0; idx < N_COMPONENTS; idx++) 1662 { 1663 char buf[30]; 1664 unsigned char *rawmpi; 1665 unsigned int rawmpilen; 1666 1667 rawmpi = _gcry_mpi_get_buffer (values[idx], &rawmpilen, NULL); 1668 if (!rawmpi) 1669 { 1670 ec = gpg_err_code_from_syserror (); 1671 goto leave; 1672 } 1673 snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen); 1674 gcry_md_write (md, buf, strlen (buf)); 1675 gcry_md_write (md, rawmpi, rawmpilen); 1676 gcry_md_write (md, ")", 1); 1677 gcry_free (rawmpi); 1678 } 1679 1680 leave: 1681 for (idx = 0; idx < N_COMPONENTS; idx++) 1682 _gcry_mpi_release (values[idx]); 1683 1684 return ec; 1685#undef N_COMPONENTS 1686} 1687 1688 1689 1690 1691 1692/* 1693 Self-test section. 1694 */ 1695 1696 1697static gpg_err_code_t 1698selftests_ecdsa (selftest_report_func_t report) 1699{ 1700 const char *what; 1701 const char *errtxt; 1702 1703 what = "low-level"; 1704 errtxt = NULL; /*selftest ();*/ 1705 if (errtxt) 1706 goto failed; 1707 1708 /* FIXME: need more tests. */ 1709 1710 return 0; /* Succeeded. */ 1711 1712 failed: 1713 if (report) 1714 report ("pubkey", GCRY_PK_ECDSA, what, errtxt); 1715 return GPG_ERR_SELFTEST_FAILED; 1716} 1717 1718 1719/* Run a full self-test for ALGO and return 0 on success. */ 1720static gpg_err_code_t 1721run_selftests (int algo, int extended, selftest_report_func_t report) 1722{ 1723 gpg_err_code_t ec; 1724 1725 (void)extended; 1726 1727 switch (algo) 1728 { 1729 case GCRY_PK_ECDSA: 1730 ec = selftests_ecdsa (report); 1731 break; 1732 default: 1733 ec = GPG_ERR_PUBKEY_ALGO; 1734 break; 1735 1736 } 1737 return ec; 1738} 1739 1740 1741 1742 1743static const char *ecdsa_names[] = 1744 { 1745 "ecdsa", 1746 "ecc", 1747 NULL, 1748 }; 1749static const char *ecdh_names[] = 1750 { 1751 "ecdh", 1752 "ecc", 1753 NULL, 1754 }; 1755 1756gcry_pk_spec_t _gcry_pubkey_spec_ecdsa = 1757 { 1758 "ECDSA", ecdsa_names, 1759 "pabgnq", "pabgnqd", "", "rs", "pabgnq", 1760 GCRY_PK_USAGE_SIGN, 1761 ecc_generate, 1762 ecc_check_secret_key, 1763 NULL, 1764 NULL, 1765 ecc_sign, 1766 ecc_verify, 1767 ecc_get_nbits 1768 }; 1769 1770gcry_pk_spec_t _gcry_pubkey_spec_ecdh = 1771 { 1772 "ECDH", ecdh_names, 1773 "pabgnq", "pabgnqd", "se", "", "pabgnq", 1774 GCRY_PK_USAGE_ENCR, 1775 ecc_generate, 1776 ecc_check_secret_key, 1777 ecc_encrypt_raw, 1778 ecc_decrypt_raw, 1779 NULL, 1780 NULL, 1781 ecc_get_nbits 1782 }; 1783 1784 1785pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa = 1786 { 1787 run_selftests, 1788 ecc_generate_ext, 1789 compute_keygrip, 1790 ecc_get_param, 1791 ecc_get_curve, 1792 ecc_get_param_sexp 1793 }; 1794