diff options
author | Werner Koch <wk@gnupg.org> | 2007-03-28 10:47:25 +0000 |
---|---|---|
committer | Werner Koch <wk@gnupg.org> | 2007-03-28 10:47:25 +0000 |
commit | 6966f968530365a74b9141da4269245b3d393fbb (patch) | |
tree | b6ed25be944dbe662ab485154a086deb5516f8a8 | |
parent | 5c8ee46baeed3d72945729e5792213cc6850782d (diff) | |
download | libgcrypt-6966f968530365a74b9141da4269245b3d393fbb.tar.gz |
Rewrote the ECDSA implementation.
-rw-r--r-- | AUTHORS | 6 | ||||
-rw-r--r-- | cipher/ChangeLog | 10 | ||||
-rw-r--r-- | cipher/dsa.c | 2 | ||||
-rw-r--r-- | cipher/ecc.c | 1914 | ||||
-rw-r--r-- | cipher/pubkey.c | 4 | ||||
-rw-r--r-- | mpi/ChangeLog | 4 | ||||
-rw-r--r-- | mpi/Makefile.am | 3 | ||||
-rw-r--r-- | mpi/ec.c | 690 | ||||
-rw-r--r-- | src/mpi.h | 32 | ||||
-rw-r--r-- | tests/ChangeLog | 7 | ||||
-rw-r--r-- | tests/Makefile.am | 8 | ||||
-rw-r--r-- | tests/benchmark.c | 37 |
12 files changed, 1181 insertions, 1536 deletions
@@ -85,9 +85,6 @@ werner.dittmann@t-online.de (mpi/amd64, tests/mpitests.c) -FIXME: The ECC code needs an entry here. - - More credits ============ The ATH implementation (src/ath*) has been taken from GPGME and @@ -101,6 +98,9 @@ The files cipher/rndunix.c and cipher/rndw32.c are based on those files from Cryptlib. Copyright Peter Gutmann, Paul Kendall, and Chris Wedgwood 1996-1999. +The ECC code cipher/ecc.c was based on code by Sergi Blanch i Torne, +sergi at calcurco dot org. + Copyright 1998, 1999, 2000, 2001, 2002, 2003, 2006 Free Software Foundation, Inc. diff --git a/cipher/ChangeLog b/cipher/ChangeLog index 3fe17e07..747a5c2a 100644 --- a/cipher/ChangeLog +++ b/cipher/ChangeLog @@ -1,3 +1,13 @@ +2007-03-28 Werner Koch <wk@g10code.com> + + * ecc.c: Entirely rewritten with only a few traces of the old + code left. + +2007-03-26 Werner Koch <wk@g10code.com> + + * pubkey.c (gcry_pk_genkey): Increase size of SKEY array and add a + runtime bounds check. + 2007-03-23 Werner Koch <wk@g10code.com> * ecc.c (ecc_ctx_init, ecc_ctx_free, ecc_mod, ecc_mulm): New. diff --git a/cipher/dsa.c b/cipher/dsa.c index 45b638ca..bf5bf6d9 100644 --- a/cipher/dsa.c +++ b/cipher/dsa.c @@ -5,7 +5,7 @@ * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify - * it under the terms of the GNU Lesser general Public License as + * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * diff --git a/cipher/ecc.c b/cipher/ecc.c index 44f18024..b38a5d02 100644 --- a/cipher/ecc.c +++ b/cipher/ecc.c @@ -1,161 +1,89 @@ -/* ecc.c - ECElGamal Public Key encryption & ECDSA signature algorithm - * Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, - * USA. - */ - -/* TODO wk - - - Check whether we can LGPL the code. +/* ecc.c - Elliptic Curve Cryptography + Copyright (C) 2007 Free Software Foundation, Inc. - - Use affine coordinates for points with the public API and format - them in the way described by BSI's TR-03111, 5.1.3. + This file is part of Libgcrypt. + + Libgcrypt is free software; you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as + published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + Libgcrypt is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, + USA. */ + +/* This code is originally based on the Patch 0.1.6 for the gnupg + 1.4.x branch as retrieved on 2007-03-21 from + http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2 + The original authors are: + Written by + Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>, + Ramiro Moreno Chiral <ramiro at eup.udl.es> + Maintainers + Sergi Blanch i Torne + Ramiro Moreno Chiral + Mikael Mylnikov (mmr) + For use in Libgcrypt the code has been heavily modified and cleaned + up. In fact there is not much left of the orginally code except for + some variable names and the text book implementaion of the sign and + verification algorithms. The arithmetic functions have entirely + been rewritten and moved to mpi/ec.c. */ + + +/* TODO: - If we support point compression we need to decide how to compute - the keygrip it should not change due to compression. - - - mpi_mulm is quite slow which has never been a problem for the - other algorithms. However here we are using it several times in a - row and thus it is an important performance factor. - - - We use mpi_powm for x^2 mod p: Either implement a special case in - mpi_powm or check whether mpi_mulm is faster. - + the keygrip - it should not change due to compression. + - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a + special case in mpi_powm or check whether mpi_mulm is faster. -Algorithm generate 100*sign 100*verify ----------------------------------------------- -Orginal version: -ECDSA 192 bit 100ms 2630ms 5040ms -ECDSA 256 bit 120ms 2960ms 6070ms -ECDSA 384 bit 370ms 9570ms 18900ms - -Using Barrett: -ECDSA 192 bit 130ms 3050ms 5620ms -ECDSA 256 bit 140ms 3410ms 6950ms -ECDSA 384 bit 400ms 10500ms 21670ms - + - Decide whether we should hide the mpi_point_t definition. + - Support more than just ECDSA. */ -/* This code is a based on the - * Patch 0.1.6 for the gnupg 1.4.x branch - * as retrieved on 2007-03-21 from - * http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2 - * - * Written by - * Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>, - * Ramiro Moreno Chiral <ramiro at eup.udl.es> - * Maintainers - * Sergi Blanch i Torne - * Ramiro Moreno Chiral - * Mikael Mylnikov (mmr) - */ - -/* - * This module are under development, it would not have to be used - * in a production environments. It can have bugs! - * - * Made work: - * alex: found a bug over the passphrase. - * mmr: signature bug found and solved (afine conversion). - * mmr: found too many mistakes in the mathematical background transcription. - * mmr: improve the mathematical performance. - * mmr: solve ECElGamal IFP weakness. - * more polite gen_k() and its calls. - * mmr: extend the check_secret_key() - * In progress: - * gen_big_point(): Randomize the point generation. - * improve te memory uses. - * Separation between sign & encrypt keys to facility the subkeys creation. - * read & reread the code in a bug search! - * To do: - * 2-isogeny: randomize the elliptic curves. - * E(F_{2^m}) - */ #include <config.h> #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <assert.h> #include "g10lib.h" #include "mpi.h" #include "cipher.h" -/* - ECC over F_p; E(F_p) - T=(p,a,b,G,n,h) - p: big odd number - a,b: curve generators - G: Subgroup generator point - n: big int, in G order - h: cofactor - y^2=x^3+ax+b --> (Y^2)Z=X^3+aX(Z^2)+b(Z^3) - - - Q=[d]G, 1<=d<=n-1 -*/ - - -/* An object to hold a computation context. */ -struct ecc_ctx_s -{ - gcry_mpi_t m; /* The modulus - may not be modified. */ - int m_copied; /* If true, M needs to be released. */ -}; -typedef struct ecc_ctx_s *ecc_ctx_t; - - -/* Point representation in projective coordinates. */ -typedef struct -{ - gcry_mpi_t x_; - gcry_mpi_t y_; - gcry_mpi_t z_; -} point_t; - - /* Definition of a curve. */ typedef struct { - gcry_mpi_t p_; /* Prime specifying the field GF(p). */ - gcry_mpi_t a_; /* First coefficient of the Weierstrass equation. */ - gcry_mpi_t b_; /* Second coefficient of teh Weierstrass equation. */ - point_t G; /* Base point (generator). */ - gcry_mpi_t n_; /* Order of G. */ - /*gcry_mpi_t h_; =1 fixme: We will need to change this value in 2-isogeny */ -} elliptic_curve_t; /* Fixme: doubtful name */ + gcry_mpi_t p; /* Prime specifying the field GF(p). */ + gcry_mpi_t a; /* First coefficient of the Weierstrass equation. */ + gcry_mpi_t b; /* Second coefficient of the Weierstrass equation. */ + mpi_point_t G; /* Base point (generator). */ + gcry_mpi_t n; /* Order of G. */ +} elliptic_curve_t; typedef struct { elliptic_curve_t E; - point_t Q; /* Q=[d]G */ -} ECC_public_key; /* Q */ + mpi_point_t Q; /* Q = [d]G */ +} ECC_public_key; typedef struct { elliptic_curve_t E; - point_t Q; /* Q=[d]G */ + mpi_point_t Q; gcry_mpi_t d; -} ECC_secret_key; /* d */ +} ECC_secret_key; /* This static table defines all available curves. */ @@ -163,21 +91,23 @@ static const struct { const char *desc; /* Description of the curve. */ unsigned int nbits; /* Number of bits. */ - const char *p, *a, *b, *n; /* Parameters. */ - const char *g_x, *g_y; /* G_z is always 1. */ -} domain_parms[] = + const char *p; /* Order of the prime field. */ + const char *a, *b; /* The coefficients. */ + const char *n; /* The order of the base point. */ + const char *g_x, *g_y; /* Base point. */ +} domain_parms[] = { - { + { "NIST P-192", 192, "0xfffffffffffffffffffffffffffffffeffffffffffffffff", "0xfffffffffffffffffffffffffffffffefffffffffffffffc", "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", "0xffffffffffffffffffffffff99def836146bc9b1b4d22831", - + "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811" }, - { + { "NIST P-224", 224, "0xffffffffffffffffffffffffffffffff000000000000000000000001", "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe", @@ -187,13 +117,13 @@ static const struct "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34" }, - { + { "NIST P-256", 256, "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff", "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc", "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", - + "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5" }, @@ -202,7 +132,7 @@ static const struct "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" "ffffffff0000000000000000ffffffff", "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" - "ffffffff0000000000000000fffffffc", + "ffffffff0000000000000000fffffffc", "0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a" "c656398d8a2ed19d2a85c8edd3ec2aef", "0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf" @@ -238,20 +168,21 @@ static void (*progress_cb) (void *, const char*, int, int, int); static void *progress_cb_data; +#define point_init(a) _gcry_mpi_ec_point_init ((a)) +#define point_free(a) _gcry_mpi_ec_point_free ((a)) + /* Local prototypes. */ -static gcry_mpi_t gen_k (gcry_mpi_t p, int secure); +static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level); static void test_keys (ECC_secret_key * sk, unsigned int nbits); static int check_secret_key (ECC_secret_key * sk); -static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey, +static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s); static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s); -static int point_at_infinity (point_t query); - static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base); @@ -266,115 +197,23 @@ _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *, progress_cb_data = cb_data; } -static void -progress (int c) -{ - if (progress_cb) - progress_cb (progress_cb_data, "pk_dsa", c, 0, 0); - else - fputc (c, stderr); -} - - -/* - - M P I W R A P P E R - - */ - -static ecc_ctx_t -ecc_ctx_init (gcry_mpi_t m, int copy) -{ - ecc_ctx_t ctx; - - ctx = gcry_xcalloc (1, sizeof *ctx); - - if (copy) - { - ctx->m = mpi_copy (m); - ctx->m_copied = 1; - } - else - ctx->m = m; - - return ctx; -} - -static void -ecc_ctx_free (ecc_ctx_t ctx) -{ - if (!ctx) - return; - if (ctx->m_copied) - mpi_free (ctx->m); - gcry_free (ctx); -} - -/* Our version of mpi_mod which uses a reduction algorithm depending - on the the context. The modulus is part of the context. */ -static void -ecc_mod (gcry_mpi_t r, gcry_mpi_t x, ecc_ctx_t ctx) -{ - mpi_mod (r, x, ctx->m); -} - -/* Our version of mpi_mulm which uses a reduction algorithm depending - on the the context. The modulus is part of the context. */ -static void -ecc_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, ecc_ctx_t ctx) -{ - /* Barrett is actually slower, so we don't do any switching here. - Howerver, we should take advantage of fast reduction for the NIST - curves. */ - mpi_mulm (w, u, v, ctx->m); -} - +/* static void */ +/* progress (int c) */ +/* { */ +/* if (progress_cb) */ +/* progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */ +/* } */ -/* - - O B J E C T M A I N T E N A N C E - - */ -/* Intialize a point object, so that its elements may be sued directly - as MPI functions. point_free is required for each initialzied - point. */ +/* Set the value from S into D. */ static void -point_init (point_t *P) +point_set (mpi_point_t *d, mpi_point_t *s) { - P->x_ = mpi_new (0); - P->y_ = mpi_new (0); - P->z_ = mpi_new (0); -} - - -/* - * Release a point object. - */ -static void -point_free (point_t *P) -{ - mpi_free (P->x_); P->x_ = NULL; - mpi_free (P->y_); P->y_ = NULL; - mpi_free (P->z_); P->z_ = NULL; -} - - -/* - * Return a copy of a point object. - */ -static point_t -point_copy (point_t P) -{ - point_t R; - - R.x_ = mpi_copy (P.x_); - R.y_ = mpi_copy (P.y_); - R.z_ = mpi_copy (P.z_); - - return R; + mpi_set (d->x, s->x); + mpi_set (d->y, s->y); + mpi_set (d->z, s->z); } @@ -384,11 +223,11 @@ point_copy (point_t P) static void curve_free (elliptic_curve_t *E) { - mpi_free (E->p_); E->p_ = NULL; - mpi_free (E->a_); E->a_ = NULL; - mpi_free (E->b_); E->b_ = NULL; + mpi_free (E->p); E->p = NULL; + mpi_free (E->a); E->a = NULL; + mpi_free (E->b); E->b = NULL; point_free (&E->G); - mpi_free (E->n_); E->n_ = NULL; + mpi_free (E->n); E->n = NULL; } @@ -400,622 +239,34 @@ curve_copy (elliptic_curve_t E) { elliptic_curve_t R; - R.p_ = mpi_copy (E.p_); - R.a_ = mpi_copy (E.a_); - R.b_ = mpi_copy (E.b_); - R.G = point_copy (E.G); - R.n_ = mpi_copy (E.n_); + R.p = mpi_copy (E.p); + R.a = mpi_copy (E.a); + R.b = mpi_copy (E.b); + point_init (&R.G); + point_set (&R.G, &E.G); + R.n = mpi_copy (E.n); return R; } - -/* - - A D D I T I O N A L M P I F U N C T I O N S - - */ - -/**************** - * Find, if it exist, the square root of one integer modulo a big prime. - * Return the square root or NULL if it is not found. - */ -#if 0 +/* Helper to scan a hex string. */ static gcry_mpi_t -exist_square_root (gcry_mpi_t integer, gcry_mpi_t modulus) +scanval (const char *string) { - unsigned long int i = 0; - gcry_mpi_t one, two, three, four, five, eight; - gcry_mpi_t k, r, z, k1; - gcry_mpi_t t1, t2, t3, t4; - - one = mpi_alloc_set_ui (1); - two = mpi_alloc_set_ui (2); - three = mpi_alloc_set_ui (3); - four = mpi_alloc_set_ui (4); - five = mpi_alloc_set_ui (5); - eight = mpi_alloc_set_ui (8); - k = mpi_alloc (mpi_get_nlimbs (modulus)); - r = mpi_alloc (mpi_get_nlimbs (modulus)); - z = mpi_alloc (mpi_get_nlimbs (modulus)); - k1 = mpi_alloc (mpi_get_nlimbs (modulus)); - t1 = mpi_alloc (mpi_get_nlimbs (modulus)); - t2 = mpi_alloc (mpi_get_nlimbs (modulus)); - t3 = mpi_alloc (mpi_get_nlimbs (modulus)); - t4 = mpi_alloc (mpi_get_nlimbs (modulus)); - - if (DBG_CIPHER) - log_mpidump ("?exist Square Root of ", integer); + gpg_error_t err; + gcry_mpi_t val; - mpi_fdiv_qr (k, r, modulus, four); - if (mpi_cmp (r, three)) - { /* p=3 (mod 4) */ - mpi_addm (k1, k, one, modulus); - mpi_powm (z, integer, k1, modulus); - if (DBG_CIPHER) - { - log_mpidump ("z=", z); - } - return z; /* value found */ - } - mpi_fdiv_qr (k, r, modulus, eight); - if (mpi_cmp (r, five)) - { /* p=5 (mod 8) */ - mpi_mulm (t1, two, integer, modulus); - mpi_powm (t2, t1, k, modulus); - mpi_powm (t2, t2, two, modulus); - mpi_mulm (t2, t1, t2, modulus); - mpi_mulm (t3, integer, t1, modulus); - mpi_subm (t4, t2, one, modulus); - mpi_mulm (z, t3, t4, modulus); - if (DBG_CIPHER) - { - log_mpidump ("z=", z); - } - return z; /* value found */ - } - if (mpi_cmp (r, one)) - { /* p=1 (mod 8) */ - while (i < 0xFF) - { /* while not find z after 256 iterations */ - if (DBG_CIPHER) - log_debug ("Square root bucle.\n"); - t1 = mpi_copy (integer); - t2 = gen_k (modulus, 0); - mpi_add_ui (t3, modulus, 1); /* t3=p+1 */ - mpi_rshift (t3, t3, 1); /* t3=t3/2 */ - lucas (t1, t2, t3, modulus, t4, t3); /* t4=V_k */ - mpi_rshift (z, t4, 1); /* z=V/2 */ - mpi_sub_ui (t3, modulus, 1); /* t3=p-1 */ - mpi_rshift (t4, t3, 2); /* t4=t3/2 */ - lucas (t1, t2, t4, modulus, t4, t1); /* t1=Q_0 */ - mpi_powm (t2, z, two, modulus); /* t2=z^2 */ - if (mpi_cmp (t1, integer)) - { - if (DBG_CIPHER) - { - log_mpidump ("z=", z); - } - return z; /* value found */ - } - if (t4 > mpi_alloc_set_ui (1) && t4 < t3) - { - if (DBG_CIPHER) - log_debug ("Rejected.\n"); - return (0); /* NULL */ - } - if (DBG_CIPHER) - log_debug ("Another loop.\n"); - } - } - if (DBG_CIPHER) - log_debug ("iterations limit.\n"); - return (0); /* because this algorithm not always finish. */ + err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL); + if (err) + log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err)); + return val; } -#endif /*0*/ - -/**************** - * Formal definition: - * V_0 = 2; V_1 = p - * V_k = (p*V_(k-1)) - (q*V_(k-2)) for k >= 2 - */ -#if 0 -static void -lucas (gcry_mpi_t n, gcry_mpi_t p_, gcry_mpi_t q_, - gcry_mpi_t k, gcry_mpi_t V_n, gcry_mpi_t Q_0) -{ - - gcry_mpi_t v0, v1, q0, q1; - gcry_mpi_t t1, t2; - unsigned int r, i; - v0 = mpi_alloc_set_ui (2); - v1 = mpi_copy (p_); - q0 = mpi_alloc_set_ui (1); - q1 = mpi_alloc_set_ui (1); - t1 = mpi_alloc_set_ui (0); - t2 = mpi_alloc_set_ui (0); - - if (DBG_CIPHER) - { - log_debug ("Generating lucas sequence.\n"); - log_mpidump ("k=", k); - } - r = mpi_get_nbits (k) - 1; - i = 0; - while (mpi_test_bit (k, i) != 1) - { /* search the first bit with value '1' */ - i++; - } - while (i < r) - { - if (DBG_CIPHER) - { - log_debug ("Lucas sequence bucle.\n"); - log_mpidump ("i=", mpi_alloc_set_ui (i)); - log_mpidump ("r=", mpi_alloc_set_ui (r)); - } - mpi_mulm (q0, q0, q1, n); - if (mpi_test_bit (k, i) == 1) - { - mpi_mulm (q1, q0, q_, n); - mpi_mul (t1, v0, v1); - mpi_mul (t2, p_, q0); - mpi_subm (v0, t1, t2, n); - mpi_powm (t1, v1, mpi_alloc_set_ui (2), n); - mpi_mul (t2, mpi_alloc_set_ui (2), q1); - mpi_subm (v1, t1, t2, n); - } - else - { - q1 = mpi_copy (q0); - mpi_mul (t1, v0, v1); - mpi_mul (t2, p_, q0); - mpi_subm (v1, t1, t2, n); - mpi_powm (t1, v0, mpi_alloc_set_ui (2), n); - mpi_mul (t2, mpi_alloc_set_ui (2), q0); - mpi_subm (v0, t1, t2, n); - } - i++; - } - V_n = mpi_copy (v0); - Q_0 = mpi_copy (q0); - if (DBG_CIPHER) - { - log_debug ("Lucas sequence generated.\n"); - log_mpidump ("V_n=", V_n); - log_mpidump ("Q_0=", Q_0); - } -} -#endif /*0*/ -/* - - P O I N T A N D C U R V E O P E R A T I O N S - - */ - -/* fixme: - * The point at infinity is needed to make - * a group structure to the elliptic curve. - * Know if one point is it, is needed so - * much times in this code. - * - * return true(1), false(0), or error(-1) for an invalid point - */ -static int -point_at_infinity (point_t query) -{ - if (!mpi_cmp_ui (query.z_, 0)) /* Z == 0 */ - { - if ( /*mpi_cmp_ui(Query.x_,0) && */ mpi_cmp_ui (query.y_, 0)) - { - /* X && Y != 0 & Z == 0 */ - /* Fixme: The above condition is not asserted. We may get - to here if X is 0 ! */ - if (DBG_CIPHER) - log_debug ("True:It is a Point at Infinite.\n"); - return 1; - } - if (DBG_CIPHER) - log_debug ("Error:It isn't an elliptic curve valid point.\n"); - return -1; - } - return 0; /* It is a valid curve point, but not the point at infinity. */ -} - - -/* - * Turn a projective coordinate P to affine. - * Returns 0 on success and the affine coordinates at X and Y. - * - * Note, that Y is never used as we can do without it. - */ -static int -point_affine (point_t *P, gcry_mpi_t x, gcry_mpi_t y, elliptic_curve_t *base) -{ - gcry_mpi_t z1, z2, z3; - - if (point_at_infinity (*P)) - { - if (DBG_CIPHER) - log_debug ("ecc point_affine: " - "Point at Infinity does NOT exist in the affine plane!\n"); - return 1; - } - - z1 = mpi_new (0); - z2 = mpi_new (0); - z3 = mpi_new (0); - - mpi_invm (z1, P->z_, base->p_); /* z1 =Z^{-1} (mod p) */ - mpi_mulm (z2, z1, z1, base->p_); /* z2 =Z^(-2) (mod p) */ - mpi_mulm (z3, z2, z1, base->p_); /* z3 =Z^(-3) (mod p) */ - mpi_mulm (x, P->x_, z2, base->p_); - mpi_mulm (y, P->y_, z3, base->p_); - - mpi_free (z1); - mpi_free (z2); - mpi_free (z3); - return 0; -} - - -/* - * The point inversion over F_p is a simple modular inversion of the Y - * coordinate. - */ -static void -invert_point (point_t *P, elliptic_curve_t *base) -{ - mpi_subm (P->y_, base->p_, P->y_, base->p_); /* y = p - y mod p */ -} - - -/* - * Scalar multiplication of one point, with the integer fixed to 2. - * R = 2P - */ -static void -duplicate_point (point_t *R, point_t *P, elliptic_curve_t *base, - ecc_ctx_t pctx) -{ - gcry_mpi_t one, two, three, four, eight; - gcry_mpi_t p_3, a; - gcry_mpi_t t1, t2, t3, t4, t5, t6, t7; - gcry_mpi_t aux; - - one = mpi_alloc_set_ui (1); - two = mpi_alloc_set_ui (2); - three = mpi_alloc_set_ui (3); - four = mpi_alloc_set_ui (4); - eight = mpi_alloc_set_ui (8); - - p_3 = mpi_alloc_like (base->p_); - mpi_sub_ui (p_3, base->p_, 3); /* p_3 = p - 3 */ - - a = mpi_copy (base->a_); - t1 = mpi_alloc_like (base->p_); - t2 = mpi_alloc_like (base->p_); - t3 = mpi_alloc_like (base->p_); - t4 = mpi_alloc_like (base->p_); - t5 = mpi_alloc_like (base->p_); - t6 = mpi_alloc_like (base->p_); - t7 = mpi_alloc_like (base->p_); - aux = mpi_alloc_like (base->p_); - - t1 = mpi_copy (P->x_); /* t1=x1 */ - t2 = mpi_copy (P->y_); /* t2=y1 */ - t3 = mpi_copy (P->z_); /* t3=z1 */ - - if (!mpi_cmp_ui (t2, 0) || !mpi_cmp_ui (t3, 0)) - { /* t2==0 | t3==0 => [1:1:0] */ - mpi_set_ui (R->x_, 1); - mpi_set_ui (R->y_, 1); - mpi_set_ui (R->z_, 0); - } - else - { - ecc_mod (a, a, pctx); /* a mod p FIXME: really needed? */ - if (!mpi_cmp (a, p_3)) - { /* a==p-3 */ - mpi_powm (t4, t3, two, base->p_); /* t4=t3^2 mod p */ - mpi_subm (t5, t1, t4, base->p_); /* t5=t1-t4 mod p */ - mpi_addm (t4, t1, t4, base->p_); /* t4=t1+t4 mod p */ - ecc_mulm (t5, t4, t5, pctx); /* t5=t4*t5 mod p */ - ecc_mulm (t4, three, t5, pctx); /* t4=3*t5 mod p */ - } - else - { - mpi_set (t4, a); /* t4=a */ - mpi_powm (t5, t3, two, base->p_); /* t5=t3^2 mod p */ - mpi_powm (t5, t5, two, base->p_); /* t5=t5^2 mod p */ - ecc_mulm (t5, t4, t5, pctx); /* t5=t4*t5 mod p */ - mpi_powm (t4, t1, two, base->p_); /* t4=t1^2 mod p */ - ecc_mulm (t4, three, t4, pctx); /* t4=3*t4 mod p */ - mpi_addm (t4, t4, t5, base->p_); /* t4=t4+t5 mod p */ - } - ecc_mulm (t3, t2, t3, pctx); /* t3=t2*t3 mod p */ - ecc_mulm (t3, two, t3, pctx); /* t3=2*t3 mod p */ - mpi_powm (aux, t2, two, base->p_); /* t2=t2^2 mod p */ - mpi_set (t2, aux); - ecc_mulm (t5, t1, t2, pctx); /* t5=t1*t2 mod p */ - ecc_mulm (t5, four, t5, pctx); /* t5=4*t5 mod p */ - mpi_powm (t1, t4, two, base->p_); /* t1=t4^2 mod p */ - ecc_mulm (aux, two, t5, pctx); - mpi_subm (t1, t1, aux, base->p_); /* t1=t1-2*t5 mod p */ - mpi_powm (aux, t2, two, base->p_); /* t2=t2^2 mod p */ - mpi_set (t2, aux); - ecc_mulm (t2, eight, t2, pctx); /* t2=8*t2 mod p */ - mpi_subm (t5, t5, t1, base->p_); /* t5=t5-t1 mod p */ - ecc_mulm (t5, t4, t5, pctx); /* t5=t4*t5 mod p */ - mpi_subm (t2, t5, t2, base->p_); /* t2=t5-t2 mod p */ - - mpi_set (R->x_, t1); - mpi_set (R->y_, t2); - mpi_set (R->z_, t3); - } - - mpi_free (aux); - mpi_free (t7); - mpi_free (t6); - mpi_free (t5); - mpi_free (t4); - mpi_free (t3); - mpi_free (t2); - mpi_free (t1); - mpi_free (p_3); - mpi_free (a); - mpi_free (eight); - mpi_free (four); - mpi_free (three); - mpi_free (two); - mpi_free (one); -} - - -/* - Point addition is the group operation. - - R = P0 + P1 - */ -static void -sum_points (point_t *R, point_t *P0, point_t *P1, elliptic_curve_t *base, - ecc_ctx_t pctx) -{ - - if ( (!mpi_cmp (P1->x_, P0->x_)) - && (!mpi_cmp (P1->y_, P0->y_)) - && (!mpi_cmp (P1->z_, P0->z_)) ) /* P1 == P0 */ - { - duplicate_point (R, P0, base, pctx); - } - else if (point_at_infinity (*P0)) /* R == 0 && P1 == P1 */ - { - mpi_set (R->x_, P1->x_); - mpi_set (R->y_, P1->y_); - mpi_set (R->z_, P1->z_); - } - else if (point_at_infinity (*P1)) /* R == P0 && P0 == 0 */ - { - mpi_set (R->x_, P0->x_); - mpi_set (R->y_, P0->y_); - mpi_set (R->z_, P0->z_); - } - else - { - gcry_mpi_t two; - gcry_mpi_t t1, t2, t3, t4, t5, t6, t7; - - two = mpi_alloc_set_ui (2); - - t1 = mpi_copy (P0->x_); /* t1=x0 */ - t2 = mpi_copy (P0->y_); /* t2=y0 */ - t3 = mpi_copy (P0->z_); /* t3=z0 */ - t4 = mpi_copy (P1->x_); /* t4=x1 */ - t5 = mpi_copy (P1->y_); /* t5=y2 */ - t6 = mpi_new (0); - t7 = mpi_new (0); - - if (mpi_cmp_ui (P1->z_, 1)) /* z1 != 1 */ - { - mpi_set (t6, P1->z_); /* t6=z1 */ - mpi_powm (t7, t6, two, base->p_); /* t7=t6^2 mod p */ - ecc_mulm (t1, t1, t7, pctx); /* t1=t1*t7 mod p */ - ecc_mulm (t7, t6, t7, pctx); /* t7=t6*t7 mod p */ - ecc_mulm (t2, t2, t7, pctx); /* t2=t2*t7 mod p */ - } - mpi_powm (t7, t3, two, base->p_);/* t7=t3^2 mod p */ - ecc_mulm (t4, t4, t7, pctx); /* t4=t4*t7 mod p */ - ecc_mulm (t7, t3, t7, pctx); /* t7=t3*t7 mod p */ - ecc_mulm (t5, t5, t7, pctx); /* t5=t5*t7 mod p */ - mpi_subm (t4, t1, t4, base->p_); /* t4=t1-t4 mod p */ - mpi_subm (t5, t2, t5, base->p_); /* t5=t2-t5 mod p */ - - if (!mpi_cmp_ui (t4, 0)) /* t4==0 */ - { - if (!mpi_cmp_ui (t5, 0)) - { - /* return (0:0:0), it has a special mean. */ - if (DBG_CIPHER) - log_debug ("ecc sum_points: [0:0:0]!\n"); - mpi_set_ui (R->x_, 0); - mpi_set_ui (R->y_, 0); - mpi_set_ui (R->z_, 0); - } - else - { - if (DBG_CIPHER) - log_debug ("ecc sum_points: [1:1:0]!\n"); - mpi_set_ui (R->x_, 1); - mpi_set_ui (R->y_, 1); - mpi_set_ui (R->z_, 0); - } - } - else - { - ecc_mulm (t1, two, t1, pctx); - mpi_subm (t1, t1, t4, base->p_); /* t1=2*t1-t4 mod p */ - ecc_mulm (t2, two, t2, pctx); - mpi_subm (t2, t2, t5, base->p_); /* t2=2*t2-t5 mod p */ - if (mpi_cmp_ui (P1->z_, 1)) /* z1 != 1 */ - { - ecc_mulm (t3, t3, t6, pctx); /* t3=t3*t6 */ - } - ecc_mulm (t3, t3, t4, pctx); /* t3=t3*t4 mod p */ - mpi_powm (t7, t4, two, base->p_); /* t7=t4^2 mod p */ - ecc_mulm (t4, t4, t7, pctx); /* t4=t4*t7 mod p */ - ecc_mulm (t7, t1, t7, pctx); /* t7=t1*t7 mod p */ - mpi_powm (t1, t5, two, base->p_); /* t1=t5^2 mod p */ - mpi_subm (t1, t1, t7, base->p_); /* t1=t1-t7 mod p */ - ecc_mulm (t6, two, t1, pctx); - mpi_subm (t7, t7, t6, base->p_); /* t7=t7-2*t1 mod p */ - ecc_mulm (t5, t5, t7, pctx); /* t5=t5*t7 mod p */ - ecc_mulm (t4, t2, t4, pctx); /* t4=t2*t4 mod p */ - mpi_subm (t2, t5, t4, base->p_); /* t2=t5-t4 mod p */ - mpi_invm (t6, two, base->p_); - ecc_mulm (t2, t2, t6, pctx); /* t2 = t2/2 */ - - mpi_set (R->x_, t1); - mpi_set (R->y_, t2); - mpi_set (R->z_, t3); - } - mpi_free (t7); - mpi_free (t6); - mpi_free (t5); - mpi_free (t4); - mpi_free (t3); - mpi_free (t2); - mpi_free (t1); - mpi_free (two); - } -} - -/**************** - * The modular power used without EC, - * is this function over EC. - return R = escalarP - - ESCALAR = input - P = input - BASE = input - R = output (caller must have intialized this point) - - */ -static void -escalar_mult (point_t *R, gcry_mpi_t escalar, point_t *P, - elliptic_curve_t *base, ecc_ctx_t pctx) -{ - gcry_mpi_t one, two, three; - gcry_mpi_t x1, y1, z1, z2, z3, k, h; - gcry_mpi_t xx, yy, zz; - unsigned int i, loops; - point_t P1, P2, P1_; - - if (DBG_CIPHER) - log_debug ("escalar_mult: begin\n"); - - one = mpi_alloc_set_ui (1); - two = mpi_alloc_set_ui (2); - three = mpi_alloc_set_ui (3); - - x1 = mpi_alloc_like (P->x_); - y1 = mpi_alloc_like (P->y_); - /* z1 is not yet intialized. */ - z2 = mpi_alloc_like (P->z_); - z3 = mpi_alloc_like (P->z_); - /* k is not yet intialized. */ - h = mpi_alloc_like (P->z_); - - - if (!mpi_cmp_ui (escalar, 0) || mpi_cmp_ui (P->z_, 0)) - { /* n=0 | Z=0 => [1:1:0] */ - mpi_set_ui (R->x_, 1); - mpi_set_ui (R->y_, 1); - mpi_set_ui (R->z_, 0); - } - xx = mpi_copy (P->x_); - zz = mpi_copy (P->z_); - z1 = mpi_copy (one); - - if (mpi_is_neg (escalar)) - { /* (-n)P=n(-P) */ - escalar->sign = 0; /* +n */ - k = mpi_copy (escalar); - yy = mpi_copy (P->y_); /* -P */ - mpi_invm (yy, yy, base->p_); - } - else - { - k = mpi_copy (escalar); - yy = mpi_copy (P->y_); - } - if (!mpi_cmp (zz, one)) - { /* zz==1 */ - x1 = mpi_copy (xx); - y1 = mpi_copy (yy); - } - else - { - ecc_mulm (z2, zz, zz, pctx); /* z^2 */ - ecc_mulm (z3, zz, z2, pctx); /* z^3 */ - mpi_invm (z2, z2, base->p_); /* 1/Z^2 */ - ecc_mulm (x1, xx, z2, pctx); /* xx/z^2 */ - mpi_invm (z3, z3, base->p_); /* 1/z^3 */ - ecc_mulm (y1, yy, z3, pctx); /* yy/z^3 */ - } - mpi_mul (h, three, k); /* h=3k */ - loops = mpi_get_nbits (h); - i = loops - 2; /* i = l-1 = loops-2 */ - mpi_set (R->x_, xx); - mpi_set (R->y_, yy); - mpi_set (R->z_, zz); - P1.x_ = mpi_copy (x1); - P1.y_ = mpi_copy (y1); - P1.z_ = mpi_copy (z1); - while (i > 0) - { /* A.10.9. step 11 i from l-1 downto 1 */ - duplicate_point (R, R, base, pctx); - if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0) - { /* h_i=1 & k_i=0 */ - P2 = point_copy (*R); - sum_points (R, &P2, &P1, base, pctx); /* R=P2+P1 over the base elliptic curve */ - } - if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1) - { /* h_i=0 & k_i=1 */ - P2 = point_copy (*R); - P1_ = point_copy (P1); - invert_point (&P1_, base); - sum_points (R, &P2, &P1_, base, pctx); /* R=P2+P1_ over the base elliptic curve */ - } - i--; - } - - if (DBG_CIPHER) - log_debug ("escalar_mult: ready\n"); - - point_free (&P1); - point_free (&P2); - point_free (&P1_); - mpi_free (h); - mpi_free (k); - mpi_free (z3); - mpi_free (z2); - mpi_free (z1); - mpi_free (y1); - mpi_free (x1); - mpi_free (zz); - mpi_free (yy); - mpi_free (xx); - mpi_free (three); - mpi_free (two); - mpi_free (one); -} - /**************** * Solve the right side of the equation that defines a curve. @@ -1023,32 +274,21 @@ escalar_mult (point_t *R, gcry_mpi_t escalar, point_t *P, static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base) { - gcry_mpi_t three; - gcry_mpi_t x_3, ax, axb, y; - gcry_mpi_t a, b, p; - unsigned int nbits; + gcry_mpi_t three, x_3, axb, y; three = mpi_alloc_set_ui (3); - a = mpi_copy (base->a_); - b = mpi_copy (base->b_); - p = mpi_copy (base->p_); - nbits = mpi_get_nbits (p); - x_3 = mpi_new (nbits); - ax = mpi_new (nbits); - axb = mpi_new (nbits); - y = mpi_new (nbits); - - if (DBG_CIPHER) - log_debug ("ecc gen_y_2: Solving an elliptic equation.\n"); - - mpi_powm (x_3, x, three, p); /* x_3=x^3 mod p */ - mpi_mulm (ax, a, x, p); /* ax=a*x mod p */ - mpi_addm (axb, ax, b, p); /* axb=ax+b mod p */ - mpi_addm (y, x_3, axb, p); /* y=x^3+ax+b mod p */ + x_3 = mpi_new (0); + axb = mpi_new (0); + y = mpi_new (0); - if (DBG_CIPHER) - log_debug ("ecc gen_y_2: Solved.\n"); + mpi_powm (x_3, x, three, base->p); + mpi_mulm (axb, base->a, x, base->p); + mpi_addm (axb, axb, base->b, base->p); + mpi_addm (y, x_3, axb, base->p); + mpi_free (x_3); + mpi_free (axb); + mpi_free (three); return y; /* The quadratic value of the coordinate if it exist. */ } @@ -1056,58 +296,28 @@ gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base) - -/* - - E C C C O R E F U N C T I O N S - - */ - - - /* Generate a random secret scalar k with an order of p At the beginning this was identical to the code is in elgamal.c. Later imporved by mmr. Further simplified by wk. */ static gcry_mpi_t -gen_k (gcry_mpi_t p, int secure) +gen_k (gcry_mpi_t p, int security_level) { gcry_mpi_t k; unsigned int nbits; nbits = mpi_get_nbits (p); - k = (secure - ? mpi_alloc_secure ( mpi_get_nlimbs (p) ) - : mpi_alloc ( mpi_get_nlimbs (p) )); - + k = mpi_snew (nbits); if (DBG_CIPHER) log_debug ("choosing a random k of %u bits\n", nbits); - - gcry_mpi_randomize (k, nbits, GCRY_STRONG_RANDOM); - mpi_mod (k, k, p); /* k = k mod p */ + gcry_mpi_randomize (k, nbits, security_level); - if (DBG_CIPHER) - progress ('\n'); + mpi_mod (k, k, p); /* k = k mod p */ return k; } - -/* Helper to scan a hex string. */ -static gcry_mpi_t -scanval (const char *string) -{ - gpg_error_t err; - gcry_mpi_t val; - - err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL); - if (err) - log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err)); - return val; -} - - /**************** * Generate the crypto system setup. * As of now the fix NIST recommended values are used. @@ -1124,122 +334,98 @@ generate_curve (unsigned int nbits, elliptic_curve_t *curve) if (!domain_parms[idx].desc) return GPG_ERR_INV_VALUE; - curve->p_ = scanval (domain_parms[idx].p); - curve->a_ = scanval (domain_parms[idx].a); - curve->b_ = scanval (domain_parms[idx].b); - curve->n_ = scanval (domain_parms[idx].n); - curve->G.x_ = scanval (domain_parms[idx].g_x); - curve->G.y_ = scanval (domain_parms[idx].g_y); - curve->G.z_ = mpi_alloc_set_ui (1); - - /* Gx, Gy, Gz are planned to be generated by code like this: - if ( gen_big_point (&curve->n_, curve, &curve->G, nbits) == -1) - { - log_fatal ("ECC operation: Point generation failed\n"); - } - - A point of order 'n' is needed to generate a cyclic subgroup. - Over this cyclic subgroup it's defined the ECDLP. Now it use a - fix values from NIST FIPS PUB 186-2. Returns -1 if it isn't - possible. - static int - gen_big_point (gcry_mpi_t * prime, elliptic_curve_t * base, point_t * G, - unsigned int nbits) - { - unsigned int i=0; - gcry_mpi_t one; - point_t Big, P; - - one = mpi_alloc_set_ui(1); - G->x_ = mpi_alloc(mpi_get_nlimbs(*prime)); - G->y_ = mpi_alloc(mpi_get_nlimbs(*prime)); - G->z_ = mpi_alloc(mpi_get_nlimbs(*prime)); - - if( DBG_CIPHER )log_debug("Generating a Big point.\n"); - do{ - do{ - *P = genPoint(*prime,*base); - }while(PointAtInfinity(*P));//A random point in the curve that it's not PaI - escalarMult(base.h,&P,&G,&base);//cofactor (1 o 2), could be improved - }while(PointAtInfinity(G)); - if( DBG_CIPHER )log_debug("Big point generated.\n"); - if( DBG_CIPHER ){ - log_mpidump("Gx=",G->x_);log_mpidump("Gy=",G->y_);log_mpidump("Gz=",G->z_); - } - return 0; - } - */ - - if (DBG_CIPHER) - { - progress ('\n'); - log_mpidump ("ecc generation p= ", curve->p_); - log_mpidump ("ecc generation a= ", curve->a_); - log_mpidump ("ecc generation b= ", curve->b_); - log_mpidump ("ecc generation n= ", curve->n_); - log_mpidump ("ecc generation Gx= ", curve->G.x_); - log_mpidump ("ecc generation Gy= ", curve->G.y_); - log_mpidump ("ecc generation Gz= ", curve->G.z_); - } - if (DBG_CIPHER) - progress ('\n'); + curve->p = scanval (domain_parms[idx].p); + curve->a = scanval (domain_parms[idx].a); + curve->b = scanval (domain_parms[idx].b); + curve->n = scanval (domain_parms[idx].n); + curve->G.x = scanval (domain_parms[idx].g_x); + curve->G.y = scanval (domain_parms[idx].g_y); + curve->G.z = mpi_alloc_set_ui (1); return 0; } -/**************** +/* * First obtain the setup. Over the finite field randomize an scalar * secret value, and calculate the public point. */ static gpg_err_code_t -generate_key (ECC_secret_key *sk, unsigned int nbits) +generate_key (ECC_secret_key *sk, unsigned int nbits, + gcry_mpi_t g_x, gcry_mpi_t g_y, + gcry_mpi_t q_x, gcry_mpi_t q_y) { gpg_err_code_t err; elliptic_curve_t E; gcry_mpi_t d; - point_t Q, G; - ecc_ctx_t pctx; + mpi_point_t Q, G; + mpi_ec_t ctx; err = generate_curve (nbits, &E); if (err) return err; + if (DBG_CIPHER) + { + log_mpidump ("ecc generation p", E.p); + log_mpidump ("ecc generation a", E.a); + log_mpidump ("ecc generation b", E.b); + log_mpidump ("ecc generation n", E.n); + log_mpidump ("ecc generation Gx", E.G.x); + log_mpidump ("ecc generation Gy", E.G.y); + log_mpidump ("ecc generation Gz", E.G.z); + } + d = mpi_snew (nbits); if (DBG_CIPHER) log_debug ("choosing a random x of size %u\n", nbits); - d = gen_k (E.n_, 2); /* generate_secret_prime(nbits); */ - G = point_copy (E.G); + d = gen_k (E.n, GCRY_VERY_STRONG_RANDOM); + point_init (&G); + point_set (&G, &E.G); /* Compute Q. */ point_init (&Q); - pctx = ecc_ctx_init (E.p_, 0); - escalar_mult (&Q, d, &E.G, &E, pctx); - ecc_ctx_free (pctx); + ctx = _gcry_mpi_ec_init (E.p, E.a); + _gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx); /* Copy the stuff to the key structures. */ - sk->E.p_ = mpi_copy (E.p_); - sk->E.a_ = mpi_copy (E.a_); - sk->E.b_ = mpi_copy (E.b_); - sk->E.G = point_copy (E.G); - sk->E.n_ = mpi_copy (E.n_); - sk->Q = point_copy (Q); + sk->E.p = mpi_copy (E.p); + sk->E.a = mpi_copy (E.a); + sk->E.b = mpi_copy (E.b); + point_init (&sk->E.G); + point_set (&sk->E.G, &E.G); + sk->E.n = mpi_copy (E.n); + point_init (&sk->Q); + point_set (&sk->Q, &Q); sk->d = mpi_copy (d); - - /* Now we can test our keys (this should never fail!). */ - test_keys (sk, nbits - 64); + /* We also return copies of G and Q in affine coordinates if + requested. */ + if (g_x && q_x) + { + if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx)) + log_fatal ("ecc generate: Failed to get affine coordinates\n"); + } + if (q_x && q_x) + { + if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx)) + log_fatal ("ecc generate: Failed to get affine coordinates\n"); + } + _gcry_mpi_ec_free (ctx); point_free (&Q); mpi_free (d); curve_free (&E); + /* Now we can test our keys (this should never fail!). */ + test_keys (sk, nbits - 64); + return 0; } /**************** * To verify correct skey it use a random information. - * First, encrypt and decrypt this dummy value, + * First, encrypt and decrypt this dummy value, * test if the information is recuperated. * Second, test with the sign and verify functions. */ @@ -1248,7 +434,7 @@ test_keys (ECC_secret_key *sk, unsigned int nbits) { ECC_public_key pk; gcry_mpi_t test = mpi_new (nbits); - point_t R_; + mpi_point_t R_; gcry_mpi_t c = mpi_new (nbits); gcry_mpi_t out = mpi_new (nbits); gcry_mpi_t r = mpi_new (nbits); @@ -1260,21 +446,11 @@ test_keys (ECC_secret_key *sk, unsigned int nbits) point_init (&R_); pk.E = curve_copy (sk->E); - pk.Q = point_copy (sk->Q); + point_init (&pk.Q); + point_set (&pk.Q, &sk->Q); gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM); -#if 0 - doEncrypt (test, &pk, &R_, c); - - out = decrypt (out, sk, R_, c); - - if (mpi_cmp (test, out)) /* test!=out */ - log_fatal ("ECELG operation: encrypt, decrypt failed\n"); - if (DBG_CIPHER) - log_debug ("ECELG operation: encrypt, decrypt ok.\n"); -#endif - if (sign (test, sk, r, s) ) log_fatal ("ECDSA operation: sign failed\n"); @@ -1299,20 +475,20 @@ test_keys (ECC_secret_key *sk, unsigned int nbits) /**************** * To check the validity of the value, recalculate the correspondence - * between the public value and de secret one. + * between the public value and the secret one. */ static int check_secret_key (ECC_secret_key * sk) { - point_t Q; + mpi_point_t Q; gcry_mpi_t y_2, y2 = mpi_alloc (0); - ecc_ctx_t pctx; + mpi_ec_t ctx; /* ?primarity test of 'p' */ /* (...) //!! */ /* G in E(F_p) */ - y_2 = gen_y_2 (sk->E.G.x_, &sk->E); /* y^2=x^3+a*x+b */ - mpi_mulm (y2, sk->E.G.y_, sk->E.G.y_, sk->E.p_); /* y^2=y*y */ + y_2 = gen_y_2 (sk->E.G.x, &sk->E); /* y^2=x^3+a*x+b */ + mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p); /* y^2=y*y */ if (mpi_cmp (y_2, y2)) { if (DBG_CIPHER) @@ -1320,142 +496,48 @@ check_secret_key (ECC_secret_key * sk) return (1); } /* G != PaI */ - if (point_at_infinity (sk->E.G)) + if (!mpi_cmp_ui (sk->E.G.z, 0)) { if (DBG_CIPHER) log_debug ("Bad check: 'G' cannot be Point at Infinity!\n"); return (1); } - /* ?primarity test of 'n' */ - /* (...) //!! */ - /* ?(p-sqrt(p)) < n < (p+sqrt(p)) */ - /* ?n!=p */ - /* ?(n^k) mod p !=1 for k=1 to 31 (from GOST) or k=1 to 50 (from MIRACL) */ - /* Q=[n]G over E = PaI */ point_init (&Q); - pctx = ecc_ctx_init (sk->E.p_, 0); - escalar_mult (&Q, sk->E.n_, &sk->E.G, &sk->E, pctx); - if (!point_at_infinity (Q)) + ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a); + _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx); + if (mpi_cmp_ui (Q.z, 0)) { if (DBG_CIPHER) log_debug ("check_secret_key: E is not a curve of order n\n"); point_free (&Q); - ecc_ctx_free (pctx); + _gcry_mpi_ec_free (ctx); return 1; } /* pubkey cannot be PaI */ - if (point_at_infinity (sk->Q)) + if (!mpi_cmp_ui (sk->Q.z, 0)) { if (DBG_CIPHER) log_debug ("Bad check: Q can not be a Point at Infinity!\n"); - ecc_ctx_free (pctx); + _gcry_mpi_ec_free (ctx); return (1); } /* pubkey = [d]G over E */ - escalar_mult (&Q, sk->d, &sk->E.G, &sk->E, pctx); - if ((Q.x_ == sk->Q.x_) && (Q.y_ == sk->Q.y_) && (Q.z_ == sk->Q.z_)) + _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx); + if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z)) { if (DBG_CIPHER) log_debug ("Bad check: There is NO correspondence between 'd' and 'Q'!\n"); - ecc_ctx_free (pctx); + _gcry_mpi_ec_free (ctx); return (1); } - ecc_ctx_free (pctx); + _gcry_mpi_ec_free (ctx); point_free (&Q); return 0; } -#if 0 -/**************** - * Encrypt a number and obtain and struct (R,c) - */ -static void -doEncrypt (gcry_mpi_t input, ECC_public_key * pkey, point_t * R, gcry_mpi_t c) -{ - - gcry_mpi_t k, p, x, y; - point_t P, Q, G; - elliptic_curve_t E; - - k = mpi_alloc (0); - p = mpi_copy (pkey->E.p_); - x = mpi_alloc (0); - y = mpi_alloc (0); - Q = point_copy (pkey->Q); - G = point_copy (pkey->E.G); - E = curve_copy (pkey->E); - - k = gen_k (p, 1); /* 2nd parametre: how much security? */ - escalarMult (k, &Q, &P, &E); /* P=[k]Q=[k]([d]G) */ - escalarMult (k, &G, R, &E); /* R=[k]G */ - /* IFP weakness//mpi_mul(c,input,Q.x_);//c=input*Q_x */ - /* MMR Use affine conversion befor extract x-coordinate */ - if (point_affine (&P, x, y, &E)) - { /* Q cannot turn to affine coordinate */ - if (DBG_CIPHER) - { - log_debug ("Encrypting: Cannot turn to affine.\n"); - } - } - /* MMR According to the standard P1363 we can not use x-coordinate directly. */ - /* It is necessary to add hash-operation later. */ - /* As the maximal length of a key for the symmetric cipher is 256 bit it is possible to take hash-function SHA256. */ - sha256_hashing (x, &x); - aes256_encrypting (x, input, &c); - - if (DBG_CIPHER) - { - log_debug ("doEncrypt: end.\n"); - } -} -#endif /*0*/ - -#if 0 -/**************** - * Undo the ciphertext - */ -static gcry_mpi_t -decrypt (gcry_mpi_t output, ECC_secret_key * skey, point_t R, gcry_mpi_t c) -{ - - gcry_mpi_t p, inv, x, y; - point_t P, Q; - elliptic_curve_t E; - - p = mpi_copy (skey->E.p_); - inv = mpi_alloc (0); - x = mpi_alloc (0); - y = mpi_alloc (0); - Q = point_copy (skey->Q); - E = curve_copy (skey->E); - - escalarMult (skey->d, &R, &P, &E); /* P=[d]R */ - /* That is like: mpi_fdiv_q(output,c,Q.x_); */ - /* IFP weakness//mpi_invm(inv,Q.x_,p);//inv=Q{_x}^-1 (mod p) */ - /* IFP weakness//mpi_mulm(output,c,inv,p);//output=c*inv (mod p) */ - /* MMR Use affine conversion befor extract x-coordinate */ - if (point_affine (&P, x, y, &E)) - { /* Q cannot turn to affine coordinate */ - if (DBG_CIPHER) - { - log_debug ("Encrypting: Cannot turn to affine.\n"); - } - } - sha256_hashing (x, &x); - aes256_decrypting (x, c, &output); - - if (DBG_CIPHER) - { - log_debug ("decrypt: end.\n"); - } - return (output); -} -#endif /*0*/ - - /* * Return the signature struct (r,s) from the message hash. The caller * must have allocated R and S. @@ -1464,54 +546,51 @@ static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s) { gpg_err_code_t err = 0; - gcry_mpi_t k, dr, sum, k_1, x, y; - point_t I; - ecc_ctx_t pctx; - + gcry_mpi_t k, dr, sum, k_1, x; + mpi_point_t I; + mpi_ec_t ctx; + k = NULL; dr = mpi_alloc (0); sum = mpi_alloc (0); k_1 = mpi_alloc (0); x = mpi_alloc (0); - y = mpi_alloc (0); point_init (&I); mpi_set_ui (s, 0); mpi_set_ui (r, 0); - pctx = ecc_ctx_init (skey->E.p_, 0); + ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a); while (!mpi_cmp_ui (s, 0)) /* s == 0 */ - { + { while (!mpi_cmp_ui (r, 0)) /* r == 0 */ - { + { /* Note, that we are guaranteed to enter this loop at least once because r has been intialized to 0. We can't use a do_while because we want to keep the value of R even if S has to be recomputed. */ mpi_free (k); - k = gen_k (skey->E.p_, 1); /* fixme: shouldn't that be E.n ? */ - escalar_mult (&I, k, &skey->E.G, &skey->E, pctx); /* I = [k]G */ - if (point_affine (&I, x, y, &skey->E)) + k = gen_k (skey->E.n, GCRY_STRONG_RANDOM); + _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); + if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx)) { if (DBG_CIPHER) - log_debug ("ecc sign: Cannot turn to affine. " - " Cannot complete sign.\n"); + log_debug ("ecc sign: Failed to get affine coordinates\n"); err = GPG_ERR_BAD_SIGNATURE; goto leave; } - mpi_mod (r, x, skey->E.n_); /* r = x mod n */ + mpi_mod (r, x, skey->E.n); /* r = x mod n */ } - mpi_mulm (dr, skey->d, r, skey->E.n_);/* dr = d*r mod n */ - mpi_addm (sum, input, dr, skey->E.n_);/* sum = hash + (d*r) mod n */ - mpi_invm (k_1, k, skey->E.n_); /* k_1 = k^(-1) mod n */ - mpi_mulm (s, k_1, sum, skey->E.n_); /* s = k^(-1)*(hash+(d*r)) mod n */ + mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */ + mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n */ + mpi_invm (k_1, k, skey->E.n); /* k_1 = k^(-1) mod n */ + mpi_mulm (s, k_1, sum, skey->E.n); /* s = k^(-1)*(hash+(d*r)) mod n */ } leave: - ecc_ctx_free (pctx); + _gcry_mpi_ec_free (ctx); point_free (&I); - mpi_free (y); mpi_free (x); mpi_free (k_1); mpi_free (sum); @@ -1529,12 +608,12 @@ verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s) { gpg_err_code_t err = 0; gcry_mpi_t h, h1, h2, x, y; - point_t Q, Q1, Q2; - ecc_ctx_t pctx; + mpi_point_t Q, Q1, Q2; + mpi_ec_t ctx; - if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n_) < 0) ) + if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) ) return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */ - if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n_) < 0) ) + if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) ) return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */ h = mpi_alloc (0); @@ -1546,48 +625,48 @@ verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s) point_init (&Q1); point_init (&Q2); - pctx = ecc_ctx_init (pkey->E.p_, 0); + ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a); /* h = s^(-1) (mod n) */ - mpi_invm (h, s, pkey->E.n_); + mpi_invm (h, s, pkey->E.n); /* h1 = hash * s^(-1) (mod n) */ - mpi_mulm (h1, input, h, pkey->E.n_); + mpi_mulm (h1, input, h, pkey->E.n); /* Q1 = [ hash * s^(-1) ]G */ - escalar_mult (&Q1, h1, &pkey->E.G, &pkey->E, pctx ); + _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx); /* h2 = r * s^(-1) (mod n) */ - mpi_mulm (h2, r, h, pkey->E.n_); + mpi_mulm (h2, r, h, pkey->E.n); /* Q2 = [ r * s^(-1) ]Q */ - escalar_mult (&Q2, h2, &pkey->Q, &pkey->E, pctx); + _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx); /* Q = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */ - sum_points (&Q, &Q1, &Q2, &pkey->E, pctx); + _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx); - if (point_at_infinity (Q)) + if (!mpi_cmp_ui (Q.z, 0)) { if (DBG_CIPHER) - log_debug ("ecc verification: Rejected.\n"); + log_debug ("ecc verify: Rejected\n"); err = GPG_ERR_BAD_SIGNATURE; goto leave; } - if (point_affine (&Q, x, y, &pkey->E)) - { + if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx)) + { if (DBG_CIPHER) - log_debug ("ecc verification: Cannot turn to affine. Rejected.\n"); + log_debug ("ecc verify: Failed to get affine coordinates\n"); err = GPG_ERR_BAD_SIGNATURE; goto leave; } - mpi_mod (x, x, pkey->E.n_); /* x = x mod E_n */ + mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */ if (mpi_cmp (x, r)) /* x != r */ - { + { if (DBG_CIPHER) - log_debug ("ecc verification: Not verified.\n"); + log_debug ("ecc verify: Not verified\n"); err = GPG_ERR_BAD_SIGNATURE; goto leave; } if (DBG_CIPHER) - log_debug ("ecc verification: Accepted.\n"); + log_debug ("ecc verify: Accepted\n"); leave: - ecc_ctx_free (pctx); + _gcry_mpi_ec_free (ctx); point_free (&Q2); point_free (&Q1); point_free (&Q); @@ -1600,208 +679,116 @@ verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s) } -/**************** - * Generate a random point over an Elliptic curve is the first step to - * find a random cyclic subgroup generator. - * - * !! At this moment it isn't used !! //!! - */ -#if 0 -static point_t -gen_point (gcry_mpi_t prime, elliptic_curve_t base) -{ - unsigned int i = 0; - gcry_mpi_t x, y_2, y; - gcry_mpi_t one, one_neg, bit; - point_t P; - - x = mpi_alloc (mpi_get_nlimbs (base.p_)); - y_2 = mpi_alloc (mpi_get_nlimbs (base.p_)); - y = mpi_alloc (mpi_get_nlimbs (base.p_)); - one = mpi_alloc_set_ui (1); - one_neg = mpi_alloc (mpi_get_nlimbs (one)); - mpi_invm (one_neg, one, base.p_); - - if (DBG_CIPHER) - log_debug ("Generating a normal point.\n"); - do +/********************************************* + ************** interface ****************** + *********************************************/ +static gcry_mpi_t +ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p) +{ + gpg_error_t err; + int pbytes = (mpi_get_nbits (p)+7)/8; + size_t n; + unsigned char *buf, *ptr; + gcry_mpi_t result; + + buf = gcry_xmalloc ( 1 + 2*pbytes ); + *buf = 04; /* Uncompressed point. */ + ptr = buf+1; + err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x); + if (err) + log_fatal ("mpi_print failed: %s\n", gpg_strerror (err)); + if (n < pbytes) { - x = gen_k (base.p_, 1); /* generate_public_prime(mpi_get_nlimbs(base.n_)*BITS_PER_MPI_LIMB); */ - do - { - y_2 = gen_y_2 (x, &base); /* x^3+ax+b (mod p) */ - mpi_add_ui (x, x, 1); - i++; - } - while (!mpi_cmp_ui (y_2, 0) && i < 0xf); /* Try to find a valid value until 16 iterations. */ - i = 0; - y = existSquareRoot (y_2, base.p_); + memmove (ptr+(pbytes-n), buf+1, n); + memset (ptr, 0, (pbytes-n)); } - while (!mpi_cmp_ui (y, 0)); /* Repeat until a valid coordinate is found. */ - bit = gen_bit (); /* generate one bit */ - if (mpi_cmp_ui (bit, 1)) - { /* choose the y coordinate */ - mpi_invm (y, y, base.p_); /* mpi_powm(y, y, one_neg,base.p_); */ + ptr += pbytes; + err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y); + if (err) + log_fatal ("mpi_print failed: %s\n", gpg_strerror (err)); + if (n < pbytes) + { + memmove (ptr+(pbytes-n), buf+1, n); + memset (ptr, 0, (pbytes-n)); } - if (DBG_CIPHER) - log_debug ("Normal point generated.\n"); - - P.x_ = mpi_copy (x); - P.y_ = mpi_copy (y); - P.z_ = mpi_copy (one); + + err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL); + if (err) + log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err)); + gcry_free (buf); - mpi_free (bit); - mpi_free (one_neg); - mpi_free (one); - mpi_free (y); - mpi_free (y_2); mpi_free (x); + mpi_free (y); - return (P); + return result; } -#endif /*0*/ -/**************** - * Boolean generator to choose between to coordinates. - */ -#if 0 -static gcry_mpi_t -gen_bit () +/* RESULT must have been initialized and is set on success to the + point given by VALUE. */ +static gcry_error_t +os2ec (mpi_point_t *result, gcry_mpi_t value) { - gcry_mpi_t aux = mpi_alloc_set_ui (0); - - /* FIXME: This is highly ineffective but the whole function is used - only at one place. */ + gcry_error_t err; + size_t n; + unsigned char *buf; + gcry_mpi_t x, y; - /* Get one random bit, with less security level, and translate it to - an MPI. */ - mpi_set_buffer (aux, get_random_bits (1, 0, 1), 1, 0); /* gen_k(...) */ - - return aux; /* b; */ -} -#endif /*0*/ - - - -#if 0 -/* Function to solve an IFP ECElGamal weakness: */ -/* sha256_hashing() */ -/* aes256_encrypting() */ -/* aes356_decrypting() */ - -/**************** - * Compute 256 bit hash value from input MPI. - * Use SHA256 Algorithm. - */ -static void -sha256_hashing (gcry_mpi_t input, gcry_mpi_t * output) -{ /* */ - - int sign; - byte *hash_inp_buf; - byte hash_out_buf[32]; - MD_HANDLE hash = md_open (8, 1); /* algo SHA256 in secure mode */ - - unsigned int nbytes; - - hash_inp_buf = mpi_get_secure_buffer (input, &nbytes, &sign); /* convert gcry_mpi_t input to string */ - - md_write (hash, hash_inp_buf, nbytes); /* hashing input string */ - wipememory (hash_inp_buf, sizeof hash_inp_buf); /* burn temp value */ - xfree (hash_inp_buf); - - md_digest (hash, 8, hash_out_buf, 32); - mpi_set_buffer (*output, hash_out_buf, 32, 0); /* convert 256 bit digest to MPI */ - - wipememory (hash_out_buf, sizeof hash_out_buf); /* burn temp value */ - md_close (hash); /* destroy and free hash state. */ - -} - -/**************** - * Encrypt input MPI. - * Use AES256 algorithm. - */ - -static void -aes256_encrypting (gcry_mpi_t key, gcry_mpi_t input, gcry_mpi_t * output) -{ /* */ - - int sign; - byte *key_buf; - byte *cipher_buf; - - unsigned int keylength; - unsigned int nbytes; - - - CIPHER_HANDLE cipher = cipher_open (9, CIPHER_MODE_CFB, 1); /* algo AES256 CFB mode in secure memory */ - cipher_setiv (cipher, NULL, 0); /* Zero IV */ - - key_buf = mpi_get_secure_buffer (key, &keylength, &sign); /* convert MPI key to string */ - cipher_setkey (cipher, key_buf, keylength); - wipememory (key_buf, sizeof key_buf); /* burn temp value */ - xfree (key_buf); - - cipher_buf = mpi_get_secure_buffer (input, &nbytes, &sign); /* convert MPI input to string */ - - cipher_encrypt (cipher, cipher_buf + 1, cipher_buf + 1, nbytes - 1); /* */ - cipher_close (cipher); /* destroy and free cipher state. */ - - mpi_set_buffer (*output, cipher_buf, nbytes, 0); /* convert encrypted string to MPI */ - wipememory (cipher_buf, sizeof cipher_buf); /* burn temp value */ - xfree (cipher_buf); -} - -/**************** - * Decrypt input MPI. - * Use AES256 algorithm. - */ - -static void -aes256_decrypting (gcry_mpi_t key, gcry_mpi_t input, gcry_mpi_t * output) -{ /* */ - - int sign; - byte *key_buf; - byte *cipher_buf; - - unsigned int keylength; - unsigned int nbytes; - - - CIPHER_HANDLE cipher = cipher_open (9, CIPHER_MODE_CFB, 1); /* algo AES256 CFB mode in secure memory */ - cipher_setiv (cipher, NULL, 0); /* Zero IV */ - - key_buf = mpi_get_secure_buffer (key, &keylength, &sign); /* convert MPI input to string */ - cipher_setkey (cipher, key_buf, keylength); - wipememory (key_buf, sizeof key_buf); /* burn temp value */ - xfree (key_buf); - - cipher_buf = mpi_get_secure_buffer (input, &nbytes, &sign); /* convert MPI input to string; */ + n = (mpi_get_nbits (value)+7)/8; + buf = gcry_xmalloc (n); + err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value); + if (err) + { + gcry_free (buf); + return err; + } + if (n < 1) + { + gcry_free (buf); + return GPG_ERR_INV_OBJ; + } + if (*buf != 4) + { + gcry_free (buf); + return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression. */ + } + if ( ((n-1)%2) ) + { + gcry_free (buf); + return GPG_ERR_INV_OBJ; + } + n = (n-1)/2; + err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL); + if (err) + { + gcry_free (buf); + return err; + } + err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL); + gcry_free (buf); + if (err) + { + mpi_free (x); + return err; + } - cipher_decrypt (cipher, cipher_buf + 1, cipher_buf + 1, nbytes - 1); /* */ - cipher_close (cipher); /* destroy and free cipher state. */ + mpi_set (result->x, x); + mpi_set (result->y, y); + mpi_set_ui (result->z, 1); - mpi_set_buffer (*output, cipher_buf, nbytes, 0); /* convert encrypted string to MPI */ - wipememory (cipher_buf, sizeof cipher_buf); /* burn temp value */ - xfree (cipher_buf); + mpi_free (x); + mpi_free (y); + + return 0; } -/* End of IFP ECElGamal weakness functions. */ -#endif /*0*/ - -/********************************************* - ************** interface ****************** - *********************************************/ - static gcry_err_code_t ecc_generate (int algo, unsigned int nbits, unsigned long dummy, gcry_mpi_t *skey, gcry_mpi_t **retfactors) { gpg_err_code_t err; ECC_secret_key sk; + gcry_mpi_t g_x, g_y, q_x, q_y; (void)algo; @@ -1810,7 +797,11 @@ ecc_generate (int algo, unsigned int nbits, unsigned long dummy, if (!*retfactors) return gpg_err_code_from_syserror (); - err = generate_key (&sk, nbits); + g_x = mpi_new (0); + g_y = mpi_new (0); + q_x = mpi_new (0); + q_y = mpi_new (0); + err = generate_key (&sk, nbits, g_x, g_y, q_x, q_y); if (err) { gcry_free (*retfactors); @@ -1818,39 +809,14 @@ ecc_generate (int algo, unsigned int nbits, unsigned long dummy, return err; } - skey[0] = sk.E.p_; - skey[1] = sk.E.a_; - skey[2] = sk.E.b_; - skey[3] = sk.E.G.x_; - skey[4] = sk.E.G.y_; - skey[5] = sk.E.G.z_; - skey[6] = sk.E.n_; - skey[7] = sk.Q.x_; - skey[8] = sk.Q.y_; - skey[9] = sk.Q.z_; - skey[10] = sk.d; - - if (DBG_CIPHER) - { - progress ('\n'); - - log_mpidump ("[ecc] p= ", skey[0]); - log_mpidump ("[ecc] a= ", skey[1]); - log_mpidump ("[ecc] b= ", skey[2]); - log_mpidump ("[ecc] Gx= ", skey[3]); - log_mpidump ("[ecc] Gy= ", skey[4]); - log_mpidump ("[ecc] Gz= ", skey[5]); - log_mpidump ("[ecc] n= ", skey[6]); - log_mpidump ("[ecc] Qx= ", skey[7]); - log_mpidump ("[ecc] Qy= ", skey[8]); - log_mpidump ("[ecc] Qz= ", skey[9]); - log_mpidump ("[ecc] d= ", skey[10]); - } + skey[0] = sk.E.p; + skey[1] = sk.E.a; + skey[2] = sk.E.b; + skey[3] = ec2os (g_x, g_y, sk.E.p); + skey[4] = sk.E.n; + skey[5] = ec2os (q_x, q_y, sk.E.p); + skey[6] = sk.d; - if (DBG_CIPHER) - { - log_debug ("ECC key Generated.\n"); - } return 0; } @@ -1858,6 +824,7 @@ ecc_generate (int algo, unsigned int nbits, unsigned long dummy, static gcry_err_code_t ecc_check_secret_key (int algo, gcry_mpi_t *skey) { + gpg_err_code_t err; ECC_secret_key sk; (void)algo; @@ -1866,110 +833,39 @@ ecc_check_secret_key (int algo, gcry_mpi_t *skey) || !skey[6] || !skey[7] || !skey[8] || !skey[9] || !skey[10]) return GPG_ERR_BAD_MPI; - if (DBG_CIPHER) + sk.E.p = skey[0]; + sk.E.a = skey[1]; + sk.E.b = skey[2]; + point_init (&sk.E.G); + err = os2ec (&sk.E.G, skey[3]); + if (err) { - log_debug ("ECC check secret key.\n"); + point_free (&sk.E.G); + return err; } - sk.E.p_ = skey[0]; - sk.E.a_ = skey[1]; - sk.E.b_ = skey[2]; - sk.E.G.x_ = skey[3]; - sk.E.G.y_ = skey[4]; - sk.E.G.z_ = skey[5]; - sk.E.n_ = skey[6]; - sk.Q.x_ = skey[7]; - sk.Q.y_ = skey[8]; - sk.Q.z_ = skey[9]; - sk.d = skey[10]; - - if (check_secret_key (&sk)) + sk.E.n = skey[4]; + point_init (&sk.Q); + err = os2ec (&sk.Q, skey[5]); + if (err) { - if (DBG_CIPHER) - log_debug ("Bad check: Bad secret key.\n"); - return GPG_ERR_BAD_SECKEY; + point_free (&sk.E.G); + point_free (&sk.Q); + return err; } - return 0; -} + sk.d = skey[6]; -#if 0 -static int -ecc_encrypt_FIXME (int algo, gcry_mpi_t * resarr, gcry_mpi_t data, gcry_mpi_t * pkey) -{ - ECC_public_key pk; - point R; - - if (algo != PUBKEY_ALGO_ECC && algo != PUBKEY_ALGO_ECC_E) - return G10ERR_PUBKEY_ALGO; - if (!data || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] - || !pkey[5] || !pkey[6] || !pkey[7] || !pkey[8] || !pkey[9]) - return G10ERR_BAD_MPI; - - if (DBG_CIPHER) + if (check_secret_key (&sk)) { - log_debug ("ECC encrypt.\n"); + point_free (&sk.E.G); + point_free (&sk.Q); + return GPG_ERR_BAD_SECKEY; } - pk.E.p_ = pkey[0]; - pk.E.a_ = pkey[1]; - pk.E.b_ = pkey[2]; - pk.E.G.x_ = pkey[3]; - pk.E.G.y_ = pkey[4]; - pk.E.G.z_ = pkey[5]; - pk.E.n_ = pkey[6]; - pk.Q.x_ = pkey[7]; - pk.Q.y_ = pkey[8]; - pk.Q.z_ = pkey[9]; - - R.x_ = resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.Q.x_)); - R.y_ = resarr[1] = mpi_alloc (mpi_get_nlimbs (pk.Q.y_)); - R.z_ = resarr[2] = mpi_alloc (mpi_get_nlimbs (pk.Q.z_)); - resarr[3] = mpi_alloc (mpi_get_nlimbs (pk.E.p_)); - - doEncrypt (data, &pk, &R, resarr[3]); - - resarr[0] = mpi_copy (R.x_); - resarr[1] = mpi_copy (R.y_); - resarr[2] = mpi_copy (R.z_); + point_free (&sk.E.G); + point_free (&sk.Q); return 0; } -int -ecc_decrypt_FIXME (int algo, gcry_mpi_t * result, gcry_mpi_t * data, gcry_mpi_t * skey) -{ - ECC_secret_key sk; - point R; - - if (algo != PUBKEY_ALGO_ECC && algo != PUBKEY_ALGO_ECC_E) - return G10ERR_PUBKEY_ALGO; - if (!data[0] || !data[1] || !data[2] || !data[3] || !skey[0] || !skey[1] - || !skey[2] || !skey[3] || !skey[4] || !skey[5] || !skey[6] || !skey[7] - || !skey[8] || !skey[9] || !skey[10]) - return G10ERR_BAD_MPI; - - if (DBG_CIPHER) - { - log_debug ("ECC decrypt.\n"); - } - R.x_ = data[0]; - R.y_ = data[1]; - R.z_ = data[2]; - sk.E.p_ = skey[0]; - sk.E.a_ = skey[1]; - sk.E.b_ = skey[2]; - sk.E.G.x_ = skey[3]; - sk.E.G.y_ = skey[4]; - sk.E.G.z_ = skey[5]; - sk.E.n_ = skey[6]; - sk.Q.x_ = skey[7]; - sk.Q.y_ = skey[8]; - sk.Q.z_ = skey[9]; - sk.d = skey[10]; - - *result = mpi_alloc_secure (mpi_get_nlimbs (sk.E.p_)); - *result = decrypt (*result, &sk, R, data[3]); - return 0; -} -#endif /*0*/ static gcry_err_code_t ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey) @@ -1980,24 +876,32 @@ ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey) (void)algo; if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] - || !skey[5] || !skey[6] || !skey[7] || !skey[8] || !skey[9] - || !skey[10]) + || !skey[5] || !skey[6] ) return GPG_ERR_BAD_MPI; - sk.E.p_ = skey[0]; - sk.E.a_ = skey[1]; - sk.E.b_ = skey[2]; - sk.E.G.x_ = skey[3]; - sk.E.G.y_ = skey[4]; - sk.E.G.z_ = skey[5]; - sk.E.n_ = skey[6]; - sk.Q.x_ = skey[7]; - sk.Q.y_ = skey[8]; - sk.Q.z_ = skey[9]; - sk.d = skey[10]; - - resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p_)); - resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p_)); + sk.E.p = skey[0]; + sk.E.a = skey[1]; + sk.E.b = skey[2]; + point_init (&sk.E.G); + err = os2ec (&sk.E.G, skey[3]); + if (err) + { + point_free (&sk.E.G); + return err; + } + sk.E.n = skey[4]; + point_init (&sk.Q); + err = os2ec (&sk.Q, skey[5]); + if (err) + { + point_free (&sk.E.G); + point_free (&sk.Q); + return err; + } + sk.d = skey[6]; + + resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p)); + resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p)); err = sign (data, &sk, resarr[0], resarr[1]); if (err) { @@ -2005,6 +909,8 @@ ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey) mpi_free (resarr[1]); resarr[0] = NULL; /* Mark array as released. */ } + point_free (&sk.E.G); + point_free (&sk.Q); return err; } @@ -2012,29 +918,40 @@ static gcry_err_code_t ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey, int (*cmp)(void *, gcry_mpi_t), void *opaquev) { + gpg_err_code_t err; ECC_public_key pk; (void)algo; if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2] - || !pkey[3] || !pkey[4] || !pkey[5] || !pkey[6] || !pkey[7] || !pkey[8] - || !pkey[9]) + || !pkey[3] || !pkey[4] || !pkey[5] ) return GPG_ERR_BAD_MPI; - if (DBG_CIPHER) - log_debug ("ECC verify.\n"); - pk.E.p_ = pkey[0]; - pk.E.a_ = pkey[1]; - pk.E.b_ = pkey[2]; - pk.E.G.x_ = pkey[3]; - pk.E.G.y_ = pkey[4]; - pk.E.G.z_ = pkey[5]; - pk.E.n_ = pkey[6]; - pk.Q.x_ = pkey[7]; - pk.Q.y_ = pkey[8]; - pk.Q.z_ = pkey[9]; - - return verify (hash, &pk, data[0], data[1]); + pk.E.p = pkey[0]; + pk.E.a = pkey[1]; + pk.E.b = pkey[2]; + point_init (&pk.E.G); + err = os2ec (&pk.E.G, pkey[3]); + if (err) + { + point_free (&pk.E.G); + return err; + } + pk.E.n = pkey[4]; + point_init (&pk.Q); + err = os2ec (&pk.Q, pkey[5]); + if (err) + { + point_free (&pk.E.G); + point_free (&pk.Q); + return err; + } + + err = verify (hash, &pk, data[0], data[1]); + + point_free (&pk.E.G); + point_free (&pk.Q); + return err; } @@ -2044,27 +961,6 @@ ecc_get_nbits (int algo, gcry_mpi_t *pkey) { (void)algo; - if (DBG_CIPHER) - { - log_debug ("ECC get nbits.\n"); - } - - if (DBG_CIPHER) - { - progress ('\n'); - - log_mpidump ("[ecc] p= ", pkey[0]); - log_mpidump ("[ecc] a= ", pkey[1]); - log_mpidump ("[ecc] b= ", pkey[2]); - log_mpidump ("[ecc] Gx= ", pkey[3]); - log_mpidump ("[ecc] Gy= ", pkey[4]); - log_mpidump ("[ecc] Gz= ", pkey[5]); - log_mpidump ("[ecc] n= ", pkey[6]); - log_mpidump ("[ecc] Qx= ", pkey[7]); - log_mpidump ("[ecc] Qy= ", pkey[8]); - log_mpidump ("[ecc] Qz= ", pkey[9]); - } - return mpi_get_nbits (pkey[0]); } @@ -2077,8 +973,8 @@ static const char *ecdsa_names[] = gcry_pk_spec_t _gcry_pubkey_spec_ecdsa = { - "ECDSA", ecdsa_names, - "pabxyznXYZ", "pabxyznXYZd", "", "rs", "pabxyznXYZ", + "ECDSA", ecdsa_names, + "pabgnq", "pabgnqd", "", "rs", "pabgnq", GCRY_PK_USAGE_SIGN, ecc_generate, ecc_check_secret_key, @@ -2089,5 +985,3 @@ gcry_pk_spec_t _gcry_pubkey_spec_ecdsa = ecc_get_nbits }; - - diff --git a/cipher/pubkey.c b/cipher/pubkey.c index fe9ccdf6..82df226b 100644 --- a/cipher/pubkey.c +++ b/cipher/pubkey.c @@ -1928,7 +1928,7 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms) const char *algo_name = NULL; int algo; const char *sec_elems = NULL, *pub_elems = NULL; - gcry_mpi_t skey[10], *factors = NULL; + gcry_mpi_t skey[12], *factors = NULL; unsigned int nbits = 0; unsigned long use_e = 0; unsigned int qbits; @@ -1990,6 +1990,8 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms) algo_name = pubkey->name; pub_elems = pubkey->elements_pkey; sec_elems = pubkey->elements_skey; + if (strlen (sec_elems) >= DIM(skey)) + BUG (); /* Handle the optional rsa-use-e element. */ l2 = gcry_sexp_find_token (list, "rsa-use-e", 0); diff --git a/mpi/ChangeLog b/mpi/ChangeLog index fac7e0ce..8ca4783e 100644 --- a/mpi/ChangeLog +++ b/mpi/ChangeLog @@ -1,3 +1,7 @@ +2007-03-28 Werner Koch <wk@g10code.com> + + * ec.c: New. + 2007-03-23 Werner Koch <wk@g10code.com> * mpi-bit.c (_gcry_mpi_lshift_limbs): Assign AP after the resize. diff --git a/mpi/Makefile.am b/mpi/Makefile.am index 8ee15b78..2b17f455 100644 --- a/mpi/Makefile.am +++ b/mpi/Makefile.am @@ -175,7 +175,8 @@ libmpi_la_SOURCES = longlong.h \ mpicoder.c \ mpih-div.c \ mpih-mul.c \ - mpiutil.c + mpiutil.c \ + ec.c libmpi_la_LIBADD = @MPI_MOD_LIST_LO@ libmpi_la_DEPENDENCIES = @MPI_MOD_LIST_LO@ diff --git a/mpi/ec.c b/mpi/ec.c new file mode 100644 index 00000000..6addb66f --- /dev/null +++ b/mpi/ec.c @@ -0,0 +1,690 @@ +/* ec.c - Elliptic Curve functions + Copyright (C) 2007 Free Software Foundation, Inc. + + This file is part of Libgcrypt. + + Libgcrypt is free software; you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as + published by the Free Software Foundation; either version 2.1 of + the License, or (at your option) any later version. + + Libgcrypt is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, + USA. */ + + +#include <config.h> +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> + +#include "mpi-internal.h" +#include "longlong.h" +#include "g10lib.h" + + +#define point_init(a) _gcry_mpi_ec_point_init ((a)) +#define point_free(a) _gcry_mpi_ec_point_free ((a)) + + +/* Object to represent a point in projective coordinates. */ +/* Currently defined in mpi.h */ + +/* This context is used with all our EC functions. */ +struct mpi_ec_ctx_s +{ + /* Domain parameters. */ + gcry_mpi_t p; /* Prime specifying the field GF(p). */ + gcry_mpi_t a; /* First coefficient of the Weierstrass equation. */ + + int a_is_pminus3; /* True if A = P - 3. */ + + /* Some often used constants. */ + gcry_mpi_t one; + gcry_mpi_t two; + gcry_mpi_t three; + gcry_mpi_t four; + gcry_mpi_t eight; + gcry_mpi_t two_inv_p; + + /* Scratch variables. */ + gcry_mpi_t scratch[11]; + + /* Helper for fast reduction. */ +/* int nist_nbits; /\* If this is a NIST curve, the number of bits. *\/ */ +/* gcry_mpi_t s[10]; */ +/* gcry_mpi_t c; */ + +}; + + + +/* Initialized a point object. gcry_mpi_ec_point_free shall be used + to release this object. */ +void +_gcry_mpi_ec_point_init (mpi_point_t *p) +{ + p->x = mpi_new (0); + p->y = mpi_new (0); + p->z = mpi_new (0); +} + + +/* Release a point object. */ +void +_gcry_mpi_ec_point_free (mpi_point_t *p) +{ + mpi_free (p->x); p->x = NULL; + mpi_free (p->y); p->y = NULL; + mpi_free (p->z); p->z = NULL; +} + +/* Set the value from S into D. */ +static void +point_set (mpi_point_t *d, mpi_point_t *s) +{ + mpi_set (d->x, s->x); + mpi_set (d->y, s->y); + mpi_set (d->z, s->z); +} + + + +static void +ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) +{ + mpi_addm (w, u, v, ctx->p); +} + +static void +ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) +{ + mpi_subm (w, u, v, ctx->p); +} + +static void +ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) +{ +#if 0 + /* NOTE: This code works only for limb sizes of 32 bit. */ + mpi_limb_t *wp, *sp; + + if (ctx->nist_nbits == 192) + { + mpi_mul (w, u, v); + mpi_resize (w, 12); + wp = w->d; + + sp = ctx->s[0]->d; + sp[0*2+0] = wp[0*2+0]; + sp[0*2+1] = wp[0*2+1]; + sp[1*2+0] = wp[1*2+0]; + sp[1*2+1] = wp[1*2+1]; + sp[2*2+0] = wp[2*2+0]; + sp[2*2+1] = wp[2*2+1]; + + sp = ctx->s[1]->d; + sp[0*2+0] = wp[3*2+0]; + sp[0*2+1] = wp[3*2+1]; + sp[1*2+0] = wp[3*2+0]; + sp[1*2+1] = wp[3*2+1]; + sp[2*2+0] = 0; + sp[2*2+1] = 0; + + sp = ctx->s[2]->d; + sp[0*2+0] = 0; + sp[0*2+1] = 0; + sp[1*2+0] = wp[4*2+0]; + sp[1*2+1] = wp[4*2+1]; + sp[2*2+0] = wp[4*2+0]; + sp[2*2+1] = wp[4*2+1]; + + sp = ctx->s[3]->d; + sp[0*2+0] = wp[5*2+0]; + sp[0*2+1] = wp[5*2+1]; + sp[1*2+0] = wp[5*2+0]; + sp[1*2+1] = wp[5*2+1]; + sp[2*2+0] = wp[5*2+0]; + sp[2*2+1] = wp[5*2+1]; + + ctx->s[0]->nlimbs = 6; + ctx->s[1]->nlimbs = 6; + ctx->s[2]->nlimbs = 6; + ctx->s[3]->nlimbs = 6; + + mpi_add (ctx->c, ctx->s[0], ctx->s[1]); + mpi_add (ctx->c, ctx->c, ctx->s[2]); + mpi_add (ctx->c, ctx->c, ctx->s[3]); + + while ( mpi_cmp (ctx->c, ctx->p ) >= 0 ) + mpi_sub ( ctx->c, ctx->c, ctx->p ); + mpi_set (w, ctx->c); + } + else if (ctx->nist_nbits == 384) + { + int i; + mpi_mul (w, u, v); + mpi_resize (w, 24); + wp = w->d; + +#define NEXT(a) do { ctx->s[(a)]->nlimbs = 12; \ + sp = ctx->s[(a)]->d; \ + i = 0; } while (0) +#define X(a) do { sp[i++] = wp[(a)];} while (0) +#define X0(a) do { sp[i++] = 0; } while (0) + NEXT(0); + X(0);X(1);X(2);X(3);X(4);X(5);X(6);X(7);X(8);X(9);X(10);X(11); + NEXT(1); + X0();X0();X0();X0();X(21);X(22);X(23);X0();X0();X0();X0();X0(); + NEXT(2); + X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);X(21);X(22);X(23); + NEXT(3); + X(21);X(22);X(23);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20); + NEXT(4); + X0();X(23);X0();X(20);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19); + NEXT(5); + X0();X0();X0();X0();X(20);X(21);X(22);X(23);X0();X0();X0();X0(); + NEXT(6); + X(20);X0();X0();X(21);X(22);X(23);X0();X0();X0();X0();X0();X0(); + NEXT(7); + X(23);X(12);X(13);X(14);X(15);X(16);X(17);X(18);X(19);X(20);X(21);X(22); + NEXT(8); + X0();X(20);X(21);X(22);X(23);X0();X0();X0();X0();X0();X0();X0(); + NEXT(9); + X0();X0();X0();X(23);X(23);X0();X0();X0();X0();X0();X0();X0(); +#undef X0 +#undef X +#undef NEXT + mpi_add (ctx->c, ctx->s[0], ctx->s[1]); + mpi_add (ctx->c, ctx->c, ctx->s[1]); + mpi_add (ctx->c, ctx->c, ctx->s[2]); + mpi_add (ctx->c, ctx->c, ctx->s[3]); + mpi_add (ctx->c, ctx->c, ctx->s[4]); + mpi_add (ctx->c, ctx->c, ctx->s[5]); + mpi_add (ctx->c, ctx->c, ctx->s[6]); + mpi_sub (ctx->c, ctx->c, ctx->s[7]); + mpi_sub (ctx->c, ctx->c, ctx->s[8]); + mpi_sub (ctx->c, ctx->c, ctx->s[9]); + + while ( mpi_cmp (ctx->c, ctx->p ) >= 0 ) + mpi_sub ( ctx->c, ctx->c, ctx->p ); + while ( ctx->c->sign ) + mpi_add ( ctx->c, ctx->c, ctx->p ); + mpi_set (w, ctx->c); + } + else +#endif /*0*/ + mpi_mulm (w, u, v, ctx->p); +} + +static void +ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e, + mpi_ec_t ctx) +{ + mpi_powm (w, b, e, ctx->p); +} + +static void +ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx) +{ + mpi_invm (x, a, ctx->p); +} + + + +/* This function returns a new context for elliptic curve based on the + field GF(p). P is the prime specifying thuis field, A is the first + coefficient. + + This context needs to be released using _gcry_mpi_ec_free. */ +mpi_ec_t +_gcry_mpi_ec_init (gcry_mpi_t p, gcry_mpi_t a) +{ + int i; + mpi_ec_t ctx; + gcry_mpi_t tmp; + + mpi_normalize (p); + mpi_normalize (a); + + /* Fixme: Do we want to check some constraints? e.g. + a < p + */ + + ctx = gcry_xcalloc (1, sizeof *ctx); + + ctx->p = mpi_copy (p); + ctx->a = mpi_copy (a); + + tmp = mpi_alloc_like (ctx->p); + mpi_sub_ui (tmp, ctx->p, 3); + ctx->a_is_pminus3 = !mpi_cmp (ctx->a, tmp); + mpi_free (tmp); + + + /* Allocate constants. */ + ctx->one = mpi_alloc_set_ui (1); + ctx->two = mpi_alloc_set_ui (2); + ctx->three = mpi_alloc_set_ui (3); + ctx->four = mpi_alloc_set_ui (4); + ctx->eight = mpi_alloc_set_ui (8); + ctx->two_inv_p = mpi_alloc (0); + ec_invm (ctx->two_inv_p, ctx->two, ctx); + + /* Allocate scratch variables. */ + for (i=0; i< DIM(ctx->scratch); i++) + ctx->scratch[i] = mpi_alloc_like (ctx->p); + + /* Prepare for fast reduction. */ + /* FIXME: need a test for NIST values. However it does not gain us + any real advantage, for 384 bits it is actually slower than using + mpi_mulm. */ +/* ctx->nist_nbits = mpi_get_nbits (ctx->p); */ +/* if (ctx->nist_nbits == 192) */ +/* { */ +/* for (i=0; i < 4; i++) */ +/* ctx->s[i] = mpi_new (192); */ +/* ctx->c = mpi_new (192*2); */ +/* } */ +/* else if (ctx->nist_nbits == 384) */ +/* { */ +/* for (i=0; i < 10; i++) */ +/* ctx->s[i] = mpi_new (384); */ +/* ctx->c = mpi_new (384*2); */ +/* } */ + + return ctx; +} + +void +_gcry_mpi_ec_free (mpi_ec_t ctx) +{ + int i; + + if (!ctx) + return; + + mpi_free (ctx->p); + mpi_free (ctx->a); + + mpi_free (ctx->one); + mpi_free (ctx->two); + mpi_free (ctx->three); + mpi_free (ctx->four); + mpi_free (ctx->eight); + + mpi_free (ctx->two_inv_p); + + for (i=0; i< DIM(ctx->scratch); i++) + mpi_free (ctx->scratch[i]); + +/* if (ctx->nist_nbits == 192) */ +/* { */ +/* for (i=0; i < 4; i++) */ +/* mpi_free (ctx->s[i]); */ +/* mpi_free (ctx->c); */ +/* } */ +/* else if (ctx->nist_nbits == 384) */ +/* { */ +/* for (i=0; i < 10; i++) */ +/* mpi_free (ctx->s[i]); */ +/* mpi_free (ctx->c); */ +/* } */ + + gcry_free (ctx); +} + +/* Compute the affine coordinates from the projective coordinates in + POINT. Set them into X and Y. If one coordinate is not required, + X or Y may be passed as NULL. CTX is the usual context. Returns: 0 + on success or !0 if POINT is at infinity. */ +int +_gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t *point, + mpi_ec_t ctx) +{ + gcry_mpi_t z1, z2, z3; + + if (!mpi_cmp_ui (point->z, 0)) + return -1; + + z1 = mpi_new (0); + z2 = mpi_new (0); + ec_invm (z1, point->z, ctx); /* z1 = z^(-1) mod p */ + ec_mulm (z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ + + if (x) + ec_mulm (x, point->x, z2, ctx); + + if (y) + { + z3 = mpi_new (0); + ec_mulm (z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ + ec_mulm (y, point->y, z3, ctx); + mpi_free (z3); + } + + mpi_free (z2); + mpi_free (z1); + return 0; +} + + + + + +/* RESULT = 2 * POINT */ +void +_gcry_mpi_ec_dup_point (mpi_point_t *result, mpi_point_t *point, mpi_ec_t ctx) +{ +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define t1 (ctx->scratch[0]) +#define t2 (ctx->scratch[1]) +#define t3 (ctx->scratch[2]) +#define l1 (ctx->scratch[3]) +#define l2 (ctx->scratch[4]) +#define l3 (ctx->scratch[5]) + + if (!mpi_cmp_ui (point->y, 0) || !mpi_cmp_ui (point->z, 0)) + { + /* P_y == 0 || P_z == 0 => [1:1:0] */ + mpi_set_ui (x3, 1); + mpi_set_ui (y3, 1); + mpi_set_ui (z3, 0); + } + else + { + if (ctx->a_is_pminus3) /* Use the faster case. */ + { + /* L1 = 3(X - Z^2)(X + Z^2) */ + /* T1: used for Z^2. */ + /* T2: used for the right term. */ + ec_powm (t1, point->z, ctx->two, ctx); + ec_subm (l1, point->x, t1, ctx); + ec_mulm (l1, l1, ctx->three, ctx); + ec_addm (t2, point->x, t1, ctx); + ec_mulm (l1, l1, t2, ctx); + } + else /* Standard case. */ + { + /* L1 = 3X^2 + aZ^4 */ + /* T1: used for aZ^4. */ + ec_powm (l1, point->x, ctx->two, ctx); + ec_mulm (l1, l1, ctx->three, ctx); + ec_powm (t1, point->z, ctx->four, ctx); + ec_mulm (t1, t1, ctx->a, ctx); + ec_addm (l1, l1, t1, ctx); + } + /* Z3 = 2YZ */ + ec_mulm (z3, point->y, point->z, ctx); + ec_mulm (z3, z3, ctx->two, ctx); + + /* L2 = 4XY^2 */ + /* T2: used for Y2; required later. */ + ec_powm (t2, point->y, ctx->two, ctx); + ec_mulm (l2, t2, point->x, ctx); + ec_mulm (l2, l2, ctx->four, ctx); + + /* X3 = L1^2 - 2L2 */ + /* T1: used for L2^2. */ + ec_powm (x3, l1, ctx->two, ctx); + ec_mulm (t1, l2, ctx->two, ctx); + ec_subm (x3, x3, t1, ctx); + + /* L3 = 8Y^4 */ + /* T2: taken from above. */ + ec_powm (t2, t2, ctx->two, ctx); + ec_mulm (l3, t2, ctx->eight, ctx); + + /* Y3 = L1(L2 - X3) - L3 */ + ec_subm (y3, l2, x3, ctx); + ec_mulm (y3, y3, l1, ctx); + ec_subm (y3, y3, l3, ctx); + } + +#undef x3 +#undef y3 +#undef z3 +#undef t1 +#undef t2 +#undef t3 +#undef l1 +#undef l2 +#undef l3 +} + + + +/* RESULT = P1 + P2 */ +void +_gcry_mpi_ec_add_points (mpi_point_t *result, + mpi_point_t *p1, mpi_point_t *p2, + mpi_ec_t ctx) +{ +#define x1 (p1->x ) +#define y1 (p1->y ) +#define z1 (p1->z ) +#define x2 (p2->x ) +#define y2 (p2->y ) +#define z2 (p2->z ) +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define l1 (ctx->scratch[0]) +#define l2 (ctx->scratch[1]) +#define l3 (ctx->scratch[2]) +#define l4 (ctx->scratch[3]) +#define l5 (ctx->scratch[4]) +#define l6 (ctx->scratch[5]) +#define l7 (ctx->scratch[6]) +#define l8 (ctx->scratch[7]) +#define l9 (ctx->scratch[8]) +#define t1 (ctx->scratch[9]) +#define t2 (ctx->scratch[10]) + + if ( (!mpi_cmp (x1, x2)) && (!mpi_cmp (y1, y2)) && (!mpi_cmp (z1, z2)) ) + { + /* Same point; need to call the duplicate function. */ + _gcry_mpi_ec_dup_point (result, p1, ctx); + } + else if (!mpi_cmp_ui (z1, 0)) + { + /* P1 is at infinity. */ + mpi_set (x3, p2->x); + mpi_set (y3, p2->y); + mpi_set (z3, p2->z); + } + else if (!mpi_cmp_ui (z2, 0)) + { + /* P2 is at infinity. */ + mpi_set (x3, p1->x); + mpi_set (y3, p1->y); + mpi_set (z3, p1->z); + } + else + { + int z1_is_one = !mpi_cmp_ui (z1, 1); + int z2_is_one = !mpi_cmp_ui (z2, 1); + + /* l1 = x1 z2^2 */ + /* l2 = x2 z1^2 */ + if (z2_is_one) + mpi_set (l1, x1); + else + { + ec_powm (l1, z2, ctx->two, ctx); + ec_mulm (l1, l1, x1, ctx); + } + if (z1_is_one) + mpi_set (l2, x1); + else + { + ec_powm (l2, z1, ctx->two, ctx); + ec_mulm (l2, l2, x2, ctx); + } + /* l3 = l1 - l2 */ + ec_subm (l3, l1, l2, ctx); + /* l4 = y1 z2^3 */ + ec_powm (l4, z2, ctx->three, ctx); + ec_mulm (l4, l4, y1, ctx); + /* l5 = y2 z1^3 */ + ec_powm (l5, z1, ctx->three, ctx); + ec_mulm (l5, l5, y2, ctx); + /* l6 = l4 - l5 */ + ec_subm (l6, l4, l5, ctx); + + if (!mpi_cmp_ui (l3, 0)) + { + if (!mpi_cmp_ui (l6, 0)) + { + /* P1 and P2 are the same - use duplicate function. */ + _gcry_mpi_ec_dup_point (result, p1, ctx); + } + else + { + /* P1 is the inverse of P2. */ + mpi_set_ui (x3, 1); + mpi_set_ui (y3, 1); + mpi_set_ui (z3, 0); + } + } + else + { + /* l7 = l1 + l2 */ + ec_addm (l7, l1, l2, ctx); + /* l8 = l4 + l5 */ + ec_addm (l8, l4, l5, ctx); + /* z3 = z1 z2 l3 */ + ec_mulm (z3, z1, z2, ctx); + ec_mulm (z3, z3, l3, ctx); + /* x3 = l6^2 - l7 l3^2 */ + ec_powm (t1, l6, ctx->two, ctx); + ec_powm (t2, l3, ctx->two, ctx); + ec_mulm (t2, t2, l7, ctx); + ec_subm (x3, t1, t2, ctx); + /* l9 = l7 l3^2 - 2 x3 */ + ec_mulm (t1, x3, ctx->two, ctx); + ec_subm (l9, t2, t1, ctx); + /* y3 = (l9 l6 - l8 l3^3)/2 */ + ec_mulm (l9, l9, l6, ctx); + ec_powm (t1, l3, ctx->three, ctx); /* fixme: Use saved value*/ + ec_mulm (t1, t1, l8, ctx); + ec_subm (y3, l9, t1, ctx); + ec_mulm (y3, y3, ctx->two_inv_p, ctx); + } + } + +#undef x1 +#undef y1 +#undef z1 +#undef x2 +#undef y2 +#undef z2 +#undef x3 +#undef y3 +#undef z3 +#undef l1 +#undef l2 +#undef l3 +#undef l4 +#undef l5 +#undef l6 +#undef l7 +#undef l8 +#undef l9 +#undef t1 +#undef t2 +} + + + +/* Scalar point multiplication - the main function for ECC. If takes + an integer SCALAR and a POINT as well as the usual context CTX. + RESULT will be set to the resulting point. */ +void +_gcry_mpi_ec_mul_point (mpi_point_t *result, + gcry_mpi_t scalar, mpi_point_t *point, + mpi_ec_t ctx) +{ + gcry_mpi_t x1, y1, z1, k, h, yy; + unsigned int i, loops; + mpi_point_t p1, p2, p1inv; + + x1 = mpi_alloc_like (ctx->p); + y1 = mpi_alloc_like (ctx->p); + h = mpi_alloc_like (ctx->p); + k = mpi_copy (scalar); + yy = mpi_copy (point->y); + + if ( mpi_is_neg (k) ) + { + k->sign = 0; + ec_invm (yy, yy, ctx); + } + + if (!mpi_cmp_ui (point->z, 1)) + { + mpi_set (x1, point->x); + mpi_set (y1, yy); + } + else + { + gcry_mpi_t z2, z3; + + z2 = mpi_alloc_like (ctx->p); + z3 = mpi_alloc_like (ctx->p); + ec_mulm (z2, point->z, point->z, ctx); + ec_mulm (z3, point->z, z2, ctx); + ec_invm (z2, z2, ctx); + ec_mulm (x1, point->x, z2, ctx); + ec_invm (z3, z3, ctx); + ec_mulm (y1, yy, z3, ctx); + mpi_free (z2); + mpi_free (z3); + } + z1 = mpi_copy (ctx->one); + + mpi_mul (h, k, ctx->three); /* h = 3k */ + loops = mpi_get_nbits (h); + + mpi_set (result->x, point->x); + mpi_set (result->y, yy); mpi_free (yy); yy = NULL; + mpi_set (result->z, point->z); + + p1.x = x1; x1 = NULL; + p1.y = y1; y1 = NULL; + p1.z = z1; z1 = NULL; + point_init (&p2); + point_init (&p1inv); + + for (i=loops-2; i > 0; i--) + { + _gcry_mpi_ec_dup_point (result, result, ctx); + if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0) + { + point_set (&p2, result); + _gcry_mpi_ec_add_points (result, &p2, &p1, ctx); + } + if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1) + { + point_set (&p2, result); + /* Invert point: y = p - y mod p */ + point_set (&p1inv, &p1); + ec_subm (p1inv.y, ctx->p, p1inv.y, ctx); + _gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx); + } + } + + point_free (&p1); + point_free (&p2); + point_free (&p1inv); + mpi_free (h); + mpi_free (k); +} @@ -228,5 +228,37 @@ void _gcry_mpi_normalize( gcry_mpi_t a ); #define mpi_invm(a,b,c) _gcry_mpi_invm ((a),(b),(c)) void _gcry_mpi_invm( gcry_mpi_t x, gcry_mpi_t u, gcry_mpi_t v ); +/*-- ec.c --*/ + +/* Object to represent a point in projective coordinates. */ +struct mpi_point_s; +typedef struct mpi_point_s mpi_point_t; +struct mpi_point_s +{ + gcry_mpi_t x; + gcry_mpi_t y; + gcry_mpi_t z; +}; + +/* Context used with elliptic curve fucntions. */ +struct mpi_ec_ctx_s; +typedef struct mpi_ec_ctx_s *mpi_ec_t; + +void _gcry_mpi_ec_point_init (mpi_point_t *p); +void _gcry_mpi_ec_point_free (mpi_point_t *p); +mpi_ec_t _gcry_mpi_ec_init (gcry_mpi_t p, gcry_mpi_t a); +void _gcry_mpi_ec_free (mpi_ec_t ctx); +int _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t *point, + mpi_ec_t ctx); +void _gcry_mpi_ec_dup_point (mpi_point_t *result, + mpi_point_t *point, mpi_ec_t ctx); +void _gcry_mpi_ec_add_points (mpi_point_t *result, + mpi_point_t *p1, mpi_point_t *p2, + mpi_ec_t ctx); +void _gcry_mpi_ec_mul_point (mpi_point_t *result, + gcry_mpi_t scalar, mpi_point_t *point, + mpi_ec_t ctx); + + #endif /*G10_MPI_H*/ diff --git a/tests/ChangeLog b/tests/ChangeLog index 07e48d42..a46800ea 100644 --- a/tests/ChangeLog +++ b/tests/ChangeLog @@ -1,3 +1,10 @@ +2007-03-28 Werner Koch <wk@g10code.com> + + * benchmark.c (dsa_bench): New args ITERATIONS and PRINT_HEADER. + (main): Call dsa and ecc benchs. + + * Makefile.am (TESTS): Move pkbench to EXTRA_PROGRAMS. + 2007-03-22 Werner Koch <wk@g10code.com> * benchmark.c (die): New. diff --git a/tests/Makefile.am b/tests/Makefile.am index 1c892902..ecd77c35 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -21,11 +21,9 @@ TESTS = t-mpi-bit prime register ac ac-schemes ac-data basic \ mpitests tsexp keygen pubkey hmac keygrip -# pkbench uses mmap for no good reason. Needs to be fixed. Code for -# this can be found in libksba/tests. # random tests forking thus no a test for W32 does not make any sense. if !HAVE_W32_SYSTEM -TESTS += pkbench random +TESTS += random endif # The last test to run. @@ -39,6 +37,8 @@ AM_CFLAGS = $(GPG_ERROR_CFLAGS) LDADD = ../src/libgcrypt.la -EXTRA_PROGRAMS = testapi +# pkbench uses mmap for no good reason. Needs to be fixed. Code for +# this can be found in libksba/tests. +EXTRA_PROGRAMS = testapi pkbench noinst_PROGRAMS = $(TESTS) diff --git a/tests/benchmark.c b/tests/benchmark.c index 5cdf4f0e..dc231295 100644 --- a/tests/benchmark.c +++ b/tests/benchmark.c @@ -535,7 +535,7 @@ cipher_bench ( const char *algoname ) static void -dsa_bench (void) +dsa_bench (int iterations, int print_header) { gpg_error_t err; gcry_sexp_t pub_key[3], sec_key[3]; @@ -569,9 +569,10 @@ dsa_bench (void) exit (1); } - - fputs ("Algorithm generate 100*sign 100*verify\n" - "----------------------------------------------\n", stdout); + if (print_header) + printf ("Algorithm generate %4d*sign %4d*verify\n" + "----------------------------------------------\n", + iterations, iterations ); for (i=0; i < DIM (q_sizes); i++) { gcry_mpi_t x; @@ -591,7 +592,7 @@ dsa_bench (void) fflush (stdout); start_timer (); - for (j=0; j < 100; j++) + for (j=0; j < iterations; j++) { err = gcry_pk_sign (&sig, data, sec_key[i]); if (err) @@ -607,7 +608,7 @@ dsa_bench (void) fflush (stdout); start_timer (); - for (j=0; j < 100; j++) + for (j=0; j < iterations; j++) { err = gcry_pk_verify (sig, data, pub_key[i]); if (err) @@ -636,16 +637,17 @@ dsa_bench (void) static void -ecc_bench (void) +ecc_bench (int iterations, int print_header) { #if USE_ECC gpg_error_t err; - int p_sizes[] = { 192, 256, 384 /*, 521*/ }; + int p_sizes[] = { 192, 224, 256, 384, 521 }; int testno; - - fputs ("Algorithm generate 100*sign 100*verify\n" - "----------------------------------------------\n", stdout); + if (print_header) + printf ("Algorithm generate %4d*sign %4d*verify\n" + "----------------------------------------------\n", + iterations, iterations ); for (testno=0; testno < DIM (p_sizes); testno++) { gcry_sexp_t key_spec, key_pair, pub_key, sec_key; @@ -689,7 +691,7 @@ ecc_bench (void) die ("converting data failed: %s\n", gcry_strerror (err)); start_timer (); - for (count=0; count < 100; count++) + for (count=0; count < iterations; count++) { gcry_sexp_release (sig); err = gcry_pk_sign (&sig, data, sec_key); @@ -701,7 +703,7 @@ ecc_bench (void) fflush (stdout); start_timer (); - for (count=0; count < 100; count++) + for (count=0; count < iterations; count++) { err = gcry_pk_verify (sig, data, pub_key); if (err) @@ -811,10 +813,14 @@ main( int argc, char **argv ) if ( !argc ) { + gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0); md_bench (NULL); putchar ('\n'); cipher_bench (NULL); putchar ('\n'); + dsa_bench (100, 1); + ecc_bench (100, 0); + putchar ('\n'); mpi_bench (); putchar ('\n'); random_bench (0); @@ -858,12 +864,12 @@ main( int argc, char **argv ) else if ( !strcmp (*argv, "dsa")) { gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0); - dsa_bench (); + dsa_bench (100, 1); } else if ( !strcmp (*argv, "ecc")) { gcry_control (GCRYCTL_ENABLE_QUICK_RANDOM, 0); - ecc_bench (); + ecc_bench (100, 1); } else { @@ -874,4 +880,3 @@ main( int argc, char **argv ) return 0; } - |