2
* seccure - Copyright 2009 B. Poettering
4
* Maintained by R. Tyler Ballance <tyler@slide.com>
6
* This library is free software; you can redistribute it and/or
7
* modify it under the terms of the GNU Lesser General Public
8
* License as published by the Free Software Foundation; either
9
* version 2.1 of the License, or (at your option) any later version.
11
* This library 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 GNU
14
* 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 library; if not, write to the Free Software
18
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22
* SECCURE Elliptic Curve Crypto Utility for Reliable Encryption
24
* Current homepage: http://slideinc.github.com/pyecc
25
* Original homepage: http://point-at-infinity.org/seccure/
28
* seccure implements a selection of asymmetric algorithms based on
29
* elliptic curve cryptography (ECC). See the manpage or the project's
30
* homepage for further details.
32
* This code links against the GNU gcrypt library "libgcrypt" (which
33
* is part of the GnuPG project). Use the included Makefile to build
36
* Report bugs to: http://github.com/rtyler/PyECC/issues
44
#include "numtheory.h"
46
/******************************************************************************/
48
/* Chapter 3.1.2 in the "Guide to Elliptic Curve Cryptography" */
50
struct affine_point point_new(void)
52
struct affine_point r;
53
r.x = gcry_mpi_snew(0);
54
r.y = gcry_mpi_snew(0);
58
void point_release(struct affine_point *p)
60
gcry_mpi_release(p->x);
61
gcry_mpi_release(p->y);
66
void point_set(struct affine_point *p1, const struct affine_point *p2)
68
gcry_mpi_set(p1->x, p2->x);
69
gcry_mpi_set(p1->y, p2->y);
72
void point_load_zero(struct affine_point *p)
74
gcry_mpi_set_ui(p->x, 0);
75
gcry_mpi_set_ui(p->y, 0);
78
int point_is_zero(const struct affine_point *p)
80
return ! gcry_mpi_cmp_ui(p->x, 0) && ! gcry_mpi_cmp_ui(p->y, 0);
83
int point_on_curve(const struct affine_point *p, const struct domain_params *dp)
86
if (! (res = point_is_zero(p))) {
88
h1 = gcry_mpi_snew(0);
89
h2 = gcry_mpi_snew(0);
90
gcry_mpi_mulm(h1, p->x, p->x, dp->m);
91
gcry_mpi_addm(h1, h1, dp->a, dp->m);
92
gcry_mpi_mulm(h1, h1, p->x, dp->m);
93
gcry_mpi_addm(h1, h1, dp->b, dp->m);
94
gcry_mpi_mulm(h2, p->y, p->y, dp->m);
95
res = ! gcry_mpi_cmp(h1, h2);
102
int point_compress(const struct affine_point *p)
104
return gcry_mpi_test_bit(p->y, 0);
107
int point_decompress(struct affine_point *p, const gcry_mpi_t x, int yflag,
108
const struct domain_params *dp)
112
h = gcry_mpi_snew(0);
113
y = gcry_mpi_snew(0);
114
gcry_mpi_mulm(h, x, x, dp->m);
115
gcry_mpi_addm(h, h, dp->a, dp->m);
116
gcry_mpi_mulm(h, h, x, dp->m);
117
gcry_mpi_addm(h, h, dp->b, dp->m);
118
if ((res = mod_root(y, h, dp->m)))
119
if ((res = (gcry_mpi_cmp_ui(y, 0) || ! yflag))) {
120
p->x = gcry_mpi_snew(0);
121
p->y = gcry_mpi_snew(0);
122
gcry_mpi_set(p->x, x);
123
if (gcry_mpi_test_bit(y, 0) == yflag)
124
gcry_mpi_set(p->y, y);
126
gcry_mpi_sub(p->y, dp->m, y);
127
rc = point_on_curve(p, dp);
135
void point_double(struct affine_point *p, const struct domain_params *dp)
137
if (gcry_mpi_cmp_ui(p->y, 0)) {
139
t1 = gcry_mpi_snew(0);
140
t2 = gcry_mpi_snew(0);
141
gcry_mpi_mulm(t2, p->x, p->x, dp->m);
142
gcry_mpi_addm(t1, t2, t2, dp->m);
143
gcry_mpi_addm(t1, t1, t2, dp->m);
144
gcry_mpi_addm(t1, t1, dp->a, dp->m);
145
gcry_mpi_addm(t2, p->y, p->y, dp->m);
146
gcry_mpi_invm(t2, t2, dp->m);
147
gcry_mpi_mulm(t1, t1, t2, dp->m);
148
gcry_mpi_mulm(t2, t1, t1, dp->m);
149
gcry_mpi_subm(t2, t2, p->x, dp->m);
150
gcry_mpi_subm(t2, t2, p->x, dp->m);
151
gcry_mpi_subm(p->x, p->x, t2, dp->m);
152
gcry_mpi_mulm(t1, t1, p->x, dp->m);
153
gcry_mpi_subm(p->y, t1, p->y, dp->m);
154
gcry_mpi_set(p->x, t2);
155
gcry_mpi_release(t1);
156
gcry_mpi_release(t2);
159
gcry_mpi_set_ui(p->x, 0);
162
void point_add(struct affine_point *p1, const struct affine_point *p2,
163
const struct domain_params *dp)
165
if (! point_is_zero(p2)) {
166
if (! point_is_zero(p1)) {
167
if (! gcry_mpi_cmp(p1->x, p2->x)) {
168
if (! gcry_mpi_cmp(p1->y, p2->y))
169
point_double(p1, dp);
175
t = gcry_mpi_snew(0);
176
gcry_mpi_subm(t, p1->y, p2->y, dp->m);
177
gcry_mpi_subm(p1->y, p1->x, p2->x, dp->m);
178
gcry_mpi_invm(p1->y, p1->y, dp->m);
179
gcry_mpi_mulm(p1->y, t, p1->y, dp->m);
180
gcry_mpi_mulm(t, p1->y, p1->y, dp->m);
181
gcry_mpi_addm(p1->x, p1->x, p2->x, dp->m);
182
gcry_mpi_subm(p1->x, t, p1->x, dp->m);
183
gcry_mpi_subm(t, p2->x, p1->x, dp->m);
184
gcry_mpi_mulm(p1->y, p1->y, t, dp->m);
185
gcry_mpi_subm(p1->y, p1->y, p2->y, dp->m);
194
/******************************************************************************/
196
/* Chapter 3.2.2 in the "Guide to Elliptic Curve Cryptography" */
198
struct jacobian_point jacobian_new(void)
200
struct jacobian_point r;
201
r.x = gcry_mpi_snew(0);
202
r.y = gcry_mpi_snew(0);
203
r.z = gcry_mpi_snew(0);
207
void jacobian_release(struct jacobian_point *p)
209
gcry_mpi_release(p->x);
210
gcry_mpi_release(p->y);
211
gcry_mpi_release(p->z);
214
void jacobian_load_affine(struct jacobian_point *p1,
215
const struct affine_point *p2)
217
if (! point_is_zero(p2)) {
218
gcry_mpi_set(p1->x, p2->x);
219
gcry_mpi_set(p1->y, p2->y);
220
gcry_mpi_set_ui(p1->z, 1);
223
gcry_mpi_set_ui(p1->z, 0);
226
void jacobian_load_zero(struct jacobian_point *p)
228
gcry_mpi_set_ui(p->z, 0);
231
int jacobian_is_zero(const struct jacobian_point *p)
233
return ! gcry_mpi_cmp_ui(p->z, 0);
236
void jacobian_double(struct jacobian_point *p, const struct domain_params *dp)
238
if (gcry_mpi_cmp_ui(p->z, 0)) {
239
if (gcry_mpi_cmp_ui(p->y, 0)) {
241
t1 = gcry_mpi_snew(0);
242
t2 = gcry_mpi_snew(0);
243
gcry_mpi_mulm(t1, p->x, p->x, dp->m);
244
gcry_mpi_addm(t2, t1, t1, dp->m);
245
gcry_mpi_addm(t2, t2, t1, dp->m);
246
gcry_mpi_mulm(t1, p->z, p->z, dp->m);
247
gcry_mpi_mulm(t1, t1, t1, dp->m);
248
gcry_mpi_mulm(t1, t1, dp->a, dp->m);
249
gcry_mpi_addm(t1, t1, t2, dp->m);
250
gcry_mpi_mulm(p->z, p->z, p->y, dp->m);
251
gcry_mpi_addm(p->z, p->z, p->z, dp->m);
252
gcry_mpi_mulm(p->y, p->y, p->y, dp->m);
253
gcry_mpi_addm(p->y, p->y, p->y, dp->m);
254
gcry_mpi_mulm(t2, p->x, p->y, dp->m);
255
gcry_mpi_addm(t2, t2, t2, dp->m);
256
gcry_mpi_mulm(p->x, t1, t1, dp->m);
257
gcry_mpi_subm(p->x, p->x, t2, dp->m);
258
gcry_mpi_subm(p->x, p->x, t2, dp->m);
259
gcry_mpi_subm(t2, t2, p->x, dp->m);
260
gcry_mpi_mulm(t1, t1, t2, dp->m);
261
gcry_mpi_mulm(t2, p->y, p->y, dp->m);
262
gcry_mpi_addm(t2, t2, t2, dp->m);
263
gcry_mpi_subm(p->y, t1, t2, dp->m);
264
gcry_mpi_release(t1);
265
gcry_mpi_release(t2);
268
gcry_mpi_set_ui(p->z, 0);
272
void jacobian_affine_point_add(struct jacobian_point *p1,
273
const struct affine_point *p2,
274
const struct domain_params *dp)
276
if (! point_is_zero(p2)) {
277
if (gcry_mpi_cmp_ui(p1->z, 0)) {
278
gcry_mpi_t t1, t2, t3;
279
t1 = gcry_mpi_snew(0);
280
t2 = gcry_mpi_snew(0);
281
gcry_mpi_mulm(t1, p1->z, p1->z, dp->m);
282
gcry_mpi_mulm(t2, t1, p2->x, dp->m);
283
gcry_mpi_mulm(t1, t1, p1->z, dp->m);
284
gcry_mpi_mulm(t1, t1, p2->y, dp->m);
285
if (! gcry_mpi_cmp(p1->x, t2)) {
286
if (! gcry_mpi_cmp(p1->y, t1))
287
jacobian_double(p1, dp);
289
jacobian_load_zero(p1);
292
t3 = gcry_mpi_snew(0);
293
gcry_mpi_subm(p1->x, p1->x, t2, dp->m);
294
gcry_mpi_subm(p1->y, p1->y, t1, dp->m);
295
gcry_mpi_mulm(p1->z, p1->z, p1->x, dp->m);
296
gcry_mpi_mulm(t3, p1->x, p1->x, dp->m);
297
gcry_mpi_mulm(t2, t2, t3, dp->m);
298
gcry_mpi_mulm(t3, t3, p1->x, dp->m);
299
gcry_mpi_mulm(t1, t1, t3, dp->m);
300
gcry_mpi_mulm(p1->x, p1->y, p1->y, dp->m);
301
gcry_mpi_subm(p1->x, p1->x, t3, dp->m);
302
gcry_mpi_subm(p1->x, p1->x, t2, dp->m);
303
gcry_mpi_subm(p1->x, p1->x, t2, dp->m);
304
gcry_mpi_subm(t2, t2, p1->x, dp->m);
305
gcry_mpi_mulm(p1->y, p1->y, t2, dp->m);
306
gcry_mpi_subm(p1->y, p1->y, t1, dp->m);
307
gcry_mpi_release(t3);
309
gcry_mpi_release(t1);
310
gcry_mpi_release(t2);
313
jacobian_load_affine(p1, p2);
317
struct affine_point jacobian_to_affine(const struct jacobian_point *p,
318
const struct domain_params *dp)
320
struct affine_point r = point_new();
321
if (gcry_mpi_cmp_ui(p->z, 0)) {
323
h = gcry_mpi_snew(0);
324
gcry_mpi_invm(h, p->z, dp->m);
325
gcry_mpi_mulm(r.y, h, h, dp->m);
326
gcry_mpi_mulm(r.x, p->x, r.y, dp->m);
327
gcry_mpi_mulm(r.y, r.y, h, dp->m);
328
gcry_mpi_mulm(r.y, r.y, p->y, dp->m);
334
/******************************************************************************/
336
/* Algorithm 3.27 in the "Guide to Elliptic Curve Cryptography" */
340
struct affine_point pointmul(const struct affine_point *p,
341
const gcry_mpi_t exp,
342
const struct domain_params *dp)
344
struct affine_point r = point_new();
345
int n = gcry_mpi_get_nbits(exp);
347
point_double(&r, dp);
348
if (gcry_mpi_test_bit(exp, --n))
349
point_add(&r, p, dp);
351
assert(point_on_curve(&r, dp));
357
struct affine_point pointmul(const struct affine_point *p,
358
const gcry_mpi_t exp,
359
const struct domain_params *dp)
361
struct jacobian_point r = jacobian_new();
362
struct affine_point R;
363
int n = gcry_mpi_get_nbits(exp);
366
jacobian_double(&r, dp);
367
if (gcry_mpi_test_bit(exp, --n))
368
jacobian_affine_point_add(&r, p, dp);
370
R = jacobian_to_affine(&r, dp);
371
jacobian_release(&r);
372
rc = point_on_curve(&R, dp);
379
/******************************************************************************/
381
/* Algorithm 4.26 in the "Guide to Elliptic Curve Cryptography" */
382
int embedded_key_validation(const struct affine_point *p,
383
const struct domain_params *dp)
385
if (gcry_mpi_cmp_ui(p->x, 0) < 0 || gcry_mpi_cmp(p->x, dp->m) >= 0 ||
386
gcry_mpi_cmp_ui(p->y, 0) < 0 || gcry_mpi_cmp(p->y, dp->m) >= 0)
388
return ! point_is_zero(p) && point_on_curve(p, dp);
391
/* Algorithm 4.25 in the "Guide to Elliptic Curve Cryptography" */
392
int full_key_validation(const struct affine_point *p,
393
const struct domain_params *dp)
395
if (! embedded_key_validation(p, dp))
397
if (dp->cofactor != 1) {
398
struct affine_point bp;
400
bp = pointmul(p, dp->order, dp);
401
res = point_is_zero(&bp);
added
removed
dependencies/PyECC/seccure/ecc.c
