blob: bf570fe16cbc2a62006ca6859df72004e21f19ab [file] [log] [blame]
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +01001/*
2 * Elliptic curves over GF(p)
3 *
4 * Copyright (C) 2012, Brainspark B.V.
5 *
6 * This file is part of PolarSSL (http://www.polarssl.org)
7 * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8 *
9 * All rights reserved.
10 *
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2 of the License, or
14 * (at your option) any later version.
15 *
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License along
22 * with this program; if not, write to the Free Software Foundation, Inc.,
23 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 */
25
26/*
27 * References:
28 *
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +010029 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +010030 * Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
31 */
32
33#include "polarssl/config.h"
34
35#if defined(POLARSSL_ECP_C)
36
37#include "polarssl/ecp.h"
38
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +010039/*
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +010040 * Initialize (the components of) a point
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +010041 */
42void ecp_point_init( ecp_point *pt )
43{
44 if( pt == NULL )
45 return;
46
47 pt->is_zero = 1;
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +010048 mpi_init( &pt->X );
49 mpi_init( &pt->Y );
50}
51
52/*
53 * Initialize (the components of) a group
54 */
55void ecp_group_init( ecp_group *grp )
56{
57 if( grp == NULL )
58 return;
59
60 mpi_init( &grp->P );
61 mpi_init( &grp->B );
62 ecp_point_init( &grp->G );
63 mpi_init( &grp->N );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +010064}
65
66/*
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +010067 * Unallocate (the components of) a point
68 */
69void ecp_point_free( ecp_point *pt )
70{
71 if( pt == NULL )
72 return;
73
Manuel Pégourié-Gonnard5179e462012-10-31 19:37:54 +010074 pt->is_zero = 1;
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +010075 mpi_free( &( pt->X ) );
76 mpi_free( &( pt->Y ) );
77}
78
79/*
80 * Unallocate (the components of) a group
81 */
82void ecp_group_free( ecp_group *grp )
83{
84 if( grp == NULL )
85 return;
86
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +010087 mpi_free( &grp->P );
88 mpi_free( &grp->B );
89 ecp_point_free( &grp->G );
90 mpi_free( &grp->N );
Manuel Pégourié-Gonnard1e8c8ec2012-10-31 19:24:21 +010091}
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +010092
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +010093/*
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +010094 * Set point to zero
95 */
96void ecp_set_zero( ecp_point *pt )
97{
98 pt->is_zero = 1;
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +010099 mpi_free( &pt->X );
100 mpi_free( &pt->Y );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100101}
102
103/*
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +0100104 * Copy the contents of Q into P
105 */
106int ecp_copy( ecp_point *P, const ecp_point *Q )
107{
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100108 int ret = 0;
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +0100109
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100110 if( Q->is_zero ) {
111 ecp_set_zero( P );
112 return( ret );
113 }
114
Manuel Pégourié-Gonnard883f3132012-11-02 09:40:25 +0100115 P->is_zero = Q->is_zero;
116 MPI_CHK( mpi_copy( &P->X, &Q->X ) );
117 MPI_CHK( mpi_copy( &P->Y, &Q->Y ) );
118
119cleanup:
120 return( ret );
121}
Manuel Pégourié-Gonnard5179e462012-10-31 19:37:54 +0100122
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100123/*
Manuel Pégourié-Gonnard847395a2012-11-05 13:13:44 +0100124 * Import a non-zero point from ASCII strings
125 */
126int ecp_point_read_string( ecp_point *P, int radix,
127 const char *x, const char *y )
128{
129 int ret = 0;
130
131 P->is_zero = 0;
132 MPI_CHK( mpi_read_string( &P->X, radix, x ) );
133 MPI_CHK( mpi_read_string( &P->Y, radix, y ) );
134
135cleanup:
136 return( ret );
137}
138
139/*
140 * Import an ECP group from ASCII strings
141 */
142int ecp_group_read_string( ecp_group *grp, int radix,
143 const char *p, const char *b,
144 const char *gx, const char *gy, const char *n)
145{
146 int ret = 0;
147
148 MPI_CHK( mpi_read_string( &grp->P, radix, p ) );
149 MPI_CHK( mpi_read_string( &grp->B, radix, b ) );
150 MPI_CHK( ecp_point_read_string( &grp->G, radix, gx, gy ) );
151 MPI_CHK( mpi_read_string( &grp->N, radix, n ) );
152
153cleanup:
154 return( ret );
155}
156
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100157#define dbg(X) printf(#X " = %s%lu\n", X.s < 0 ? "-" : "", X.p[0])
158
Manuel Pégourié-Gonnard847395a2012-11-05 13:13:44 +0100159/*
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100160 * Addition: R = P + Q, generic case (P != Q, P != 0, Q != 0, R != 0)
161 * Cf SEC1 v2 p. 7, item 4
162 */
163static int ecp_add_generic( const ecp_group *grp, ecp_point *R,
164 const ecp_point *P, const ecp_point *Q )
165{
166 int ret = 0;
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100167 mpi DX, DY, K, L, LL, X, Y;
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100168
169 mpi_init( &DX ); mpi_init( &DY ); mpi_init( &K ); mpi_init( &L );
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100170 mpi_init( &LL ); mpi_init( &X ); mpi_init( &Y );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100171
172 /*
173 * L = (Q.Y - P.Y) / (Q.X - P.X) mod p
174 */
175 MPI_CHK( mpi_sub_mpi( &DY, &Q->Y, &P->Y ) );
176 MPI_CHK( mpi_sub_mpi( &DX, &Q->X, &P->X ) );
177 MPI_CHK( mpi_inv_mod( &K, &DX, &grp->P ) );
178 MPI_CHK( mpi_mul_mpi( &K, &K, &DY ) );
179 MPI_CHK( mpi_mod_mpi( &L, &K, &grp->P ) );
180
181 /*
182 * LL = L^2 mod p
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100183 */
184 MPI_CHK( mpi_mul_mpi( &LL, &L, &L ) );
185 MPI_CHK( mpi_mod_mpi( &LL, &LL, &grp->P ) );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100186
187 /*
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100188 * X = L^2 - P.X - Q.X
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100189 */
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100190 MPI_CHK( mpi_sub_mpi( &X, &LL, &P->X ) );
191 MPI_CHK( mpi_sub_mpi( &X, &X, &Q->X ) );
192
193 /*
194 * Y = L * (P.X - X) - P.Y
195 */
196 MPI_CHK( mpi_sub_mpi( &Y, &P->X, &X) );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100197 MPI_CHK( mpi_mul_mpi( &Y, &Y, &L ) );
198 MPI_CHK( mpi_sub_mpi( &Y, &Y, &P->Y ) );
199
200 /*
201 * R = (X mod p, Y mod p)
202 */
203 R->is_zero = 0;
204 MPI_CHK( mpi_mod_mpi( &R->X, &X, &grp->P ) );
205 MPI_CHK( mpi_mod_mpi( &R->Y, &Y, &grp->P ) );
206
207cleanup:
208
209 mpi_free( &DX ); mpi_free( &DY ); mpi_free( &K ); mpi_free( &L );
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100210 mpi_free( &LL ); mpi_free( &X ); mpi_free( &Y );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100211
212 return( ret );
213}
214
215/*
216 * Doubling: R = 2 * P, generic case (P != 0, R != 0)
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100217 * Cf SEC1 v2 p. 7, item 5
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100218 */
219static int ecp_double_generic( const ecp_group *grp, ecp_point *R,
220 const ecp_point *P )
221{
222 int ret = 0;
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100223 mpi LN, LD, K, L, LL, X, Y;
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100224
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100225 mpi_init( &LN ); mpi_init( &LD ); mpi_init( &K ); mpi_init( &L );
226 mpi_init( &LL ); mpi_init( &X ); mpi_init( &Y );
227
228 /*
229 * L = 3 (P.X - 1) (P.X + 1) / (2 P.Y) mod p
230 */
231 MPI_CHK( mpi_copy( &LD, &P->Y ) );
232 MPI_CHK( mpi_shift_l( &LD, 1 ) );
233 MPI_CHK( mpi_inv_mod( &K, &LD, &grp->P ) );
234 MPI_CHK( mpi_mul_int( &K, &K, 3 ) );
235 MPI_CHK( mpi_sub_int( &LN, &P->X, 1 ) );
236 MPI_CHK( mpi_mul_mpi( &K, &K, &LN ) );
237 MPI_CHK( mpi_add_int( &LN, &P->X, 1 ) );
238 MPI_CHK( mpi_mul_mpi( &K, &K, &LN ) );
239 MPI_CHK( mpi_mod_mpi( &L, &K, &grp->P ) );
240
241 /*
242 * LL = L^2 mod p
243 */
244 MPI_CHK( mpi_mul_mpi( &LL, &L, &L ) );
245 MPI_CHK( mpi_mod_mpi( &LL, &LL, &grp->P ) );
246
247 /*
248 * X = L^2 - 2 * P.X
249 */
250 MPI_CHK( mpi_sub_mpi( &X, &LL, &P->X ) );
251 MPI_CHK( mpi_sub_mpi( &X, &X, &P->X ) );
252
253 /*
254 * Y = L * (P.X - X) - P.Y
255 */
256 MPI_CHK( mpi_sub_mpi( &Y, &P->X, &X) );
257 MPI_CHK( mpi_mul_mpi( &Y, &Y, &L ) );
258 MPI_CHK( mpi_sub_mpi( &Y, &Y, &P->Y ) );
259
260 /*
261 * R = (X mod p, Y mod p)
262 */
263 R->is_zero = 0;
264 MPI_CHK( mpi_mod_mpi( &R->X, &X, &grp->P ) );
265 MPI_CHK( mpi_mod_mpi( &R->Y, &Y, &grp->P ) );
266
267cleanup:
268
Manuel Pégourié-Gonnardb4ab8a82012-11-06 18:13:32 +0100269 mpi_free( &LN ); mpi_free( &LD ); mpi_free( &K ); mpi_free( &L );
270 mpi_free( &LL ); mpi_free( &X ); mpi_free( &Y );
Manuel Pégourié-Gonnardae180d02012-11-02 18:14:40 +0100271
272 return( ret );
273}
274
275/*
276 * Addition: R = P + Q, cf p. 7 of SEC1 v2
277 */
278int ecp_add( const ecp_group *grp, ecp_point *R,
279 const ecp_point *P, const ecp_point *Q )
280{
281 int ret = 0;
282
283 if( P->is_zero )
284 {
285 ret = ecp_copy( R, Q );
286 }
287 else if( Q->is_zero )
288 {
289 ret = ecp_copy( R, P );
290 }
291 else if( mpi_cmp_mpi( &P->X, &Q->X ) != 0 )
292 {
293 ret = ecp_add_generic( grp, R, P, Q );
294 }
295 else if( mpi_cmp_int( &P->Y, 0 ) == 0 ||
296 mpi_cmp_mpi( &P->Y, &Q->Y ) != 0 )
297 {
298 ecp_set_zero( R );
299 }
300 else
301 {
302 /*
303 * P == Q
304 */
305 ret = ecp_double_generic( grp, R, P );
306 }
307
308 return ret;
309}
310
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +0100311#if defined(POLARSSL_SELF_TEST)
312
313/*
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100314 * Return true iff P and Q are the same point
315 */
316static int ecp_point_eq( const ecp_point *P, const ecp_point *Q )
317{
318 if( P->is_zero || Q->is_zero )
319 return( P->is_zero && Q->is_zero );
320
321 return( mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&
322 mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 );
323}
324
325/*
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100326 * Print a point assuming its coordinates are small
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100327 */
328static void ecp_point_print( const ecp_point *P )
329{
330 if( P->is_zero )
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100331 printf( "zero\n" );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100332 else
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100333 printf( "(%lu, %lu)\n", P->X.p[0], P->Y.p[0] );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100334}
335
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100336/*
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +0100337 * Checkup routine
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100338 *
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100339 * Data for basic tests with small values gathered from
340 * http://danher6.100webspace.net/ecc/#EFp_interactivo and double-checked
341 * using Pari-GP.
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +0100342 */
343int ecp_self_test( int verbose )
344{
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100345 int ret = 0;
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100346 unsigned i;
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100347 ecp_group grp;
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100348 ecp_point O, A, B, C, D, E, F, G, H, TMP;
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100349 ecp_point *add_tbl[][3] =
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100350 {
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100351 {&O, &O, &O}, {&O, &A, &A}, {&A, &O, &A},
352 {&A, &A, &O}, {&B, &C, &O}, {&C, &B, &O},
353 {&A, &D, &E}, {&D, &A, &E},
354 {&B, &D, &F}, {&D, &B, &F},
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100355 {&D, &D, &G}, {&B, &B, &H},
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100356 };
357
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100358 ecp_group_init( &grp );
359 ecp_point_init( &O ); ecp_point_init( &A ); ecp_point_init( &B );
360 ecp_point_init( &C ); ecp_point_init( &D ); ecp_point_init( &E );
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100361 ecp_point_init( &F ); ecp_point_init( &G ); ecp_point_init( &H );
362 ecp_point_init( &TMP );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100363
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100364 ecp_set_zero( &O );
365 MPI_CHK( ecp_group_read_string( &grp, 10, "47", "4", "17", "42", "13" ) );
366 MPI_CHK( ecp_point_read_string( &A, 10, "13", "0" ) );
367 MPI_CHK( ecp_point_read_string( &B, 10, "14", "11" ) );
368 MPI_CHK( ecp_point_read_string( &C, 10, "14", "36" ) );
369 MPI_CHK( ecp_point_read_string( &D, 10, "37", "31" ) );
370 MPI_CHK( ecp_point_read_string( &E, 10, "34", "14" ) );
371 MPI_CHK( ecp_point_read_string( &F, 10, "45", "7" ) );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100372 MPI_CHK( ecp_point_read_string( &G, 10, "21", "32" ) );
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100373 MPI_CHK( ecp_point_read_string( &H, 10, "27", "30" ) );
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100374
375 if( verbose != 0 )
376 printf( " ECP test #1 (ecp_add): " );
377
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100378 for( i = 0; i < sizeof( add_tbl ) / sizeof( add_tbl[0] ); i++ )
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100379 {
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100380 MPI_CHK( ecp_add( &grp, &TMP, add_tbl[i][0], add_tbl[i][1] ) );
381 if( ! ecp_point_eq( &TMP, add_tbl[i][2] ) )
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100382 {
383 if( verbose != 0 )
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100384 {
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100385 printf(" failed (%u)\n", i );
386 printf( " GOT: " );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100387 ecp_point_print( &TMP );
Manuel Pégourié-Gonnardab38b702012-11-05 17:34:55 +0100388 printf( " EXPECTED: " );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100389 ecp_point_print( add_tbl[i][2] );
390 }
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100391
392 return( 1 );
393 }
394 }
395
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100396 if (verbose != 0 )
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100397 printf( "passed\n" );
Manuel Pégourié-Gonnardb505c272012-11-05 17:27:54 +0100398
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100399cleanup:
400
401 if( ret != 0 && verbose != 0 )
402 printf( "Unexpected error, return code = %08X\n", ret );
403
404 ecp_group_free( &grp );
405 ecp_point_free( &O ); ecp_point_free( &A ); ecp_point_free( &B );
406 ecp_point_free( &C ); ecp_point_free( &D ); ecp_point_free( &E );
Manuel Pégourié-Gonnardde532ee2012-11-06 16:10:47 +0100407 ecp_point_free( &F ); ecp_point_free( &G ); ecp_point_free( &H );
408 ecp_point_free( &TMP );
Manuel Pégourié-Gonnardd0dc6312012-11-05 16:28:33 +0100409
410 if( verbose != 0 )
411 printf( "\n" );
412
413 return( ret );
Manuel Pégourié-Gonnard39d2adb2012-10-31 09:26:55 +0100414}
415
416#endif
417
418#endif