← Back to branch summary

~timkross/cjdns/cjdns

« back to all changes in this revision

Viewing changes to crypto/seccure/ecc.c

  • Committer: cjdelisle
  • Date: 2011-02-16 23:03:00 UTC
  • Revision ID: git-v1:d475c9c10adc25590bea5e7dc5383b32f66d5eb8
First commit for cjdns.

Show diffs side-by-side

added added

removed removed

Lines of Context:
crypto/seccure/ecc.c
 
1
/*
 
2
 *  seccure  -  Copyright 2009 B. Poettering
 
3
 *
 
4
 *  This program is free software; you can redistribute it and/or
 
5
 *  modify it under the terms of the GNU General Public License as
 
6
 *  published by the Free Software Foundation; either version 2 of the
 
7
 *  License, or (at your option) any later version.
 
8
 *
 
9
 *  This program is distributed in the hope that it will be useful,
 
10
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
12
 *  General Public License for more details.
 
13
 *
 
14
 *  You should have received a copy of the GNU General Public License
 
15
 *  along with this program; if not, write to the Free Software
 
16
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 
17
 *  02111-1307 USA
 
18
 */
 
19
 
 
20
/* 
 
21
 *   SECCURE Elliptic Curve Crypto Utility for Reliable Encryption
 
22
 *
 
23
 *              http://point-at-infinity.org/seccure/
 
24
 *
 
25
 *
 
26
 * seccure implements a selection of asymmetric algorithms based on  
 
27
 * elliptic curve cryptography (ECC). See the manpage or the project's  
 
28
 * homepage for further details.
 
29
 *
 
30
 * This code links against the GNU gcrypt library "libgcrypt" (which
 
31
 * is part of the GnuPG project). Use the included Makefile to build
 
32
 * the binary.
 
33
 * 
 
34
 * Report bugs to: seccure AT point-at-infinity.org
 
35
 *
 
36
 */
 
37
 
 
38
#include <gcrypt.h>
 
39
#include <assert.h>
 
40
 
 
41
#include "ecc.h"
 
42
#include "numtheory.h"
 
43
 
 
44
/******************************************************************************/
 
45
 
 
46
/* Chapter 3.1.2 in the "Guide to Elliptic Curve Cryptography"                */
 
47
 
 
48
struct affine_point point_new(void)
 
49
{
 
50
  struct affine_point r;
 
51
  r.x = gcry_mpi_snew(0);
 
52
  r.y = gcry_mpi_snew(0);
 
53
  return r;
 
54
}
 
55
 
 
56
void point_release(struct affine_point *p)
 
57
{
 
58
  gcry_mpi_release(p->x);
 
59
  gcry_mpi_release(p->y);
 
60
}
 
61
 
 
62
void point_set(struct affine_point *p1, const struct affine_point *p2)
 
63
{
 
64
  gcry_mpi_set(p1->x, p2->x);
 
65
  gcry_mpi_set(p1->y, p2->y);
 
66
}
 
67
 
 
68
void point_load_zero(struct affine_point *p)
 
69
{
 
70
  gcry_mpi_set_ui(p->x, 0);
 
71
  gcry_mpi_set_ui(p->y, 0);
 
72
}
 
73
 
 
74
int point_is_zero(const struct affine_point *p)
 
75
{
 
76
  return ! gcry_mpi_cmp_ui(p->x, 0) && ! gcry_mpi_cmp_ui(p->y, 0);
 
77
}
 
78
 
 
79
int point_on_curve(const struct affine_point *p, const struct domain_params *dp)
 
80
{
 
81
  int res;
 
82
  if (! (res = point_is_zero(p))) {
 
83
    gcry_mpi_t h1, h2;
 
84
    h1 = gcry_mpi_snew(0);
 
85
    h2 = gcry_mpi_snew(0);
 
86
    gcry_mpi_mulm(h1, p->x, p->x, dp->m);
 
87
    gcry_mpi_addm(h1, h1, dp->a, dp->m);
 
88
    gcry_mpi_mulm(h1, h1, p->x, dp->m);
 
89
    gcry_mpi_addm(h1, h1, dp->b, dp->m);
 
90
    gcry_mpi_mulm(h2, p->y, p->y, dp->m);
 
91
    res = ! gcry_mpi_cmp(h1, h2);
 
92
    gcry_mpi_release(h1);
 
93
    gcry_mpi_release(h2);
 
94
  }
 
95
  return res;
 
96
}
 
97
 
 
98
int point_compress(const struct affine_point *p)
 
99
{
 
100
  return gcry_mpi_test_bit(p->y, 0);
 
101
}
 
102
 
 
103
int point_decompress(struct affine_point *p, const gcry_mpi_t x, int yflag, 
 
104
                     const struct domain_params *dp)
 
105
{
 
106
  gcry_mpi_t h, y;
 
107
  int res;
 
108
  h = gcry_mpi_snew(0);
 
109
  y = gcry_mpi_snew(0);
 
110
  gcry_mpi_mulm(h, x, x, dp->m);
 
111
  gcry_mpi_addm(h, h, dp->a, dp->m);
 
112
  gcry_mpi_mulm(h, h, x, dp->m);
 
113
  gcry_mpi_addm(h, h, dp->b, dp->m);
 
114
  if ((res = mod_root(y, h, dp->m)))
 
115
    if ((res = (gcry_mpi_cmp_ui(y, 0) || ! yflag))) {
 
116
      p->x = gcry_mpi_snew(0);
 
117
      p->y = gcry_mpi_snew(0);
 
118
      gcry_mpi_set(p->x, x);
 
119
      if (gcry_mpi_test_bit(y, 0) == yflag)
 
120
        gcry_mpi_set(p->y, y);
 
121
      else
 
122
        gcry_mpi_sub(p->y, dp->m, y);
 
123
      assert(point_on_curve(p, dp));
 
124
    }
 
125
  gcry_mpi_release(h);
 
126
  gcry_mpi_release(y);
 
127
  return res;
 
128
}
 
129
 
 
130
void point_double(struct affine_point *p, const struct domain_params *dp)
 
131
{
 
132
  if (gcry_mpi_cmp_ui(p->y, 0)) {
 
133
    gcry_mpi_t t1, t2;
 
134
    t1 = gcry_mpi_snew(0);
 
135
    t2 = gcry_mpi_snew(0);
 
136
    gcry_mpi_mulm(t2, p->x, p->x, dp->m);
 
137
    gcry_mpi_addm(t1, t2, t2, dp->m);
 
138
    gcry_mpi_addm(t1, t1, t2, dp->m);
 
139
    gcry_mpi_addm(t1, t1, dp->a, dp->m);
 
140
    gcry_mpi_addm(t2, p->y, p->y, dp->m);
 
141
    gcry_mpi_invm(t2, t2, dp->m);
 
142
    gcry_mpi_mulm(t1, t1, t2, dp->m);
 
143
    gcry_mpi_mulm(t2, t1, t1, dp->m);
 
144
    gcry_mpi_subm(t2, t2, p->x, dp->m);
 
145
    gcry_mpi_subm(t2, t2, p->x, dp->m);
 
146
    gcry_mpi_subm(p->x, p->x, t2, dp->m);
 
147
    gcry_mpi_mulm(t1, t1, p->x, dp->m);
 
148
    gcry_mpi_subm(p->y, t1, p->y, dp->m);
 
149
    gcry_mpi_set(p->x, t2);
 
150
    gcry_mpi_release(t1);
 
151
    gcry_mpi_release(t2);
 
152
  }
 
153
  else
 
154
    gcry_mpi_set_ui(p->x, 0);
 
155
}
 
156
 
 
157
void point_add(struct affine_point *p1, const struct affine_point *p2,
 
158
               const struct domain_params *dp)
 
159
{
 
160
  if (! point_is_zero(p2)) {
 
161
    if (! point_is_zero(p1)) {
 
162
      if (! gcry_mpi_cmp(p1->x, p2->x)) {
 
163
        if (! gcry_mpi_cmp(p1->y, p2->y))
 
164
          point_double(p1, dp);
 
165
        else
 
166
          point_load_zero(p1);
 
167
      }
 
168
      else {
 
169
        gcry_mpi_t t;
 
170
        t = gcry_mpi_snew(0);
 
171
        gcry_mpi_subm(t, p1->y, p2->y, dp->m);
 
172
        gcry_mpi_subm(p1->y, p1->x, p2->x, dp->m);
 
173
        gcry_mpi_invm(p1->y, p1->y, dp->m);
 
174
        gcry_mpi_mulm(p1->y, t, p1->y, dp->m);
 
175
        gcry_mpi_mulm(t, p1->y, p1->y, dp->m);
 
176
        gcry_mpi_addm(p1->x, p1->x, p2->x, dp->m);
 
177
        gcry_mpi_subm(p1->x, t, p1->x, dp->m);
 
178
        gcry_mpi_subm(t, p2->x, p1->x, dp->m);
 
179
        gcry_mpi_mulm(p1->y, p1->y, t, dp->m);
 
180
        gcry_mpi_subm(p1->y, p1->y, p2->y, dp->m);
 
181
        gcry_mpi_release(t);
 
182
      }
 
183
    }
 
184
    else
 
185
      point_set(p1, p2);
 
186
  }
 
187
}
 
188
 
 
189
/******************************************************************************/
 
190
 
 
191
/* Chapter 3.2.2 in the "Guide to Elliptic Curve Cryptography"                */
 
192
 
 
193
struct jacobian_point jacobian_new(void)
 
194
{
 
195
  struct jacobian_point r;
 
196
  r.x = gcry_mpi_snew(0);
 
197
  r.y = gcry_mpi_snew(0);
 
198
  r.z = gcry_mpi_snew(0);
 
199
  return r;
 
200
}
 
201
 
 
202
void jacobian_release(struct jacobian_point *p)
 
203
{
 
204
  gcry_mpi_release(p->x);
 
205
  gcry_mpi_release(p->y);
 
206
  gcry_mpi_release(p->z);
 
207
}
 
208
 
 
209
void jacobian_load_affine(struct jacobian_point *p1,
 
210
                          const struct affine_point *p2)
 
211
{
 
212
  if (! point_is_zero(p2)) {
 
213
    gcry_mpi_set(p1->x, p2->x);
 
214
    gcry_mpi_set(p1->y, p2->y);
 
215
    gcry_mpi_set_ui(p1->z, 1);
 
216
  }
 
217
  else
 
218
    gcry_mpi_set_ui(p1->z, 0);
 
219
}
 
220
 
 
221
void jacobian_load_zero(struct jacobian_point *p)
 
222
{
 
223
  gcry_mpi_set_ui(p->z, 0);
 
224
}
 
225
 
 
226
int jacobian_is_zero(const struct jacobian_point *p)
 
227
{
 
228
  return ! gcry_mpi_cmp_ui(p->z, 0);
 
229
}
 
230
 
 
231
void jacobian_double(struct jacobian_point *p, const struct domain_params *dp)
 
232
{
 
233
  if (gcry_mpi_cmp_ui(p->z, 0)) {
 
234
    if (gcry_mpi_cmp_ui(p->y, 0)) {
 
235
      gcry_mpi_t t1, t2;
 
236
      t1 = gcry_mpi_snew(0);
 
237
      t2 = gcry_mpi_snew(0);
 
238
      gcry_mpi_mulm(t1, p->x, p->x, dp->m);
 
239
      gcry_mpi_addm(t2, t1, t1, dp->m);
 
240
      gcry_mpi_addm(t2, t2, t1, dp->m);
 
241
      gcry_mpi_mulm(t1, p->z, p->z, dp->m);
 
242
      gcry_mpi_mulm(t1, t1, t1, dp->m);
 
243
      gcry_mpi_mulm(t1, t1, dp->a, dp->m);
 
244
      gcry_mpi_addm(t1, t1, t2, dp->m);
 
245
      gcry_mpi_mulm(p->z, p->z, p->y, dp->m);
 
246
      gcry_mpi_addm(p->z, p->z, p->z, dp->m);
 
247
      gcry_mpi_mulm(p->y, p->y, p->y, dp->m);
 
248
      gcry_mpi_addm(p->y, p->y, p->y, dp->m);
 
249
      gcry_mpi_mulm(t2, p->x, p->y, dp->m);
 
250
      gcry_mpi_addm(t2, t2, t2, dp->m);
 
251
      gcry_mpi_mulm(p->x, t1, t1, dp->m);
 
252
      gcry_mpi_subm(p->x, p->x, t2, dp->m);
 
253
      gcry_mpi_subm(p->x, p->x, t2, dp->m);
 
254
      gcry_mpi_subm(t2, t2, p->x, dp->m);
 
255
      gcry_mpi_mulm(t1, t1, t2, dp->m);
 
256
      gcry_mpi_mulm(t2, p->y, p->y, dp->m);
 
257
      gcry_mpi_addm(t2, t2, t2, dp->m);
 
258
      gcry_mpi_subm(p->y, t1, t2, dp->m);
 
259
      gcry_mpi_release(t1);
 
260
      gcry_mpi_release(t2);
 
261
    }
 
262
    else
 
263
      gcry_mpi_set_ui(p->z, 0);
 
264
  }
 
265
}
 
266
 
 
267
void jacobian_affine_point_add(struct jacobian_point *p1, 
 
268
                               const struct affine_point *p2,
 
269
                               const struct domain_params *dp)
 
270
{
 
271
  if (! point_is_zero(p2)) {
 
272
    if (gcry_mpi_cmp_ui(p1->z, 0)) {
 
273
      gcry_mpi_t t1, t2, t3;
 
274
      t1 = gcry_mpi_snew(0);
 
275
      t2 = gcry_mpi_snew(0);
 
276
      gcry_mpi_mulm(t1, p1->z, p1->z, dp->m);
 
277
      gcry_mpi_mulm(t2, t1, p2->x, dp->m);
 
278
      gcry_mpi_mulm(t1, t1, p1->z, dp->m);
 
279
      gcry_mpi_mulm(t1, t1, p2->y, dp->m);
 
280
      if (! gcry_mpi_cmp(p1->x, t2)) {
 
281
        if (! gcry_mpi_cmp(p1->y, t1))
 
282
          jacobian_double(p1, dp);
 
283
        else
 
284
          jacobian_load_zero(p1);
 
285
      }
 
286
      else {
 
287
        t3 = gcry_mpi_snew(0);
 
288
        gcry_mpi_subm(p1->x, p1->x, t2, dp->m);
 
289
        gcry_mpi_subm(p1->y, p1->y, t1, dp->m);
 
290
        gcry_mpi_mulm(p1->z, p1->z, p1->x, dp->m);
 
291
        gcry_mpi_mulm(t3, p1->x, p1->x, dp->m);
 
292
        gcry_mpi_mulm(t2, t2, t3, dp->m);
 
293
        gcry_mpi_mulm(t3, t3, p1->x, dp->m);
 
294
        gcry_mpi_mulm(t1, t1, t3, dp->m);
 
295
        gcry_mpi_mulm(p1->x, p1->y, p1->y, dp->m);
 
296
        gcry_mpi_subm(p1->x, p1->x, t3, dp->m);
 
297
        gcry_mpi_subm(p1->x, p1->x, t2, dp->m);
 
298
        gcry_mpi_subm(p1->x, p1->x, t2, dp->m);
 
299
        gcry_mpi_subm(t2, t2, p1->x, dp->m);
 
300
        gcry_mpi_mulm(p1->y, p1->y, t2, dp->m);
 
301
        gcry_mpi_subm(p1->y, p1->y, t1, dp->m);
 
302
        gcry_mpi_release(t3);
 
303
      }
 
304
      gcry_mpi_release(t1);
 
305
      gcry_mpi_release(t2);
 
306
    }
 
307
    else
 
308
      jacobian_load_affine(p1, p2);
 
309
  }
 
310
}
 
311
 
 
312
struct affine_point jacobian_to_affine(const struct jacobian_point *p,
 
313
                                       const struct domain_params *dp)
 
314
{
 
315
  struct affine_point r = point_new();
 
316
  if (gcry_mpi_cmp_ui(p->z, 0)) {
 
317
    gcry_mpi_t h;
 
318
    h = gcry_mpi_snew(0);
 
319
    gcry_mpi_invm(h, p->z, dp->m);
 
320
    gcry_mpi_mulm(r.y, h, h, dp->m);
 
321
    gcry_mpi_mulm(r.x, p->x, r.y, dp->m);
 
322
    gcry_mpi_mulm(r.y, r.y, h, dp->m);
 
323
    gcry_mpi_mulm(r.y, r.y, p->y, dp->m);
 
324
    gcry_mpi_release(h);
 
325
  }
 
326
  return r;
 
327
}
 
328
 
 
329
/******************************************************************************/
 
330
 
 
331
/* Algorithm 3.27 in the "Guide to Elliptic Curve Cryptography"               */
 
332
 
 
333
#if 0
 
334
 
 
335
struct affine_point pointmul(const struct affine_point *p,
 
336
                             const gcry_mpi_t exp, 
 
337
                             const struct domain_params *dp)
 
338
{
 
339
  struct affine_point r = point_new();
 
340
  int n = gcry_mpi_get_nbits(exp);
 
341
  while (n) {
 
342
    point_double(&r, dp);
 
343
    if (gcry_mpi_test_bit(exp, --n))
 
344
      point_add(&r, p, dp);
 
345
  }
 
346
  assert(point_on_curve(&r, dp));
 
347
  return r;
 
348
}
 
349
 
 
350
#else
 
351
 
 
352
struct affine_point pointmul(const struct affine_point *p,
 
353
                             const gcry_mpi_t exp, 
 
354
                             const struct domain_params *dp)
 
355
{
 
356
  struct jacobian_point r = jacobian_new();
 
357
  struct affine_point R;
 
358
  int n = gcry_mpi_get_nbits(exp);
 
359
  while (n) {
 
360
    jacobian_double(&r, dp);
 
361
    if (gcry_mpi_test_bit(exp, --n))
 
362
      jacobian_affine_point_add(&r, p, dp);
 
363
  }
 
364
  R = jacobian_to_affine(&r, dp);
 
365
  jacobian_release(&r);
 
366
  assert(point_on_curve(&R, dp));
 
367
  return R;
 
368
}
 
369
 
 
370
#endif
 
371
 
 
372
/******************************************************************************/
 
373
 
 
374
/* Algorithm 4.26 in the "Guide to Elliptic Curve Cryptography"               */
 
375
int embedded_key_validation(const struct affine_point *p,
 
376
                            const struct domain_params *dp)
 
377
{
 
378
  if (gcry_mpi_cmp_ui(p->x, 0) < 0 || gcry_mpi_cmp(p->x, dp->m) >= 0 ||
 
379
      gcry_mpi_cmp_ui(p->y, 0) < 0 || gcry_mpi_cmp(p->y, dp->m) >= 0)
 
380
    return 0;
 
381
  return ! point_is_zero(p) && point_on_curve(p, dp);
 
382
}
 
383
 
 
384
/* Algorithm 4.25 in the "Guide to Elliptic Curve Cryptography"               */
 
385
int full_key_validation(const struct affine_point *p,
 
386
                        const struct domain_params *dp)
 
387
{
 
388
  if (! embedded_key_validation(p, dp))
 
389
    return 0;
 
390
  if (dp->cofactor != 1) {
 
391
    struct affine_point bp;
 
392
    int res;
 
393
    bp = pointmul(p, dp->order, dp);
 
394
    res = point_is_zero(&bp);
 
395
    point_release(&bp);
 
396
    return res;
 
397
  }
 
398
  else
 
399
    return 1;
 
400
}