nettle-bugs

nettle-bugs@lists.lysator.liu.se

1 participants
2200 discussions

ECC status update for February
by nisse＠lysator.liu.se 04 Apr '13

04 Apr '13

Here's a copy of the second status update, which I just submitted to Internetfonden. Regards, /Niels Nettle project funded by Internetfonden Status update for February 2013 * Summary New ECC code integrated in the Nettle repository. The code has been optimized with respect to both storage and computation requirements. * Activities Most of the time in February has been spent on the ECC code, both optimization, and integration work. The ECC code has been integrated into Nettle, including a preliminary high-level interface for ECDSA signatures. The code is available in the branch "ecc-support" in the repository at git://git.lysator.liu.se/nettle/nettle.git. Final days and first days of February have been used to implement the most important curve-specific functions in ARM assembly. Independently if the ECC support, also the function memxor has been optimized for ARM. During the month, roughly 120 working hours have been spent on the project. * Elliptic curves Point multiplication involving an arbitrary point now uses a side-channel silent window based algorithm. This gave a speedup of around 30% for ECDSA signature verification. For each curve, arithmetic on the coordinates is done modulo a curve specific prime number, e.g., p = 2^192 - 2^64 + 1 for the curve "secp-192r1", and p = 2^224 - 2^96 - 1 for the curve "secp-224r1". These primes all have special structure, which can be used to speed up the modp operation following each multiplication of two coordinates. Since the key operation is add with carry, which is poorly supported by the C programming language, writing these functions in assembly is attractive. Reducing a 384 bit number, typically the product of two 192-bit numbers, modulo the 192-bit prime above can be done with 12 add with carry instructions on the x86_64 architecture, or 26 on the 32-bit ARM. ARM assembly implementation gave a speedup of 2-4 times of the modulo operations, corresponding to a speedup around 50% for ECDSA sign and verify operations. The functions for doing ECC point addition have also been optimized to reduce the amount of temporary storage. E.g, with the current code, ECDSA signatures over the curve secp-256r1 requires 384 bytes of temporary storage for signing, and 2080 bytes to verify a signature. A few operations did not use side-channel silent algorithms earlier. These have been replaced by side-channel silent versions, which causes some slowdown. In particular, the side-channel silent modular inversion is very slow. Benchmarks, as of March 5, including changes relative the the numbers in the previous status report: Intel i5, 3.4 GHz: name size sign/ms verify/ms rsa 1024 6.3299 105.0161 rsa 2048 0.9573 29.5316 dsa 1024 11.1947 5.7647 ecdsa 192 18.1878 +1.4% 6.2035 +64% ecdsa 224 8.9302 -11% 2.8714 +41% ecdsa 256 8.1958 -13% 2.6707 +20% ecdsa 384 3.1515 -10% 0.9866 +25% ecdsa 521 1.8874 -13% 0.6858 +30% ecdsa (openssl) 224 3.4829 3.0458 ecdsa (openssl) 384 1.4516 1.2711 ecdsa (openssl) 521 0.6855 0.5831 ARM Cortex A9, 1 GHz: name size sign/ms verify/ms rsa 1024 0.2634 4.5464 rsa 2048 0.0392 1.2481 dsa 1024 0.4688 0.2381 ecdsa 192 1.2303 -4.5% 0.4318 +50% ecdsa 224 0.8526 +8.5% 0.3075 +72% ecdsa 256 0.6286 +6.5% 0.2243 +75% ecdsa 384 0.2532 +4.5% 0.0876 +61% ecdsa 521 0.1319 -0.6% 0.0448 +51% ecdsa (openssl) 224 0.1843 0.1563 ecdsa (openssl) 384 0.0693 0.0589 ecdsa (openssl) 521 0.0259 0.0214 So in these benchmarks, the net effect of the development is a great improvement of the speed of signature verification, with more mixed results for signature creation. For comparison, the benchmark also includes figures for the ECDSA functions provided by the OpenSSL library (for the three curves supported by both Nettle and OpenSSL). On x86_64, signing is 2.2 -- 2.8 times faster than OpenSSL, and verification is from 22% slower to 18% faster. On ARM, signature performance is 3.6 -- 5 times faster, and verify performance is 1.5 -- 2 times faster. Speaking of benchmarks, the ARM assembly for Nettle's memxor function, also developed during February, gave a speedup of 20% -- 50% depending on the input alignment. * Remaining tasks The ECC interface needs to be finalized and documented. There are always additional optimizations that are possible. Writing x86_64 assembly for the modulo functions is tempting, but of low priority within this project. As mentioned, the modular inversion is slow, with the current code, 20% -- 30% of the time to create an ECDSA signature is spent computing a modular inverse. This could be sped up by assembly implementation of the primitives this algorithm needs, or by writing the complete function in assembler. The optimization of other cryptographic primitives such as the AES cipher and the SHA256 hash function remains to do. It has turned out that some internal functions in the GMP library, used for arithmetic on larger numbers, would be useful for the ECC implementation. One possible direction is to extend the public GMP interface so these functions can be used. -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 1

Possible bug and patch for nettle
by Sarat Chandra Addepalli 01 Apr '13

01 Apr '13

1 0

openssl tests
by Nikos Mavrogiannopoulos 27 Mar '13

27 Mar '13

Hello, In some systems the elliptic curves part of openssl is disabled. This patch disables the openssl examples/tests if it does not exist (I had issue with the EC tests). Also in some issue I replaced an #if with and #ifdef, because the rule didn't work. -#if WITH_OPENSSL +#ifdef WITH_OPENSSL In general I noticed a lot of uses of "#if" that actually mean ifdef. Are these intentional? I'm not really sure what #if does if followed by an undefined expression. regards, Nikos

2 2

salsa20r12
by Nikos Mavrogiannopoulos 25 Mar '13

25 Mar '13

Hello, This patch adds a function to use the Salsa20 with 12 rounds. regards, Nikos

2 3

[PATCH] Factorize timing functions to a separate file
by Martin Storsjö 25 Mar '13

25 Mar '13

This avoids unconditionally using clock_gettime in {ecc,hogweed}-benchmark, falling back to clock() in these as well. This makes building succeed on e.g. OS X. --- examples/Makefile.in | 16 +++--- examples/ecc-benchmark.c | 26 ++-------- examples/hogweed-benchmark.c | 26 ++-------- examples/nettle-benchmark.c | 69 ++------------------------ examples/timing.c | 110 ++++++++++++++++++++++++++++++++++++++++++ examples/timing.h | 30 ++++++++++++ 6 files changed, 162 insertions(+), 115 deletions(-) create mode 100644 examples/timing.c create mode 100644 examples/timing.h diff --git a/examples/Makefile.in b/examples/Makefile.in index 3455a58..563d0dc 100644 --- a/examples/Makefile.in +++ b/examples/Makefile.in @@ -28,7 +28,7 @@ SOURCES = nettle-benchmark.c hogweed-benchmark.c ecc-benchmark.c \ nettle-openssl.c \ io.c read_rsa_key.c \ rsa-encrypt.c rsa-decrypt.c rsa-keygen.c rsa-sign.c rsa-verify.c \ - base16enc.c base16dec.c base64enc.c base64dec.c + base16enc.c base16dec.c base64enc.c base64dec.c timing.c GETOPT_OBJS = ../getopt.$(OBJEXT) ../getopt1.$(OBJEXT) @@ -36,7 +36,7 @@ GETOPT_OBJS = ../getopt.$(OBJEXT) ../getopt1.$(OBJEXT) TS_ALL = rsa-sign-test rsa-verify-test rsa-encrypt-test DISTFILES= $(SOURCES) Makefile.in $(TS_ALL) setup-env teardown-env \ - io.h rsa-session.h + io.h rsa-session.h timing.h all: $(TARGETS) @@ -102,16 +102,18 @@ eratosthenes$(EXEEXT): eratosthenes.$(OBJEXT) $(GETOPT_OBJS) $(LINK) eratosthenes.$(OBJEXT) $(GETOPT_OBJS) -o eratosthenes$(EXEEXT) BENCH_OBJS = nettle-benchmark.$(OBJEXT) nettle-openssl.$(OBJEXT) \ - $(GETOPT_OBJS) ../nettle-internal.$(OBJEXT) + $(GETOPT_OBJS) ../nettle-internal.$(OBJEXT) timing.$(OBJEXT) nettle-benchmark$(EXEEXT): $(BENCH_OBJS) $(LINK) $(BENCH_OBJS) -lnettle $(BENCH_LIBS) $(OPENSSL_LIBFLAGS) -o nettle-benchmark$(EXEEXT) -ecc-benchmark$(EXEEXT): ecc-benchmark.$(OBJEXT) - $(LINK) ecc-benchmark.$(OBJEXT) -lhogweed -lnettle $(BENCH_LIBS) $(LIBS) \ +ECC_BENCH_OBJS = ecc-benchmark.$(OBJEXT) timing.$(OBJEXT) +ecc-benchmark$(EXEEXT): $(ECC_BENCH_OBJS) + $(LINK) $(ECC_BENCH_OBJS) -lhogweed -lnettle $(BENCH_LIBS) $(LIBS) \ -o ecc-benchmark$(EXEEXT) -hogweed-benchmark$(EXEEXT): hogweed-benchmark.$(OBJEXT) - $(LINK) hogweed-benchmark.$(OBJEXT) \ +HOGWEED_BENCH_OBJS = hogweed-benchmark.$(OBJEXT) timing.$(OBJEXT) +hogweed-benchmark$(EXEEXT): $(HOGWEED_BENCH_OBJS) + $(LINK) $(HOGWEED_BENCH_OBJS) \ -lhogweed -lnettle $(BENCH_LIBS) $(LIBS) $(OPENSSL_LIBFLAGS) \ -o hogweed-benchmark$(EXEEXT) diff --git a/examples/ecc-benchmark.c b/examples/ecc-benchmark.c index 596b2ff..e14e55e 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -35,6 +35,8 @@ #include <time.h> +#include "timing.h" + #include "../ecc.h" #include "../ecc-internal.h" #include "../gmp-glue.h" @@ -70,24 +72,6 @@ xalloc_limbs (mp_size_t size) return xalloc (size * sizeof(mp_limb_t)); } -inline static void -time_start(struct timespec *start) -{ - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, start) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); -} - -static inline double -time_end(struct timespec *start) -{ - struct timespec end; - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); - - return end.tv_sec - start->tv_sec - + 1e-9 * (end.tv_nsec - start->tv_nsec); -} - /* Returns second per function call */ static double time_function(void (*f)(void *arg), void *arg) @@ -100,12 +84,11 @@ time_function(void (*f)(void *arg), void *arg) for (ncalls = 10 ;;) { unsigned i; - struct timespec t; - time_start(&t); + time_start(); for (i = 0; i < ncalls; i++) f(arg); - elapsed = time_end(&t); + elapsed = time_end(); if (elapsed > BENCH_INTERVAL) break; else if (elapsed < BENCH_INTERVAL / 10) @@ -293,6 +276,7 @@ main (int argc UNUSED, char **argv UNUSED) { unsigned i; + time_init(); printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n", "size", "modp", "redc", "modq", "modinv", "mi_gcd", "dup_jj", "ad_jja", "ad_jjj", diff --git a/examples/hogweed-benchmark.c b/examples/hogweed-benchmark.c index f6ceda9..56860e0 100644 --- a/examples/hogweed-benchmark.c +++ b/examples/hogweed-benchmark.c @@ -34,6 +34,8 @@ #include <time.h> +#include "timing.h" + #include "dsa.h" #include "rsa.h" @@ -90,24 +92,6 @@ hash_string (const struct nettle_hash *hash, return digest; } -inline static void -time_start(struct timespec *start) -{ - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, start) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); -} - -static inline double -time_end(struct timespec *start) -{ - struct timespec end; - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); - - return end.tv_sec - start->tv_sec - + 1e-9 * (end.tv_nsec - start->tv_nsec); -} - struct alg { const char *name; unsigned size; @@ -129,12 +113,11 @@ time_function(void (*f)(void *arg), void *arg) for (ncalls = 10 ;;) { unsigned i; - struct timespec t; - time_start(&t); + time_start(); for (i = 0; i < ncalls; i++) f(arg); - elapsed = time_end(&t); + elapsed = time_end(); if (elapsed > BENCH_INTERVAL) break; else if (elapsed < BENCH_INTERVAL / 10) @@ -625,6 +608,7 @@ main (int argc, char **argv) if (argc > 1) filter = argv[1]; + time_init(); printf ("%15s %4s %9s %9s\n", "name", "size", "sign/ms", "verify/ms"); diff --git a/examples/nettle-benchmark.c b/examples/nettle-benchmark.c index 90d6c72..852baef 100644 --- a/examples/nettle-benchmark.c +++ b/examples/nettle-benchmark.c @@ -38,6 +38,8 @@ #include <time.h> +#include "timing.h" + #include "aes.h" #include "arcfour.h" #include "blowfish.h" @@ -112,58 +114,6 @@ die(const char *format, ...) static double overhead = 0.0; -#if HAVE_CLOCK_GETTIME && defined CLOCK_PROCESS_CPUTIME_ID -#define TRY_CLOCK_GETTIME 1 -struct timespec cgt_start; - -static int -cgt_works_p(void) -{ - struct timespec now; - return clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &now) == 0; -} - -static void -cgt_time_start(void) -{ - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cgt_start) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); -} - -static double -cgt_time_end(void) -{ - struct timespec end; - if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) - die("clock_gettime failed: %s\n", strerror(errno)); - - return end.tv_sec - cgt_start.tv_sec - + 1e-9 * (end.tv_nsec - cgt_start.tv_nsec); -} - -static void (*time_start)(void); -static double (*time_end)(void); - -#else /* !HAVE_CLOCK_GETTIME */ -#define TRY_CLOCK_GETTIME 0 -#define time_start clock_time_start -#define time_end clock_time_end -#endif /* !HAVE_CLOCK_GETTIME */ - -static clock_t clock_start; - -static void -clock_time_start(void) -{ - clock_start = clock(); -} - -static double -clock_time_end(void) -{ - return (double) (clock() - (clock_start)) / CLOCKS_PER_SEC; -} - /* Returns second per function call */ static double time_function(void (*f)(void *arg), void *arg) @@ -700,20 +650,7 @@ main(int argc, char **argv) alg = argv[optind]; - /* Choose timing function */ -#if TRY_CLOCK_GETTIME - if (cgt_works_p()) - { - time_start = cgt_time_start; - time_end = cgt_time_end; - } - else - { - fprintf(stderr, "clock_gettime not working, falling back to clock\n"); - time_start = clock_time_start; - time_end = clock_time_end; - } -#endif + time_init(); bench_sha1_compress(); bench_salsa20_core(); bench_sha3_permute(); diff --git a/examples/timing.c b/examples/timing.c new file mode 100644 index 0000000..108399a --- /dev/null +++ b/examples/timing.c @@ -0,0 +1,110 @@ +/* timing.c */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2013 Niels Möller + * + * The nettle 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 2.1 of the License, or (at your + * option) any later version. + * + * The nettle 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 the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02111-1301, USA. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "timing.h" + +#include <errno.h> +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#if HAVE_CLOCK_GETTIME && defined CLOCK_PROCESS_CPUTIME_ID +#define TRY_CLOCK_GETTIME 1 +struct timespec cgt_start; + +static void NORETURN PRINTF_STYLE(1,2) +die(const char *format, ...) +{ + va_list args; + va_start(args, format); + vfprintf(stderr, format, args); + va_end(args); + + exit(EXIT_FAILURE); +} + +static int +cgt_works_p(void) +{ + struct timespec now; + return clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &now) == 0; +} + +static void +cgt_time_start(void) +{ + if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cgt_start) < 0) + die("clock_gettime failed: %s\n", strerror(errno)); +} + +static double +cgt_time_end(void) +{ + struct timespec end; + if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) + die("clock_gettime failed: %s\n", strerror(errno)); + + return end.tv_sec - cgt_start.tv_sec + + 1e-9 * (end.tv_nsec - cgt_start.tv_nsec); +} +#endif /* !HAVE_CLOCK_GETTIME */ + +static clock_t clock_start; + +static void +clock_time_start(void) +{ + clock_start = clock(); +} + +static double +clock_time_end(void) +{ + return (double) (clock() - (clock_start)) / CLOCKS_PER_SEC; +} + +void (*time_start)(void) = clock_time_start; +double (*time_end)(void) = clock_time_end; + +void time_init(void) +{ + /* Choose timing function */ +#if TRY_CLOCK_GETTIME + if (cgt_works_p()) + { + time_start = cgt_time_start; + time_end = cgt_time_end; + } + else + { + fprintf(stderr, "clock_gettime not working, falling back to clock\n"); + time_start = clock_time_start; + time_end = clock_time_end; + } +#endif +} diff --git a/examples/timing.h b/examples/timing.h new file mode 100644 index 0000000..7307fa1 --- /dev/null +++ b/examples/timing.h @@ -0,0 +1,30 @@ +/* timing.c */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2013 Niels Möller + * + * The nettle 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 2.1 of the License, or (at your + * option) any later version. + * + * The nettle 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 the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02111-1301, USA. + */ + +#ifndef NETTLE_EXAMPLES_TIMING_H_INCLUDED +#define NETTLE_EXAMPLES_TIMING_H_INCLUDED + +void time_init(void); +extern void (*time_start)(void); +extern double (*time_end)(void); + +#endif /* NETTLE_EXAMPLES_TIMING_H_INCLUDED */ -- 1.7.9.4

2 1

[PATCH] Add a fallback definition for mpn_sqr
by Martin Storsjö 25 Mar '13

25 Mar '13

--- gmp-glue.h | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/gmp-glue.h b/gmp-glue.h index 0cde62f..d154a50 100644 --- a/gmp-glue.h +++ b/gmp-glue.h @@ -58,6 +58,10 @@ typedef unsigned long int mp_bitcnt_t; #define mpn_zero _nettle_mpn_zero #endif +#ifndef mpn_sqr +#define mpn_sqr(rp, ap, n) mpn_mul_n((rp), (ap), (ap), (n)) +#endif + #define mpz_limbs_cmp _nettle_mpz_limbs_cmp #define mpz_limbs_read_n _nettle_mpz_limbs_read_n #define mpz_limbs_copy _nettle_mpz_limbs_copy -- 1.7.9.4

1 0

[PATCH] Use local paths for including headers in examples and tests
by Martin Storsjö 23 Mar '13

23 Mar '13

This makes sure a plain "make" succeeds without doing "make install". --- examples/hogweed-benchmark.c | 10 +++++----- testsuite/ecdsa-keygen-test.c | 2 +- 2 files changed, 6 insertions(+), 6 deletions(-) diff --git a/examples/hogweed-benchmark.c b/examples/hogweed-benchmark.c index 803f056..b1a0e89 100644 --- a/examples/hogweed-benchmark.c +++ b/examples/hogweed-benchmark.c @@ -34,12 +34,12 @@ #include <time.h> -#include <nettle/dsa.h> -#include <nettle/rsa.h> +#include "dsa.h" +#include "rsa.h" -#include <nettle/nettle-meta.h> -#include <nettle/sexp.h> -#include <nettle/knuth-lfib.h> +#include "nettle-meta.h" +#include "sexp.h" +#include "knuth-lfib.h" #include "../ecdsa.h" #include "../ecc-internal.h" diff --git a/testsuite/ecdsa-keygen-test.c b/testsuite/ecdsa-keygen-test.c index 4f46d0d..7c25421 100644 --- a/testsuite/ecdsa-keygen-test.c +++ b/testsuite/ecdsa-keygen-test.c @@ -1,5 +1,5 @@ #include "testutils.h" -#include <nettle/knuth-lfib.h> +#include "knuth-lfib.h" /* Check if y^2 = x^3 - 3x + b */ static int -- 1.7.9.4

1 0

ARM assembly
by nisse＠lysator.liu.se 16 Mar '13

16 Mar '13

I've new written some ARM assembly files for AES, SHA1 and SHA256. I haven't tried any clever scheduling (it seems quite unpredictable), so I think I win over the C code is mainly because I fit the important values in registers. I have benchmarked on a cortex-a9 system, with nice but not earth-shattering improvements over the C implementation. In my benchmarks, AES decrypt is significantly slower than AES decrypt, for no reason that I understand, and I have tried some other variants of instruction scheduling. I have one question on the ABI, if there's anyone on the list with more ARM experience: In the ABI spec, register r9 is reserved for use for things such as thread local storage. I'm almost sure that a leaf function can use r9 like any other callee-save register, but I'd like to have that confirmed before I make use of it. Potential problem case is if the function is interrupted by a signal and signal handler somehow depends on having a valid value in r9, or if context switching somehow assumes that r9 is never modified. Any suggestion for what to try optimizing next? I imagine all algorithms that make use of 64-bit data or are designed for simd operations could be sped up a bit using the neon simd instructions (which I so far haven't made any use of). This includes sha512, sha3, serpent, salsa, maybe camellia. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

3 3

ECC integration
by nisse＠lysator.liu.se 18 Feb '13

18 Feb '13

I'm working on integration of the new ECC code into nettle, on a separate branch, see http://git.lysator.liu.se/nettle/nettle/commits/ecc-support I've probably broken cross-compilation support, but otherwise it should be working. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

1 0

ECC low-level interface
by nisse＠lysator.liu.se 18 Feb '13

18 Feb '13

I'd like to post the interface I use for low-level ecc functions. All functions are intended to be side-channel silent. I have tried to stick to the nettle principle of "no allocation" (I mostly call low-level gmp functions which don't allocate storage). Functions which need scratch space gets this space from the caller, as an extra argument. And for the function foo, there's a corresponding function foo_itch, saying how much working storage is needed. Sizes are in units of mp_limb_t. Of these low-level functions, the highest level ones are ecc_mul_g and ecc_mul_a. Feedback is appreciated. The rest of the code is available at http://git.lysator.liu.se/nettle/se-nettle-2013 Regards, /Niels /* ecc.h */ /* nettle, low-level cryptographics library * * Copyright (C) 2013 Niels MÃ¶ller * * The nettle 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 2.1 of the License, or (at your * option) any later version. * * The nettle 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 the nettle library; see the file COPYING.LIB. If not, write to * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, * MA 02111-1301, USA. */ /* Development of Nettle's ECC support was funded by Internetfonden. */ #ifndef NETTLE_ECC_H_INCLUDED #define NETTLE_ECC_H_INCLUDED #include <stdint.h> #include <gmp.h> /* The contets of this struct is internal. */ struct ecc_curve; extern const struct ecc_curve ecc_secp_192r1; extern const struct ecc_curve ecc_secp_224r1; extern const struct ecc_curve ecc_secp_256r1; extern const struct ecc_curve ecc_secp_384r1; extern const struct ecc_curve ecc_secp_521r1; /* Points on a curve are represented as arrays of mp_limb_t. For some curves, point coordinates are represented in montgomery form. We use either affine coordinates x,y, or Jacobian coordinates X, Y, Z, where x = X/Z^2 and y = X/Z^2. Since we use additive notation for the groups, the infinity point on the curve is denoted 0. The infinity point can be represented with x = y = 0 in affine coordinates, and Z = 0 in Jacobian coordinates. However, note that most of the ECC functions do *not* support infinity as an input or output. */ /* FIXME: Also provided some compile time constants? */ /* Returns the size of a single coordinate. */ mp_size_t ecc_size (const struct ecc_curve *ecc); /* Size of a point, using affine coordinates x, y. */ mp_size_t ecc_size_a (const struct ecc_curve *ecc); /* Size of a point, using jacobian coordinates X, Y and Z. */ mp_size_t ecc_size_j (const struct ecc_curve *ecc); /* FIXME: Rename the low-level (and side-channel silent) functions to _ecc_*, and provide public ecc_* functions which handle the infinity points properly? */ /* Converts the affine coordinates of a point into montgomery form, if used for this curve. */ mp_size_t ecc_a_to_a_itch (const struct ecc_curve *ecc); void ecc_a_to_a (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Converts a point P in affine coordinates into a point R in jacobian coordinates. If INITIAL is non-zero, and the curve uses montgomery coordinates, also convert coordinates to montgomery form. */ void ecc_a_to_j (const struct ecc_curve *ecc, int initial, mp_limb_t *r, const mp_limb_t *p); /* Converts a point P in jacobian coordinates into a point R in affine coordinates. If FLAGS has bit 0 set, and the curve uses montgomery coordinates, also undo the montgomery conversion. If flags has bit 1 set, produce x coordinate only. */ mp_size_t ecc_j_to_a_itch (const struct ecc_curve *ecc); void ecc_j_to_a (const struct ecc_curve *ecc, int flags, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Group operations */ /* Point doubling, with jacobian output and affine input. Corner cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ mp_size_t ecc_dup_ja_itch (const struct ecc_curve *ecc); void ecc_dup_ja (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Point doubling, with jacobian input and output. Corner cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ mp_size_t ecc_dup_jj_itch (const struct ecc_curve *ecc); void ecc_dup_jj (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); /* Point addition, with jacobian output, one jacobian input and one affine input. Corner cases: Fails for the cases P = Q != 0 Duplication of non-zero point P = 0, Q != 0 or P != 0, Q = 0 One input zero Correctly gives R = 0 if P = Q = 0 or P = -Q. */ mp_size_t ecc_add_jja_itch (const struct ecc_curve *ecc); void ecc_add_jja (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, mp_limb_t *scratch); /* Point addition with Jacobian input and output. */ mp_size_t ecc_add_jjj_itch (const struct ecc_curve *ecc); void ecc_add_jjj (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, mp_limb_t *scratch); /* Computes N * the group generator. N is an array of ecc_size() limbs. It must be in the range 0 < N < group order, then R != 0, and the algorithm can work without any intermediate values getting to zero. */ mp_size_t ecc_mul_g_itch (const struct ecc_curve *ecc); void ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *np, mp_limb_t *scratch); /* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a non-zero point on the curve, in affine coordinates. Pass a non-zero INITIAL if the point coordinates have not previously been converted to Montgomery representation. Output R is a non-zero point, in Jacobian coordinates. */ mp_size_t ecc_mul_a_itch (const struct ecc_curve *ecc); void ecc_mul_a (const struct ecc_curve *ecc, int initial, mp_limb_t *r, const mp_limb_t *np, const mp_limb_t *p, mp_limb_t *scratch); #endif /* NETTLE_ECC_H_INCLUDED */ -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance.

2 11

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

nettle-bugs