1
/* This file was automatically imported with
2
import_gcry.py. Please don't modify it */
3
/* ecc.c - Elliptic Curve Cryptography
4
Copyright (C) 2007, 2008 Free Software Foundation, Inc.
6
This file is part of Libgcrypt.
8
Libgcrypt is free software; you can redistribute it and/or modify
9
it under the terms of the GNU Lesser General Public License as
10
published by the Free Software Foundation; either version 2.1 of
11
the License, or (at your option) any later version.
13
Libgcrypt is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16
GNU Lesser General Public License for more details.
18
You should have received a copy of the GNU Lesser General Public
19
License along with this program; if not, write to the Free Software
20
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
23
/* This code is originally based on the Patch 0.1.6 for the gnupg
24
1.4.x branch as retrieved on 2007-03-21 from
25
http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2
26
The original authors are:
28
Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>,
29
Ramiro Moreno Chiral <ramiro at eup.udl.es>
34
For use in Libgcrypt the code has been heavily modified and cleaned
35
up. In fact there is not much left of the orginally code except for
36
some variable names and the text book implementaion of the sign and
37
verification algorithms. The arithmetic functions have entirely
38
been rewritten and moved to mpi/ec.c. */
43
- If we support point compression we need to decide how to compute
44
the keygrip - it should not change due to compression.
46
- In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a
47
special case in mpi_powm or check whether mpi_mulm is faster.
49
- Decide whether we should hide the mpi_point_t definition.
51
- Support more than just ECDSA.
61
/* Definition of a curve. */
64
gcry_mpi_t p; /* Prime specifying the field GF(p). */
65
gcry_mpi_t a; /* First coefficient of the Weierstrass equation. */
66
gcry_mpi_t b; /* Second coefficient of the Weierstrass equation. */
67
mpi_point_t G; /* Base point (generator). */
68
gcry_mpi_t n; /* Order of G. */
75
mpi_point_t Q; /* Q = [d]G */
86
/* This tables defines aliases for curve names. */
89
const char *name; /* Our name. */
90
const char *other; /* Other name. */
93
{ "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID */
94
{ "NIST P-192", "prime192v1" }, /* X9.62 name. */
95
{ "NIST P-192", "secp192r1" }, /* SECP name. */
97
{ "NIST P-224", "secp224r1" },
98
{ "NIST P-224", "1.3.132.0.33" }, /* SECP OID. */
100
{ "NIST P-256", "1.2.840.10045.3.1.7" }, /* From NIST SP 800-78-1. */
101
{ "NIST P-256", "prime256v1" },
102
{ "NIST P-256", "secp256r1" },
104
{ "NIST P-384", "secp384r1" },
105
{ "NIST P-384", "1.3.132.0.34" },
107
{ "NIST P-521", "secp521r1" },
108
{ "NIST P-521", "1.3.132.0.35" },
110
{ "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.1" },
111
{ "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.3" },
112
{ "brainpoolP224r1", "1.3.36.3.3.2.8.1.1.5" },
113
{ "brainpoolP256r1", "1.3.36.3.3.2.8.1.1.7" },
114
{ "brainpoolP320r1", "1.3.36.3.3.2.8.1.1.9" },
115
{ "brainpoolP384r1", "1.3.36.3.3.2.8.1.1.11"},
116
{ "brainpoolP512r1", "1.3.36.3.3.2.8.1.1.13"},
123
/* This static table defines all available curves. */
126
const char *desc; /* Description of the curve. */
127
unsigned int nbits; /* Number of bits. */
128
unsigned int fips:1; /* True if this is a FIPS140-2 approved curve. */
129
const char *p; /* Order of the prime field. */
130
const char *a, *b; /* The coefficients. */
131
const char *n; /* The order of the base point. */
132
const char *g_x, *g_y; /* Base point. */
136
"NIST P-192", 192, 1,
137
"0xfffffffffffffffffffffffffffffffeffffffffffffffff",
138
"0xfffffffffffffffffffffffffffffffefffffffffffffffc",
139
"0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
140
"0xffffffffffffffffffffffff99def836146bc9b1b4d22831",
142
"0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
143
"0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
146
"NIST P-224", 224, 1,
147
"0xffffffffffffffffffffffffffffffff000000000000000000000001",
148
"0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
149
"0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
150
"0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" ,
152
"0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
153
"0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"
156
"NIST P-256", 256, 1,
157
"0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
158
"0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
159
"0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
160
"0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
162
"0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
163
"0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
166
"NIST P-384", 384, 1,
167
"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
168
"ffffffff0000000000000000ffffffff",
169
"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
170
"ffffffff0000000000000000fffffffc",
171
"0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a"
172
"c656398d8a2ed19d2a85c8edd3ec2aef",
173
"0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf"
174
"581a0db248b0a77aecec196accc52973",
176
"0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a38"
177
"5502f25dbf55296c3a545e3872760ab7",
178
"0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0"
179
"0a60b1ce1d7e819d7a431d7c90ea0e5f"
182
"NIST P-521", 521, 1,
183
"0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
184
"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
185
"0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
186
"fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc",
187
"0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef10"
188
"9e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00",
189
"0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
190
"ffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409",
192
"0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3d"
193
"baa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66",
194
"0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e6"
195
"62c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650"
198
{ "brainpoolP160r1", 160, 0,
199
"0xe95e4a5f737059dc60dfc7ad95b3d8139515620f",
200
"0x340e7be2a280eb74e2be61bada745d97e8f7c300",
201
"0x1e589a8595423412134faa2dbdec95c8d8675e58",
202
"0xe95e4a5f737059dc60df5991d45029409e60fc09",
203
"0xbed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3",
204
"0x1667cb477a1a8ec338f94741669c976316da6321"
207
{ "brainpoolP192r1", 192, 0,
208
"0xc302f41d932a36cda7a3463093d18db78fce476de1a86297",
209
"0x6a91174076b1e0e19c39c031fe8685c1cae040e5c69a28ef",
210
"0x469a28ef7c28cca3dc721d044f4496bcca7ef4146fbf25c9",
211
"0xc302f41d932a36cda7a3462f9e9e916b5be8f1029ac4acc1",
212
"0xc0a0647eaab6a48753b033c56cb0f0900a2f5c4853375fd6",
213
"0x14b690866abd5bb88b5f4828c1490002e6773fa2fa299b8f"
216
{ "brainpoolP224r1", 224, 0,
217
"0xd7c134aa264366862a18302575d1d787b09f075797da89f57ec8c0ff",
218
"0x68a5e62ca9ce6c1c299803a6c1530b514e182ad8b0042a59cad29f43",
219
"0x2580f63ccfe44138870713b1a92369e33e2135d266dbb372386c400b",
220
"0xd7c134aa264366862a18302575d0fb98d116bc4b6ddebca3a5a7939f",
221
"0x0d9029ad2c7e5cf4340823b2a87dc68c9e4ce3174c1e6efdee12c07d",
222
"0x58aa56f772c0726f24c6b89e4ecdac24354b9e99caa3f6d3761402cd"
225
{ "brainpoolP256r1", 256, 0,
226
"0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377",
227
"0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9",
228
"0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6",
229
"0xa9fb57dba1eea9bc3e660a909d838d718c397aa3b561a6f7901e0e82974856a7",
230
"0x8bd2aeb9cb7e57cb2c4b482ffc81b7afb9de27e1e3bd23c23a4453bd9ace3262",
231
"0x547ef835c3dac4fd97f8461a14611dc9c27745132ded8e545c1d54c72f046997"
234
{ "brainpoolP320r1", 320, 0,
235
"0xd35e472036bc4fb7e13c785ed201e065f98fcfa6f6f40def4f92b9ec7893ec28"
237
"0x3ee30b568fbab0f883ccebd46d3f3bb8a2a73513f5eb79da66190eb085ffa9f4"
239
"0x520883949dfdbc42d3ad198640688a6fe13f41349554b49acc31dccd88453981"
241
"0xd35e472036bc4fb7e13c785ed201e065f98fcfa5b68f12a32d482ec7ee8658e9"
243
"0x43bd7e9afb53d8b85289bcc48ee5bfe6f20137d10a087eb6e7871e2a10a599c7"
245
"0x14fdd05545ec1cc8ab4093247f77275e0743ffed117182eaa9c77877aaac6ac7"
249
{ "brainpoolP384r1", 384, 0,
250
"0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b412b1da197fb71123"
251
"acd3a729901d1a71874700133107ec53",
252
"0x7bc382c63d8c150c3c72080ace05afa0c2bea28e4fb22787139165efba91f90f"
253
"8aa5814a503ad4eb04a8c7dd22ce2826",
254
"0x04a8c7dd22ce28268b39b55416f0447c2fb77de107dcd2a62e880ea53eeb62d5"
255
"7cb4390295dbc9943ab78696fa504c11",
256
"0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b31f166e6cac0425a7"
257
"cf3ab6af6b7fc3103b883202e9046565",
258
"0x1d1c64f068cf45ffa2a63a81b7c13f6b8847a3e77ef14fe3db7fcafe0cbd10e8"
259
"e826e03436d646aaef87b2e247d4af1e",
260
"0x8abe1d7520f9c2a45cb1eb8e95cfd55262b70b29feec5864e19c054ff9912928"
261
"0e4646217791811142820341263c5315"
264
{ "brainpoolP512r1", 512, 0,
265
"0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330871"
266
"7d4d9b009bc66842aecda12ae6a380e62881ff2f2d82c68528aa6056583a48f3",
267
"0x7830a3318b603b89e2327145ac234cc594cbdd8d3df91610a83441caea9863bc"
268
"2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a72bf2c7b9e7c1ac4d77fc94ca",
269
"0x3df91610a83441caea9863bc2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a7"
270
"2bf2c7b9e7c1ac4d77fc94cadc083e67984050b75ebae5dd2809bd638016f723",
271
"0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330870"
272
"553e5c414ca92619418661197fac10471db1d381085ddaddb58796829ca90069",
273
"0x81aee4bdd82ed9645a21322e9c4c6a9385ed9f70b5d916c1b43b62eef4d0098e"
274
"ff3b1f78e2d0d48d50d1687b93b97d5f7c6d5047406a5e688b352209bcb9f822",
275
"0x7dde385d566332ecc0eabfa9cf7822fdf209f70024a57b1aa000c55b881f8111"
276
"b2dcde494a5f485e5bca4bd88a2763aed1ca2b2fa8f0540678cd1e0f3ad80892"
279
{ NULL, 0, 0, NULL, NULL, NULL, NULL }
283
/* Registered progress function and its callback value. */
284
static void (*progress_cb) (void *, const char*, int, int, int);
285
static void *progress_cb_data;
288
#define point_init(a) _gcry_mpi_ec_point_init ((a))
289
#define point_free(a) _gcry_mpi_ec_point_free ((a))
293
/* Local prototypes. */
294
static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level);
295
static void test_keys (ECC_secret_key * sk, unsigned int nbits);
296
static int check_secret_key (ECC_secret_key * sk);
297
static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey,
298
gcry_mpi_t r, gcry_mpi_t s);
299
static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey,
300
gcry_mpi_t r, gcry_mpi_t s);
303
static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
309
_gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
314
progress_cb_data = cb_data;
318
/* progress (int c) */
320
/* if (progress_cb) */
321
/* progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
327
/* Set the value from S into D. */
329
point_set (mpi_point_t *d, mpi_point_t *s)
331
mpi_set (d->x, s->x);
332
mpi_set (d->y, s->y);
333
mpi_set (d->z, s->z);
338
* Release a curve object.
341
curve_free (elliptic_curve_t *E)
343
mpi_free (E->p); E->p = NULL;
344
mpi_free (E->a); E->a = NULL;
345
mpi_free (E->b); E->b = NULL;
347
mpi_free (E->n); E->n = NULL;
352
* Return a copy of a curve object.
354
static elliptic_curve_t
355
curve_copy (elliptic_curve_t E)
359
R.p = mpi_copy (E.p);
360
R.a = mpi_copy (E.a);
361
R.b = mpi_copy (E.b);
363
point_set (&R.G, &E.G);
364
R.n = mpi_copy (E.n);
371
/* Helper to scan a hex string. */
373
scanval (const char *string)
378
err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
380
log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
389
* Solve the right side of the equation that defines a curve.
392
gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
394
gcry_mpi_t three, x_3, axb, y;
396
three = mpi_alloc_set_ui (3);
401
mpi_powm (x_3, x, three, base->p);
402
mpi_mulm (axb, base->a, x, base->p);
403
mpi_addm (axb, axb, base->b, base->p);
404
mpi_addm (y, x_3, axb, base->p);
409
return y; /* The quadratic value of the coordinate if it exist. */
416
/* Generate a random secret scalar k with an order of p
418
At the beginning this was identical to the code is in elgamal.c.
419
Later imporved by mmr. Further simplified by wk. */
421
gen_k (gcry_mpi_t p, int security_level)
426
nbits = mpi_get_nbits (p);
427
k = mpi_snew (nbits);
429
log_debug ("choosing a random k of %u bits\n", nbits);
431
gcry_mpi_randomize (k, nbits, security_level);
433
mpi_mod (k, k, p); /* k = k mod p */
439
* Generate the crypto system setup.
440
* As of now the fix NIST recommended values are used.
441
* The subgroup generator point is in another function: gen_big_point.
443
static gpg_err_code_t
444
generate_curve (unsigned int nbits, const char *name,
445
elliptic_curve_t *curve, unsigned int *r_nbits)
451
/* First check nor native curves. */
452
for (idx = 0; domain_parms[idx].desc; idx++)
453
if (!strcmp (name, domain_parms[idx].desc))
455
/* If not found consult the alias table. */
456
if (!domain_parms[idx].desc)
458
for (aliasno = 0; curve_aliases[aliasno].name; aliasno++)
459
if (!strcmp (name, curve_aliases[aliasno].other))
461
if (curve_aliases[aliasno].name)
463
for (idx = 0; domain_parms[idx].desc; idx++)
464
if (!strcmp (curve_aliases[aliasno].name,
465
domain_parms[idx].desc))
472
for (idx = 0; domain_parms[idx].desc; idx++)
473
if (nbits == domain_parms[idx].nbits)
476
if (!domain_parms[idx].desc)
477
return GPG_ERR_INV_VALUE;
479
/* In fips mode we only support NIST curves. Note that it is
480
possible to bypass this check by specifying the curve parameters
482
if (fips_mode () && !domain_parms[idx].fips )
483
return GPG_ERR_NOT_SUPPORTED;
486
*r_nbits = domain_parms[idx].nbits;
487
curve->p = scanval (domain_parms[idx].p);
488
curve->a = scanval (domain_parms[idx].a);
489
curve->b = scanval (domain_parms[idx].b);
490
curve->n = scanval (domain_parms[idx].n);
491
curve->G.x = scanval (domain_parms[idx].g_x);
492
curve->G.y = scanval (domain_parms[idx].g_y);
493
curve->G.z = mpi_alloc_set_ui (1);
500
* First obtain the setup. Over the finite field randomize an scalar
501
* secret value, and calculate the public point.
503
static gpg_err_code_t
504
generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
505
gcry_mpi_t g_x, gcry_mpi_t g_y,
506
gcry_mpi_t q_x, gcry_mpi_t q_y)
514
err = generate_curve (nbits, name, &E, &nbits);
520
log_mpidump ("ecc generation p", E.p);
521
log_mpidump ("ecc generation a", E.a);
522
log_mpidump ("ecc generation b", E.b);
523
log_mpidump ("ecc generation n", E.n);
524
log_mpidump ("ecc generation Gx", E.G.x);
525
log_mpidump ("ecc generation Gy", E.G.y);
526
log_mpidump ("ecc generation Gz", E.G.z);
530
log_debug ("choosing a random x of size %u\n", nbits);
531
d = gen_k (E.n, GCRY_VERY_STRONG_RANDOM);
535
ctx = _gcry_mpi_ec_init (E.p, E.a);
536
_gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx);
538
/* Copy the stuff to the key structures. */
539
sk->E.p = mpi_copy (E.p);
540
sk->E.a = mpi_copy (E.a);
541
sk->E.b = mpi_copy (E.b);
542
point_init (&sk->E.G);
543
point_set (&sk->E.G, &E.G);
544
sk->E.n = mpi_copy (E.n);
546
point_set (&sk->Q, &Q);
547
sk->d = mpi_copy (d);
548
/* We also return copies of G and Q in affine coordinates if
552
if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
553
log_fatal ("ecc generate: Failed to get affine coordinates\n");
557
if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
558
log_fatal ("ecc generate: Failed to get affine coordinates\n");
560
_gcry_mpi_ec_free (ctx);
566
/* Now we can test our keys (this should never fail!). */
567
test_keys (sk, nbits - 64);
574
* To verify correct skey it use a random information.
575
* First, encrypt and decrypt this dummy value,
576
* test if the information is recuperated.
577
* Second, test with the sign and verify functions.
580
test_keys (ECC_secret_key *sk, unsigned int nbits)
583
gcry_mpi_t test = mpi_new (nbits);
585
gcry_mpi_t c = mpi_new (nbits);
586
gcry_mpi_t out = mpi_new (nbits);
587
gcry_mpi_t r = mpi_new (nbits);
588
gcry_mpi_t s = mpi_new (nbits);
591
log_debug ("Testing key.\n");
595
pk.E = curve_copy (sk->E);
597
point_set (&pk.Q, &sk->Q);
599
gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
601
if (sign (test, sk, r, s) )
602
log_fatal ("ECDSA operation: sign failed\n");
604
if (verify (test, &pk, r, s))
606
log_fatal ("ECDSA operation: sign, verify failed\n");
610
log_debug ("ECDSA operation: sign, verify ok.\n");
624
* To check the validity of the value, recalculate the correspondence
625
* between the public value and the secret one.
628
check_secret_key (ECC_secret_key * sk)
631
gcry_mpi_t y_2, y2 = mpi_alloc (0);
634
/* ?primarity test of 'p' */
637
y_2 = gen_y_2 (sk->E.G.x, &sk->E); /* y^2=x^3+a*x+b */
638
mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p); /* y^2=y*y */
639
if (mpi_cmp (y_2, y2))
642
log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
646
if (!mpi_cmp_ui (sk->E.G.z, 0))
649
log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
654
ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
655
_gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
656
if (mpi_cmp_ui (Q.z, 0))
659
log_debug ("check_secret_key: E is not a curve of order n\n");
661
_gcry_mpi_ec_free (ctx);
664
/* pubkey cannot be PaI */
665
if (!mpi_cmp_ui (sk->Q.z, 0))
668
log_debug ("Bad check: Q can not be a Point at Infinity!\n");
669
_gcry_mpi_ec_free (ctx);
672
/* pubkey = [d]G over E */
673
_gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
674
if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z))
678
("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
679
_gcry_mpi_ec_free (ctx);
682
_gcry_mpi_ec_free (ctx);
689
* Return the signature struct (r,s) from the message hash. The caller
690
* must have allocated R and S.
692
static gpg_err_code_t
693
sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
695
gpg_err_code_t err = 0;
696
gcry_mpi_t k, dr, sum, k_1, x;
710
ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
712
while (!mpi_cmp_ui (s, 0)) /* s == 0 */
714
while (!mpi_cmp_ui (r, 0)) /* r == 0 */
716
/* Note, that we are guaranteed to enter this loop at least
717
once because r has been intialized to 0. We can't use a
718
do_while because we want to keep the value of R even if S
719
has to be recomputed. */
721
k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
722
_gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
723
if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
726
log_debug ("ecc sign: Failed to get affine coordinates\n");
727
err = GPG_ERR_BAD_SIGNATURE;
730
mpi_mod (r, x, skey->E.n); /* r = x mod n */
732
mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */
733
mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n */
734
mpi_invm (k_1, k, skey->E.n); /* k_1 = k^(-1) mod n */
735
mpi_mulm (s, k_1, sum, skey->E.n); /* s = k^(-1)*(hash+(d*r)) mod n */
739
_gcry_mpi_ec_free (ctx);
751
* Check if R and S verifies INPUT.
753
static gpg_err_code_t
754
verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
756
gpg_err_code_t err = 0;
757
gcry_mpi_t h, h1, h2, x, y;
758
mpi_point_t Q, Q1, Q2;
761
if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
762
return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */
763
if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
764
return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */
775
ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
777
/* h = s^(-1) (mod n) */
778
mpi_invm (h, s, pkey->E.n);
779
/* log_mpidump (" h", h); */
780
/* h1 = hash * s^(-1) (mod n) */
781
mpi_mulm (h1, input, h, pkey->E.n);
782
/* log_mpidump (" h1", h1); */
783
/* Q1 = [ hash * s^(-1) ]G */
784
_gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
785
/* log_mpidump ("Q1.x", Q1.x); */
786
/* log_mpidump ("Q1.y", Q1.y); */
787
/* log_mpidump ("Q1.z", Q1.z); */
788
/* h2 = r * s^(-1) (mod n) */
789
mpi_mulm (h2, r, h, pkey->E.n);
790
/* log_mpidump (" h2", h2); */
791
/* Q2 = [ r * s^(-1) ]Q */
792
_gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
793
/* log_mpidump ("Q2.x", Q2.x); */
794
/* log_mpidump ("Q2.y", Q2.y); */
795
/* log_mpidump ("Q2.z", Q2.z); */
796
/* Q = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
797
_gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
798
/* log_mpidump (" Q.x", Q.x); */
799
/* log_mpidump (" Q.y", Q.y); */
800
/* log_mpidump (" Q.z", Q.z); */
802
if (!mpi_cmp_ui (Q.z, 0))
805
log_debug ("ecc verify: Rejected\n");
806
err = GPG_ERR_BAD_SIGNATURE;
809
if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
812
log_debug ("ecc verify: Failed to get affine coordinates\n");
813
err = GPG_ERR_BAD_SIGNATURE;
816
mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
817
if (mpi_cmp (x, r)) /* x != r */
821
log_mpidump (" x", x);
822
log_mpidump (" y", y);
823
log_mpidump (" r", r);
824
log_mpidump (" s", s);
825
log_debug ("ecc verify: Not verified\n");
827
err = GPG_ERR_BAD_SIGNATURE;
831
log_debug ("ecc verify: Accepted\n");
834
_gcry_mpi_ec_free (ctx);
848
/*********************************************
849
************** interface ******************
850
*********************************************/
852
ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
855
int pbytes = (mpi_get_nbits (p)+7)/8;
857
unsigned char *buf, *ptr;
860
buf = gcry_xmalloc ( 1 + 2*pbytes );
861
*buf = 04; /* Uncompressed point. */
863
err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
865
log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
868
memmove (ptr+(pbytes-n), ptr, n);
869
memset (ptr, 0, (pbytes-n));
872
err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
874
log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
877
memmove (ptr+(pbytes-n), ptr, n);
878
memset (ptr, 0, (pbytes-n));
881
err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
883
log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
892
/* RESULT must have been initialized and is set on success to the
893
point given by VALUE. */
895
os2ec (mpi_point_t *result, gcry_mpi_t value)
902
n = (mpi_get_nbits (value)+7)/8;
903
buf = gcry_xmalloc (n);
904
err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value);
913
return GPG_ERR_INV_OBJ;
918
return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression. */
923
return GPG_ERR_INV_OBJ;
926
err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
932
err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
940
mpi_set (result->x, x);
941
mpi_set (result->y, y);
942
mpi_set_ui (result->z, 1);
951
/* Extended version of ecc_generate. */
952
static gcry_err_code_t
953
ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
954
const gcry_sexp_t genparms,
955
gcry_mpi_t *skey, gcry_mpi_t **retfactors,
956
gcry_sexp_t *r_extrainfo)
960
gcry_mpi_t g_x, g_y, q_x, q_y;
961
char *curve_name = NULL;
970
/* Parse the optional "curve" parameter. */
971
l1 = gcry_sexp_find_token (genparms, "curve", 0);
974
curve_name = _gcry_sexp_nth_string (l1, 1);
975
gcry_sexp_release (l1);
977
return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
981
/* NBITS is required if no curve name has been given. */
982
if (!nbits && !curve_name)
983
return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
989
ec = generate_key (&sk, nbits, curve_name, g_x, g_y, q_x, q_y);
990
gcry_free (curve_name);
997
/* The function ec2os releases g_x and g_y. */
998
skey[3] = ec2os (g_x, g_y, sk.E.p);
1000
/* The function ec2os releases g_x and g_y. */
1001
skey[5] = ec2os (q_x, q_y, sk.E.p);
1004
point_free (&sk.E.G);
1007
/* Make an empty list of factors. */
1008
*retfactors = gcry_calloc ( 1, sizeof **retfactors );
1010
return gpg_err_code_from_syserror ();
1016
static gcry_err_code_t
1017
ecc_generate (int algo, unsigned int nbits, unsigned long evalue,
1018
gcry_mpi_t *skey, gcry_mpi_t **retfactors)
1021
return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
1025
/* Return the parameters of the curve NAME. */
1026
static gcry_err_code_t
1027
ecc_get_param (const char *name, gcry_mpi_t *pkey)
1033
gcry_mpi_t g_x, g_y;
1035
err = generate_curve (0, name, &E, &nbits);
1041
ctx = _gcry_mpi_ec_init (E.p, E.a);
1042
if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx))
1043
log_fatal ("ecc get param: Failed to get affine coordinates\n");
1044
_gcry_mpi_ec_free (ctx);
1050
pkey[3] = ec2os (g_x, g_y, E.p);
1058
static gcry_err_code_t
1059
ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1066
if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1067
|| !skey[6] || !skey[7] || !skey[8] || !skey[9] || !skey[10])
1068
return GPG_ERR_BAD_MPI;
1073
point_init (&sk.E.G);
1074
err = os2ec (&sk.E.G, skey[3]);
1077
point_free (&sk.E.G);
1082
err = os2ec (&sk.Q, skey[5]);
1085
point_free (&sk.E.G);
1092
if (check_secret_key (&sk))
1094
point_free (&sk.E.G);
1096
return GPG_ERR_BAD_SECKEY;
1098
point_free (&sk.E.G);
1104
static gcry_err_code_t
1105
ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
1112
if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1113
|| !skey[5] || !skey[6] )
1114
return GPG_ERR_BAD_MPI;
1119
point_init (&sk.E.G);
1120
err = os2ec (&sk.E.G, skey[3]);
1123
point_free (&sk.E.G);
1128
err = os2ec (&sk.Q, skey[5]);
1131
point_free (&sk.E.G);
1137
resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1138
resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1139
err = sign (data, &sk, resarr[0], resarr[1]);
1142
mpi_free (resarr[0]);
1143
mpi_free (resarr[1]);
1144
resarr[0] = NULL; /* Mark array as released. */
1146
point_free (&sk.E.G);
1151
static gcry_err_code_t
1152
ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1153
int (*cmp)(void *, gcry_mpi_t), void *opaquev)
1162
if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1163
|| !pkey[3] || !pkey[4] || !pkey[5] )
1164
return GPG_ERR_BAD_MPI;
1169
point_init (&pk.E.G);
1170
err = os2ec (&pk.E.G, pkey[3]);
1173
point_free (&pk.E.G);
1178
err = os2ec (&pk.Q, pkey[5]);
1181
point_free (&pk.E.G);
1186
err = verify (hash, &pk, data[0], data[1]);
1188
point_free (&pk.E.G);
1196
ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1200
return mpi_get_nbits (pkey[0]);
1205
/* See rsa.c for a description of this function. */
1206
static gpg_err_code_t
1207
compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1209
static const char names[] = "pabgnq";
1210
gpg_err_code_t ec = 0;
1212
gcry_mpi_t values[6];
1215
/* Clear the values for easier error cleanup. */
1216
for (idx=0; idx < 6; idx++)
1219
/* Fill values with all available parameters. */
1220
for (idx=0; idx < 6; idx++)
1222
l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
1225
values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1226
gcry_sexp_release (l1);
1229
ec = GPG_ERR_INV_OBJ;
1235
/* Check whether a curve parameter is available and use that to fill
1236
in missing values. */
1237
l1 = gcry_sexp_find_token (keyparam, "curve", 5);
1241
gcry_mpi_t tmpvalues[6];
1243
for (idx = 0; idx < 6; idx++)
1244
tmpvalues[idx] = NULL;
1246
curve = _gcry_sexp_nth_string (l1, 1);
1249
ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
1252
ec = ecc_get_param (curve, tmpvalues);
1257
for (idx = 0; idx < 6; idx++)
1260
values[idx] = tmpvalues[idx];
1262
mpi_free (tmpvalues[idx]);
1266
/* Check that all parameters are known and normalize all MPIs (that
1267
should not be required but we use an internal fucntion later and
1268
thus we better make 100% sure that they are normalized). */
1269
for (idx = 0; idx < 6; idx++)
1272
ec = GPG_ERR_NO_OBJ;
1276
_gcry_mpi_normalize (values[idx]);
1278
/* Hash them all. */
1279
for (idx = 0; idx < 6; idx++)
1282
unsigned char *rawmpi;
1283
unsigned int rawmpilen;
1285
rawmpi = _gcry_mpi_get_buffer (values[idx], &rawmpilen, NULL);
1288
ec = gpg_err_code_from_syserror ();
1291
snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
1292
gcry_md_write (md, buf, strlen (buf));
1293
gcry_md_write (md, rawmpi, rawmpilen);
1294
gcry_md_write (md, ")", 1);
1299
for (idx = 0; idx < 6; idx++)
1300
_gcry_mpi_release (values[idx]);
1316
/* Run a full self-test for ALGO and return 0 on success. */
1321
static const char *ecdsa_names[] =
1328
gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1330
"ECDSA", ecdsa_names,
1331
"pabgnq", "pabgnqd", "", "rs", "pabgnq",
1334
ecc_check_secret_key,
1342
pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa =
added
removed
lib/libgcrypt-grub/cipher/ecc.c
