1
/* ecc.c - Elliptic Curve Cryptography
2
Copyright (C) 2007, 2008 Free Software Foundation, Inc.
4
This file is part of Libgcrypt.
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.
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.
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,
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:
26
Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>,
27
Ramiro Moreno Chiral <ramiro at eup.udl.es>
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. */
41
- If we support point compression we need to decide how to compute
42
the keygrip - it should not change due to compression.
44
- In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a
45
special case in mpi_powm or check whether mpi_mulm is faster.
47
- Decide whether we should hide the mpi_point_t definition.
49
- Support more than just ECDSA.
63
/* Definition of a curve. */
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. */
77
mpi_point_t Q; /* Q = [d]G */
88
/* This tables defines aliases for curve names. */
91
const char *name; /* Our name. */
92
const char *other; /* Other name. */
95
{ "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID */
96
{ "NIST P-192", "prime192v1" }, /* X9.62 name. */
97
{ "NIST P-192", "secp192r1" }, /* SECP name. */
99
{ "NIST P-224", "secp224r1" },
100
{ "NIST P-224", "1.3.132.0.33" }, /* SECP OID. */
102
{ "NIST P-256", "1.2.840.10045.3.1.7" }, /* From NIST SP 800-78-1. */
103
{ "NIST P-256", "prime256v1" },
104
{ "NIST P-256", "secp256r1" },
106
{ "NIST P-384", "secp384r1" },
107
{ "NIST P-384", "1.3.132.0.34" },
109
{ "NIST P-521", "secp521r1" },
110
{ "NIST P-521", "1.3.132.0.35" },
112
{ "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.1" },
113
{ "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.3" },
114
{ "brainpoolP224r1", "1.3.36.3.3.2.8.1.1.5" },
115
{ "brainpoolP256r1", "1.3.36.3.3.2.8.1.1.7" },
116
{ "brainpoolP320r1", "1.3.36.3.3.2.8.1.1.9" },
117
{ "brainpoolP384r1", "1.3.36.3.3.2.8.1.1.11"},
118
{ "brainpoolP512r1", "1.3.36.3.3.2.8.1.1.13"},
125
/* This static table defines all available curves. */
128
const char *desc; /* Description of the curve. */
129
unsigned int nbits; /* Number of bits. */
130
unsigned int fips:1; /* True if this is a FIPS140-2 approved curve. */
131
const char *p; /* Order of the prime field. */
132
const char *a, *b; /* The coefficients. */
133
const char *n; /* The order of the base point. */
134
const char *g_x, *g_y; /* Base point. */
138
"NIST P-192", 192, 1,
139
"0xfffffffffffffffffffffffffffffffeffffffffffffffff",
140
"0xfffffffffffffffffffffffffffffffefffffffffffffffc",
141
"0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
142
"0xffffffffffffffffffffffff99def836146bc9b1b4d22831",
144
"0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
145
"0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
148
"NIST P-224", 224, 1,
149
"0xffffffffffffffffffffffffffffffff000000000000000000000001",
150
"0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
151
"0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
152
"0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" ,
154
"0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
155
"0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"
158
"NIST P-256", 256, 1,
159
"0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
160
"0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
161
"0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
162
"0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
164
"0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
165
"0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
168
"NIST P-384", 384, 1,
169
"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
170
"ffffffff0000000000000000ffffffff",
171
"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
172
"ffffffff0000000000000000fffffffc",
173
"0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a"
174
"c656398d8a2ed19d2a85c8edd3ec2aef",
175
"0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf"
176
"581a0db248b0a77aecec196accc52973",
178
"0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a38"
179
"5502f25dbf55296c3a545e3872760ab7",
180
"0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0"
181
"0a60b1ce1d7e819d7a431d7c90ea0e5f"
184
"NIST P-521", 521, 1,
185
"0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
186
"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
187
"0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
188
"fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc",
189
"0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef10"
190
"9e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00",
191
"0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
192
"ffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409",
194
"0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3d"
195
"baa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66",
196
"0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e6"
197
"62c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650"
200
{ "brainpoolP160r1", 160, 0,
201
"0xe95e4a5f737059dc60dfc7ad95b3d8139515620f",
202
"0x340e7be2a280eb74e2be61bada745d97e8f7c300",
203
"0x1e589a8595423412134faa2dbdec95c8d8675e58",
204
"0xe95e4a5f737059dc60df5991d45029409e60fc09",
205
"0xbed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3",
206
"0x1667cb477a1a8ec338f94741669c976316da6321"
209
{ "brainpoolP192r1", 192, 0,
210
"0xc302f41d932a36cda7a3463093d18db78fce476de1a86297",
211
"0x6a91174076b1e0e19c39c031fe8685c1cae040e5c69a28ef",
212
"0x469a28ef7c28cca3dc721d044f4496bcca7ef4146fbf25c9",
213
"0xc302f41d932a36cda7a3462f9e9e916b5be8f1029ac4acc1",
214
"0xc0a0647eaab6a48753b033c56cb0f0900a2f5c4853375fd6",
215
"0x14b690866abd5bb88b5f4828c1490002e6773fa2fa299b8f"
218
{ "brainpoolP224r1", 224, 0,
219
"0xd7c134aa264366862a18302575d1d787b09f075797da89f57ec8c0ff",
220
"0x68a5e62ca9ce6c1c299803a6c1530b514e182ad8b0042a59cad29f43",
221
"0x2580f63ccfe44138870713b1a92369e33e2135d266dbb372386c400b",
222
"0xd7c134aa264366862a18302575d0fb98d116bc4b6ddebca3a5a7939f",
223
"0x0d9029ad2c7e5cf4340823b2a87dc68c9e4ce3174c1e6efdee12c07d",
224
"0x58aa56f772c0726f24c6b89e4ecdac24354b9e99caa3f6d3761402cd"
227
{ "brainpoolP256r1", 256, 0,
228
"0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377",
229
"0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9",
230
"0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6",
231
"0xa9fb57dba1eea9bc3e660a909d838d718c397aa3b561a6f7901e0e82974856a7",
232
"0x8bd2aeb9cb7e57cb2c4b482ffc81b7afb9de27e1e3bd23c23a4453bd9ace3262",
233
"0x547ef835c3dac4fd97f8461a14611dc9c27745132ded8e545c1d54c72f046997"
236
{ "brainpoolP320r1", 320, 0,
237
"0xd35e472036bc4fb7e13c785ed201e065f98fcfa6f6f40def4f92b9ec7893ec28"
239
"0x3ee30b568fbab0f883ccebd46d3f3bb8a2a73513f5eb79da66190eb085ffa9f4"
241
"0x520883949dfdbc42d3ad198640688a6fe13f41349554b49acc31dccd88453981"
243
"0xd35e472036bc4fb7e13c785ed201e065f98fcfa5b68f12a32d482ec7ee8658e9"
245
"0x43bd7e9afb53d8b85289bcc48ee5bfe6f20137d10a087eb6e7871e2a10a599c7"
247
"0x14fdd05545ec1cc8ab4093247f77275e0743ffed117182eaa9c77877aaac6ac7"
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"
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"
281
{ NULL, 0, 0, NULL, NULL, NULL, NULL }
285
/* Registered progress function and its callback value. */
286
static void (*progress_cb) (void *, const char*, int, int, int);
287
static void *progress_cb_data;
290
#define point_init(a) _gcry_mpi_ec_point_init ((a))
291
#define point_free(a) _gcry_mpi_ec_point_free ((a))
295
/* Local prototypes. */
296
static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level);
297
static void test_keys (ECC_secret_key * sk, unsigned int nbits);
298
static int check_secret_key (ECC_secret_key * sk);
299
static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey,
300
gcry_mpi_t r, gcry_mpi_t s);
301
static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey,
302
gcry_mpi_t r, gcry_mpi_t s);
305
static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
311
_gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
316
progress_cb_data = cb_data;
320
/* progress (int c) */
322
/* if (progress_cb) */
323
/* progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
329
/* Set the value from S into D. */
331
point_set (mpi_point_t *d, mpi_point_t *s)
333
mpi_set (d->x, s->x);
334
mpi_set (d->y, s->y);
335
mpi_set (d->z, s->z);
340
* Release a curve object.
343
curve_free (elliptic_curve_t *E)
345
mpi_free (E->p); E->p = NULL;
346
mpi_free (E->a); E->a = NULL;
347
mpi_free (E->b); E->b = NULL;
349
mpi_free (E->n); E->n = NULL;
354
* Return a copy of a curve object.
356
static elliptic_curve_t
357
curve_copy (elliptic_curve_t E)
361
R.p = mpi_copy (E.p);
362
R.a = mpi_copy (E.a);
363
R.b = mpi_copy (E.b);
365
point_set (&R.G, &E.G);
366
R.n = mpi_copy (E.n);
373
/* Helper to scan a hex string. */
375
scanval (const char *string)
380
err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
382
log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
391
* Solve the right side of the equation that defines a curve.
394
gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
396
gcry_mpi_t three, x_3, axb, y;
398
three = mpi_alloc_set_ui (3);
403
mpi_powm (x_3, x, three, base->p);
404
mpi_mulm (axb, base->a, x, base->p);
405
mpi_addm (axb, axb, base->b, base->p);
406
mpi_addm (y, x_3, axb, base->p);
411
return y; /* The quadratic value of the coordinate if it exist. */
418
/* Generate a random secret scalar k with an order of p
420
At the beginning this was identical to the code is in elgamal.c.
421
Later imporved by mmr. Further simplified by wk. */
423
gen_k (gcry_mpi_t p, int security_level)
428
nbits = mpi_get_nbits (p);
429
k = mpi_snew (nbits);
431
log_debug ("choosing a random k of %u bits\n", nbits);
433
gcry_mpi_randomize (k, nbits, security_level);
435
mpi_mod (k, k, p); /* k = k mod p */
441
* Generate the crypto system setup.
442
* As of now the fix NIST recommended values are used.
443
* The subgroup generator point is in another function: gen_big_point.
445
static gpg_err_code_t
446
generate_curve (unsigned int nbits, const char *name,
447
elliptic_curve_t *curve, unsigned int *r_nbits)
453
/* First check nor native curves. */
454
for (idx = 0; domain_parms[idx].desc; idx++)
455
if (!strcmp (name, domain_parms[idx].desc))
457
/* If not found consult the alias table. */
458
if (!domain_parms[idx].desc)
460
for (aliasno = 0; curve_aliases[aliasno].name; aliasno++)
461
if (!strcmp (name, curve_aliases[aliasno].other))
463
if (curve_aliases[aliasno].name)
465
for (idx = 0; domain_parms[idx].desc; idx++)
466
if (!strcmp (curve_aliases[aliasno].name,
467
domain_parms[idx].desc))
474
for (idx = 0; domain_parms[idx].desc; idx++)
475
if (nbits == domain_parms[idx].nbits)
478
if (!domain_parms[idx].desc)
479
return GPG_ERR_INV_VALUE;
481
/* In fips mode we only support NIST curves. Note that it is
482
possible to bypass this check by specifying the curve parameters
484
if (fips_mode () && !domain_parms[idx].fips )
485
return GPG_ERR_NOT_SUPPORTED;
488
*r_nbits = domain_parms[idx].nbits;
489
curve->p = scanval (domain_parms[idx].p);
490
curve->a = scanval (domain_parms[idx].a);
491
curve->b = scanval (domain_parms[idx].b);
492
curve->n = scanval (domain_parms[idx].n);
493
curve->G.x = scanval (domain_parms[idx].g_x);
494
curve->G.y = scanval (domain_parms[idx].g_y);
495
curve->G.z = mpi_alloc_set_ui (1);
502
* First obtain the setup. Over the finite field randomize an scalar
503
* secret value, and calculate the public point.
505
static gpg_err_code_t
506
generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
507
gcry_mpi_t g_x, gcry_mpi_t g_y,
508
gcry_mpi_t q_x, gcry_mpi_t q_y)
516
err = generate_curve (nbits, name, &E, &nbits);
522
log_mpidump ("ecc generation p", E.p);
523
log_mpidump ("ecc generation a", E.a);
524
log_mpidump ("ecc generation b", E.b);
525
log_mpidump ("ecc generation n", E.n);
526
log_mpidump ("ecc generation Gx", E.G.x);
527
log_mpidump ("ecc generation Gy", E.G.y);
528
log_mpidump ("ecc generation Gz", E.G.z);
532
log_debug ("choosing a random x of size %u\n", nbits);
533
d = gen_k (E.n, GCRY_VERY_STRONG_RANDOM);
537
ctx = _gcry_mpi_ec_init (E.p, E.a);
538
_gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx);
540
/* Copy the stuff to the key structures. */
541
sk->E.p = mpi_copy (E.p);
542
sk->E.a = mpi_copy (E.a);
543
sk->E.b = mpi_copy (E.b);
544
point_init (&sk->E.G);
545
point_set (&sk->E.G, &E.G);
546
sk->E.n = mpi_copy (E.n);
548
point_set (&sk->Q, &Q);
549
sk->d = mpi_copy (d);
550
/* We also return copies of G and Q in affine coordinates if
554
if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
555
log_fatal ("ecc generate: Failed to get affine coordinates\n");
559
if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
560
log_fatal ("ecc generate: Failed to get affine coordinates\n");
562
_gcry_mpi_ec_free (ctx);
568
/* Now we can test our keys (this should never fail!). */
569
test_keys (sk, nbits - 64);
576
* To verify correct skey it use a random information.
577
* First, encrypt and decrypt this dummy value,
578
* test if the information is recuperated.
579
* Second, test with the sign and verify functions.
582
test_keys (ECC_secret_key *sk, unsigned int nbits)
585
gcry_mpi_t test = mpi_new (nbits);
587
gcry_mpi_t c = mpi_new (nbits);
588
gcry_mpi_t out = mpi_new (nbits);
589
gcry_mpi_t r = mpi_new (nbits);
590
gcry_mpi_t s = mpi_new (nbits);
593
log_debug ("Testing key.\n");
597
pk.E = curve_copy (sk->E);
599
point_set (&pk.Q, &sk->Q);
601
gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
603
if (sign (test, sk, r, s) )
604
log_fatal ("ECDSA operation: sign failed\n");
606
if (verify (test, &pk, r, s))
608
log_fatal ("ECDSA operation: sign, verify failed\n");
612
log_debug ("ECDSA operation: sign, verify ok.\n");
626
* To check the validity of the value, recalculate the correspondence
627
* between the public value and the secret one.
630
check_secret_key (ECC_secret_key * sk)
633
gcry_mpi_t y_2, y2 = mpi_alloc (0);
636
/* ?primarity test of 'p' */
639
y_2 = gen_y_2 (sk->E.G.x, &sk->E); /* y^2=x^3+a*x+b */
640
mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p); /* y^2=y*y */
641
if (mpi_cmp (y_2, y2))
644
log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
648
if (!mpi_cmp_ui (sk->E.G.z, 0))
651
log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
656
ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
657
_gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
658
if (mpi_cmp_ui (Q.z, 0))
661
log_debug ("check_secret_key: E is not a curve of order n\n");
663
_gcry_mpi_ec_free (ctx);
666
/* pubkey cannot be PaI */
667
if (!mpi_cmp_ui (sk->Q.z, 0))
670
log_debug ("Bad check: Q can not be a Point at Infinity!\n");
671
_gcry_mpi_ec_free (ctx);
674
/* pubkey = [d]G over E */
675
_gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
676
if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z))
680
("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
681
_gcry_mpi_ec_free (ctx);
684
_gcry_mpi_ec_free (ctx);
691
* Return the signature struct (r,s) from the message hash. The caller
692
* must have allocated R and S.
694
static gpg_err_code_t
695
sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
697
gpg_err_code_t err = 0;
698
gcry_mpi_t k, dr, sum, k_1, x;
712
ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
714
while (!mpi_cmp_ui (s, 0)) /* s == 0 */
716
while (!mpi_cmp_ui (r, 0)) /* r == 0 */
718
/* Note, that we are guaranteed to enter this loop at least
719
once because r has been intialized to 0. We can't use a
720
do_while because we want to keep the value of R even if S
721
has to be recomputed. */
723
k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
724
_gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
725
if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
728
log_debug ("ecc sign: Failed to get affine coordinates\n");
729
err = GPG_ERR_BAD_SIGNATURE;
732
mpi_mod (r, x, skey->E.n); /* r = x mod n */
734
mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */
735
mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n */
736
mpi_invm (k_1, k, skey->E.n); /* k_1 = k^(-1) mod n */
737
mpi_mulm (s, k_1, sum, skey->E.n); /* s = k^(-1)*(hash+(d*r)) mod n */
741
_gcry_mpi_ec_free (ctx);
753
* Check if R and S verifies INPUT.
755
static gpg_err_code_t
756
verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
758
gpg_err_code_t err = 0;
759
gcry_mpi_t h, h1, h2, x, y;
760
mpi_point_t Q, Q1, Q2;
763
if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
764
return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */
765
if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
766
return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */
777
ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
779
/* h = s^(-1) (mod n) */
780
mpi_invm (h, s, pkey->E.n);
781
/* log_mpidump (" h", h); */
782
/* h1 = hash * s^(-1) (mod n) */
783
mpi_mulm (h1, input, h, pkey->E.n);
784
/* log_mpidump (" h1", h1); */
785
/* Q1 = [ hash * s^(-1) ]G */
786
_gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
787
/* log_mpidump ("Q1.x", Q1.x); */
788
/* log_mpidump ("Q1.y", Q1.y); */
789
/* log_mpidump ("Q1.z", Q1.z); */
790
/* h2 = r * s^(-1) (mod n) */
791
mpi_mulm (h2, r, h, pkey->E.n);
792
/* log_mpidump (" h2", h2); */
793
/* Q2 = [ r * s^(-1) ]Q */
794
_gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
795
/* log_mpidump ("Q2.x", Q2.x); */
796
/* log_mpidump ("Q2.y", Q2.y); */
797
/* log_mpidump ("Q2.z", Q2.z); */
798
/* Q = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
799
_gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
800
/* log_mpidump (" Q.x", Q.x); */
801
/* log_mpidump (" Q.y", Q.y); */
802
/* log_mpidump (" Q.z", Q.z); */
804
if (!mpi_cmp_ui (Q.z, 0))
807
log_debug ("ecc verify: Rejected\n");
808
err = GPG_ERR_BAD_SIGNATURE;
811
if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
814
log_debug ("ecc verify: Failed to get affine coordinates\n");
815
err = GPG_ERR_BAD_SIGNATURE;
818
mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
819
if (mpi_cmp (x, r)) /* x != r */
823
log_mpidump (" x", x);
824
log_mpidump (" y", y);
825
log_mpidump (" r", r);
826
log_mpidump (" s", s);
827
log_debug ("ecc verify: Not verified\n");
829
err = GPG_ERR_BAD_SIGNATURE;
833
log_debug ("ecc verify: Accepted\n");
836
_gcry_mpi_ec_free (ctx);
850
/*********************************************
851
************** interface ******************
852
*********************************************/
854
ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
857
int pbytes = (mpi_get_nbits (p)+7)/8;
859
unsigned char *buf, *ptr;
862
buf = gcry_xmalloc ( 1 + 2*pbytes );
863
*buf = 04; /* Uncompressed point. */
865
err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
867
log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
870
memmove (ptr+(pbytes-n), ptr, n);
871
memset (ptr, 0, (pbytes-n));
874
err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
876
log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
879
memmove (ptr+(pbytes-n), ptr, n);
880
memset (ptr, 0, (pbytes-n));
883
err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
885
log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
894
/* RESULT must have been initialized and is set on success to the
895
point given by VALUE. */
897
os2ec (mpi_point_t *result, gcry_mpi_t value)
904
n = (mpi_get_nbits (value)+7)/8;
905
buf = gcry_xmalloc (n);
906
err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value);
915
return GPG_ERR_INV_OBJ;
920
return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression. */
925
return GPG_ERR_INV_OBJ;
928
err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
934
err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
942
mpi_set (result->x, x);
943
mpi_set (result->y, y);
944
mpi_set_ui (result->z, 1);
953
/* Extended version of ecc_generate. */
954
static gcry_err_code_t
955
ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
956
const gcry_sexp_t genparms,
957
gcry_mpi_t *skey, gcry_mpi_t **retfactors,
958
gcry_sexp_t *r_extrainfo)
962
gcry_mpi_t g_x, g_y, q_x, q_y;
963
char *curve_name = NULL;
972
/* Parse the optional "curve" parameter. */
973
l1 = gcry_sexp_find_token (genparms, "curve", 0);
976
curve_name = _gcry_sexp_nth_string (l1, 1);
977
gcry_sexp_release (l1);
979
return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
983
/* NBITS is required if no curve name has been given. */
984
if (!nbits && !curve_name)
985
return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
991
ec = generate_key (&sk, nbits, curve_name, g_x, g_y, q_x, q_y);
992
gcry_free (curve_name);
999
/* The function ec2os releases g_x and g_y. */
1000
skey[3] = ec2os (g_x, g_y, sk.E.p);
1002
/* The function ec2os releases g_x and g_y. */
1003
skey[5] = ec2os (q_x, q_y, sk.E.p);
1006
point_free (&sk.E.G);
1009
/* Make an empty list of factors. */
1010
*retfactors = gcry_calloc ( 1, sizeof **retfactors );
1012
return gpg_err_code_from_syserror ();
1018
static gcry_err_code_t
1019
ecc_generate (int algo, unsigned int nbits, unsigned long evalue,
1020
gcry_mpi_t *skey, gcry_mpi_t **retfactors)
1023
return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
1027
/* Return the parameters of the curve NAME. */
1028
static gcry_err_code_t
1029
ecc_get_param (const char *name, gcry_mpi_t *pkey)
1035
gcry_mpi_t g_x, g_y;
1037
err = generate_curve (0, name, &E, &nbits);
1043
ctx = _gcry_mpi_ec_init (E.p, E.a);
1044
if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx))
1045
log_fatal ("ecc get param: Failed to get affine coordinates\n");
1046
_gcry_mpi_ec_free (ctx);
1052
pkey[3] = ec2os (g_x, g_y, E.p);
1060
static gcry_err_code_t
1061
ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1068
if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1069
|| !skey[6] || !skey[7] || !skey[8] || !skey[9] || !skey[10])
1070
return GPG_ERR_BAD_MPI;
1075
point_init (&sk.E.G);
1076
err = os2ec (&sk.E.G, skey[3]);
1079
point_free (&sk.E.G);
1084
err = os2ec (&sk.Q, skey[5]);
1087
point_free (&sk.E.G);
1094
if (check_secret_key (&sk))
1096
point_free (&sk.E.G);
1098
return GPG_ERR_BAD_SECKEY;
1100
point_free (&sk.E.G);
1106
static gcry_err_code_t
1107
ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
1114
if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1115
|| !skey[5] || !skey[6] )
1116
return GPG_ERR_BAD_MPI;
1121
point_init (&sk.E.G);
1122
err = os2ec (&sk.E.G, skey[3]);
1125
point_free (&sk.E.G);
1130
err = os2ec (&sk.Q, skey[5]);
1133
point_free (&sk.E.G);
1139
resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1140
resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1141
err = sign (data, &sk, resarr[0], resarr[1]);
1144
mpi_free (resarr[0]);
1145
mpi_free (resarr[1]);
1146
resarr[0] = NULL; /* Mark array as released. */
1148
point_free (&sk.E.G);
1153
static gcry_err_code_t
1154
ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1155
int (*cmp)(void *, gcry_mpi_t), void *opaquev)
1164
if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1165
|| !pkey[3] || !pkey[4] || !pkey[5] )
1166
return GPG_ERR_BAD_MPI;
1171
point_init (&pk.E.G);
1172
err = os2ec (&pk.E.G, pkey[3]);
1175
point_free (&pk.E.G);
1180
err = os2ec (&pk.Q, pkey[5]);
1183
point_free (&pk.E.G);
1188
err = verify (hash, &pk, data[0], data[1]);
1190
point_free (&pk.E.G);
1198
ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1202
return mpi_get_nbits (pkey[0]);
1207
/* See rsa.c for a description of this function. */
1208
static gpg_err_code_t
1209
compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1211
static const char names[] = "pabgnq";
1212
gpg_err_code_t ec = 0;
1214
gcry_mpi_t values[6];
1217
/* Clear the values for easier error cleanup. */
1218
for (idx=0; idx < 6; idx++)
1221
/* Fill values with all available parameters. */
1222
for (idx=0; idx < 6; idx++)
1224
l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
1227
values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1228
gcry_sexp_release (l1);
1231
ec = GPG_ERR_INV_OBJ;
1237
/* Check whether a curve parameter is available and use that to fill
1238
in missing values. */
1239
l1 = gcry_sexp_find_token (keyparam, "curve", 5);
1243
gcry_mpi_t tmpvalues[6];
1245
for (idx = 0; idx < 6; idx++)
1246
tmpvalues[idx] = NULL;
1248
curve = _gcry_sexp_nth_string (l1, 1);
1251
ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
1254
ec = ecc_get_param (curve, tmpvalues);
1259
for (idx = 0; idx < 6; idx++)
1262
values[idx] = tmpvalues[idx];
1264
mpi_free (tmpvalues[idx]);
1268
/* Check that all parameters are known and normalize all MPIs (that
1269
should not be required but we use an internal fucntion later and
1270
thus we better make 100% sure that they are normalized). */
1271
for (idx = 0; idx < 6; idx++)
1274
ec = GPG_ERR_NO_OBJ;
1278
_gcry_mpi_normalize (values[idx]);
1280
/* Hash them all. */
1281
for (idx = 0; idx < 6; idx++)
1284
unsigned char *rawmpi;
1285
unsigned int rawmpilen;
1287
rawmpi = _gcry_mpi_get_buffer (values[idx], &rawmpilen, NULL);
1290
ec = gpg_err_code_from_syserror ();
1293
snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
1294
gcry_md_write (md, buf, strlen (buf));
1295
gcry_md_write (md, rawmpi, rawmpilen);
1296
gcry_md_write (md, ")", 1);
1301
for (idx = 0; idx < 6; idx++)
1302
_gcry_mpi_release (values[idx]);
1316
static gpg_err_code_t
1317
selftests_ecdsa (selftest_report_func_t report)
1323
errtxt = NULL; /*selftest ();*/
1327
/* FIXME: need more tests. */
1329
return 0; /* Succeeded. */
1333
report ("pubkey", GCRY_PK_ECDSA, what, errtxt);
1334
return GPG_ERR_SELFTEST_FAILED;
1338
/* Run a full self-test for ALGO and return 0 on success. */
1339
static gpg_err_code_t
1340
run_selftests (int algo, int extended, selftest_report_func_t report)
1349
ec = selftests_ecdsa (report);
1352
ec = GPG_ERR_PUBKEY_ALGO;
1362
static const char *ecdsa_names[] =
1369
gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1371
"ECDSA", ecdsa_names,
1372
"pabgnq", "pabgnqd", "", "rs", "pabgnq",
1375
ecc_check_secret_key,
1383
pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa =
added
removed
lib/libgcrypt/cipher/ecc.c
