[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[SCM] GNU gnutls branch, gnutls_3_1_x, updated. gnutls_3_1_0-48-g4ae6b97
|
From: |
Nikos Mavrogiannopoulos |
|
Subject: |
[SCM] GNU gnutls branch, gnutls_3_1_x, updated. gnutls_3_1_0-48-g4ae6b97 |
|
Date: |
Sun, 02 Sep 2012 18:52:10 +0000 |
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU gnutls".
http://git.savannah.gnu.org/cgit/gnutls.git/commit/?id=4ae6b978306bd15a5d6dec65fba26a9d2faf7d9a
The branch, gnutls_3_1_x has been updated
via 4ae6b978306bd15a5d6dec65fba26a9d2faf7d9a (commit)
via f988c1b1cc57b53895b60f47aaa7c5b178f31796 (commit)
via a93b8fb12792930d14a51eee78261913142431c8 (commit)
via 45bf20ad3f799bf219958c3ba705898440c74e4a (commit)
via 6a26fe8843054ef58fe947b3301c995122ffa0ac (commit)
via 2cdd21e598e1b5adbe23dd4387259ba580ce2657 (commit)
from cf897b154ec929335cb377b0556330cc60e72882 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 4ae6b978306bd15a5d6dec65fba26a9d2faf7d9a
Author: Nikos Mavrogiannopoulos <address@hidden>
Date: Sun Sep 2 20:12:00 2012 +0200
bumped version
commit f988c1b1cc57b53895b60f47aaa7c5b178f31796
Author: Nikos Mavrogiannopoulos <address@hidden>
Date: Sun Sep 2 10:39:49 2012 +0200
removed unused code
commit a93b8fb12792930d14a51eee78261913142431c8
Author: Nikos Mavrogiannopoulos <address@hidden>
Date: Thu Aug 30 20:02:18 2012 +0200
corrected deinitialization of wmnaf cache.
commit 45bf20ad3f799bf219958c3ba705898440c74e4a
Author: Ilya Tumaykin <address@hidden>
Date: Thu Aug 30 11:36:34 2012 +0400
wMNAF-based multiplication
Signed-off-by: Nikos Mavrogiannopoulos <address@hidden>
commit 6a26fe8843054ef58fe947b3301c995122ffa0ac
Author: Nikos Mavrogiannopoulos <address@hidden>
Date: Sun Sep 2 19:50:34 2012 +0200
documented fix
commit 2cdd21e598e1b5adbe23dd4387259ba580ce2657
Author: Nikos Mavrogiannopoulos <address@hidden>
Date: Sun Sep 2 18:46:47 2012 +0200
The default system_recv_timeout() doesn't include a call to recv() to avoid
issue in few systems.
-----------------------------------------------------------------------
Summary of changes:
NEWS | 10 +-
configure.ac | 2 +-
doc/invoke-gnutls-cli.texi | 3 +-
doc/invoke-gnutls-serv.texi | 3 +-
lib/gnutls_buffers.c | 9 +-
lib/gnutls_global.c | 1 +
lib/gnutls_global.h | 1 +
lib/nettle/Makefile.am | 8 +-
lib/nettle/ecc.h | 45 +++-
lib/nettle/ecc_make_key.c | 13 +-
lib/nettle/ecc_mulmod_wmnaf.c | 165 +++++++++++
lib/nettle/ecc_mulmod_wmnaf_cached.c | 457 +++++++++++++++++++++++++++++
lib/nettle/ecc_projective_add_point.c | 41 +++-
lib/nettle/ecc_projective_add_point_ng.c | 462 ++++++++++++++++++++++++++++++
lib/nettle/ecc_projective_dbl_point_3.c | 226 ++++++++-------
lib/nettle/ecc_projective_isneutral.c | 81 ++++++
lib/nettle/ecc_projective_negate_point.c | 56 ++++
lib/nettle/ecc_shared_secret.c | 2 +-
lib/nettle/ecc_sign_hash.c | 6 +-
lib/nettle/ecc_verify_hash.c | 9 +-
lib/nettle/init.c | 12 +-
lib/nettle/pk.c | 18 +-
lib/nettle/wmnaf.c | 154 ++++++++++
lib/system.c | 6 +-
m4/hooks.m4 | 4 +-
src/cli-args.c | 2 +-
src/cli-args.h | 2 +-
27 files changed, 1638 insertions(+), 160 deletions(-)
create mode 100644 lib/nettle/ecc_mulmod_wmnaf.c
create mode 100644 lib/nettle/ecc_mulmod_wmnaf_cached.c
create mode 100644 lib/nettle/ecc_projective_add_point_ng.c
create mode 100644 lib/nettle/ecc_projective_isneutral.c
create mode 100644 lib/nettle/ecc_projective_negate_point.c
create mode 100644 lib/nettle/wmnaf.c
diff --git a/NEWS b/NEWS
index 9a2cd4a..c733a92 100644
--- a/NEWS
+++ b/NEWS
@@ -2,7 +2,7 @@ GnuTLS NEWS -- History of user-visible changes.
-*- outline -*-
Copyright (C) 2000-2012 Free Software Foundation, Inc.
See the end for copying conditions.
-* Version 3.1.1 (unreleased)
+* Version 3.1.1 (released 2012-09-02)
** gnutls-serv: Listens on IPv6. Patch by Bernhard R. Link.
@@ -13,6 +13,14 @@ assume the PKCS #8 file format, instead of ignoring the
password.
** tpmtool: No longer asks for key password in registered keys.
+** libgnutls: Elliptic curve code was optimized by Ilya Tumaykin.
+wmNAF is now used for point multiplication and other optimizations.
+(the major part of the work was done during Google Summer of Code).
+
+** libgnutls: The default pull_timeout_function only uses select
+instead of a combination of select() and recv() to prevent issues
+when used in stream sockets in some systems.
+
** libgnutls: Be tolerant in ECDSA signature violations (e.g. using
SHA256 with a SECP384 curve instead of SHA-384), to interoperate with
openssl.
diff --git a/configure.ac b/configure.ac
index 81b6e8a..ccd2729 100644
--- a/configure.ac
+++ b/configure.ac
@@ -21,7 +21,7 @@ dnl Process this file with autoconf to produce a configure
script.
# USA
AC_PREREQ(2.61)
-AC_INIT([GnuTLS], [3.1.0], address@hidden)
+AC_INIT([GnuTLS], [3.1.1], address@hidden)
AC_CONFIG_AUX_DIR([build-aux])
AC_CONFIG_MACRO_DIR([m4])
diff --git a/doc/invoke-gnutls-cli.texi b/doc/invoke-gnutls-cli.texi
index b7c35c9..977f69d 100644
--- a/doc/invoke-gnutls-cli.texi
+++ b/doc/invoke-gnutls-cli.texi
@@ -7,7 +7,7 @@
#
# DO NOT EDIT THIS FILE (invoke-gnutls-cli.texi)
#
-# It has been AutoGen-ed June 6, 2012 at 09:11:09 PM by AutoGen 5.16
+# It has been AutoGen-ed September 2, 2012 at 08:04:10 PM by AutoGen 5.16
# From the definitions ../src/cli-args.def
# and the template file agtexi-cmd.tpl
@end ignore
@@ -48,6 +48,7 @@ USAGE: gnutls-cli [ -<flag> [<val>] |
--<name>address@hidden| @}<val>] ]... [hostname]
--ocsp Enable OCSP certificate verification
- disabled as --no-ocsp
-r, --resume Establish a session and resume
+ -b, --heartbeat Activate heartbeat support
-e, --rehandshake Establish a session and rehandshake
--noticket Don't accept session tickets
-s, --starttls Connect, establish a plain session and start TLS.
diff --git a/doc/invoke-gnutls-serv.texi b/doc/invoke-gnutls-serv.texi
index bd7b686..f544225 100644
--- a/doc/invoke-gnutls-serv.texi
+++ b/doc/invoke-gnutls-serv.texi
@@ -7,7 +7,7 @@
#
# DO NOT EDIT THIS FILE (invoke-gnutls-serv.texi)
#
-# It has been AutoGen-ed May 9, 2012 at 08:06:12 PM by AutoGen 5.16
+# It has been AutoGen-ed September 2, 2012 at 08:04:11 PM by AutoGen 5.16
# From the definitions ../src/serv-args.def
# and the template file agtexi-cmd.tpl
@end ignore
@@ -52,6 +52,7 @@ USAGE: gnutls-serv [ -<flag> [<val>] |
--<name>address@hidden| @}<val>] ]...
0 to 17000
-a, --disable-client-cert Do not request a client certificate
-r, --require-client-cert Require a client certificate
+ -b, --heartbeat Activate heartbeat support
--x509fmtder Use DER format for certificates to read from
--priority=str Priorities string
--dhparams=file DH params file to use
diff --git a/lib/gnutls_buffers.c b/lib/gnutls_buffers.c
index ff0f82a..cc645c9 100644
--- a/lib/gnutls_buffers.c
+++ b/lib/gnutls_buffers.c
@@ -460,12 +460,6 @@ _gnutls_io_read_buffered (gnutls_session_t session, size_t
total,
return GNUTLS_E_INVALID_REQUEST;
}
- if (ret < 0)
- {
- gnutls_assert ();
- return ret;
- }
-
/* READ DATA
*/
if (readsize > 0)
@@ -661,10 +655,9 @@ _gnutls_io_check_recv (gnutls_session_t session, unsigned
int ms)
reset_errno (session);
ret = session->internals.pull_timeout_func(fd, ms);
-
- err = get_errno (session);
if (ret == -1)
{
+ err = get_errno (session);
_gnutls_read_log ("READ_TIMEOUT: %d returned from %p, errno=%d (timeout:
%u)\n",
(int) ret, fd, err, ms);
return errno_to_gerr(err);
diff --git a/lib/gnutls_global.c b/lib/gnutls_global.c
index 3a71eae..8b84f46 100644
--- a/lib/gnutls_global.c
+++ b/lib/gnutls_global.c
@@ -295,6 +295,7 @@ gnutls_global_deinit (void)
if (_gnutls_init == 1)
{
gl_sockets_cleanup ();
+ gnutls_crypto_deinit();
_gnutls_rnd_deinit ();
_gnutls_ext_deinit ();
asn1_delete_structure (&_gnutls_gnutls_asn);
diff --git a/lib/gnutls_global.h b/lib/gnutls_global.h
index f92d321..4be3ca1 100644
--- a/lib/gnutls_global.h
+++ b/lib/gnutls_global.h
@@ -42,6 +42,7 @@ extern gnutls_log_func _gnutls_log_func;
extern gnutls_audit_log_func _gnutls_audit_log_func;
extern int _gnutls_log_level;
extern int gnutls_crypto_init (void);
+extern void gnutls_crypto_deinit (void);
void _gnutls_priority_prefer_aes_gcm(void);
#endif
diff --git a/lib/nettle/Makefile.am b/lib/nettle/Makefile.am
index 71d7802..313a69d 100644
--- a/lib/nettle/Makefile.am
+++ b/lib/nettle/Makefile.am
@@ -34,7 +34,9 @@ endif
noinst_LTLIBRARIES = libcrypto.la
libcrypto_la_SOURCES = pk.c mpi.c mac.c cipher.c rnd.c init.c egd.c egd.h \
- multi.c ecc_free.c ecc.h ecc_make_key.c ecc_shared_secret.c \
- ecc_map.c ecc_mulmod.c ecc_points.c ecc_projective_dbl_point_3.c \
- ecc_projective_add_point.c ecc_projective_check_point.c \
+ multi.c wmnaf.c ecc_free.c ecc.h ecc_make_key.c ecc_shared_secret.c \
+ ecc_map.c ecc_mulmod.c ecc_mulmod_wmnaf.c ecc_mulmod_wmnaf_cached.c \
+ ecc_points.c ecc_projective_dbl_point_3.c ecc_projective_isneutral.c \
+ ecc_projective_check_point.c ecc_projective_negate_point.c \
+ ecc_projective_add_point.c ecc_projective_add_point_ng.c \
ecc_sign_hash.c ecc_verify_hash.c gnettle.h ecc_mulmod_timing.c
diff --git a/lib/nettle/ecc.h b/lib/nettle/ecc.h
index 0925216..44adffb 100644
--- a/lib/nettle/ecc.h
+++ b/lib/nettle/ecc.h
@@ -42,6 +42,13 @@
/* max private key size */
#define ECC_MAXSIZE 66
+/* wMNAF window size */
+#define WMNAF_WINSIZE 4
+
+/* length of a single array of precomputed values for wMNAF
+ * we have two such arrays for positive and negative multipliers */
+#define WMNAF_PRECOMPUTED_LENGTH (1 << (WMNAF_WINSIZE - 1))
+
/** Structure defines a NIST GF(p) curve */
typedef struct {
/** The size of the curve in octets */
@@ -61,10 +68,10 @@ typedef struct {
/** The order of the curve (hex) */
const char *order;
-
+
/** The x co-ordinate of the base point on the curve (hex) */
const char *Gx;
-
+
/** The y co-ordinate of the base point on the curve (hex) */
const char *Gy;
} ecc_set_type;
@@ -103,36 +110,56 @@ typedef struct {
void ecc_sizes(int *low, int *high);
int ecc_get_size(ecc_key *key);
-int ecc_make_key(void *random_ctx, nettle_random_func random, ecc_key *key,
const ecc_set_type *dp);
-int ecc_make_key_ex(void *random_ctx, nettle_random_func random, ecc_key *key,
mpz_t prime, mpz_t order, mpz_t A, mpz_t B, mpz_t Gx, mpz_t Gy, int timing_res);
+int ecc_make_key(void *random_ctx, nettle_random_func random, ecc_key *key,
const ecc_set_type *dp, gnutls_ecc_curve_t id);
+int ecc_make_key_ex(void *random_ctx, nettle_random_func random, ecc_key *key,
mpz_t prime, mpz_t order, mpz_t A, mpz_t B, mpz_t Gx, mpz_t Gy,
gnutls_ecc_curve_t id, int timing_res);
void ecc_free(ecc_key *key);
-int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
+int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
unsigned char *out, unsigned long *outlen);
-int ecc_sign_hash(const unsigned char *in, unsigned long inlen,
+int ecc_sign_hash(const unsigned char *in, unsigned long inlen,
struct dsa_signature *signature,
- void *random_ctx, nettle_random_func random, ecc_key
*key);
+ void *random_ctx, nettle_random_func random,
+ ecc_key *key, gnutls_ecc_curve_t id);
int ecc_verify_hash(struct dsa_signature * signature,
- const unsigned char *hash, unsigned long hashlen,
- int *stat, ecc_key *key);
+ const unsigned char *hash, unsigned long hashlen,
+ int *stat, ecc_key *key, gnutls_ecc_curve_t id);
/* low level functions */
ecc_point *ecc_new_point(void);
void ecc_del_point(ecc_point *p);
/* point ops (mp == montgomery digit) */
+/* R = -P */
+int ecc_projective_negate_point(ecc_point *P, ecc_point *R, mpz_t modulus);
+
/* R = 2P */
int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mpz_t a, mpz_t
modulus);
/* R = P + Q */
int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mpz_t
A, mpz_t modulus);
+int ecc_projective_add_point_ng(ecc_point *P, ecc_point *Q, ecc_point *R,
mpz_t A, mpz_t modulus);
+int ecc_projective_madd (ecc_point* P, ecc_point* Q, ecc_point* R, mpz_t a,
mpz_t modulus);
/* R = kG */
int ecc_mulmod(mpz_t k, ecc_point *G, ecc_point *R, mpz_t a, mpz_t modulus,
int map);
int ecc_mulmod_timing(mpz_t k, ecc_point *G, ecc_point *R, mpz_t a, mpz_t
modulus, int map);
+/* wMNAF-based mulmod */
+signed char* ecc_wMNAF(mpz_t x, size_t *ret_len);
+int ecc_mulmod_wmnaf(mpz_t k, ecc_point *G, ecc_point *R, mpz_t a, mpz_t
modulus, int map);
+
+/* cache-enabled wMNAF-based mulmod */
+int ecc_wmnaf_cache_init(void);
+void ecc_wmnaf_cache_free(void);
+int ecc_mulmod_wmnaf_cached (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R,
mpz_t a, mpz_t modulus, int map);
+int ecc_mulmod_wmnaf_cached_timing (mpz_t k, gnutls_ecc_curve_t id, ecc_point
* R, mpz_t a, mpz_t modulus, int map);
+int ecc_mulmod_wmnaf_cached_lookup (mpz_t k, ecc_point *G, ecc_point *R, mpz_t
a, mpz_t modulus, int map);
+
+/* check if the given point is neutral point */
+int ecc_projective_isneutral(ecc_point *P, mpz_t modulus);
+
/* map P to affine from projective */
int ecc_map(ecc_point *P, mpz_t modulus);
diff --git a/lib/nettle/ecc_make_key.c b/lib/nettle/ecc_make_key.c
index 6886846..8c777da 100644
--- a/lib/nettle/ecc_make_key.c
+++ b/lib/nettle/ecc_make_key.c
@@ -38,6 +38,7 @@
@param A The "a" parameter of the curve
@param Gx The x coordinate of the base point
@param Gy The y coordinate of the base point
+ @param curve_id The id of the curve we are working with
@timing_res If non zero the function will try to return in constant
time.
@return 0 if successful, upon error all allocated memory will be freed
*/
@@ -45,7 +46,7 @@
int
ecc_make_key_ex (void *random_ctx, nettle_random_func random, ecc_key * key,
mpz_t prime, mpz_t order, mpz_t A, mpz_t B, mpz_t Gx, mpz_t
Gy,
- int timing_res)
+ gnutls_ecc_curve_t curve_id, int timing_res)
{
int err;
ecc_point *base;
@@ -92,7 +93,7 @@ ecc_make_key_ex (void *random_ctx, nettle_random_func random,
ecc_key * key,
mpz_set (base->x, key->Gx);
mpz_set (base->y, key->Gy);
mpz_set_ui (base->z, 1);
-
+
nettle_mpz_set_str_256_u (key->k, keysize, buf);
/* the key should be smaller than the order of base point */
@@ -102,9 +103,9 @@ ecc_make_key_ex (void *random_ctx, nettle_random_func
random, ecc_key * key,
}
/* make the public key */
if (timing_res)
- err = ecc_mulmod_timing (key->k, base, &key->pubkey, key->A, key->prime,
1);
+ err = ecc_mulmod_wmnaf_cached_timing (key->k, curve_id, &key->pubkey,
key->A, key->prime, 1);
else
- err = ecc_mulmod (key->k, base, &key->pubkey, key->A, key->prime, 1);
+ err = ecc_mulmod_wmnaf_cached (key->k, curve_id, &key->pubkey, key->A,
key->prime, 1);
if (err != 0)
goto errkey;
@@ -127,7 +128,7 @@ ERR_BUF:
int
ecc_make_key (void *random_ctx, nettle_random_func random, ecc_key * key,
- const ecc_set_type * dp)
+ const ecc_set_type * dp, gnutls_ecc_curve_t curve_id)
{
mpz_t prime, order, Gx, Gy, A, B;
int err;
@@ -146,7 +147,7 @@ ecc_make_key (void *random_ctx, nettle_random_func random,
ecc_key * key,
mpz_set_str (A, (char *) dp->A, 16);
mpz_set_str (B, (char *) dp->B, 16);
- err = ecc_make_key_ex (random_ctx, random, key, prime, order, A, B, Gx, Gy,
0);
+ err = ecc_make_key_ex (random_ctx, random, key, prime, order, A, B, Gx, Gy,
curve_id, 0);
mp_clear_multi (&prime, &order, &A, &B, &Gx, &Gy, NULL);
cleanup:
diff --git a/lib/nettle/ecc_mulmod_wmnaf.c b/lib/nettle/ecc_mulmod_wmnaf.c
new file mode 100644
index 0000000..87d6a38
--- /dev/null
+++ b/lib/nettle/ecc_mulmod_wmnaf.c
@@ -0,0 +1,165 @@
+/*
+ * Copyright (C) 2011-2012 Free Software Foundation, Inc.
+ *
+ * Author: Ilya Tumaykin
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library 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 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This library 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, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#include "ecc.h"
+
+
+/*
+ Perform a point multiplication using wMNAF representation
+ @param k The scalar to multiply by
+ @param G The base point
+ @param R [out] Destination for kG
+ @param a The curve's A value
+ @param modulus The modulus of the field the ECC curve is in
+ @param map Boolean whether to map back to affine or not (1 == map, 0
== leave in projective)
+ @return GNUTLS_E_SUCCESS on success
+*/
+int
+ecc_mulmod_wmnaf (mpz_t k, ecc_point * G, ecc_point * R, mpz_t a,
+ mpz_t modulus, int map)
+{
+ ecc_point *pos[WMNAF_PRECOMPUTED_LENGTH], *neg[WMNAF_PRECOMPUTED_LENGTH];
+ int i, j, err;
+
+ signed char *wmnaf = NULL;
+ size_t wmnaf_len;
+ signed char digit;
+
+ if (k == NULL || G == NULL || R == NULL || modulus == NULL)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ /* alloc ram for precomputed values */
+ for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
+ {
+ pos[i] = ecc_new_point ();
+ neg[i] = ecc_new_point ();
+ if (pos[i] == NULL || neg[i] == NULL)
+ {
+ for (j = 0; j < i; ++j)
+ {
+ ecc_del_point (pos[j]);
+ ecc_del_point (neg[j]);
+ }
+
+ return GNUTLS_E_MEMORY_ERROR;
+ }
+ }
+
+ /* fill in pos and neg arrays with precomputed values
+ * pos holds kG for k == 1, 3, 5, ..., (2^w - 1)
+ * neg holds kG for k == -1,-3,-5, ...,-(2^w - 1)
+ */
+
+ /* pos[0] == 2G for a while, later it will be set to the expected 1G */
+ if ((err = ecc_projective_dbl_point (G, pos[0], a, modulus)) != 0)
+ goto done;
+
+ /* pos[1] == 3G */
+ if ((err =
+ ecc_projective_add_point_ng (pos[0], G, pos[1], a, modulus)) != 0)
+ goto done;
+
+ /* fill in kG for k = 5, 7, ..., (2^w - 1) */
+ for (j = 2; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
+ {
+ if ((err =
+ ecc_projective_add_point_ng (pos[j - 1], pos[0], pos[j], a,
+ modulus)) != 0)
+ goto done;
+ }
+
+ /* set pos[0] == 1G as expected
+ * after this step we don't need G at all
+ * and can change it without worries even if R == G */
+ mpz_set (pos[0]->x, G->x);
+ mpz_set (pos[0]->y, G->y);
+ mpz_set (pos[0]->z, G->z);
+
+ /* neg[i] == -pos[i] */
+ for (j = 0; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
+ {
+ if ((err = ecc_projective_negate_point (pos[j], neg[j], modulus)) != 0)
+ goto done;
+ }
+
+ /* calculate wMNAF */
+ wmnaf = ecc_wMNAF (k, &wmnaf_len);
+ if (!wmnaf)
+ {
+ err = GNUTLS_E_INTERNAL_ERROR;
+ goto done;
+ }
+
+ /* actual point computation */
+
+ /* set R to neutral */
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+
+ /* perform ops */
+ for (j = wmnaf_len - 1; j >= 0; --j)
+ {
+ if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
+ goto done;
+
+ digit = wmnaf[j];
+
+ if (digit)
+ {
+ if (digit > 0)
+ {
+ if ((err =
+ ecc_projective_add_point_ng (R, pos[(digit / 2)], R, a,
+ modulus)) != 0)
+ goto done;
+ }
+ else
+ {
+ if ((err =
+ ecc_projective_add_point_ng (R, neg[(-digit / 2)], R, a,
+ modulus)) != 0)
+ goto done;
+ }
+ }
+ }
+
+
+ /* map R back from projective space */
+ if (map)
+ {
+ err = ecc_map (R, modulus);
+ }
+ else
+ {
+ err = GNUTLS_E_SUCCESS;
+ }
+done:
+ for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
+ {
+ ecc_del_point (pos[i]);
+ ecc_del_point (neg[i]);
+ }
+ if (wmnaf)
+ free (wmnaf);
+ return err;
+}
diff --git a/lib/nettle/ecc_mulmod_wmnaf_cached.c
b/lib/nettle/ecc_mulmod_wmnaf_cached.c
new file mode 100644
index 0000000..e75b884
--- /dev/null
+++ b/lib/nettle/ecc_mulmod_wmnaf_cached.c
@@ -0,0 +1,457 @@
+/*
+ * Copyright (C) 2011-2012 Free Software Foundation, Inc.
+ *
+ * Author: Ilya Tumaykin
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library 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 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This library 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, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+/* needed for gnutls_* types */
+#include <gnutls_int.h>
+#include <algorithms.h>
+
+#include "ecc.h"
+
+
+/* per-curve cache structure */
+typedef struct
+{
+ /* curve's id */
+ gnutls_ecc_curve_t id;
+
+ /** The array of positive multipliers of G */
+ ecc_point *pos[WMNAF_PRECOMPUTED_LENGTH];
+
+ /** The array of negative multipliers of G */
+ ecc_point *neg[WMNAF_PRECOMPUTED_LENGTH];
+} gnutls_ecc_curve_cache_entry_t;
+
+/* global cache */
+static gnutls_ecc_curve_cache_entry_t *ecc_wmnaf_cache = NULL;
+
+/* free single cache entry */
+static void
+_ecc_wmnaf_cache_entry_free (gnutls_ecc_curve_cache_entry_t * p)
+{
+ int i;
+
+ for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
+ {
+ ecc_del_point (p->pos[i]);
+ ecc_del_point (p->neg[i]);
+ }
+}
+
+/* free curves caches */
+void
+ecc_wmnaf_cache_free (void)
+{
+ gnutls_ecc_curve_cache_entry_t *p = ecc_wmnaf_cache;
+ if (p)
+ {
+ for (; p->id != GNUTLS_ECC_CURVE_INVALID; ++p)
+ {
+ _ecc_wmnaf_cache_entry_free (p);
+ }
+
+ free (ecc_wmnaf_cache);
+ }
+}
+
+/* initialize single cache entry
+ * for a curve with the given id */
+static int
+_ecc_wmnaf_cache_entry_init (gnutls_ecc_curve_cache_entry_t * p,
+ gnutls_ecc_curve_t id)
+{
+ int i, j, err;
+ ecc_point *G;
+ mpz_t a, modulus;
+
+ const gnutls_ecc_curve_entry_st *st = NULL;
+
+ if (p == NULL || id == 0)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ G = ecc_new_point ();
+ if (G == NULL)
+ {
+ return GNUTLS_E_MEMORY_ERROR;
+ }
+
+ st = _gnutls_ecc_curve_get_params (id);
+ if (st == NULL)
+ {
+ err = GNUTLS_E_INTERNAL_ERROR;
+ goto done;
+ }
+
+ if ((err = mp_init_multi (&a, &modulus, NULL) != 0))
+ return err;
+
+ /* set id */
+ p->id = id;
+
+ /* set modulus */
+ mpz_set_str (modulus, st->prime, 16);
+
+ /* get generator point */
+ mpz_set_str (G->x, st->Gx, 16);
+ mpz_set_str (G->y, st->Gy, 16);
+ mpz_set_ui (G->z, 1);
+
+ /* set A */
+ mpz_set_str (a, st->A, 16);
+
+ /* alloc ram for precomputed values */
+ for (i = 0; i < WMNAF_PRECOMPUTED_LENGTH; ++i)
+ {
+ p->pos[i] = ecc_new_point ();
+ p->neg[i] = ecc_new_point ();
+ if (p->pos[i] == NULL || p->neg[i] == NULL)
+ {
+ for (j = 0; j < i; ++j)
+ {
+ ecc_del_point (p->pos[j]);
+ ecc_del_point (p->neg[j]);
+ }
+
+ err = GNUTLS_E_MEMORY_ERROR;
+ goto done;
+ }
+ }
+
+ /* fill in pos and neg arrays with precomputed values
+ * pos holds kG for k == 1, 3, 5, ..., (2^w - 1)
+ * neg holds kG for k == -1,-3,-5, ...,-(2^w - 1)
+ */
+
+ /* pos[0] == 2G for a while, later it will be set to the expected 1G */
+ if ((err = ecc_projective_dbl_point (G, p->pos[0], a, modulus)) != 0)
+ goto done;
+
+ /* pos[1] == 3G */
+ if ((err =
+ ecc_projective_add_point_ng (p->pos[0], G, p->pos[1], a,
+ modulus)) != 0)
+ goto done;
+
+ /* fill in kG for k = 5, 7, ..., (2^w - 1) */
+ for (j = 2; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
+ {
+ if ((err =
+ ecc_projective_add_point_ng (p->pos[j - 1], p->pos[0], p->pos[j],
+ a, modulus)) != 0)
+ goto done;
+ }
+
+ /* set pos[0] == 1G as expected
+ * after this step we don't need G at all */
+ mpz_set (p->pos[0]->x, G->x);
+ mpz_set (p->pos[0]->y, G->y);
+ mpz_set (p->pos[0]->z, G->z);
+
+ /* map to affine all elements in pos
+ * this will allow to use ecc_projective_madd later
+ * set neg[i] == -pos[i] */
+ for (j = 0; j < WMNAF_PRECOMPUTED_LENGTH; ++j)
+ {
+ if ((err = ecc_map (p->pos[j], modulus)) != 0)
+ goto done;
+
+ if ((err =
+ ecc_projective_negate_point (p->pos[j], p->neg[j], modulus)) != 0)
+ goto done;
+ }
+
+ err = 0;
+done:
+ ecc_del_point (G);
+ mp_clear_multi (&a, &modulus, NULL);
+
+ return err;
+}
+
+/* initialize curves caches */
+int
+ecc_wmnaf_cache_init (void)
+{
+ int j, err;
+
+ gnutls_ecc_curve_cache_entry_t *ret;
+
+ const gnutls_ecc_curve_t *p;
+
+ ret = (gnutls_ecc_curve_cache_entry_t *)
+ malloc (MAX_ALGOS * sizeof (gnutls_ecc_curve_cache_entry_t));
+ if (ret == NULL)
+ return GNUTLS_E_MEMORY_ERROR;
+
+ /* get supported curves' ids */
+ p = gnutls_ecc_curve_list ();
+
+ for (j = 0; *p; ++p, ++j)
+ {
+ if ((err = _ecc_wmnaf_cache_entry_init (ret + *p - 1, *p)) != 0)
+ goto done;
+ }
+
+ /* nullify last cache entry id */
+ ret[j].id = GNUTLS_ECC_CURVE_INVALID;
+
+ err = GNUTLS_E_SUCCESS;
+
+ ecc_wmnaf_cache = ret;
+done:
+ if (err)
+ {
+ int i;
+ for (i = 0; i < j; ++i)
+ {
+ _ecc_wmnaf_cache_entry_free (ret + i);
+ }
+
+ free (ret);
+ ecc_wmnaf_cache = NULL;
+ }
+ return err;
+}
+
+
+/*
+ Perform a point wMNAF-multiplication utilizing cache
+ @param k The scalar to multiply by
+ @param id The curve's id
+ @param R [out] Destination for kG
+ @param a The curve's A value
+ @param modulus The modulus of the field the ECC curve is in
+ @param map Boolean whether to map back to affine or not (1 == map, 0
== leave in projective)
+ @return GNUTLS_E_SUCCESS on success
+*/
+int
+ecc_mulmod_wmnaf_cached (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R,
+ mpz_t a, mpz_t modulus, int map)
+{
+ int j, err;
+
+ gnutls_ecc_curve_cache_entry_t *cache = NULL;
+ signed char *wmnaf = NULL;
+ size_t wmnaf_len;
+ signed char digit;
+
+ if (k == NULL || R == NULL || modulus == NULL || id == 0)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ /* calculate wMNAF */
+ wmnaf = ecc_wMNAF (k, &wmnaf_len);
+ if (!wmnaf)
+ {
+ err = GNUTLS_E_INTERNAL_ERROR;
+ goto done;
+ }
+
+ /* set R to neutral */
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+
+ /* do cache lookup */
+ cache = ecc_wmnaf_cache + id - 1;
+
+ /* perform ops */
+ for (j = wmnaf_len - 1; j >= 0; --j)
+ {
+ if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
+ goto done;
+
+ digit = wmnaf[j];
+
+ if (digit)
+ {
+ if (digit > 0)
+ {
+ if ((err =
+ ecc_projective_madd (R, cache->pos[(digit / 2)], R, a,
+ modulus)) != 0)
+ goto done;
+ }
+ else
+ {
+ if ((err =
+ ecc_projective_madd (R, cache->neg[(-digit / 2)], R, a,
+ modulus)) != 0)
+ goto done;
+ }
+ }
+ }
+
+
+ /* map R back from projective space */
+ if (map)
+ {
+ err = ecc_map (R, modulus);
+ }
+ else
+ {
+ err = GNUTLS_E_SUCCESS;
+ }
+done:
+ if (wmnaf)
+ free (wmnaf);
+ return err;
+}
+
+/*
+ Perform a point wMNAF-multiplication utilizing cache
+ This version tries to be timing resistant
+ @param k The scalar to multiply by
+ @param id The curve's id
+ @param R [out] Destination for kG
+ @param a The curve's A value
+ @param modulus The modulus of the field the ECC curve is in
+ @param map Boolean whether to map back to affine or not (1 == map, 0
== leave in projective)
+ @return GNUTLS_E_SUCCESS on success
+*/
+int
+ecc_mulmod_wmnaf_cached_timing (mpz_t k, gnutls_ecc_curve_t id, ecc_point * R,
+ mpz_t a, mpz_t modulus, int map)
+{
+ int j, err;
+
+ gnutls_ecc_curve_cache_entry_t *cache = NULL;
+ signed char *wmnaf = NULL;
+ size_t wmnaf_len;
+ signed char digit;
+ /* point for throttle */
+ ecc_point *T;
+
+ if (k == NULL || R == NULL || modulus == NULL || id == 0)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ /* prepare T point */
+ T = ecc_new_point ();
+ if (T == NULL)
+ return GNUTLS_E_MEMORY_ERROR;
+
+ /* calculate wMNAF */
+ wmnaf = ecc_wMNAF (k, &wmnaf_len);
+ if (!wmnaf)
+ {
+ err = GNUTLS_E_INTERNAL_ERROR;
+ goto done;
+ }
+
+ /* set R to neutral */
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+
+ /* set T to neutral */
+ mpz_set_ui (T->x, 1);
+ mpz_set_ui (T->y, 1);
+ mpz_set_ui (T->z, 0);
+
+ /* do cache lookup */
+ cache = ecc_wmnaf_cache + id - 1;
+
+ /* perform ops */
+ for (j = wmnaf_len - 1; j >= 0; --j)
+ {
+ if ((err = ecc_projective_dbl_point (R, R, a, modulus)) != 0)
+ goto done;
+
+ digit = wmnaf[j];
+
+ if (digit)
+ {
+ if (digit > 0)
+ {
+ if ((err =
+ ecc_projective_madd (R, cache->pos[(digit / 2)], R, a,
+ modulus)) != 0)
+ goto done;
+ }
+ else
+ {
+ if ((err =
+ ecc_projective_madd (R, cache->neg[(-digit / 2)], R, a,
+ modulus)) != 0)
+ goto done;
+ }
+ }
+ else
+ {
+ /* we add middle element of pos array as a general case
+ * there is no real difference between using pos and neg */
+ if ((err =
+ ecc_projective_madd (R,
+ cache->
+ pos[(WMNAF_PRECOMPUTED_LENGTH / 2)], T, a,
+ modulus)) != 0)
+ goto done;
+ }
+ }
+
+
+ /* map R back from projective space */
+ if (map)
+ {
+ err = ecc_map (R, modulus);
+ }
+ else
+ {
+ err = GNUTLS_E_SUCCESS;
+ }
+done:
+ ecc_del_point (T);
+ if (wmnaf)
+ free (wmnaf);
+ return err;
+}
+
+/*
+ Perform a point wMNAF-multiplication utilizing cache
+ This function will lookup for an apropriate curve first
+ This function's definition allows in-place substitution instead of
ecc_mulmod
+ @param k The scalar to multiply by
+ @param id The curve's id
+ @param R [out] Destination for kG
+ @param a The curve's A value
+ @param modulus The modulus of the field the ECC curve is in
+ @param map Boolean whether to map back to affine or not (1 == map, 0
== leave in projective)
+ @return GNUTLS_E_SUCCESS on success
+*/
+int
+ecc_mulmod_wmnaf_cached_lookup (mpz_t k, ecc_point * G, ecc_point * R,
+ mpz_t a, mpz_t modulus, int map)
+{
+ int i, id;
+
+ if (k == NULL || G == NULL || R == NULL || modulus == NULL)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ for (i = 0; (id = ecc_wmnaf_cache[i].id); ++i)
+ {
+ if (!(mpz_cmp (G->x, ecc_wmnaf_cache[i].pos[0]->x)) &&
+ !(mpz_cmp (G->y, ecc_wmnaf_cache[i].pos[0]->y)))
+ {
+ break;
+ }
+ }
+
+ return ecc_mulmod_wmnaf_cached (k, id, R, a, modulus, map);
+}
diff --git a/lib/nettle/ecc_projective_add_point.c
b/lib/nettle/ecc_projective_add_point.c
index 89c96e5..586f116 100644
--- a/lib/nettle/ecc_projective_add_point.c
+++ b/lib/nettle/ecc_projective_add_point.c
@@ -36,25 +36,52 @@
@param R [out] The destination of the double
@param a Curve's a value
@param modulus The modulus of the field the ECC curve is in
- @return 0 on success
+ @return GNUTLS_E_SUCCESS on success
*/
int
ecc_projective_add_point (ecc_point * P, ecc_point * Q, ecc_point * R,
mpz_t a, mpz_t modulus)
{
+ /* Using "(m)add-2004-hmv" algorithm
+ * It costs 12M + 4S + half. */
mpz_t t1, t2, x, y, z;
int err;
if (P == NULL || Q == NULL || R == NULL || modulus == NULL)
- return -1;
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ /* check for neutral points */
+ if ( (err = ecc_projective_isneutral(Q, modulus)) == 0 ) {
+ /* P + Q = P + neutral = P */
+
+ mpz_set (R->x, P->x);
+ mpz_set (R->y, P->y);
+ mpz_set (R->z, P->z);
+
+ return GNUTLS_E_SUCCESS;
+ } else if (err < 0) {
+ return err;
+ }
+
+ if ( (err = ecc_projective_isneutral(P, modulus)) == 0 ) {
+ /* P + Q = neutral + Q = Q */
+
+ mpz_set (R->x, Q->x);
+ mpz_set (R->y, Q->y);
+ mpz_set (R->z, Q->z);
+
+ return GNUTLS_E_SUCCESS;
+ } else if (err < 0) {
+ return err;
+ }
if ((err = mp_init_multi (&t1, &t2, &x, &y, &z, NULL)) != 0)
{
return err;
}
- /* Check if P == Q and do doubling in that case
- * If Q == -P then P+Q=point at infinity
+ /* Check if P == Q and do doubling in that case
+ * If Q == -P then P + Q = neutral element
*/
if ((mpz_cmp (P->x, Q->x) == 0) &&
(mpz_cmp (P->z, Q->z) == 0))
@@ -66,7 +93,7 @@ ecc_projective_add_point (ecc_point * P, ecc_point * Q,
ecc_point * R,
mp_clear_multi (&t1, &t2, &x, &y, &z, NULL);
return ecc_projective_dbl_point (P, R, a, modulus);
}
-
+
mpz_sub (t1, modulus, Q->y);
if (mpz_cmp (P->y, t1) == 0)
{
@@ -74,7 +101,7 @@ ecc_projective_add_point (ecc_point * P, ecc_point * Q,
ecc_point * R,
mpz_set_ui(R->x, 1);
mpz_set_ui(R->y, 1);
mpz_set_ui(R->z, 0);
- return 0;
+ return GNUTLS_E_SUCCESS;
}
}
@@ -217,7 +244,7 @@ ecc_projective_add_point (ecc_point * P, ecc_point * Q,
ecc_point * R,
mpz_set (R->y, y);
mpz_set (R->z, z);
- err = 0;
+ err = GNUTLS_E_SUCCESS;
mp_clear_multi (&t1, &t2, &x, &y, &z, NULL);
return err;
diff --git a/lib/nettle/ecc_projective_add_point_ng.c
b/lib/nettle/ecc_projective_add_point_ng.c
new file mode 100644
index 0000000..72a7e7c
--- /dev/null
+++ b/lib/nettle/ecc_projective_add_point_ng.c
@@ -0,0 +1,462 @@
+/*
+ * Copyright (C) 2011-2012 Free Software Foundation, Inc.
+ *
+ * Author: Ilya Tumaykin
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library 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 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This library 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, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#include "ecc.h"
+
+/* We use two algorithms for different cases.
+ * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html
+ *
+ * The algorithm used for general case is "add-1998-cmo-2"
+ * It costs 12M + 4S.
+ *
+ * If Z2 = 1 we use "madd". It costs 8M + 3S.
+ *
+ * The original versions use a lot of vars:
+ * Z1Z1, Z2Z2, U1, U2, S1, S2, H, I, HHH, r, V, etc.
+ * We use only the needed minimum:
+ * S1, H, HHH(J), r, V.
+ * The rest of the vars are not needed for final
+ * computation, so we calculate them, but don't store.
+ * Follow the comments.
+ */
+
+
+#define __WITH_EXTENDED_CHECKS
+/* Check if H == 0
+ * In this case P + Q = neutral element.
+ *
+ * In all of the cases below when H == 0 then Z == 0
+ * and the resulting point lies at infinity.
+ *
+ * And the only point on the curve with Z == 0 MUST be
+ * the neutral point.
+ *
+ * Of course, if there wasn't a mistake somewhere before.
+ * We will be gullible and won't do any checks and simply
+ * return neutral point in that case.
+ */
+
+
+/*
+ Add two ECC points
+ @param P The point to add
+ @param Q The point to add
+ @param R [out] The destination of the double
+ @param a Curve's a value
+ @param modulus The modulus of the field the ECC curve is in
+ @return GNUTLS_E_SUCCESS on success
+
+ Note: this function WILL work when a != -3.
+ It will work in general case without a change.
+*/
+int
+ecc_projective_add_point_ng (ecc_point * P, ecc_point * Q, ecc_point * R,
+ mpz_t a, mpz_t modulus)
+{
+ mpz_t t0, t1, S1, H, HHH, r, V;
+ int err;
+
+ if (P == NULL || Q == NULL || R == NULL || modulus == NULL)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ /* check all special cases first */
+
+ /* check for neutral points */
+ if ((err = ecc_projective_isneutral (Q, modulus)) == 0)
+ {
+ /* P + Q = P + neutral = P */
+
+ mpz_set (R->x, P->x);
+ mpz_set (R->y, P->y);
+ mpz_set (R->z, P->z);
+
+ return GNUTLS_E_SUCCESS;
+ }
+ else if (err < 0)
+ {
+ return err;
+ }
+
+ if ((err = ecc_projective_isneutral (P, modulus)) == 0)
+ {
+ /* P + Q = neutral + Q = Q */
+
+ mpz_set (R->x, Q->x);
+ mpz_set (R->y, Q->y);
+ mpz_set (R->z, Q->z);
+
+ return GNUTLS_E_SUCCESS;
+ }
+ else if (err < 0)
+ {
+ return err;
+ }
+
+ if ((err = mp_init_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL)) != 0)
+ return err;
+
+ /* Check if P == Q and do doubling in that case
+ * If Q == -P then P + Q = neutral element */
+ if ((mpz_cmp (P->x, Q->x) == 0) && (mpz_cmp (P->z, Q->z) == 0))
+ {
+
+ /* x and z coordinates match.
+ * Check if P->y = Q->y, or P->y = -Q->y */
+
+ if (mpz_cmp (P->y, Q->y) == 0)
+ {
+ mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
+ return ecc_projective_dbl_point (P, R, a, modulus);
+ }
+
+ mpz_sub (t1, modulus, Q->y);
+ if (mpz_cmp (P->y, t1) == 0)
+ {
+ mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+ return GNUTLS_E_SUCCESS;
+ }
+ }
+
+
+ /* check if Z2 == 1 and do "madd" in that case */
+ if ((mpz_cmp_ui (Q->z, 1) == 0))
+ {
+ mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
+ return ecc_projective_madd (P, Q, R, a, modulus);
+ }
+
+ /* no special cases occured
+ * do general routine */
+
+ /* t1 = Z1 * Z1 */
+ /* it is the original Z1Z1 */
+ mpz_mul (t1, P->z, P->z);
+ mpz_mod (t1, t1, modulus);
+
+ /* t0 = Z1 * Z1Z1 */
+ mpz_mul (t0, t1, P->z);
+ mpz_mod (t0, t0, modulus);
+
+ /* H = X2 * Z1Z1 */
+ /* it is the original U2 */
+ mpz_mul (H, t1, Q->x);
+ mpz_mod (H, H, modulus);
+
+ /* r = Y2 * Z1 * Z1Z1 */
+ /* it is the original S2 */
+ mpz_mul (r, t0, Q->y);
+ mpz_mod (r, r, modulus);
+
+ /* S1 = Z2 * Z2 */
+ /* it is the original Z2Z2 */
+ mpz_mul (S1, Q->z, Q->z);
+ mpz_mod (S1, S1, modulus);
+
+ /* t0 = X1 * Z2Z2 */
+ /* it is the original U1 */
+ mpz_mul (t0, S1, P->x);
+ mpz_mod (t0, t0, modulus);
+
+ /* H = U2 - U1 = H - t0 */
+ mpz_sub (H, H, t0);
+#ifdef __WITH_EXTENDED_CHECKS
+ err = mpz_cmp_ui (H, 0);
+ if (err < 0)
+ {
+ mpz_add (H, H, modulus);
+ }
+ else if (!err)
+ {
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+ mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
+
+ return GNUTLS_E_SUCCESS;
+ }
+#else
+ if (mpz_cmp_ui (H, 0) < 0)
+ mpz_add (H, H, modulus);
+#endif
+ /* t1 = H^2 */
+ /* it is the original HH */
+ mpz_mul (t1, H, H);
+ mpz_mod (t1, t1, modulus);
+ /* HHH = H * HH */
+ mpz_mul (HHH, t1, H);
+ mpz_mod (HHH, HHH, modulus);
+
+ /* V = U1 * HH = t0 * t1 */
+ mpz_mul (V, t1, t0);
+ mpz_mod (V, V, modulus);
+
+ /* t0 = Z2 * Z2Z2 */
+ mpz_mul (t0, S1, Q->z);
+ mpz_mod (t0, t0, modulus);
+ /* S1 = Y1 * Z2 * Z2Z2 */
+ mpz_mul (S1, t0, P->y);
+ mpz_mod (S1, S1, modulus);
+
+ /* r = S2 - S1 = r - S1 */
+ mpz_sub (r, r, S1);
+ if (mpz_cmp_ui (r, 0) < 0)
+ mpz_add (r, r, modulus);
+
+ /* we've calculated all needed vars:
+ * S1, H, HHH, r, V
+ * now, we will calculate the coordinates */
+
+ /* t0 = (r)^2 */
+ mpz_mul (t0, r, r);
+ mpz_mod (t0, t0, modulus);
+ /* t0 = t0 - HHH */
+ mpz_sub (t0, t0, HHH);
+ if (mpz_cmp_ui (t0, 0) < 0)
+ mpz_add (t0, t0, modulus);
+ /* t1 = 2V */
+ mpz_add (t1, V, V);
+ if (mpz_cmp (t1, modulus) >= 0)
+ mpz_sub (t1, t1, modulus);
+ /* X = r^2 - HHH - 2V = t0 - t1 */
+ mpz_sub (R->x, t0, t1);
+ if (mpz_cmp_ui (R->x, 0) < 0)
+ mpz_add (R->x, R->x, modulus);
+
+
+ /* t1 = V - X */
+ mpz_sub (t1, V, R->x);
+ if (mpz_cmp_ui (t1, 0) < 0)
+ mpz_add (t1, t1, modulus);
+ /* t0 = r * t1 */
+ mpz_mul (t0, r, t1);
+ mpz_mod (t0, t0, modulus);
+ /* t1 = S1 * HHH */
+ mpz_mul (t1, S1, HHH);
+ mpz_mod (t1, t1, modulus);
+ /* Y = r*(V - X) - S1*HHH = t0 - t1 */
+ mpz_sub (R->y, t0, t1);
+ if (mpz_cmp_ui (R->y, 0) < 0)
+ mpz_add (R->y, R->y, modulus);
+
+
+ /* t1 = Z1 * Z2 */
+ mpz_mul (t1, P->z, Q->z);
+ mpz_mod (t1, t1, modulus);
+ /* Z = Z1 * Z2 * H = t1 * H */
+ mpz_mul (R->z, t1, H);
+ mpz_mod (R->z, R->z, modulus);
+
+ mp_clear_multi (&S1, &H, &HHH, &r, &V, &t0, &t1, NULL);
+
+ return GNUTLS_E_SUCCESS;
+}
+
+/*
+ Add two ECC points, when it is known that Z2 == 1
+ @param P The point to add
+ @param Q The point with Z == 1 to add
+ @param R [out] The destination of the double
+ @param a Curve's a value
+ @param modulus The modulus of the field the ECC curve is in
+ @return GNUTLS_E_SUCCESS on success
+
+ Note: this function will work when a != -3.
+ It will work in general case without a change.
+*/
+int
+ecc_projective_madd (ecc_point * P, ecc_point * Q, ecc_point * R,
+ mpz_t a, mpz_t modulus)
+{
+ mpz_t t0, t1, H, J, r, V;
+ int err;
+
+ if (P == NULL || Q == NULL || R == NULL || modulus == NULL)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ /* check all special cases first */
+
+ /* check for neutral points */
+ /* Q is guaranteed not to be neutral since it has Z == 1 */
+ if ((err = ecc_projective_isneutral (P, modulus)) == 0)
+ {
+ /* P + Q = neutral + Q = Q */
+
+ mpz_set (R->x, Q->x);
+ mpz_set (R->y, Q->y);
+ mpz_set (R->z, Q->z);
+
+ return GNUTLS_E_SUCCESS;
+ }
+ else if (err < 0)
+ {
+ return err;
+ }
+
+ if ((err = mp_init_multi (&H, &J, &r, &V, &t0, &t1, NULL)) != 0)
+ return err;
+
+ /* Check if P == Q and do doubling in that case
+ * If Q == -P then P + Q = neutral element */
+ if ((mpz_cmp (P->x, Q->x) == 0) && (mpz_cmp (P->z, Q->z) == 0))
+ {
+
+ /* x and z coordinates match.
+ * Check if P->y = Q->y, or P->y = -Q->y */
+
+ if (mpz_cmp (P->y, Q->y) == 0)
+ {
+ mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
+ return ecc_projective_dbl_point (P, R, a, modulus);
+ }
+
+ mpz_sub (t1, modulus, Q->y);
+ if (mpz_cmp (P->y, t1) == 0)
+ {
+ mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+ return GNUTLS_E_SUCCESS;
+ }
+ }
+
+ /* no special cases occured
+ * do madd */
+
+ /* t1 = Z1 * Z1 */
+ /* it is the original Z1Z1 */
+ mpz_mul (t1, P->z, P->z);
+ mpz_mod (t1, t1, modulus);
+
+ /* t0 = Z1 * Z1Z1 */
+ mpz_mul (t0, t1, P->z);
+ mpz_mod (t0, t0, modulus);
+
+ /* r = Y2 * Z1 * Z1Z1 */
+ /* it is the original S2 */
+ mpz_mul (r, t0, Q->y);
+ mpz_mod (r, r, modulus);
+ /* r = S2 - Y1 = r - Y1 */
+ mpz_sub (r, r, P->y);
+ if (mpz_cmp_ui (r, 0) < 0)
+ mpz_add (r, r, modulus);
+ /* r = 2 * (S2 - Y1) */
+ mpz_add (r, r, r);
+ if (mpz_cmp (r, modulus) >= 0)
+ mpz_sub (r, r, modulus);
+
+ /* H = X2 * Z1Z1 */
+ /* it is the original U2 */
+ mpz_mul (H, t1, Q->x);
+ mpz_mod (H, H, modulus);
+ /* H = U2 - X1 = H - X1 */
+ mpz_sub (H, H, P->x);
+#ifdef __WITH_EXTENDED_CHECKS
+ err = mpz_cmp_ui (H, 0);
+ if (err < 0)
+ {
+ mpz_add (H, H, modulus);
+ }
+ else if (!err)
+ {
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+ mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
+
+ return GNUTLS_E_SUCCESS;
+ }
+#else
+ if (mpz_cmp_ui (H, 0) < 0)
+ mpz_add (H, H, modulus);
+#endif
+
+ /* t0 = 2H */
+ mpz_add (t0, H, H);
+ if (mpz_cmp (t0, modulus) >= 0)
+ mpz_sub (t0, t0, modulus);
+ /* t1 = (2H)^2 */
+ /* it is the original I */
+ mpz_mul (t1, t0, t0);
+ mpz_mod (t1, t1, modulus);
+
+ /* J = H * I = H * t1 */
+ mpz_mul (J, t1, H);
+ mpz_mod (J, J, modulus);
+
+ /* V = X1 * I = X1 * t1 */
+ mpz_mul (V, t1, P->x);
+ mpz_mod (V, V, modulus);
+
+ /* we've calculated all needed vars:
+ * H, J, r, V
+ * now, we will calculate the coordinates */
+
+ /* Z = 2 * Z1 * H = Z1 * t0 */
+ mpz_mul (R->z, P->z, t0);
+ mpz_mod (R->z, R->z, modulus);
+
+
+ /* t0 = (r)^2 */
+ mpz_mul (t0, r, r);
+ mpz_mod (t0, t0, modulus);
+ /* t0 = t0 - J */
+ mpz_sub (t0, t0, J);
+ if (mpz_cmp_ui (t0, 0) < 0)
+ mpz_add (t0, t0, modulus);
+ /* t1 = 2V */
+ mpz_add (t1, V, V);
+ if (mpz_cmp (t1, modulus) >= 0)
+ mpz_sub (t1, t1, modulus);
+ /* X = r^2 - J - 2V = t0 - t1 */
+ mpz_sub (R->x, t0, t1);
+ if (mpz_cmp_ui (R->x, 0) < 0)
+ mpz_add (R->x, R->x, modulus);
+
+
+ /* t1 = V - X */
+ mpz_sub (t1, V, R->x);
+ if (mpz_cmp_ui (t1, 0) < 0)
+ mpz_add (t1, t1, modulus);
+ /* t0 = r * t1 */
+ mpz_mul (t0, r, t1);
+ mpz_mod (t0, t0, modulus);
+ /* t1 = Y1 * J */
+ mpz_mul (t1, J, P->y);
+ mpz_mod (t1, t1, modulus);
+ /* t1 = 2 * t1 */
+ mpz_add (t1, t1, t1);
+ if (mpz_cmp (t1, modulus) >= 0)
+ mpz_sub (t1, t1, modulus);
+ /* Y = r * (V - X) - 2 * Y1 * J = t0 - t1 */
+ mpz_sub (R->y, t0, t1);
+ if (mpz_cmp_ui (R->y, 0) < 0)
+ mpz_add (R->y, R->y, modulus);
+
+
+ mp_clear_multi (&H, &J, &r, &V, &t0, &t1, NULL);
+
+ return GNUTLS_E_SUCCESS;
+}
diff --git a/lib/nettle/ecc_projective_dbl_point_3.c
b/lib/nettle/ecc_projective_dbl_point_3.c
index 1b376fe..53b2db5 100644
--- a/lib/nettle/ecc_projective_dbl_point_3.c
+++ b/lib/nettle/ecc_projective_dbl_point_3.c
@@ -27,126 +27,150 @@
/*
@file ecc_projective_dbl_point.c
ECC Crypto, Tom St Denis
-*/
+*/
#ifdef ECC_SECP_CURVES_ONLY
/*
Double an ECC point
- @param P The point to double
+ @param P The point to double
@param R [out] The destination of the double
- @param modulus The modulus of the field the ECC curve is in
- @param mp The "b" value from montgomery_setup()
- @return 0 on success
+ @param a Curve's a value
+ @param modulus The modulus of the field the ECC curve is in
+ @return GNUTLS_E_SUCCESS on success
*/
int
-ecc_projective_dbl_point (ecc_point * P, ecc_point * R, mpz_t a /* a is -3 */,
+ecc_projective_dbl_point (ecc_point * P, ecc_point * R, mpz_t a,
mpz_t modulus)
{
+ /* Using "dbl-2004-hmv" algorithm.
+ * It costs 4M + 4S + half. */
mpz_t t1, t2;
- int err;
+ int err;
if (P == NULL || R == NULL || modulus == NULL)
- return -1;
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
- if ((err = mp_init_multi(&t1, &t2, NULL)) != 0) {
- return err;
- }
+ if ( (err = ecc_projective_isneutral(P, modulus)) == 1 ) {
- if (P != R) {
- mpz_set(R->x, P->x);
- mpz_set(R->y, P->y);
- mpz_set(R->z, P->z);
- }
+ if ((err = mp_init_multi(&t1, &t2, NULL)) != 0) {
+ return err;
+ }
- /* t1 = Z * Z */
- mpz_mul(t1, R->z, R->z);
- mpz_mod(t1, t1, modulus);
- /* Z = Y * Z */
- mpz_mul(R->z, R->y, R->z);
- mpz_mod(R->z, R->z, modulus);
- /* Z = 2Z */
- mpz_add(R->z, R->z, R->z);
- if (mpz_cmp(R->z, modulus) >= 0) {
- mpz_sub(R->z, R->z, modulus);
- }
-
- /* T2 = X - T1 */
- mpz_sub(t2, R->x, t1);
- if (mpz_cmp_ui(t2, 0) < 0) {
- mpz_add(t2, t2, modulus);
- }
- /* T1 = X + T1 */
- mpz_add(t1, t1, R->x);
- if (mpz_cmp(t1, modulus) >= 0) {
- mpz_sub(t1, t1, modulus);
- }
- /* T2 = T1 * T2 */
- mpz_mul(t2, t1, t2);
- mpz_mod(t2, t2, modulus);
- /* T1 = 2T2 */
- mpz_add(t1, t2, t2);
- if (mpz_cmp(t1, modulus) >= 0) {
- mpz_sub(t1, t1, modulus);
- }
- /* T1 = T1 + T2 */
- mpz_add(t1, t1, t2);
- if (mpz_cmp(t1, modulus) >= 0) {
- mpz_sub(t1, t1, modulus);
- }
+ if (P != R) {
+ mpz_set(R->x, P->x);
+ mpz_set(R->y, P->y);
+ mpz_set(R->z, P->z);
+ }
- /* Y = 2Y */
- mpz_add(R->y, R->y, R->y);
- if (mpz_cmp(R->y, modulus) >= 0) {
- mpz_sub(R->y, R->y, modulus);
- }
- /* Y = Y * Y */
- mpz_mul(R->y, R->y, R->y);
- mpz_mod(R->y, R->y, modulus);
- /* T2 = Y * Y */
- mpz_mul(t2, R->y, R->y);
- mpz_mod(t2, t2, modulus);
- /* T2 = T2/2 */
- if (mpz_odd_p(t2)) {
- mpz_add(t2, t2, modulus);
- }
- mpz_divexact_ui(t2, t2, 2);
- /* Y = Y * X */
- mpz_mul(R->y, R->y, R->x);
- mpz_mod(R->y, R->y, modulus);
-
- /* X = T1 * T1 */
- mpz_mul(R->x, t1, t1);
- mpz_mod(R->x, R->x, modulus);
- /* X = X - Y */
- mpz_sub(R->x, R->x, R->y);
- if (mpz_cmp_ui(R->x, 0) < 0) {
- mpz_add(R->x, R->x, modulus);
- }
- /* X = X - Y */
- mpz_sub(R->x, R->x, R->y);
- if (mpz_cmp_ui(R->x, 0) < 0) {
- mpz_add(R->x, R->x, modulus);
- }
+ if (mpz_cmp_ui (P->z, 1) != 0) {
+ /* t1 = Z * Z */
+ mpz_mul(t1, R->z, R->z);
+ mpz_mod(t1, t1, modulus);
+ /* Z = Y * Z */
+ mpz_mul(R->z, R->y, R->z);
+ mpz_mod(R->z, R->z, modulus);
+ /* Z = 2Z */
+ mpz_add(R->z, R->z, R->z);
+ if (mpz_cmp(R->z, modulus) >= 0) {
+ mpz_sub(R->z, R->z, modulus);
+ }
+ } else {
+ /* t1 = 1 */
+ mpz_set(t1, P->z);
+ /* Z = 2Y */
+ mpz_add(R->z, R->y, R->y);
+ if (mpz_cmp(R->z, modulus) >= 0) {
+ mpz_sub(R->z, R->z, modulus);
+ }
+ }
- /* Y = Y - X */
- mpz_sub(R->y, R->y, R->x);
- if (mpz_cmp_ui(R->y, 0) < 0) {
- mpz_add(R->y, R->y, modulus);
- }
- /* Y = Y * T1 */
- mpz_mul(R->y, R->y, t1);
- mpz_mod(R->y, R->y, modulus);
- /* Y = Y - T2 */
- mpz_sub(R->y, R->y, t2);
- if (mpz_cmp_ui(R->y, 0) < 0) {
- mpz_add( R->y, R->y, modulus);
- }
-
- err = 0;
+ /* T2 = X - T1 */
+ mpz_sub(t2, R->x, t1);
+ if (mpz_cmp_ui(t2, 0) < 0) {
+ mpz_add(t2, t2, modulus);
+ }
+ /* T1 = X + T1 */
+ mpz_add(t1, t1, R->x);
+ if (mpz_cmp(t1, modulus) >= 0) {
+ mpz_sub(t1, t1, modulus);
+ }
+ /* T2 = T1 * T2 */
+ mpz_mul(t2, t1, t2);
+ mpz_mod(t2, t2, modulus);
+ /* T1 = 2T2 */
+ mpz_add(t1, t2, t2);
+ if (mpz_cmp(t1, modulus) >= 0) {
+ mpz_sub(t1, t1, modulus);
+ }
+ /* T1 = T1 + T2 */
+ mpz_add(t1, t1, t2);
+ if (mpz_cmp(t1, modulus) >= 0) {
+ mpz_sub(t1, t1, modulus);
+ }
+
+ /* Y = 2Y */
+ mpz_add(R->y, R->y, R->y);
+ if (mpz_cmp(R->y, modulus) >= 0) {
+ mpz_sub(R->y, R->y, modulus);
+ }
+ /* Y = Y * Y */
+ mpz_mul(R->y, R->y, R->y);
+ mpz_mod(R->y, R->y, modulus);
+ /* T2 = Y * Y */
+ mpz_mul(t2, R->y, R->y);
+ mpz_mod(t2, t2, modulus);
+ /* T2 = T2/2 */
+ if (mpz_odd_p(t2)) {
+ mpz_add(t2, t2, modulus);
+ }
+ mpz_divexact_ui(t2, t2, 2);
+ /* Y = Y * X */
+ mpz_mul(R->y, R->y, R->x);
+ mpz_mod(R->y, R->y, modulus);
- mp_clear_multi(&t1, &t2, NULL);
- return err;
+ /* X = T1 * T1 */
+ mpz_mul(R->x, t1, t1);
+ mpz_mod(R->x, R->x, modulus);
+ /* X = X - Y */
+ mpz_sub(R->x, R->x, R->y);
+ if (mpz_cmp_ui(R->x, 0) < 0) {
+ mpz_add(R->x, R->x, modulus);
+ }
+ /* X = X - Y */
+ mpz_sub(R->x, R->x, R->y);
+ if (mpz_cmp_ui(R->x, 0) < 0) {
+ mpz_add(R->x, R->x, modulus);
+ }
+
+ /* Y = Y - X */
+ mpz_sub(R->y, R->y, R->x);
+ if (mpz_cmp_ui(R->y, 0) < 0) {
+ mpz_add(R->y, R->y, modulus);
+ }
+ /* Y = Y * T1 */
+ mpz_mul(R->y, R->y, t1);
+ mpz_mod(R->y, R->y, modulus);
+ /* Y = Y - T2 */
+ mpz_sub(R->y, R->y, t2);
+ if (mpz_cmp_ui(R->y, 0) < 0) {
+ mpz_add( R->y, R->y, modulus);
+ }
+
+ err = GNUTLS_E_SUCCESS;
+
+ mp_clear_multi(&t1, &t2, NULL);
+ return err;
+ } else if (err == 0) {
+ /* 2*neutral = neutral */
+ mpz_set_ui(R->x, 1);
+ mpz_set_ui(R->y, 1);
+ mpz_set_ui(R->z, 0);
+
+ return GNUTLS_E_SUCCESS;
+ } else {
+ return err;
+ }
}
#endif
/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_projective_dbl_point.c,v $
*/
diff --git a/lib/nettle/ecc_projective_isneutral.c
b/lib/nettle/ecc_projective_isneutral.c
new file mode 100644
index 0000000..742ae5f
--- /dev/null
+++ b/lib/nettle/ecc_projective_isneutral.c
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2011-2012 Free Software Foundation, Inc.
+ *
+ * Author: Ilya Tumaykin
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library 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 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This library 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, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#include "ecc.h"
+
+/*
+ Check if the given point is the neutral point
+ @param P The point to check
+ @param modulus The modulus of the field the ECC curve is in
+ @return 0 if given point is a neutral point
+ @return 1 if given point is not a neutral point
+ @return negative value in case of error
+*/
+int
+ecc_projective_isneutral (ecc_point * P, mpz_t modulus)
+{
+ mpz_t t1, t2;
+ int err;
+
+ if (P == NULL || modulus == NULL)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ /*
+ * neutral point is a point with projective
+ * coordinates (x,y,0) such that y^2 == x^3
+ * excluding point (0,0,0)
+ */
+ if (mpz_sgn (P->z))
+ /* Z != 0 */
+ return 1;
+
+ if ((err = mp_init_multi (&t1, &t2, NULL)) != 0)
+ {
+ return err;
+ }
+
+ /* t1 == x^3 */
+ mpz_mul (t1, P->x, P->x);
+ mpz_mod (t1, t1, modulus);
+ mpz_mul (t1, t1, P->x);
+ mpz_mod (t1, t1, modulus);
+ /* t2 == y^2 */
+ mpz_mul (t2, P->y, P->y);
+ mpz_mod (t2, t2, modulus);
+
+ if ((!mpz_cmp (t1, t2)) && (mpz_sgn (t1)))
+ {
+ /* Z == 0 and X^3 == Y^2 != 0
+ * it is neutral */
+ err = 0;
+ goto done;
+ }
+
+ /* Z == 0 and X^3 != Y^2 or
+ * Z == X == Y == 0
+ * this should never happen */
+ err = GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+ goto done;
+done:
+ mp_clear_multi (&t1, &t2, NULL);
+ return err;
+}
diff --git a/lib/nettle/ecc_projective_negate_point.c
b/lib/nettle/ecc_projective_negate_point.c
new file mode 100644
index 0000000..0021e05
--- /dev/null
+++ b/lib/nettle/ecc_projective_negate_point.c
@@ -0,0 +1,56 @@
+/*
+ * Copyright (C) 2011-2012 Free Software Foundation, Inc.
+ *
+ * Author: Ilya Tumaykin
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library 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 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This library 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, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#include "ecc.h"
+
+/*
+ Negate an ECC point
+ @param P The point to negate
+ @param R [out] The destination of the negate
+ @param modulus The modulus of the field the ECC curve is in
+ @return GNUTLS_E_SUCCESS on success
+*/
+int
+ecc_projective_negate_point (ecc_point * P, ecc_point * R, mpz_t modulus)
+{
+
+ if (P == NULL || R == NULL)
+ return GNUTLS_E_RECEIVED_ILLEGAL_PARAMETER;
+
+ if (ecc_projective_isneutral (P, modulus))
+ {
+ /* we set R.y to (modulus - P.y) to avoid negative coordinates */
+ mpz_set (R->x, P->x);
+ mpz_sub (R->y, modulus, P->y);
+ mpz_mod (R->y, R->y, modulus);
+ mpz_set (R->z, P->z);
+ }
+ else
+ {
+ /* -neutral = neutral */
+ mpz_set_ui (R->x, 1);
+ mpz_set_ui (R->y, 1);
+ mpz_set_ui (R->z, 0);
+ }
+
+ return GNUTLS_E_SUCCESS;
+}
diff --git a/lib/nettle/ecc_shared_secret.c b/lib/nettle/ecc_shared_secret.c
index c9ed006..74466ed 100644
--- a/lib/nettle/ecc_shared_secret.c
+++ b/lib/nettle/ecc_shared_secret.c
@@ -63,7 +63,7 @@ ecc_shared_secret (ecc_key * private_key, ecc_key *
public_key,
}
if ((err =
- ecc_mulmod (private_key->k, &public_key->pubkey, result,
+ ecc_mulmod_wmnaf (private_key->k, &public_key->pubkey, result,
private_key->A, private_key->prime, 1)) != 0)
{
goto done;
diff --git a/lib/nettle/ecc_sign_hash.c b/lib/nettle/ecc_sign_hash.c
index bd78da0..2adc7a2 100644
--- a/lib/nettle/ecc_sign_hash.c
+++ b/lib/nettle/ecc_sign_hash.c
@@ -38,12 +38,14 @@
@param prng An active PRNG state
@param wprng The index of the PRNG you wish to use
@param key A private ECC key
+ @param curve_id The id of the curve we are working with
@return 0 if successful
*/
int
ecc_sign_hash (const unsigned char *in, unsigned long inlen,
struct dsa_signature *sig,
- void *random_ctx, nettle_random_func random, ecc_key * key)
+ void *random_ctx, nettle_random_func random,
+ ecc_key * key, gnutls_ecc_curve_t curve_id)
{
ecc_key pubkey;
mpz_t e;
@@ -72,7 +74,7 @@ ecc_sign_hash (const unsigned char *in, unsigned long inlen,
{
if ((err =
ecc_make_key_ex (random_ctx, random, &pubkey, key->prime,
- key->order, key->A, key->B, key->Gx, key->Gy, 1))
!= 0)
+ key->order, key->A, key->B, key->Gx, key->Gy,
curve_id, 1)) != 0)
{
goto errnokey;
}
diff --git a/lib/nettle/ecc_verify_hash.c b/lib/nettle/ecc_verify_hash.c
index e7ebc23..fc31735 100644
--- a/lib/nettle/ecc_verify_hash.c
+++ b/lib/nettle/ecc_verify_hash.c
@@ -46,12 +46,13 @@
@param hashlen The length of the hash (octets)
@param stat Result of signature, 1==valid, 0==invalid
@param key The corresponding public ECC key
+ @param curve_id The id of the curve we are working with
@return 0 if successful (even if the signature is not valid)
*/
int
ecc_verify_hash (struct dsa_signature *signature,
const unsigned char *hash, unsigned long hashlen,
- int *stat, ecc_key * key)
+ int *stat, ecc_key * key, gnutls_ecc_curve_t curve_id)
{
ecc_point *mG, *mQ;
mpz_t v, w, u1, u2, e;
@@ -111,18 +112,18 @@ ecc_verify_hash (struct dsa_signature *signature,
mpz_set (mQ->z, key->pubkey.z);
/* compute u1*mG + u2*mQ = mG */
- if ((err = ecc_mulmod (u1, mG, mG, key->A, key->prime, 0)) != 0)
+ if ((err = ecc_mulmod_wmnaf_cached (u1, curve_id, mG, key->A, key->prime,
0)) != 0)
{
goto error;
}
- if ((err = ecc_mulmod (u2, mQ, mQ, key->A, key->prime, 0)) != 0)
+ if ((err = ecc_mulmod_wmnaf (u2, mQ, mQ, key->A, key->prime, 0)) != 0)
{
goto error;
}
/* add them */
if ((err =
- ecc_projective_add_point (mQ, mG, mG, key->A, key->prime)) != 0)
+ ecc_projective_add_point_ng (mQ, mG, mG, key->A, key->prime)) != 0)
{
goto error;
}
diff --git a/lib/nettle/init.c b/lib/nettle/init.c
index 34db731..bc89e40 100644
--- a/lib/nettle/init.c
+++ b/lib/nettle/init.c
@@ -24,6 +24,7 @@
#include <gnutls_errors.h>
#include <gnutls_num.h>
#include <gnutls_mpi.h>
+#include "ecc.h"
/* Functions that refer to the initialization of the nettle library.
*/
@@ -31,5 +32,14 @@
int
gnutls_crypto_init (void)
{
- return 0;
+ return ecc_wmnaf_cache_init();
+}
+
+/* Functions that refer to the deinitialization of the nettle library.
+ */
+
+void
+gnutls_crypto_deinit (void)
+{
+ ecc_wmnaf_cache_free();
}
diff --git a/lib/nettle/pk.c b/lib/nettle/pk.c
index 41a0fb1..c54d83b 100644
--- a/lib/nettle/pk.c
+++ b/lib/nettle/pk.c
@@ -327,6 +327,10 @@ _wrap_nettle_pk_sign (gnutls_pk_algorithm_t algo,
{
ecc_key priv;
struct dsa_signature sig;
+ int curve_id = pk_params->flags;
+
+ if (is_supported_curve(curve_id) == 0)
+ return gnutls_assert_val(GNUTLS_E_ECC_UNSUPPORTED_CURVE);
_ecc_params_to_privkey(pk_params, &priv);
@@ -340,8 +344,8 @@ _wrap_nettle_pk_sign (gnutls_pk_algorithm_t algo,
hash_len = vdata->size;
}
- ret = ecc_sign_hash(vdata->data, hash_len,
- &sig, NULL, rnd_func, &priv);
+ ret = ecc_sign_hash(vdata->data, hash_len,
+ &sig, NULL, rnd_func, &priv, curve_id);
if (ret != 0)
{
gnutls_assert ();
@@ -468,6 +472,10 @@ _wrap_nettle_pk_verify (gnutls_pk_algorithm_t algo,
ecc_key pub;
struct dsa_signature sig;
int stat;
+ int curve_id = pk_params->flags;
+
+ if (is_supported_curve(curve_id) == 0)
+ return gnutls_assert_val(GNUTLS_E_ECC_UNSUPPORTED_CURVE);
ret = _gnutls_decode_ber_rs (signature, &tmp[0], &tmp[1]);
if (ret < 0)
@@ -484,7 +492,7 @@ _wrap_nettle_pk_verify (gnutls_pk_algorithm_t algo,
if (hash_len > vdata->size)
hash_len = vdata->size;
- ret = ecc_verify_hash(&sig, vdata->data, hash_len, &stat, &pub);
+ ret = ecc_verify_hash(&sig, vdata->data, hash_len, &stat, &pub,
curve_id);
if (ret != 0 || stat != 1)
{
gnutls_assert();
@@ -709,7 +717,7 @@ rsa_fail:
tls_ecc_set.A = st->A;
tls_ecc_set.B = st->B;
- ret = ecc_make_key(NULL, rnd_func, &key, &tls_ecc_set);
+ ret = ecc_make_key(NULL, rnd_func, &key, &tls_ecc_set, st->id);
if (ret != 0)
return gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR);
@@ -889,7 +897,7 @@ dsa_cleanup:
memcpy(&zero.z, ecc_priv.pubkey.z, sizeof(mpz_t)); /* z = 1 */
/* verify that k*(Gx,Gy)=(x,y) */
- ret = ecc_mulmod(ecc_priv.k, &zero, R, TOMPZ(params->params[ECC_A]),
TOMPZ(params->params[ECC_PRIME]), 1);
+ ret = ecc_mulmod_wmnaf_cached(ecc_priv.k, curve, R,
TOMPZ(params->params[ECC_A]), TOMPZ(params->params[ECC_PRIME]), 1);
if (ret != 0)
{
ret = gnutls_assert_val(GNUTLS_E_ILLEGAL_PARAMETER);
diff --git a/lib/nettle/wmnaf.c b/lib/nettle/wmnaf.c
new file mode 100644
index 0000000..778518a
--- /dev/null
+++ b/lib/nettle/wmnaf.c
@@ -0,0 +1,154 @@
+/*
+ * Copyright (C) 2011-2012 Free Software Foundation, Inc.
+ *
+ * Author: Ilya Tumaykin
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library 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 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This library 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, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <gmp.h>
+
+#include "ecc.h"
+
+/* needed constants */
+#define BASEW (1 << WMNAF_WINSIZE) /* 2^w */
+#define BASEWW (1 << (WMNAF_WINSIZE + 1)) /* 2^(w+1) */
+#define WBITS (BASEWW - 1)
+
+#define ABS(x) ((x) >= 0 ? (x) : -(x))
+
+/*
+ * A local replacement for mpz_tstbit.
+ * It is needed because for negative numbers original mpz_tstbit
+ * returns an infinite number of `1`s after all bits of input number.
+ * For positive numbers it returns zeros after all bits of input number.
+ * This function mimics mpz_tstbit behavior for positive numbers in both cases.
+ */
+static int
+mpz_unitstbit (mpz_srcptr u, mp_bitcnt_t bit_index)
+ __GMP_NOTHROW
+{
+ mp_srcptr u_ptr = (u)->_mp_d;
+ mp_size_t size = (u)->_mp_size;
+ unsigned abs_size = ABS (size);
+ mp_size_t limb_index = bit_index / GMP_NUMB_BITS;
+ mp_srcptr p = u_ptr + limb_index;
+ mp_limb_t limb;
+
+ if (limb_index >= abs_size)
+ return (size < 0);
+
+ limb = *p;
+
+ return (limb >> (bit_index % GMP_NUMB_BITS)) & 1;
+}
+
+/*
+ * Return an array with wMNAF representation together with its length.
+ * The result is the array with elements from the set {0, +-1, +-3, +-5, ...,
+-(2^w - 1)}
+ * such that at most one of any (w + 1) consecutive digits is non-zero
+ * with exception for the the most significant (w + 1) bits.
+ * With the last property it is modified version of wNAF.
+ * Overview of this algorithm can be found, for exmaple, in
+ * Bodo Moller, Improved Techniques for Fast Exponentiation.
+ * Information Security and Cryptology â ICISC 2002, Springer-Verlag LNCS
2587, pp. 298â312
+ */
+/*
+ @param x The number to get wMNAF for
+ @param len [out] Destination for the length of wMNAF
+ @return array with wMNAF representation
+ @return NULL in case of errors
+ */
+signed char *
+ecc_wMNAF (mpz_t x, size_t * wmnaf_len)
+{
+ int b, c;
+ char sign = 1;
+ size_t i, len;
+
+ signed char *ret = NULL;
+
+ if (!(sign = mpz_sgn (x)))
+ {
+ /* x == 0 */
+ ret = malloc (1);
+ if (ret == NULL)
+ goto done;
+
+ ret[0] = 0;
+ *wmnaf_len = 1;
+ goto done;
+ }
+
+ /* total number of bits */
+ len = mpz_sizeinbase (x, 2);
+
+ /* wMNAF is at most (len + 1) bits long */
+ ret = malloc (len + 1);
+ if (ret == NULL)
+ goto done;
+
+ /* get (w + 1) Least Significant Bits */
+ c = (mpz_getlimbn (x, 0)) & WBITS;
+
+ /* how many bits we've already processed */
+ i = 0;
+
+ while ((c != 0) || (i + WMNAF_WINSIZE + 1 < len))
+ {
+ if (c & 1)
+ {
+ /* LSB == 1 */
+ if (c >= BASEW)
+ {
+ b = c - BASEWW;
+ }
+ else
+ {
+ b = c;
+ }
+
+ c -= b;
+ }
+ else
+ {
+ b = 0;
+ }
+
+ ret[i++] = sign * b;
+
+ /* fill c with next LSB */
+ c >>= 1;
+ c += BASEW * mpz_unitstbit (x, i + WMNAF_WINSIZE);
+ }
+
+ *wmnaf_len = i--;
+
+ /* do modified wNAF
+ * check if wNAF starts with 1 and
+ * (w + 1)th bit is negative */
+ if ((ret[i] == 1) && (ret[i - (WMNAF_WINSIZE + 1)] < 0))
+ {
+ ret[i - (WMNAF_WINSIZE + 1)] += BASEW;
+ ret[i - 1] = 1;
+ *wmnaf_len = i;
+ }
+done:
+ return ret;
+}
diff --git a/lib/system.c b/lib/system.c
index 14bd085..067f189 100644
--- a/lib/system.c
+++ b/lib/system.c
@@ -125,7 +125,7 @@ int system_recv_timeout(gnutls_transport_ptr_t ptr,
unsigned int ms)
{
fd_set rfds;
struct timeval tv;
-int ret, ret2;
+int ret;
int fd = GNUTLS_POINTER_TO_INT(ptr);
FD_ZERO(&rfds);
@@ -144,10 +144,6 @@ int fd = GNUTLS_POINTER_TO_INT(ptr);
if (ret <= 0)
return ret;
- ret2 = recv(fd, NULL, 0, MSG_PEEK);
- if (ret2 == -1)
- return ret2;
-
return ret;
}
diff --git a/m4/hooks.m4 b/m4/hooks.m4
index ed5cb2f..0b5c972 100644
--- a/m4/hooks.m4
+++ b/m4/hooks.m4
@@ -39,9 +39,9 @@ AC_DEFUN([LIBGNUTLS_HOOKS],
# Interfaces changed/added/removed: CURRENT++ REVISION=0
# Interfaces added: AGE++
# Interfaces removed: AGE=0
- AC_SUBST(LT_CURRENT, 39)
+ AC_SUBST(LT_CURRENT, 40)
AC_SUBST(LT_REVISION, 0)
- AC_SUBST(LT_AGE, 11)
+ AC_SUBST(LT_AGE, 12)
AC_SUBST(LT_SSL_CURRENT, 27)
AC_SUBST(LT_SSL_REVISION, 2)
diff --git a/src/cli-args.c b/src/cli-args.c
index 09e65e5..a7c035b 100644
--- a/src/cli-args.c
+++ b/src/cli-args.c
@@ -2,7 +2,7 @@
*
* DO NOT EDIT THIS FILE (cli-args.c)
*
- * It has been AutoGen-ed June 6, 2012 at 09:09:25 PM by AutoGen 5.16
+ * It has been AutoGen-ed September 2, 2012 at 08:04:08 PM by AutoGen 5.16
* From the definitions cli-args.def
* and the template file options
*
diff --git a/src/cli-args.h b/src/cli-args.h
index e8c9dac..21a45f2 100644
--- a/src/cli-args.h
+++ b/src/cli-args.h
@@ -2,7 +2,7 @@
*
* DO NOT EDIT THIS FILE (cli-args.h)
*
- * It has been AutoGen-ed June 6, 2012 at 09:09:25 PM by AutoGen 5.16
+ * It has been AutoGen-ed September 2, 2012 at 08:04:08 PM by AutoGen 5.16
* From the definitions cli-args.def
* and the template file options
*
hooks/post-receive
--
GNU gnutls
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [SCM] GNU gnutls branch, gnutls_3_1_x, updated. gnutls_3_1_0-48-g4ae6b97,
Nikos Mavrogiannopoulos <=