1
/* ec.c - Elliptic Curve functions
2
Copyright (C) 2007 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,
27
#include "mpi-internal.h"
32
#define point_init(a) _gcry_mpi_ec_point_init ((a))
33
#define point_free(a) _gcry_mpi_ec_point_free ((a))
36
/* Object to represent a point in projective coordinates. */
37
/* Currently defined in mpi.h */
39
/* This context is used with all our EC functions. */
42
/* Domain parameters. */
43
gcry_mpi_t p; /* Prime specifying the field GF(p). */
44
gcry_mpi_t a; /* First coefficient of the Weierstrass equation. */
46
int a_is_pminus3; /* True if A = P - 3. */
48
/* Some often used constants. */
56
/* Scratch variables. */
57
gcry_mpi_t scratch[11];
59
/* Helper for fast reduction. */
60
/* int nist_nbits; /\* If this is a NIST curve, the number of bits. *\/ */
61
/* gcry_mpi_t s[10]; */
68
/* Initialized a point object. gcry_mpi_ec_point_free shall be used
69
to release this object. */
71
_gcry_mpi_ec_point_init (mpi_point_t *p)
79
/* Release a point object. */
81
_gcry_mpi_ec_point_free (mpi_point_t *p)
83
mpi_free (p->x); p->x = NULL;
84
mpi_free (p->y); p->y = NULL;
85
mpi_free (p->z); p->z = NULL;
88
/* Set the value from S into D. */
90
point_set (mpi_point_t *d, mpi_point_t *s)
100
ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
102
mpi_addm (w, u, v, ctx->p);
106
ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
108
mpi_subm (w, u, v, ctx->p);
112
ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
115
/* NOTE: This code works only for limb sizes of 32 bit. */
118
if (ctx->nist_nbits == 192)
125
sp[0*2+0] = wp[0*2+0];
126
sp[0*2+1] = wp[0*2+1];
127
sp[1*2+0] = wp[1*2+0];
128
sp[1*2+1] = wp[1*2+1];
129
sp[2*2+0] = wp[2*2+0];
130
sp[2*2+1] = wp[2*2+1];
133
sp[0*2+0] = wp[3*2+0];
134
sp[0*2+1] = wp[3*2+1];
135
sp[1*2+0] = wp[3*2+0];
136
sp[1*2+1] = wp[3*2+1];
143
sp[1*2+0] = wp[4*2+0];
144
sp[1*2+1] = wp[4*2+1];
145
sp[2*2+0] = wp[4*2+0];
146
sp[2*2+1] = wp[4*2+1];
149
sp[0*2+0] = wp[5*2+0];
150
sp[0*2+1] = wp[5*2+1];
151
sp[1*2+0] = wp[5*2+0];
152
sp[1*2+1] = wp[5*2+1];
153
sp[2*2+0] = wp[5*2+0];
154
sp[2*2+1] = wp[5*2+1];
156
ctx->s[0]->nlimbs = 6;
157
ctx->s[1]->nlimbs = 6;
158
ctx->s[2]->nlimbs = 6;
159
ctx->s[3]->nlimbs = 6;
161
mpi_add (ctx->c, ctx->s[0], ctx->s[1]);
162
mpi_add (ctx->c, ctx->c, ctx->s[2]);
163
mpi_add (ctx->c, ctx->c, ctx->s[3]);
165
while ( mpi_cmp (ctx->c, ctx->p ) >= 0 )
166
mpi_sub ( ctx->c, ctx->c, ctx->p );
169
else if (ctx->nist_nbits == 384)
176
#define NEXT(a) do { ctx->s[(a)]->nlimbs = 12; \
177
sp = ctx->s[(a)]->d; \
179
#define X(a) do { sp[i++] = wp[(a)];} while (0)
180
#define X0(a) do { sp[i++] = 0; } while (0)
182
X(0);X(1);X(2);X(3);X(4);X(5);X(6);X(7);X(8);X(9);X(10);X(11);
184
X0();X0();X0();X0();X(21);X(22);X(23);X0();X0();X0();X0();X0();
186
X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);X(21);X(22);X(23);
188
X(21);X(22);X(23);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);
190
X0();X(23);X0();X(20);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);
192
X0();X0();X0();X0();X(20);X(21);X(22);X(23);X0();X0();X0();X0();
194
X(20);X0();X0();X(21);X(22);X(23);X0();X0();X0();X0();X0();X0();
196
X(23);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);X(21);X(22);
198
X0();X(20);X(21);X(22);X(23);X0();X0();X0();X0();X0();X0();X0();
200
X0();X0();X0();X(23);X(23);X0();X0();X0();X0();X0();X0();X0();
204
mpi_add (ctx->c, ctx->s[0], ctx->s[1]);
205
mpi_add (ctx->c, ctx->c, ctx->s[1]);
206
mpi_add (ctx->c, ctx->c, ctx->s[2]);
207
mpi_add (ctx->c, ctx->c, ctx->s[3]);
208
mpi_add (ctx->c, ctx->c, ctx->s[4]);
209
mpi_add (ctx->c, ctx->c, ctx->s[5]);
210
mpi_add (ctx->c, ctx->c, ctx->s[6]);
211
mpi_sub (ctx->c, ctx->c, ctx->s[7]);
212
mpi_sub (ctx->c, ctx->c, ctx->s[8]);
213
mpi_sub (ctx->c, ctx->c, ctx->s[9]);
215
while ( mpi_cmp (ctx->c, ctx->p ) >= 0 )
216
mpi_sub ( ctx->c, ctx->c, ctx->p );
217
while ( ctx->c->sign )
218
mpi_add ( ctx->c, ctx->c, ctx->p );
223
mpi_mulm (w, u, v, ctx->p);
227
ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e,
230
mpi_powm (w, b, e, ctx->p);
234
ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx)
236
mpi_invm (x, a, ctx->p);
241
/* This function returns a new context for elliptic curve based on the
242
field GF(p). P is the prime specifying thuis field, A is the first
245
This context needs to be released using _gcry_mpi_ec_free. */
247
_gcry_mpi_ec_init (gcry_mpi_t p, gcry_mpi_t a)
256
/* Fixme: Do we want to check some constraints? e.g.
260
ctx = gcry_xcalloc (1, sizeof *ctx);
262
ctx->p = mpi_copy (p);
263
ctx->a = mpi_copy (a);
265
tmp = mpi_alloc_like (ctx->p);
266
mpi_sub_ui (tmp, ctx->p, 3);
267
ctx->a_is_pminus3 = !mpi_cmp (ctx->a, tmp);
271
/* Allocate constants. */
272
ctx->one = mpi_alloc_set_ui (1);
273
ctx->two = mpi_alloc_set_ui (2);
274
ctx->three = mpi_alloc_set_ui (3);
275
ctx->four = mpi_alloc_set_ui (4);
276
ctx->eight = mpi_alloc_set_ui (8);
277
ctx->two_inv_p = mpi_alloc (0);
278
ec_invm (ctx->two_inv_p, ctx->two, ctx);
280
/* Allocate scratch variables. */
281
for (i=0; i< DIM(ctx->scratch); i++)
282
ctx->scratch[i] = mpi_alloc_like (ctx->p);
284
/* Prepare for fast reduction. */
285
/* FIXME: need a test for NIST values. However it does not gain us
286
any real advantage, for 384 bits it is actually slower than using
288
/* ctx->nist_nbits = mpi_get_nbits (ctx->p); */
289
/* if (ctx->nist_nbits == 192) */
291
/* for (i=0; i < 4; i++) */
292
/* ctx->s[i] = mpi_new (192); */
293
/* ctx->c = mpi_new (192*2); */
295
/* else if (ctx->nist_nbits == 384) */
297
/* for (i=0; i < 10; i++) */
298
/* ctx->s[i] = mpi_new (384); */
299
/* ctx->c = mpi_new (384*2); */
306
_gcry_mpi_ec_free (mpi_ec_t ctx)
318
mpi_free (ctx->three);
319
mpi_free (ctx->four);
320
mpi_free (ctx->eight);
322
mpi_free (ctx->two_inv_p);
324
for (i=0; i< DIM(ctx->scratch); i++)
325
mpi_free (ctx->scratch[i]);
327
/* if (ctx->nist_nbits == 192) */
329
/* for (i=0; i < 4; i++) */
330
/* mpi_free (ctx->s[i]); */
331
/* mpi_free (ctx->c); */
333
/* else if (ctx->nist_nbits == 384) */
335
/* for (i=0; i < 10; i++) */
336
/* mpi_free (ctx->s[i]); */
337
/* mpi_free (ctx->c); */
343
/* Compute the affine coordinates from the projective coordinates in
344
POINT. Set them into X and Y. If one coordinate is not required,
345
X or Y may be passed as NULL. CTX is the usual context. Returns: 0
346
on success or !0 if POINT is at infinity. */
348
_gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t *point,
351
gcry_mpi_t z1, z2, z3;
353
if (!mpi_cmp_ui (point->z, 0))
358
ec_invm (z1, point->z, ctx); /* z1 = z^(-1) mod p */
359
ec_mulm (z2, z1, z1, ctx); /* z2 = z^(-2) mod p */
362
ec_mulm (x, point->x, z2, ctx);
367
ec_mulm (z3, z2, z1, ctx); /* z3 = z^(-3) mod p */
368
ec_mulm (y, point->y, z3, ctx);
381
/* RESULT = 2 * POINT */
383
_gcry_mpi_ec_dup_point (mpi_point_t *result, mpi_point_t *point, mpi_ec_t ctx)
385
#define x3 (result->x)
386
#define y3 (result->y)
387
#define z3 (result->z)
388
#define t1 (ctx->scratch[0])
389
#define t2 (ctx->scratch[1])
390
#define t3 (ctx->scratch[2])
391
#define l1 (ctx->scratch[3])
392
#define l2 (ctx->scratch[4])
393
#define l3 (ctx->scratch[5])
395
if (!mpi_cmp_ui (point->y, 0) || !mpi_cmp_ui (point->z, 0))
397
/* P_y == 0 || P_z == 0 => [1:1:0] */
404
if (ctx->a_is_pminus3) /* Use the faster case. */
406
/* L1 = 3(X - Z^2)(X + Z^2) */
407
/* T1: used for Z^2. */
408
/* T2: used for the right term. */
409
ec_powm (t1, point->z, ctx->two, ctx);
410
ec_subm (l1, point->x, t1, ctx);
411
ec_mulm (l1, l1, ctx->three, ctx);
412
ec_addm (t2, point->x, t1, ctx);
413
ec_mulm (l1, l1, t2, ctx);
415
else /* Standard case. */
417
/* L1 = 3X^2 + aZ^4 */
418
/* T1: used for aZ^4. */
419
ec_powm (l1, point->x, ctx->two, ctx);
420
ec_mulm (l1, l1, ctx->three, ctx);
421
ec_powm (t1, point->z, ctx->four, ctx);
422
ec_mulm (t1, t1, ctx->a, ctx);
423
ec_addm (l1, l1, t1, ctx);
426
ec_mulm (z3, point->y, point->z, ctx);
427
ec_mulm (z3, z3, ctx->two, ctx);
430
/* T2: used for Y2; required later. */
431
ec_powm (t2, point->y, ctx->two, ctx);
432
ec_mulm (l2, t2, point->x, ctx);
433
ec_mulm (l2, l2, ctx->four, ctx);
435
/* X3 = L1^2 - 2L2 */
436
/* T1: used for L2^2. */
437
ec_powm (x3, l1, ctx->two, ctx);
438
ec_mulm (t1, l2, ctx->two, ctx);
439
ec_subm (x3, x3, t1, ctx);
442
/* T2: taken from above. */
443
ec_powm (t2, t2, ctx->two, ctx);
444
ec_mulm (l3, t2, ctx->eight, ctx);
446
/* Y3 = L1(L2 - X3) - L3 */
447
ec_subm (y3, l2, x3, ctx);
448
ec_mulm (y3, y3, l1, ctx);
449
ec_subm (y3, y3, l3, ctx);
465
/* RESULT = P1 + P2 */
467
_gcry_mpi_ec_add_points (mpi_point_t *result,
468
mpi_point_t *p1, mpi_point_t *p2,
477
#define x3 (result->x)
478
#define y3 (result->y)
479
#define z3 (result->z)
480
#define l1 (ctx->scratch[0])
481
#define l2 (ctx->scratch[1])
482
#define l3 (ctx->scratch[2])
483
#define l4 (ctx->scratch[3])
484
#define l5 (ctx->scratch[4])
485
#define l6 (ctx->scratch[5])
486
#define l7 (ctx->scratch[6])
487
#define l8 (ctx->scratch[7])
488
#define l9 (ctx->scratch[8])
489
#define t1 (ctx->scratch[9])
490
#define t2 (ctx->scratch[10])
492
if ( (!mpi_cmp (x1, x2)) && (!mpi_cmp (y1, y2)) && (!mpi_cmp (z1, z2)) )
494
/* Same point; need to call the duplicate function. */
495
_gcry_mpi_ec_dup_point (result, p1, ctx);
497
else if (!mpi_cmp_ui (z1, 0))
499
/* P1 is at infinity. */
504
else if (!mpi_cmp_ui (z2, 0))
506
/* P2 is at infinity. */
513
int z1_is_one = !mpi_cmp_ui (z1, 1);
514
int z2_is_one = !mpi_cmp_ui (z2, 1);
522
ec_powm (l1, z2, ctx->two, ctx);
523
ec_mulm (l1, l1, x1, ctx);
529
ec_powm (l2, z1, ctx->two, ctx);
530
ec_mulm (l2, l2, x2, ctx);
533
ec_subm (l3, l1, l2, ctx);
535
ec_powm (l4, z2, ctx->three, ctx);
536
ec_mulm (l4, l4, y1, ctx);
538
ec_powm (l5, z1, ctx->three, ctx);
539
ec_mulm (l5, l5, y2, ctx);
541
ec_subm (l6, l4, l5, ctx);
543
if (!mpi_cmp_ui (l3, 0))
545
if (!mpi_cmp_ui (l6, 0))
547
/* P1 and P2 are the same - use duplicate function. */
548
_gcry_mpi_ec_dup_point (result, p1, ctx);
552
/* P1 is the inverse of P2. */
561
ec_addm (l7, l1, l2, ctx);
563
ec_addm (l8, l4, l5, ctx);
565
ec_mulm (z3, z1, z2, ctx);
566
ec_mulm (z3, z3, l3, ctx);
567
/* x3 = l6^2 - l7 l3^2 */
568
ec_powm (t1, l6, ctx->two, ctx);
569
ec_powm (t2, l3, ctx->two, ctx);
570
ec_mulm (t2, t2, l7, ctx);
571
ec_subm (x3, t1, t2, ctx);
572
/* l9 = l7 l3^2 - 2 x3 */
573
ec_mulm (t1, x3, ctx->two, ctx);
574
ec_subm (l9, t2, t1, ctx);
575
/* y3 = (l9 l6 - l8 l3^3)/2 */
576
ec_mulm (l9, l9, l6, ctx);
577
ec_powm (t1, l3, ctx->three, ctx); /* fixme: Use saved value*/
578
ec_mulm (t1, t1, l8, ctx);
579
ec_subm (y3, l9, t1, ctx);
580
ec_mulm (y3, y3, ctx->two_inv_p, ctx);
608
/* Scalar point multiplication - the main function for ECC. If takes
609
an integer SCALAR and a POINT as well as the usual context CTX.
610
RESULT will be set to the resulting point. */
612
_gcry_mpi_ec_mul_point (mpi_point_t *result,
613
gcry_mpi_t scalar, mpi_point_t *point,
617
/* Simple left to right binary method. GECC Algorithm 3.27 */
621
nbits = mpi_get_nbits (scalar);
622
mpi_set_ui (result->x, 1);
623
mpi_set_ui (result->y, 1);
624
mpi_set_ui (result->z, 0);
626
for (i=nbits-1; i >= 0; i--)
628
_gcry_mpi_ec_dup_point (result, result, ctx);
629
if (mpi_test_bit (scalar, i) == 1)
630
_gcry_mpi_ec_add_points (result, result, point, ctx);
634
gcry_mpi_t x1, y1, z1, k, h, yy;
635
unsigned int i, loops;
636
mpi_point_t p1, p2, p1inv;
638
x1 = mpi_alloc_like (ctx->p);
639
y1 = mpi_alloc_like (ctx->p);
640
h = mpi_alloc_like (ctx->p);
641
k = mpi_copy (scalar);
642
yy = mpi_copy (point->y);
644
if ( mpi_is_neg (k) )
647
ec_invm (yy, yy, ctx);
650
if (!mpi_cmp_ui (point->z, 1))
652
mpi_set (x1, point->x);
659
z2 = mpi_alloc_like (ctx->p);
660
z3 = mpi_alloc_like (ctx->p);
661
ec_mulm (z2, point->z, point->z, ctx);
662
ec_mulm (z3, point->z, z2, ctx);
663
ec_invm (z2, z2, ctx);
664
ec_mulm (x1, point->x, z2, ctx);
665
ec_invm (z3, z3, ctx);
666
ec_mulm (y1, yy, z3, ctx);
670
z1 = mpi_copy (ctx->one);
672
mpi_mul (h, k, ctx->three); /* h = 3k */
673
loops = mpi_get_nbits (h);
675
mpi_set (result->x, point->x);
676
mpi_set (result->y, yy); mpi_free (yy); yy = NULL;
677
mpi_set (result->z, point->z);
679
p1.x = x1; x1 = NULL;
680
p1.y = y1; y1 = NULL;
681
p1.z = z1; z1 = NULL;
685
for (i=loops-2; i > 0; i--)
687
_gcry_mpi_ec_dup_point (result, result, ctx);
688
if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
690
point_set (&p2, result);
691
_gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
693
if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
695
point_set (&p2, result);
696
/* Invert point: y = p - y mod p */
697
point_set (&p1inv, &p1);
698
ec_subm (p1inv.y, ctx->p, p1inv.y, ctx);
699
_gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx);
added
removed
mpi/ec.c
