aboutsummaryrefslogtreecommitdiff
path: root/src/secp256k1
diff options
context:
space:
mode:
Diffstat (limited to 'src/secp256k1')
-rw-r--r--src/secp256k1/.travis.yml19
-rw-r--r--src/secp256k1/Makefile.am30
-rw-r--r--src/secp256k1/build-aux/m4/bitcoin_secp.m451
-rw-r--r--src/secp256k1/configure.ac11
-rw-r--r--src/secp256k1/include/secp256k1.h32
-rwxr-xr-xsrc/secp256k1/nasm_lt.sh57
-rw-r--r--src/secp256k1/src/bench.h37
-rw-r--r--src/secp256k1/src/bench_inv.c45
-rw-r--r--src/secp256k1/src/bench_recover.c46
-rw-r--r--src/secp256k1/src/bench_sign.c49
-rw-r--r--src/secp256k1/src/bench_verify.c59
-rw-r--r--src/secp256k1/src/ecdsa_impl.h8
-rw-r--r--src/secp256k1/src/eckey_impl.h8
-rw-r--r--src/secp256k1/src/ecmult_gen_impl.h6
-rw-r--r--src/secp256k1/src/ecmult_impl.h17
-rw-r--r--src/secp256k1/src/field.h8
-rw-r--r--src/secp256k1/src/field_10x26_impl.h64
-rw-r--r--src/secp256k1/src/field_5x52_asm.asm469
-rw-r--r--src/secp256k1/src/field_5x52_asm_impl.h495
-rw-r--r--src/secp256k1/src/field_5x52_impl.h48
-rw-r--r--src/secp256k1/src/field_5x52_int128_impl.h4
-rw-r--r--src/secp256k1/src/field_gmp_impl.h4
-rw-r--r--src/secp256k1/src/field_impl.h32
-rw-r--r--src/secp256k1/src/group.h7
-rw-r--r--src/secp256k1/src/group_impl.h59
-rw-r--r--src/secp256k1/src/scalar_impl.h2
-rw-r--r--src/secp256k1/src/secp256k1.c38
-rw-r--r--src/secp256k1/src/tests.c332
-rw-r--r--src/secp256k1/src/util.h6
29 files changed, 1198 insertions, 845 deletions
diff --git a/src/secp256k1/.travis.yml b/src/secp256k1/.travis.yml
index 3a85e8cba0..28cd61dbc9 100644
--- a/src/secp256k1/.travis.yml
+++ b/src/secp256k1/.travis.yml
@@ -1,12 +1,14 @@
-language: cpp
-compiler: gcc
+language: c
+compiler:
+ - clang
+ - gcc
install:
- sudo apt-get install -qq libssl-dev
- - if [ "$BIGNUM" = "gmp" -o "$BIGNUM" = "auto" -o "$FIELD" = "gmp" ]; then sudo apt-get install -qq libgmp-dev; fi
- - if [ "$FIELD" = "64bit_asm" ]; then sudo apt-get install -qq yasm; fi
+ - if [ "$BIGNUM" = "gmp" -o "$BIGNUM" = "auto" -o "$FIELD" = "gmp" ]; then sudo apt-get install --no-install-recommends --no-upgrade -qq libgmp-dev; fi
+ - if [ -n "$EXTRAPACKAGES" ]; then sudo apt-get update && sudo apt-get install --no-install-recommends --no-upgrade $EXTRAPACKAGES; fi
env:
global:
- - FIELD=auto BIGNUM=auto SCALAR=auto ENDOMORPHISM=no BUILD=check EXTRAFLAGS=
+ - FIELD=auto BIGNUM=auto SCALAR=auto ENDOMORPHISM=no BUILD=check EXTRAFLAGS= HOST= EXTRAPACKAGES=
matrix:
- SCALAR=32bit
- SCALAR=64bit
@@ -22,6 +24,11 @@ env:
- BIGNUM=none ENDOMORPHISM=yes
- BUILD=distcheck
- EXTRAFLAGS=CFLAGS=-DDETERMINISTIC
+ - HOST=i686-linux-gnu EXTRAPACKAGES="gcc-multilib"
+ - HOST=i686-linux-gnu EXTRAPACKAGES="gcc-multilib" ENDOMORPHISM=yes
before_script: ./autogen.sh
-script: ./configure --enable-endomorphism=$ENDOMORPHISM --with-field=$FIELD --with-bignum=$BIGNUM --with-scalar=$SCALAR $EXTRAFLAGS && make -j2 $BUILD
+script:
+ - if [ -n "$HOST" ]; then export USE_HOST="--host=$HOST"; fi
+ - if [ "x$HOST" = "xi686-linux-gnu" ]; then export CC="$CC -m32"; fi
+ - ./configure --enable-endomorphism=$ENDOMORPHISM --with-field=$FIELD --with-bignum=$BIGNUM --with-scalar=$SCALAR $EXTRAFLAGS $USE_HOST && make -j2 $BUILD
os: linux
diff --git a/src/secp256k1/Makefile.am b/src/secp256k1/Makefile.am
index dbf1790f34..390d2c9ffa 100644
--- a/src/secp256k1/Makefile.am
+++ b/src/secp256k1/Makefile.am
@@ -1,12 +1,6 @@
ACLOCAL_AMFLAGS = -I build-aux/m4
lib_LTLIBRARIES = libsecp256k1.la
-if USE_ASM
-COMMON_LIB = libsecp256k1_common.la
-else
-COMMON_LIB =
-endif
-noinst_LTLIBRARIES = $(COMMON_LIB)
include_HEADERS = include/secp256k1.h
noinst_HEADERS =
noinst_HEADERS += src/scalar.h
@@ -43,30 +37,30 @@ noinst_HEADERS += src/field_gmp.h
noinst_HEADERS += src/field_gmp_impl.h
noinst_HEADERS += src/field.h
noinst_HEADERS += src/field_impl.h
+noinst_HEADERS += src/bench.h
pkgconfigdir = $(libdir)/pkgconfig
pkgconfig_DATA = libsecp256k1.pc
-if USE_ASM
-libsecp256k1_common_la_SOURCES = src/field_5x52_asm.asm
-endif
-
libsecp256k1_la_SOURCES = src/secp256k1.c
libsecp256k1_la_CPPFLAGS = -I$(top_srcdir)/include $(SECP_INCLUDES)
-libsecp256k1_la_LIBADD = $(COMMON_LIB) $(SECP_LIBS)
+libsecp256k1_la_LIBADD = $(SECP_LIBS)
noinst_PROGRAMS =
if USE_BENCHMARK
-noinst_PROGRAMS += bench_verify bench_sign bench_inv
+noinst_PROGRAMS += bench_verify bench_recover bench_sign bench_inv
bench_verify_SOURCES = src/bench_verify.c
bench_verify_LDADD = libsecp256k1.la $(SECP_LIBS)
bench_verify_LDFLAGS = -static
+bench_recover_SOURCES = src/bench_recover.c
+bench_recover_LDADD = libsecp256k1.la $(SECP_LIBS)
+bench_recover_LDFLAGS = -static
bench_sign_SOURCES = src/bench_sign.c
bench_sign_LDADD = libsecp256k1.la $(SECP_LIBS)
bench_sign_LDFLAGS = -static
bench_inv_SOURCES = src/bench_inv.c
-bench_inv_LDADD = $(COMMON_LIB) $(SECP_LIBS)
+bench_inv_LDADD = $(SECP_LIBS)
bench_inv_LDFLAGS = -static
bench_inv_CPPFLAGS = $(SECP_INCLUDES)
endif
@@ -75,15 +69,9 @@ if USE_TESTS
noinst_PROGRAMS += tests
tests_SOURCES = src/tests.c
tests_CPPFLAGS = -DVERIFY $(SECP_INCLUDES) $(SECP_TEST_INCLUDES)
-tests_LDADD = $(COMMON_LIB) $(SECP_LIBS) $(SECP_TEST_LIBS)
+tests_LDADD = $(SECP_LIBS) $(SECP_TEST_LIBS)
tests_LDFLAGS = -static
TESTS = tests
endif
-EXTRA_DIST = autogen.sh nasm_lt.sh
-
-#x86_64 only
-if USE_ASM
-.asm.lo:
- $(LIBTOOL) --mode=compile --tag YASM $(srcdir)/nasm_lt.sh $(YASM) -f $(YASM_BINFMT) $(YAFLAGS) -I$(srcdir) -I. $< -o $@
-endif
+EXTRA_DIST = autogen.sh
diff --git a/src/secp256k1/build-aux/m4/bitcoin_secp.m4 b/src/secp256k1/build-aux/m4/bitcoin_secp.m4
index 4ca28f99cf..1373478c9c 100644
--- a/src/secp256k1/build-aux/m4/bitcoin_secp.m4
+++ b/src/secp256k1/build-aux/m4/bitcoin_secp.m4
@@ -11,38 +11,16 @@ fi
dnl
AC_DEFUN([SECP_64BIT_ASM_CHECK],[
-if test x"$host_cpu" == x"x86_64"; then
- AC_CHECK_PROG(YASM, yasm, yasm)
-else
- if test x"$set_field" = x"64bit_asm"; then
- AC_MSG_ERROR([$set_field field support explicitly requested but is not compatible with this host])
- fi
-fi
-if test x$YASM = x; then
- if test x"$set_field" = x"64bit_asm"; then
- AC_MSG_ERROR([$set_field field support explicitly requested but yasm was not found])
- fi
- has_64bit_asm=no
-else
- case x"$host_os" in
- xdarwin*)
- YASM_BINFMT=macho64
- ;;
- x*-gnux32)
- YASM_BINFMT=elfx32
- ;;
- *)
- YASM_BINFMT=elf64
- ;;
- esac
- if $YASM -f help | grep -q $YASM_BINFMT; then
- has_64bit_asm=yes
- else
- if test x"$set_field" = x"64bit_asm"; then
- AC_MSG_ERROR([$set_field field support explicitly requested but yasm doesn't support $YASM_BINFMT format])
- fi
- AC_MSG_WARN([yasm too old for $YASM_BINFMT format])
- has_64bit_asm=no
+AC_MSG_CHECKING(for x86_64 assembly availability)
+AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[
+ #include <stdint.h>]],[[
+ uint64_t a = 11, tmp;
+ __asm__ __volatile__("movq $0x100000000,%1; mulq %%rsi" : "+a"(a) : "S"(tmp) : "cc", "%rdx");
+ ]])],[has_64bit_asm=yes],[has_64bit_asm=no])
+AC_MSG_RESULT([$has_64bit_asm])
+if test x"$set_field" == x"64bit_asm"; then
+ if test x"$has_64bit_asm" == x"no"; then
+ AC_MSG_ERROR([$set_field field support explicitly requested but no x86_64 assembly available])
fi
fi
])
@@ -52,8 +30,13 @@ AC_DEFUN([SECP_OPENSSL_CHECK],[
if test x"$use_pkgconfig" = x"yes"; then
: #NOP
m4_ifdef([PKG_CHECK_MODULES],[
- PKG_CHECK_MODULES([CRYPTO], [libcrypto], [has_libcrypto=yes; AC_DEFINE(HAVE_LIBCRYPTO,1,[Define this symbol if libcrypto is installed])],[has_libcrypto=no])
- : #NOP
+ PKG_CHECK_MODULES([CRYPTO], [libcrypto], [has_libcrypto=yes],[has_libcrypto=no])
+ if test x"$has_libcrypto" = x"yes"; then
+ TEMP_LIBS="$LIBS"
+ LIBS="$LIBS $CRYPTO_LIBS"
+ AC_CHECK_LIB(crypto, main,[AC_DEFINE(HAVE_LIBCRYPTO,1,[Define this symbol if libcrypto is installed])],[has_libcrypto=no])
+ LIBS="$TEMP_LIBS"
+ fi
])
else
AC_CHECK_HEADER(openssl/crypto.h,[AC_CHECK_LIB(crypto, main,[has_libcrypto=yes; CRYPTO_LIBS=-lcrypto; AC_DEFINE(HAVE_LIBCRYPTO,1,[Define this symbol if libcrypto is installed])]
diff --git a/src/secp256k1/configure.ac b/src/secp256k1/configure.ac
index 6e6fccd7fd..40e121e806 100644
--- a/src/secp256k1/configure.ac
+++ b/src/secp256k1/configure.ac
@@ -18,6 +18,10 @@ AC_PATH_TOOL(AR, ar)
AC_PATH_TOOL(RANLIB, ranlib)
AC_PATH_TOOL(STRIP, strip)
+if test "x$CFLAGS" = "x"; then
+ CFLAGS="-O3 -g"
+fi
+
AC_PROG_CC_C99
if test x"$ac_cv_prog_cc_c99" == x"no"; then
AC_MSG_ERROR([c99 compiler support required])
@@ -103,7 +107,11 @@ AC_ARG_WITH([scalar], [AS_HELP_STRING([--with-scalar=64bit|32bit|auto],
AC_CHECK_TYPES([__int128])
-AC_CHECK_DECL(__builtin_expect,AC_DEFINE(HAVE_BUILTIN_EXPECT,1,[Define this symbol if __builtin_expect is available]),,)
+AC_MSG_CHECKING([for __builtin_expect])
+AC_COMPILE_IFELSE([AC_LANG_SOURCE([[void myfunc() {__builtin_expect(0,0);}]])],
+ [ AC_MSG_RESULT([yes]);AC_DEFINE(HAVE_BUILTIN_EXPECT,1,[Define this symbol if __builtin_expect is available]) ],
+ [ AC_MSG_RESULT([no])
+ ])
if test x"$req_field" = x"auto"; then
SECP_64BIT_ASM_CHECK
@@ -283,7 +291,6 @@ AC_SUBST(SECP_INCLUDES)
AC_SUBST(SECP_LIBS)
AC_SUBST(SECP_TEST_LIBS)
AC_SUBST(SECP_TEST_INCLUDES)
-AC_SUBST(YASM_BINFMT)
AM_CONDITIONAL([USE_ASM], [test x"$set_field" == x"64bit_asm"])
AM_CONDITIONAL([USE_TESTS], [test x"$use_tests" != x"no"])
AM_CONDITIONAL([USE_BENCHMARK], [test x"$use_benchmark" != x"no"])
diff --git a/src/secp256k1/include/secp256k1.h b/src/secp256k1/include/secp256k1.h
index 94a6ef483f..dca7ca00e7 100644
--- a/src/secp256k1/include/secp256k1.h
+++ b/src/secp256k1/include/secp256k1.h
@@ -62,8 +62,7 @@ void secp256k1_stop(void);
* 0: incorrect signature
* -1: invalid public key
* -2: invalid signature
- * In: msg: the message being verified (cannot be NULL)
- * msglen: the length of the message (at most 32)
+ * In: msg32: the 32-byte message hash being verified (cannot be NULL)
* sig: the signature being verified (cannot be NULL)
* siglen: the length of the signature
* pubkey: the public key to verify with (cannot be NULL)
@@ -71,19 +70,17 @@ void secp256k1_stop(void);
* Requires starting using SECP256K1_START_VERIFY.
*/
SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_verify(
- const unsigned char *msg,
- int msglen,
+ const unsigned char *msg32,
const unsigned char *sig,
int siglen,
const unsigned char *pubkey,
int pubkeylen
-) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(5);
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(4);
/** Create an ECDSA signature.
* Returns: 1: signature created
* 0: nonce invalid, try another one
- * In: msg: the message being signed (cannot be NULL)
- * msglen: the length of the message being signed (at most 32)
+ * In: msg32: the 32-byte message hash being signed (cannot be NULL)
* seckey: pointer to a 32-byte secret key (cannot be NULL, assumed to be valid)
* nonce: pointer to a 32-byte nonce (cannot be NULL, generated with a cryptographic PRNG)
* Out: sig: pointer to an array where the signature will be placed (cannot be NULL)
@@ -92,19 +89,17 @@ SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_verify(
* Requires starting using SECP256K1_START_SIGN.
*/
SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_sign(
- const unsigned char *msg,
- int msglen,
+ const unsigned char *msg32,
unsigned char *sig,
int *siglen,
const unsigned char *seckey,
const unsigned char *nonce
-) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5) SECP256K1_ARG_NONNULL(6);
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
/** Create a compact ECDSA signature (64 byte + recovery id).
* Returns: 1: signature created
* 0: nonce invalid, try another one
- * In: msg: the message being signed (cannot be NULL)
- * msglen: the length of the message being signed (at most 32)
+ * In: msg32: the 32-byte message hash being signed (cannot be NULL)
* seckey: pointer to a 32-byte secret key (cannot be NULL, assumed to be valid)
* nonce: pointer to a 32-byte nonce (cannot be NULL, generated with a cryptographic PRNG)
* Out: sig: pointer to a 64-byte array where the signature will be placed (cannot be NULL)
@@ -112,19 +107,17 @@ SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_sign(
* Requires starting using SECP256K1_START_SIGN.
*/
SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_sign_compact(
- const unsigned char *msg,
- int msglen,
+ const unsigned char *msg32,
unsigned char *sig64,
const unsigned char *seckey,
const unsigned char *nonce,
int *recid
-) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
/** Recover an ECDSA public key from a compact signature.
* Returns: 1: public key successfully recovered (which guarantees a correct signature).
* 0: otherwise.
- * In: msg: the message assumed to be signed (cannot be NULL)
- * msglen: the length of the message (at most 32)
+ * In: msg32: the 32-byte message hash assumed to be signed (cannot be NULL)
* sig64: signature as 64 byte array (cannot be NULL)
* compressed: whether to recover a compressed or uncompressed pubkey
* recid: the recovery id (0-3, as returned by ecdsa_sign_compact)
@@ -133,14 +126,13 @@ SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_sign_compact(
* Requires starting using SECP256K1_START_VERIFY.
*/
SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_recover_compact(
- const unsigned char *msg,
- int msglen,
+ const unsigned char *msg32,
const unsigned char *sig64,
unsigned char *pubkey,
int *pubkeylen,
int compressed,
int recid
-) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
/** Verify an ECDSA secret key.
* Returns: 1: secret key is valid
diff --git a/src/secp256k1/nasm_lt.sh b/src/secp256k1/nasm_lt.sh
deleted file mode 100755
index 6cd73294c0..0000000000
--- a/src/secp256k1/nasm_lt.sh
+++ /dev/null
@@ -1,57 +0,0 @@
-#! /bin/sh
-command=""
-infile=""
-o_opt=no
-pic=no
-while [ $# -gt 0 ]; do
- case "$1" in
- -DPIC|-fPIC|-fpic|-Kpic|-KPIC)
- if [ "$pic" != "yes" ] ; then
- command="$command -DPIC"
- pic=yes
- fi
- ;;
- -f|-fbin|-faout|-faoutb|-fcoff|-felf|-felf64|-fas86| \
- -fobj|-fwin32|-fwin64|-frdf|-fieee|-fmacho|-fmacho64)
- # it's a file format specifier for nasm.
- command="$command $1"
- ;;
- -f*)
- # maybe a code-generation flag for gcc.
- ;;
- -[Ii]*)
- incdir=`echo "$1" | sed 's/^-[Ii]//'`
- if [ "x$incdir" = x -a "x$2" != x ] ; then
- case "$2" in
- -*) ;;
- *) incdir="$2"; shift;;
- esac
- fi
- if [ "x$incdir" != x ] ; then
- # In the case of NASM, the trailing slash is necessary.
- incdir=`echo "$incdir" | sed 's%/*$%/%'`
- command="$command -I$incdir"
- fi
- ;;
- -o*)
- o_opt=yes
- command="$command $1"
- ;;
- *.asm)
- infile=$1
- command="$command $1"
- ;;
- *)
- command="$command $1"
- ;;
- esac
- shift
-done
-if [ "$o_opt" != yes ] ; then
- # By default, NASM creates an output file
- # in the same directory as the input file.
- outfile="-o `echo $infile | sed -e 's%^.*/%%' -e 's%\.[^.]*$%%'`.o"
- command="$command $outfile"
-fi
-echo $command
-exec $command
diff --git a/src/secp256k1/src/bench.h b/src/secp256k1/src/bench.h
new file mode 100644
index 0000000000..668ec39f71
--- /dev/null
+++ b/src/secp256k1/src/bench.h
@@ -0,0 +1,37 @@
+/**********************************************************************
+ * Copyright (c) 2014 Pieter Wuille *
+ * Distributed under the MIT software license, see the accompanying *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#ifndef _SECP256K1_BENCH_H_
+#define _SECP256K1_BENCH_H_
+
+#include <stdio.h>
+#include <math.h>
+#include "sys/time.h"
+
+static double gettimedouble(void) {
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ return tv.tv_usec * 0.000001 + tv.tv_sec;
+}
+
+void run_benchmark(void (*benchmark)(void*), void (*setup)(void*), void (*teardown)(void*), void* data, int count, int iter) {
+ double min = HUGE_VAL;
+ double sum = 0.0;
+ double max = 0.0;
+ for (int i = 0; i < count; i++) {
+ if (setup) setup(data);
+ double begin = gettimedouble();
+ benchmark(data);
+ double total = gettimedouble() - begin;
+ if (teardown) teardown(data);
+ if (total < min) min = total;
+ if (total > max) max = total;
+ sum += total;
+ }
+ printf("min %.3fus / avg %.3fus / max %.3fus\n", min * 1000000.0 / iter, (sum / count) * 1000000.0 / iter, max * 1000000.0 / iter);
+}
+
+#endif
diff --git a/src/secp256k1/src/bench_inv.c b/src/secp256k1/src/bench_inv.c
index d6f664333f..3bdedea30e 100644
--- a/src/secp256k1/src/bench_inv.c
+++ b/src/secp256k1/src/bench_inv.c
@@ -12,30 +12,41 @@
#include "field_impl.h"
#include "group_impl.h"
#include "scalar_impl.h"
+#include "bench.h"
+
+typedef struct {
+ secp256k1_scalar_t base, x;
+} bench_inv_t;
+
+void bench_inv_setup(void* arg) {
+ bench_inv_t *data = (bench_inv_t*)arg;
-int main(void) {
static const unsigned char init[32] = {
0x02, 0x03, 0x05, 0x07, 0x0b, 0x0d, 0x11, 0x13,
0x17, 0x1d, 0x1f, 0x25, 0x29, 0x2b, 0x2f, 0x35,
0x3b, 0x3d, 0x43, 0x47, 0x49, 0x4f, 0x53, 0x59,
0x61, 0x65, 0x67, 0x6b, 0x6d, 0x71, 0x7f, 0x83
};
- static const unsigned char fini[32] = {
- 0xba, 0x28, 0x58, 0xd8, 0xaa, 0x11, 0xd6, 0xf2,
- 0xfa, 0xce, 0x50, 0xb1, 0x67, 0x19, 0xb1, 0xa6,
- 0xe0, 0xaa, 0x84, 0x53, 0xf6, 0x80, 0xfc, 0x23,
- 0x88, 0x3c, 0xd6, 0x74, 0x9f, 0x27, 0x09, 0x03
- };
- secp256k1_ge_start();
- secp256k1_scalar_t base, x;
- secp256k1_scalar_set_b32(&base, init, NULL);
- secp256k1_scalar_set_b32(&x, init, NULL);
- for (int i=0; i<1000000; i++) {
- secp256k1_scalar_inverse(&x, &x);
- secp256k1_scalar_add(&x, &x, &base);
+
+ secp256k1_scalar_set_b32(&data->base, init, NULL);
+ secp256k1_scalar_set_b32(&data->x, init, NULL);
+}
+
+void bench_inv(void* arg) {
+ bench_inv_t *data = (bench_inv_t*)arg;
+
+ for (int i=0; i<20000; i++) {
+ secp256k1_scalar_inverse(&data->x, &data->x);
+ secp256k1_scalar_add(&data->x, &data->x, &data->base);
}
- unsigned char res[32];
- secp256k1_scalar_get_b32(res, &x);
- CHECK(memcmp(res, fini, 32) == 0);
+}
+
+int main(void) {
+ secp256k1_ge_start();
+
+ bench_inv_t data;
+ run_benchmark(bench_inv, bench_inv_setup, NULL, &data, 10, 20000);
+
+ secp256k1_ge_stop();
return 0;
}
diff --git a/src/secp256k1/src/bench_recover.c b/src/secp256k1/src/bench_recover.c
new file mode 100644
index 0000000000..b1e0f33efa
--- /dev/null
+++ b/src/secp256k1/src/bench_recover.c
@@ -0,0 +1,46 @@
+/**********************************************************************
+ * Copyright (c) 2014 Pieter Wuille *
+ * Distributed under the MIT software license, see the accompanying *
+ * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
+ **********************************************************************/
+
+#include "include/secp256k1.h"
+#include "util.h"
+#include "bench.h"
+
+typedef struct {
+ unsigned char msg[32];
+ unsigned char sig[64];
+} bench_recover_t;
+
+void bench_recover(void* arg) {
+ bench_recover_t *data = (bench_recover_t*)arg;
+
+ unsigned char pubkey[33];
+ for (int i=0; i<20000; i++) {
+ int pubkeylen = 33;
+ CHECK(secp256k1_ecdsa_recover_compact(data->msg, data->sig, pubkey, &pubkeylen, 1, i % 2));
+ for (int j = 0; j < 32; j++) {
+ data->sig[j + 32] = data->msg[j]; /* Move former message to S. */
+ data->msg[j] = data->sig[j]; /* Move former R to message. */
+ data->sig[j] = pubkey[j + 1]; /* Move recovered pubkey X coordinate to R (which must be a valid X coordinate). */
+ }
+ }
+}
+
+void bench_recover_setup(void* arg) {
+ bench_recover_t *data = (bench_recover_t*)arg;
+
+ for (int i = 0; i < 32; i++) data->msg[i] = 1 + i;
+ for (int i = 0; i < 64; i++) data->sig[i] = 65 + i;
+}
+
+int main(void) {
+ secp256k1_start(SECP256K1_START_VERIFY);
+
+ bench_recover_t data;
+ run_benchmark(bench_recover, bench_recover_setup, NULL, &data, 10, 20000);
+
+ secp256k1_stop();
+ return 0;
+}
diff --git a/src/secp256k1/src/bench_sign.c b/src/secp256k1/src/bench_sign.c
index f01f11d689..66e71e1ac4 100644
--- a/src/secp256k1/src/bench_sign.c
+++ b/src/secp256k1/src/bench_sign.c
@@ -3,46 +3,45 @@
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
-#include <stdio.h>
-#include <string.h>
#include "include/secp256k1.h"
#include "util.h"
+#include "bench.h"
-int main(void) {
- secp256k1_start(SECP256K1_START_SIGN);
-
+typedef struct {
unsigned char msg[32];
unsigned char nonce[32];
unsigned char key[32];
+} bench_sign_t;
- for (int i = 0; i < 32; i++) msg[i] = i + 1;
- for (int i = 0; i < 32; i++) nonce[i] = i + 33;
- for (int i = 0; i < 32; i++) key[i] = i + 65;
+static void bench_sign_setup(void* arg) {
+ bench_sign_t *data = (bench_sign_t*)arg;
- unsigned char sig[64];
+ for (int i = 0; i < 32; i++) data->msg[i] = i + 1;
+ for (int i = 0; i < 32; i++) data->nonce[i] = i + 33;
+ for (int i = 0; i < 32; i++) data->key[i] = i + 65;
+}
+
+static void bench_sign(void* arg) {
+ bench_sign_t *data = (bench_sign_t*)arg;
- for (int i=0; i<1000000; i++) {
+ unsigned char sig[64];
+ for (int i=0; i<20000; i++) {
int recid = 0;
- CHECK(secp256k1_ecdsa_sign_compact(msg, 32, sig, key, nonce, &recid));
+ CHECK(secp256k1_ecdsa_sign_compact(data->msg, sig, data->key, data->nonce, &recid));
for (int j = 0; j < 32; j++) {
- nonce[j] = key[j]; /* Move former key to nonce */
- msg[j] = sig[j]; /* Move former R to message. */
- key[j] = sig[j + 32]; /* Move former S to key. */
+ data->nonce[j] = data->key[j]; /* Move former key to nonce */
+ data->msg[j] = sig[j]; /* Move former R to message. */
+ data->key[j] = sig[j + 32]; /* Move former S to key. */
}
}
+}
+
+int main(void) {
+ secp256k1_start(SECP256K1_START_SIGN);
- static const unsigned char fini[64] = {
- 0x92, 0x03, 0xef, 0xf1, 0x58, 0x0b, 0x49, 0x8d,
- 0x22, 0x3d, 0x49, 0x0e, 0xbf, 0x26, 0x50, 0x0e,
- 0x2d, 0x62, 0x90, 0xd7, 0x82, 0xbd, 0x3d, 0x5c,
- 0xa9, 0x10, 0xa5, 0x49, 0xb1, 0xd8, 0x8c, 0xc0,
- 0x5b, 0x5e, 0x9e, 0x68, 0x51, 0x3d, 0xe8, 0xec,
- 0x82, 0x30, 0x82, 0x88, 0x8c, 0xfd, 0xe7, 0x71,
- 0x15, 0x92, 0xfc, 0x14, 0x59, 0x78, 0x31, 0xb3,
- 0xf6, 0x07, 0x91, 0x18, 0x00, 0x8d, 0x4c, 0xb2
- };
- CHECK(memcmp(sig, fini, 64) == 0);
+ bench_sign_t data;
+ run_benchmark(bench_sign, bench_sign_setup, NULL, &data, 10, 20000);
secp256k1_stop();
return 0;
diff --git a/src/secp256k1/src/bench_verify.c b/src/secp256k1/src/bench_verify.c
index 690595516d..b123c4087d 100644
--- a/src/secp256k1/src/bench_verify.c
+++ b/src/secp256k1/src/bench_verify.c
@@ -9,35 +9,46 @@
#include "include/secp256k1.h"
#include "util.h"
+#include "bench.h"
-int main(void) {
- secp256k1_start(SECP256K1_START_VERIFY);
-
+typedef struct {
unsigned char msg[32];
- unsigned char sig[64];
-
- for (int i = 0; i < 32; i++) msg[i] = 1 + i;
- for (int i = 0; i < 64; i++) sig[i] = 65 + i;
-
+ unsigned char key[32];
+ unsigned char nonce[32];
+ unsigned char sig[72];
+ int siglen;
unsigned char pubkey[33];
- for (int i=0; i<1000000; i++) {
- int pubkeylen = 33;
- CHECK(secp256k1_ecdsa_recover_compact(msg, 32, sig, pubkey, &pubkeylen, 1, i % 2));
- for (int j = 0; j < 32; j++) {
- sig[j + 32] = msg[j]; /* Move former message to S. */
- msg[j] = sig[j]; /* Move former R to message. */
- sig[j] = pubkey[j + 1]; /* Move recovered pubkey X coordinate to R (which must be a valid X coordinate). */
- }
+ int pubkeylen;
+} benchmark_verify_t;
+
+static void benchmark_verify(void* arg) {
+ benchmark_verify_t* data = (benchmark_verify_t*)arg;
+
+ for (int i=0; i<20000; i++) {
+ data->sig[data->siglen - 1] ^= (i & 0xFF);
+ data->sig[data->siglen - 2] ^= ((i >> 8) & 0xFF);
+ data->sig[data->siglen - 3] ^= ((i >> 16) & 0xFF);
+ CHECK(secp256k1_ecdsa_verify(data->msg, data->sig, data->siglen, data->pubkey, data->pubkeylen) == (i == 0));
+ data->sig[data->siglen - 1] ^= (i & 0xFF);
+ data->sig[data->siglen - 2] ^= ((i >> 8) & 0xFF);
+ data->sig[data->siglen - 3] ^= ((i >> 16) & 0xFF);
}
+}
+
+int main(void) {
+ secp256k1_start(SECP256K1_START_VERIFY | SECP256K1_START_SIGN);
+
+ benchmark_verify_t data;
+
+ for (int i = 0; i < 32; i++) data.msg[i] = 1 + i;
+ for (int i = 0; i < 32; i++) data.key[i] = 33 + i;
+ for (int i = 0; i < 32; i++) data.nonce[i] = 65 + i;
+ data.siglen = 72;
+ CHECK(secp256k1_ecdsa_sign(data.msg, data.sig, &data.siglen, data.key, data.nonce));
+ data.pubkeylen = 33;
+ CHECK(secp256k1_ec_pubkey_create(data.pubkey, &data.pubkeylen, data.key, 1));
- static const unsigned char fini[33] = {
- 0x02,
- 0x52, 0x63, 0xae, 0x9a, 0x9d, 0x47, 0x1f, 0x1a,
- 0xb2, 0x36, 0x65, 0x89, 0x11, 0xe7, 0xcc, 0x86,
- 0xa3, 0xab, 0x97, 0xb6, 0xf1, 0xaf, 0xfd, 0x8f,
- 0x9b, 0x38, 0xb6, 0x18, 0x55, 0xe5, 0xc2, 0x43
- };
- CHECK(memcmp(fini, pubkey, 33) == 0);
+ run_benchmark(benchmark_verify, NULL, NULL, &data, 10, 20000);
secp256k1_stop();
return 0;
diff --git a/src/secp256k1/src/ecdsa_impl.h b/src/secp256k1/src/ecdsa_impl.h
index a951d0b4ad..8825d05fed 100644
--- a/src/secp256k1/src/ecdsa_impl.h
+++ b/src/secp256k1/src/ecdsa_impl.h
@@ -27,7 +27,7 @@ static void secp256k1_ecdsa_start(void) {
return;
/* Allocate. */
- secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)malloc(sizeof(secp256k1_ecdsa_consts_t));
+ secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));
static const unsigned char order[] = {
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
@@ -38,7 +38,7 @@ static void secp256k1_ecdsa_start(void) {
secp256k1_fe_set_b32(&ret->order_as_fe, order);
secp256k1_fe_negate(&ret->p_minus_order, &ret->order_as_fe, 1);
- secp256k1_fe_normalize(&ret->p_minus_order);
+ secp256k1_fe_normalize_var(&ret->p_minus_order);
/* Set the global pointer. */
secp256k1_ecdsa_consts = ret;
@@ -122,7 +122,7 @@ static int secp256k1_ecdsa_sig_recompute(secp256k1_scalar_t *r2, const secp256k1
secp256k1_gej_t pr; secp256k1_ecmult(&pr, &pubkeyj, &u2, &u1);
if (!secp256k1_gej_is_infinity(&pr)) {
secp256k1_fe_t xr; secp256k1_gej_get_x_var(&xr, &pr);
- secp256k1_fe_normalize(&xr);
+ secp256k1_fe_normalize_var(&xr);
unsigned char xrb[32]; secp256k1_fe_get_b32(xrb, &xr);
secp256k1_scalar_set_b32(r2, xrb, NULL);
ret = 1;
@@ -144,7 +144,7 @@ static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256
secp256k1_fe_add(&fx, &secp256k1_ecdsa_consts->order_as_fe);
}
secp256k1_ge_t x;
- if (!secp256k1_ge_set_xo(&x, &fx, recid & 1))
+ if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1))
return 0;
secp256k1_gej_t xj;
secp256k1_gej_set_ge(&xj, &x);
diff --git a/src/secp256k1/src/eckey_impl.h b/src/secp256k1/src/eckey_impl.h
index 0f218ced9e..b3fa7d9bd2 100644
--- a/src/secp256k1/src/eckey_impl.h
+++ b/src/secp256k1/src/eckey_impl.h
@@ -17,7 +17,7 @@
static int secp256k1_eckey_pubkey_parse(secp256k1_ge_t *elem, const unsigned char *pub, int size) {
if (size == 33 && (pub[0] == 0x02 || pub[0] == 0x03)) {
secp256k1_fe_t x;
- return secp256k1_fe_set_b32(&x, pub+1) && secp256k1_ge_set_xo(elem, &x, pub[0] == 0x03);
+ return secp256k1_fe_set_b32(&x, pub+1) && secp256k1_ge_set_xo_var(elem, &x, pub[0] == 0x03);
} else if (size == 65 && (pub[0] == 0x04 || pub[0] == 0x06 || pub[0] == 0x07)) {
secp256k1_fe_t x, y;
if (!secp256k1_fe_set_b32(&x, pub+1) || !secp256k1_fe_set_b32(&y, pub+33)) {
@@ -26,7 +26,7 @@ static int secp256k1_eckey_pubkey_parse(secp256k1_ge_t *elem, const unsigned cha
secp256k1_ge_set_xy(elem, &x, &y);
if ((pub[0] == 0x06 || pub[0] == 0x07) && secp256k1_fe_is_odd(&y) != (pub[0] == 0x07))
return 0;
- return secp256k1_ge_is_valid(elem);
+ return secp256k1_ge_is_valid_var(elem);
} else {
return 0;
}
@@ -36,8 +36,8 @@ static int secp256k1_eckey_pubkey_serialize(secp256k1_ge_t *elem, unsigned char
if (secp256k1_ge_is_infinity(elem)) {
return 0;
}
- secp256k1_fe_normalize(&elem->x);
- secp256k1_fe_normalize(&elem->y);
+ secp256k1_fe_normalize_var(&elem->x);
+ secp256k1_fe_normalize_var(&elem->y);
secp256k1_fe_get_b32(&pub[1], &elem->x);
if (compressed) {
*size = 33;
diff --git a/src/secp256k1/src/ecmult_gen_impl.h b/src/secp256k1/src/ecmult_gen_impl.h
index af0ead522d..5a5b16ce14 100644
--- a/src/secp256k1/src/ecmult_gen_impl.h
+++ b/src/secp256k1/src/ecmult_gen_impl.h
@@ -34,7 +34,7 @@ static void secp256k1_ecmult_gen_start(void) {
return;
/* Allocate the precomputation table. */
- secp256k1_ecmult_gen_consts_t *ret = (secp256k1_ecmult_gen_consts_t*)malloc(sizeof(secp256k1_ecmult_gen_consts_t));
+ secp256k1_ecmult_gen_consts_t *ret = (secp256k1_ecmult_gen_consts_t*)checked_malloc(sizeof(secp256k1_ecmult_gen_consts_t));
/* get the generator */
const secp256k1_ge_t *g = &secp256k1_ge_consts->g;
@@ -47,7 +47,7 @@ static void secp256k1_ecmult_gen_start(void) {
secp256k1_fe_t nums_x;
VERIFY_CHECK(secp256k1_fe_set_b32(&nums_x, nums_b32));
secp256k1_ge_t nums_ge;
- VERIFY_CHECK(secp256k1_ge_set_xo(&nums_ge, &nums_x, 0));
+ VERIFY_CHECK(secp256k1_ge_set_xo_var(&nums_ge, &nums_x, 0));
secp256k1_gej_set_ge(&nums_gej, &nums_ge);
/* Add G to make the bits in x uniformly distributed. */
secp256k1_gej_add_ge_var(&nums_gej, &nums_gej, g);
@@ -73,7 +73,7 @@ static void secp256k1_ecmult_gen_start(void) {
secp256k1_gej_double_var(&numsbase, &numsbase);
if (j == 62) {
/* In the last iteration, numsbase is (1 - 2^j) * nums instead. */
- secp256k1_gej_neg(&numsbase, &numsbase);
+ secp256k1_gej_neg_var(&numsbase, &numsbase);
secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej);
}
}
diff --git a/src/secp256k1/src/ecmult_impl.h b/src/secp256k1/src/ecmult_impl.h
index 445b81593f..6536771046 100644
--- a/src/secp256k1/src/ecmult_impl.h
+++ b/src/secp256k1/src/ecmult_impl.h
@@ -15,11 +15,13 @@
#define WINDOW_A 5
/** larger numbers may result in slightly better performance, at the cost of
- exponentially larger precomputed tables. WINDOW_G == 14 results in 640 KiB. */
+ exponentially larger precomputed tables. */
#ifdef USE_ENDOMORPHISM
-#define WINDOW_G 14
-#else
+/** Two tables for window size 15: 1.375 MiB. */
#define WINDOW_G 15
+#else
+/** One table for window size 16: 1.375 MiB. */
+#define WINDOW_G 16
#endif
/** Fill a table 'pre' with precomputed odd multiples of a. W determines the size of the table.
@@ -43,13 +45,14 @@ static void secp256k1_ecmult_table_precomp_gej_var(secp256k1_gej_t *pre, const s
static void secp256k1_ecmult_table_precomp_ge_var(secp256k1_ge_t *pre, const secp256k1_gej_t *a, int w) {
const int table_size = 1 << (w-2);
- secp256k1_gej_t prej[table_size];
+ secp256k1_gej_t *prej = checked_malloc(sizeof(secp256k1_gej_t) * table_size);
prej[0] = *a;
secp256k1_gej_t d; secp256k1_gej_double_var(&d, a);
for (int i=1; i<table_size; i++) {
secp256k1_gej_add_var(&prej[i], &d, &prej[i-1]);
}
secp256k1_ge_set_all_gej_var(table_size, pre, prej);
+ free(prej);
}
/** The number of entries a table with precomputed multiples needs to have. */
@@ -67,8 +70,8 @@ static void secp256k1_ecmult_table_precomp_ge_var(secp256k1_ge_t *pre, const sec
(neg)((r), &(pre)[(-(n)-1)/2]); \
} while(0)
-#define ECMULT_TABLE_GET_GEJ(r,pre,n,w) ECMULT_TABLE_GET((r),(pre),(n),(w),secp256k1_gej_neg)
-#define ECMULT_TABLE_GET_GE(r,pre,n,w) ECMULT_TABLE_GET((r),(pre),(n),(w),secp256k1_ge_neg)
+#define ECMULT_TABLE_GET_GEJ(r,pre,n,w) ECMULT_TABLE_GET((r),(pre),(n),(w),secp256k1_gej_neg_var)
+#define ECMULT_TABLE_GET_GE(r,pre,n,w) ECMULT_TABLE_GET((r),(pre),(n),(w),secp256k1_ge_neg_var)
typedef struct {
/* For accelerating the computation of a*P + b*G: */
@@ -85,7 +88,7 @@ static void secp256k1_ecmult_start(void) {
return;
/* Allocate the precomputation table. */
- secp256k1_ecmult_consts_t *ret = (secp256k1_ecmult_consts_t*)malloc(sizeof(secp256k1_ecmult_consts_t));
+ secp256k1_ecmult_consts_t *ret = (secp256k1_ecmult_consts_t*)checked_malloc(sizeof(secp256k1_ecmult_consts_t));
/* get the generator */
const secp256k1_ge_t *g = &secp256k1_ge_consts->g;
diff --git a/src/secp256k1/src/field.h b/src/secp256k1/src/field.h
index 0cdf0fb479..53aa29e13f 100644
--- a/src/secp256k1/src/field.h
+++ b/src/secp256k1/src/field.h
@@ -50,6 +50,9 @@ static void secp256k1_fe_stop(void);
/** Normalize a field element. */
static void secp256k1_fe_normalize(secp256k1_fe_t *r);
+/** Normalize a field element, without constant-time guarantee. */
+static void secp256k1_fe_normalize_var(secp256k1_fe_t *r);
+
/** Set a field element equal to a small integer. Resulting field element is normalized. */
static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a);
@@ -93,7 +96,7 @@ static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a);
/** Sets a field element to be the (modular) square root (if any exist) of another. Requires the
* input's magnitude to be at most 8. The output magnitude is 1 (but not guaranteed to be
* normalized). Return value indicates whether a square root was found. */
-static int secp256k1_fe_sqrt(secp256k1_fe_t *r, const secp256k1_fe_t *a);
+static int secp256k1_fe_sqrt_var(secp256k1_fe_t *r, const secp256k1_fe_t *a);
/** Sets a field element to be the (modular) inverse of another. Requires the input's magnitude to be
* at most 8. The output magnitude is 1 (but not guaranteed to be normalized). */
@@ -105,9 +108,6 @@ static void secp256k1_fe_inv_var(secp256k1_fe_t *r, const secp256k1_fe_t *a);
/** Calculate the (modular) inverses of a batch of field elements. Requires the inputs' magnitudes to be
* at most 8. The output magnitudes are 1 (but not guaranteed to be normalized). The inputs and
* outputs must not overlap in memory. */
-static void secp256k1_fe_inv_all(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]);
-
-/** Potentially faster version of secp256k1_fe_inv_all, without constant-time guarantee. */
static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]);
/** Convert a field element to a hexadecimal string. */
diff --git a/src/secp256k1/src/field_10x26_impl.h b/src/secp256k1/src/field_10x26_impl.h
index c4403fba22..d20229cda6 100644
--- a/src/secp256k1/src/field_10x26_impl.h
+++ b/src/secp256k1/src/field_10x26_impl.h
@@ -103,6 +103,62 @@ static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
#endif
}
+static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
+ uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
+ t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
+
+ /* Reduce t9 at the start so there will be at most a single carry from the first pass */
+ uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
+ uint32_t m;
+
+ /* The first pass ensures the magnitude is 1, ... */
+ t0 += x * 0x3D1UL; t1 += (x << 6);
+ t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
+ t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
+ t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; m = t2;
+ t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; m &= t3;
+ t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; m &= t4;
+ t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; m &= t5;
+ t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; m &= t6;
+ t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; m &= t7;
+ t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; m &= t8;
+
+ /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t9 >> 23 == 0);
+
+ /* At most a single final reduction is needed; check if the value is >= the field characteristic */
+ x = (t9 >> 22) | ((t9 == 0x03FFFFFUL) & (m == 0x3FFFFFFUL)
+ & ((t1 + 0x40UL + ((t0 + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
+
+ if (x) {
+ t0 += 0x3D1UL; t1 += (x << 6);
+ t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
+ t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
+ t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
+ t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
+ t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
+ t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
+ t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
+ t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
+ t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
+
+ /* If t9 didn't carry to bit 22 already, then it should have after any final reduction */
+ VERIFY_CHECK(t9 >> 22 == x);
+
+ /* Mask off the possible multiple of 2^256 from the final reduction */
+ t9 &= 0x03FFFFFUL;
+ }
+
+ r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
+ r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
+
+#ifdef VERIFY
+ r->magnitude = 1;
+ r->normalized = 1;
+ secp256k1_fe_verify(r);
+#endif
+}
+
SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a) {
r->n[0] = a;
r->n[1] = r->n[2] = r->n[3] = r->n[4] = r->n[5] = r->n[6] = r->n[7] = r->n[8] = r->n[9] = 0;
@@ -271,7 +327,7 @@ SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe_t *r, const secp256k1
#define VERIFY_BITS(x, n) do { } while(0)
#endif
-SECP256K1_INLINE static void secp256k1_fe_mul_inner(const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b, uint32_t *r) {
+SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint32_t *r, const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b) {
VERIFY_BITS(a[0], 30);
VERIFY_BITS(a[1], 30);
VERIFY_BITS(a[2], 30);
@@ -598,7 +654,7 @@ SECP256K1_INLINE static void secp256k1_fe_mul_inner(const uint32_t *a, const uin
/* [r9 r8 r7 r6 r5 r4 r3 r2 r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
}
-SECP256K1_INLINE static void secp256k1_fe_sqr_inner(const uint32_t *a, uint32_t *r) {
+SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint32_t *r, const uint32_t *a) {
VERIFY_BITS(a[0], 30);
VERIFY_BITS(a[1], 30);
VERIFY_BITS(a[2], 30);
@@ -879,7 +935,7 @@ static void secp256k1_fe_mul(secp256k1_fe_t *r, const secp256k1_fe_t *a, const s
secp256k1_fe_verify(b);
VERIFY_CHECK(r != b);
#endif
- secp256k1_fe_mul_inner(a->n, b->n, r->n);
+ secp256k1_fe_mul_inner(r->n, a->n, b->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
@@ -892,7 +948,7 @@ static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
VERIFY_CHECK(a->magnitude <= 8);
secp256k1_fe_verify(a);
#endif
- secp256k1_fe_sqr_inner(a->n, r->n);
+ secp256k1_fe_sqr_inner(r->n, a->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
diff --git a/src/secp256k1/src/field_5x52_asm.asm b/src/secp256k1/src/field_5x52_asm.asm
deleted file mode 100644
index 5e785f7630..0000000000
--- a/src/secp256k1/src/field_5x52_asm.asm
+++ /dev/null
@@ -1,469 +0,0 @@
- ;; Added by Diederik Huys, March 2013
- ;;
- ;; Provided public procedures:
- ;; secp256k1_fe_mul_inner
- ;; secp256k1_fe_sqr_inner
- ;;
- ;; Needed tools: YASM (http://yasm.tortall.net)
- ;;
- ;;
-
- BITS 64
-
-%ifidn __OUTPUT_FORMAT__,macho64
-%define SYM(x) _ %+ x
-%else
-%define SYM(x) x
-%endif
-
- ;; Procedure ExSetMult
- ;; Register Layout:
- ;; INPUT: rdi = a->n
- ;; rsi = b->n
- ;; rdx = r->a
- ;;
- ;; INTERNAL: rdx:rax = multiplication accumulator
- ;; r9:r8 = c
- ;; r10-r13 = t0-t3
- ;; r14 = b.n[0] / t4
- ;; r15 = b.n[1] / t5
- ;; rbx = b.n[2] / t6
- ;; rcx = b.n[3] / t7
- ;; rbp = Constant 0FFFFFFFFFFFFFh / t8
- ;; rsi = b.n / b.n[4] / t9
-
- GLOBAL SYM(secp256k1_fe_mul_inner)
- ALIGN 32
-SYM(secp256k1_fe_mul_inner):
- push rbp
- push rbx
- push r12
- push r13
- push r14
- push r15
- push rdx
- mov r14,[rsi+8*0] ; preload b.n[0]. This will be the case until
- ; b.n[0] is no longer needed, then we reassign
- ; r14 to t4
- ;; c=a.n[0] * b.n[0]
- mov rax,[rdi+0*8] ; load a.n[0]
- mov rbp,0FFFFFFFFFFFFFh
- mul r14 ; rdx:rax=a.n[0]*b.n[0]
- mov r15,[rsi+1*8]
- mov r10,rbp ; load modulus into target register for t0
- mov r8,rax
- and r10,rax ; only need lower qword of c
- shrd r8,rdx,52
- xor r9,r9 ; c < 2^64, so we ditch the HO part
-
- ;; c+=a.n[0] * b.n[1] + a.n[1] * b.n[0]
- mov rax,[rdi+0*8]
- mul r15
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+1*8]
- mul r14
- mov r11,rbp
- mov rbx,[rsi+2*8]
- add r8,rax
- adc r9,rdx
- and r11,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=a.n[0 1 2] * b.n[2 1 0]
- mov rax,[rdi+0*8]
- mul rbx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+1*8]
- mul r15
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+2*8]
- mul r14
- mov r12,rbp
- mov rcx,[rsi+3*8]
- add r8,rax
- adc r9,rdx
- and r12,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=a.n[0 1 2 3] * b.n[3 2 1 0]
- mov rax,[rdi+0*8]
- mul rcx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+1*8]
- mul rbx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+2*8]
- mul r15
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+3*8]
- mul r14
- mov r13,rbp
- mov rsi,[rsi+4*8] ; load b.n[4] and destroy pointer
- add r8,rax
- adc r9,rdx
- and r13,r8
-
- shrd r8,r9,52
- xor r9,r9
-
-
- ;; c+=a.n[0 1 2 3 4] * b.n[4 3 2 1 0]
- mov rax,[rdi+0*8]
- mul rsi
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+1*8]
- mul rcx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+2*8]
- mul rbx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+3*8]
- mul r15
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+4*8]
- mul r14
- mov r14,rbp ; load modulus into t4 and destroy a.n[0]
- add r8,rax
- adc r9,rdx
- and r14,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=a.n[1 2 3 4] * b.n[4 3 2 1]
- mov rax,[rdi+1*8]
- mul rsi
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+2*8]
- mul rcx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+3*8]
- mul rbx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+4*8]
- mul r15
- mov r15,rbp
- add r8,rax
- adc r9,rdx
-
- and r15,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=a.n[2 3 4] * b.n[4 3 2]
- mov rax,[rdi+2*8]
- mul rsi
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+3*8]
- mul rcx
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+4*8]
- mul rbx
- mov rbx,rbp
- add r8,rax
- adc r9,rdx
-
- and rbx,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=a.n[3 4] * b.n[4 3]
- mov rax,[rdi+3*8]
- mul rsi
- add r8,rax
- adc r9,rdx
-
- mov rax,[rdi+4*8]
- mul rcx
- mov rcx,rbp
- add r8,rax
- adc r9,rdx
- and rcx,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=a.n[4] * b.n[4]
- mov rax,[rdi+4*8]
- mul rsi
- ;; mov rbp,rbp ; modulus already there!
- add r8,rax
- adc r9,rdx
- and rbp,r8
- shrd r8,r9,52
- xor r9,r9
-
- mov rsi,r8 ; load c into t9 and destroy b.n[4]
-
- ;; *******************************************************
-common_exit_norm:
- mov rdi,01000003D10h ; load constant
-
- mov rax,r15 ; get t5
- mul rdi
- add rax,r10 ; +t0
- adc rdx,0
- mov r10,0FFFFFFFFFFFFFh ; modulus. Sadly, we ran out of registers!
- mov r8,rax ; +c
- and r10,rax
- shrd r8,rdx,52
- xor r9,r9
-
- mov rax,rbx ; get t6
- mul rdi
- add rax,r11 ; +t1
- adc rdx,0
- mov r11,0FFFFFFFFFFFFFh ; modulus
- add r8,rax ; +c
- adc r9,rdx
- and r11,r8
- shrd r8,r9,52
- xor r9,r9
-
- mov rax,rcx ; get t7
- mul rdi
- add rax,r12 ; +t2
- adc rdx,0
- pop rbx ; retrieve pointer to this.n
- mov r12,0FFFFFFFFFFFFFh ; modulus
- add r8,rax ; +c
- adc r9,rdx
- and r12,r8
- mov [rbx+2*8],r12 ; mov into this.n[2]
- shrd r8,r9,52
- xor r9,r9
-
- mov rax,rbp ; get t8
- mul rdi
- add rax,r13 ; +t3
- adc rdx,0
- mov r13,0FFFFFFFFFFFFFh ; modulus
- add r8,rax ; +c
- adc r9,rdx
- and r13,r8
- mov [rbx+3*8],r13 ; -> this.n[3]
- shrd r8,r9,52
- xor r9,r9
-
- mov rax,rsi ; get t9
- mul rdi
- add rax,r14 ; +t4
- adc rdx,0
- mov r14,0FFFFFFFFFFFFh ; !!!
- add r8,rax ; +c
- adc r9,rdx
- and r14,r8
- mov [rbx+4*8],r14 ; -> this.n[4]
- shrd r8,r9,48 ; !!!
- xor r9,r9
-
- mov rax,01000003D1h
- mul r8
- add rax,r10
- adc rdx,0
- mov r10,0FFFFFFFFFFFFFh ; modulus
- mov r8,rax
- and rax,r10
- shrd r8,rdx,52
- mov [rbx+0*8],rax ; -> this.n[0]
- add r8,r11
- mov [rbx+1*8],r8 ; -> this.n[1]
-
- pop r15
- pop r14
- pop r13
- pop r12
- pop rbx
- pop rbp
- ret
-
-
- ;; PROC ExSetSquare
- ;; Register Layout:
- ;; INPUT: rdi = a.n
- ;; rsi = this.a
- ;; INTERNAL: rdx:rax = multiplication accumulator
- ;; r9:r8 = c
- ;; r10-r13 = t0-t3
- ;; r14 = a.n[0] / t4
- ;; r15 = a.n[1] / t5
- ;; rbx = a.n[2] / t6
- ;; rcx = a.n[3] / t7
- ;; rbp = 0FFFFFFFFFFFFFh / t8
- ;; rsi = a.n[4] / t9
- GLOBAL SYM(secp256k1_fe_sqr_inner)
- ALIGN 32
-SYM(secp256k1_fe_sqr_inner):
- push rbp
- push rbx
- push r12
- push r13
- push r14
- push r15
- push rsi
- mov rbp,0FFFFFFFFFFFFFh
-
- ;; c=a.n[0] * a.n[0]
- mov r14,[rdi+0*8] ; r14=a.n[0]
- mov r10,rbp ; modulus
- mov rax,r14
- mul rax
- mov r15,[rdi+1*8] ; a.n[1]
- add r14,r14 ; r14=2*a.n[0]
- mov r8,rax
- and r10,rax ; only need lower qword
- shrd r8,rdx,52
- xor r9,r9
-
- ;; c+=2*a.n[0] * a.n[1]
- mov rax,r14 ; r14=2*a.n[0]
- mul r15
- mov rbx,[rdi+2*8] ; rbx=a.n[2]
- mov r11,rbp ; modulus
- add r8,rax
- adc r9,rdx
- and r11,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=2*a.n[0]*a.n[2]+a.n[1]*a.n[1]
- mov rax,r14
- mul rbx
- add r8,rax
- adc r9,rdx
-
- mov rax,r15
- mov r12,rbp ; modulus
- mul rax
- mov rcx,[rdi+3*8] ; rcx=a.n[3]
- add r15,r15 ; r15=a.n[1]*2
- add r8,rax
- adc r9,rdx
- and r12,r8 ; only need lower dword
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=2*a.n[0]*a.n[3]+2*a.n[1]*a.n[2]
- mov rax,r14
- mul rcx
- add r8,rax
- adc r9,rdx
-
- mov rax,r15 ; rax=2*a.n[1]
- mov r13,rbp ; modulus
- mul rbx
- mov rsi,[rdi+4*8] ; rsi=a.n[4]
- add r8,rax
- adc r9,rdx
- and r13,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=2*a.n[0]*a.n[4]+2*a.n[1]*a.n[3]+a.n[2]*a.n[2]
- mov rax,r14 ; last time we need 2*a.n[0]
- mul rsi
- add r8,rax
- adc r9,rdx
-
- mov rax,r15
- mul rcx
- mov r14,rbp ; modulus
- add r8,rax
- adc r9,rdx
-
- mov rax,rbx
- mul rax
- add rbx,rbx ; rcx=2*a.n[2]
- add r8,rax
- adc r9,rdx
- and r14,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=2*a.n[1]*a.n[4]+2*a.n[2]*a.n[3]
- mov rax,r15 ; last time we need 2*a.n[1]
- mul rsi
- add r8,rax
- adc r9,rdx
-
- mov rax,rbx
- mul rcx
- mov r15,rbp ; modulus
- add r8,rax
- adc r9,rdx
- and r15,r8
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=2*a.n[2]*a.n[4]+a.n[3]*a.n[3]
- mov rax,rbx ; last time we need 2*a.n[2]
- mul rsi
- add r8,rax
- adc r9,rdx
-
- mov rax,rcx ; a.n[3]
- mul rax
- mov rbx,rbp ; modulus
- add r8,rax
- adc r9,rdx
- and rbx,r8 ; only need lower dword
- lea rax,[2*rcx]
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=2*a.n[3]*a.n[4]
- mul rsi
- mov rcx,rbp ; modulus
- add r8,rax
- adc r9,rdx
- and rcx,r8 ; only need lower dword
- shrd r8,r9,52
- xor r9,r9
-
- ;; c+=a.n[4]*a.n[4]
- mov rax,rsi
- mul rax
- ;; mov rbp,rbp ; modulus is already there!
- add r8,rax
- adc r9,rdx
- and rbp,r8
- shrd r8,r9,52
- xor r9,r9
-
- mov rsi,r8
-
- ;; *******************************************************
- jmp common_exit_norm
- end
-
-
diff --git a/src/secp256k1/src/field_5x52_asm_impl.h b/src/secp256k1/src/field_5x52_asm_impl.h
index f29605b11b..98cc004bf0 100644
--- a/src/secp256k1/src/field_5x52_asm_impl.h
+++ b/src/secp256k1/src/field_5x52_asm_impl.h
@@ -1,13 +1,502 @@
/**********************************************************************
- * Copyright (c) 2013 Pieter Wuille *
+ * Copyright (c) 2013-2014 Diederik Huys, Pieter Wuille *
* Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/
+/**
+ * Changelog:
+ * - March 2013, Diederik Huys: original version
+ * - November 2014, Pieter Wuille: updated to use Peter Dettman's parallel multiplication algorithm
+ * - December 2014, Pieter Wuille: converted from YASM to GCC inline assembly
+ */
+
#ifndef _SECP256K1_FIELD_INNER5X52_IMPL_H_
#define _SECP256K1_FIELD_INNER5X52_IMPL_H_
-void __attribute__ ((sysv_abi)) secp256k1_fe_mul_inner(const uint64_t *a, const uint64_t *b, uint64_t *r);
-void __attribute__ ((sysv_abi)) secp256k1_fe_sqr_inner(const uint64_t *a, uint64_t *r);
+SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint64_t *r, const uint64_t *a, const uint64_t * SECP256K1_RESTRICT b) {
+/**
+ * Registers: rdx:rax = multiplication accumulator
+ * r9:r8 = c
+ * r15:rcx = d
+ * r10-r14 = a0-a4
+ * rbx = b
+ * rdi = r
+ * rsi = a / t?
+ */
+ uint64_t tmp1, tmp2, tmp3;
+__asm__ __volatile__(
+ "movq 0(%%rsi),%%r10\n"
+ "movq 8(%%rsi),%%r11\n"
+ "movq 16(%%rsi),%%r12\n"
+ "movq 24(%%rsi),%%r13\n"
+ "movq 32(%%rsi),%%r14\n"
+
+ /* d += a3 * b0 */
+ "movq 0(%%rbx),%%rax\n"
+ "mulq %%r13\n"
+ "movq %%rax,%%rcx\n"
+ "movq %%rdx,%%r15\n"
+ /* d += a2 * b1 */
+ "movq 8(%%rbx),%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a1 * b2 */
+ "movq 16(%%rbx),%%rax\n"
+ "mulq %%r11\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d = a0 * b3 */
+ "movq 24(%%rbx),%%rax\n"
+ "mulq %%r10\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* c = a4 * b4 */
+ "movq 32(%%rbx),%%rax\n"
+ "mulq %%r14\n"
+ "movq %%rax,%%r8\n"
+ "movq %%rdx,%%r9\n"
+ /* d += (c & M) * R */
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* c >>= 52 (%%r8 only) */
+ "shrdq $52,%%r9,%%r8\n"
+ /* t3 (tmp1) = d & M */
+ "movq %%rcx,%%rsi\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rsi\n"
+ "movq %%rsi,%q1\n"
+ /* d >>= 52 */
+ "shrdq $52,%%r15,%%rcx\n"
+ "xorq %%r15,%%r15\n"
+ /* d += a4 * b0 */
+ "movq 0(%%rbx),%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a3 * b1 */
+ "movq 8(%%rbx),%%rax\n"
+ "mulq %%r13\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a2 * b2 */
+ "movq 16(%%rbx),%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a1 * b3 */
+ "movq 24(%%rbx),%%rax\n"
+ "mulq %%r11\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a0 * b4 */
+ "movq 32(%%rbx),%%rax\n"
+ "mulq %%r10\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += c * R */
+ "movq %%r8,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* t4 = d & M (%%rsi) */
+ "movq %%rcx,%%rsi\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rsi\n"
+ /* d >>= 52 */
+ "shrdq $52,%%r15,%%rcx\n"
+ "xorq %%r15,%%r15\n"
+ /* tx = t4 >> 48 (tmp3) */
+ "movq %%rsi,%%rax\n"
+ "shrq $48,%%rax\n"
+ "movq %%rax,%q3\n"
+ /* t4 &= (M >> 4) (tmp2) */
+ "movq $0xffffffffffff,%%rax\n"
+ "andq %%rax,%%rsi\n"
+ "movq %%rsi,%q2\n"
+ /* c = a0 * b0 */
+ "movq 0(%%rbx),%%rax\n"
+ "mulq %%r10\n"
+ "movq %%rax,%%r8\n"
+ "movq %%rdx,%%r9\n"
+ /* d += a4 * b1 */
+ "movq 8(%%rbx),%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a3 * b2 */
+ "movq 16(%%rbx),%%rax\n"
+ "mulq %%r13\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a2 * b3 */
+ "movq 24(%%rbx),%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a1 * b4 */
+ "movq 32(%%rbx),%%rax\n"
+ "mulq %%r11\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* u0 = d & M (%%rsi) */
+ "movq %%rcx,%%rsi\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rsi\n"
+ /* d >>= 52 */
+ "shrdq $52,%%r15,%%rcx\n"
+ "xorq %%r15,%%r15\n"
+ /* u0 = (u0 << 4) | tx (%%rsi) */
+ "shlq $4,%%rsi\n"
+ "movq %q3,%%rax\n"
+ "orq %%rax,%%rsi\n"
+ /* c += u0 * (R >> 4) */
+ "movq $0x1000003d1,%%rax\n"
+ "mulq %%rsi\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* r[0] = c & M */
+ "movq %%r8,%%rax\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rax\n"
+ "movq %%rax,0(%%rdi)\n"
+ /* c >>= 52 */
+ "shrdq $52,%%r9,%%r8\n"
+ "xorq %%r9,%%r9\n"
+ /* c += a1 * b0 */
+ "movq 0(%%rbx),%%rax\n"
+ "mulq %%r11\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* c += a0 * b1 */
+ "movq 8(%%rbx),%%rax\n"
+ "mulq %%r10\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* d += a4 * b2 */
+ "movq 16(%%rbx),%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a3 * b3 */
+ "movq 24(%%rbx),%%rax\n"
+ "mulq %%r13\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a2 * b4 */
+ "movq 32(%%rbx),%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* c += (d & M) * R */
+ "movq %%rcx,%%rax\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* d >>= 52 */
+ "shrdq $52,%%r15,%%rcx\n"
+ "xorq %%r15,%%r15\n"
+ /* r[1] = c & M */
+ "movq %%r8,%%rax\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rax\n"
+ "movq %%rax,8(%%rdi)\n"
+ /* c >>= 52 */
+ "shrdq $52,%%r9,%%r8\n"
+ "xorq %%r9,%%r9\n"
+ /* c += a2 * b0 */
+ "movq 0(%%rbx),%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* c += a1 * b1 */
+ "movq 8(%%rbx),%%rax\n"
+ "mulq %%r11\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* c += a0 * b2 (last use of %%r10 = a0) */
+ "movq 16(%%rbx),%%rax\n"
+ "mulq %%r10\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* fetch t3 (%%r10, overwrites a0), t4 (%%rsi) */
+ "movq %q2,%%rsi\n"
+ "movq %q1,%%r10\n"
+ /* d += a4 * b3 */
+ "movq 24(%%rbx),%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* d += a3 * b4 */
+ "movq 32(%%rbx),%%rax\n"
+ "mulq %%r13\n"
+ "addq %%rax,%%rcx\n"
+ "adcq %%rdx,%%r15\n"
+ /* c += (d & M) * R */
+ "movq %%rcx,%%rax\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* d >>= 52 (%%rcx only) */
+ "shrdq $52,%%r15,%%rcx\n"
+ /* r[2] = c & M */
+ "movq %%r8,%%rax\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rax\n"
+ "movq %%rax,16(%%rdi)\n"
+ /* c >>= 52 */
+ "shrdq $52,%%r9,%%r8\n"
+ "xorq %%r9,%%r9\n"
+ /* c += t3 */
+ "addq %%r10,%%r8\n"
+ /* c += d * R */
+ "movq %%rcx,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* r[3] = c & M */
+ "movq %%r8,%%rax\n"
+ "movq $0xfffffffffffff,%%rdx\n"
+ "andq %%rdx,%%rax\n"
+ "movq %%rax,24(%%rdi)\n"
+ /* c >>= 52 (%%r8 only) */
+ "shrdq $52,%%r9,%%r8\n"
+ /* c += t4 (%%r8 only) */
+ "addq %%rsi,%%r8\n"
+ /* r[4] = c */
+ "movq %%r8,32(%%rdi)\n"
+: "+S"(a), "=m"(tmp1), "=m"(tmp2), "=m"(tmp3)
+: "b"(b), "D"(r)
+: "%rax", "%rcx", "%rdx", "%r8", "%r9", "%r10", "%r11", "%r12", "%r13", "%r14", "%r15", "cc", "memory"
+);
+}
+
+SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint64_t *r, const uint64_t *a) {
+/**
+ * Registers: rdx:rax = multiplication accumulator
+ * r9:r8 = c
+ * rcx:rbx = d
+ * r10-r14 = a0-a4
+ * r15 = M (0xfffffffffffff)
+ * rdi = r
+ * rsi = a / t?
+ */
+ uint64_t tmp1, tmp2, tmp3;
+__asm__ __volatile__(
+ "movq 0(%%rsi),%%r10\n"
+ "movq 8(%%rsi),%%r11\n"
+ "movq 16(%%rsi),%%r12\n"
+ "movq 24(%%rsi),%%r13\n"
+ "movq 32(%%rsi),%%r14\n"
+ "movq $0xfffffffffffff,%%r15\n"
+
+ /* d = (a0*2) * a3 */
+ "leaq (%%r10,%%r10,1),%%rax\n"
+ "mulq %%r13\n"
+ "movq %%rax,%%rbx\n"
+ "movq %%rdx,%%rcx\n"
+ /* d += (a1*2) * a2 */
+ "leaq (%%r11,%%r11,1),%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* c = a4 * a4 */
+ "movq %%r14,%%rax\n"
+ "mulq %%r14\n"
+ "movq %%rax,%%r8\n"
+ "movq %%rdx,%%r9\n"
+ /* d += (c & M) * R */
+ "andq %%r15,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* c >>= 52 (%%r8 only) */
+ "shrdq $52,%%r9,%%r8\n"
+ /* t3 (tmp1) = d & M */
+ "movq %%rbx,%%rsi\n"
+ "andq %%r15,%%rsi\n"
+ "movq %%rsi,%q1\n"
+ /* d >>= 52 */
+ "shrdq $52,%%rcx,%%rbx\n"
+ "xorq %%rcx,%%rcx\n"
+ /* a4 *= 2 */
+ "addq %%r14,%%r14\n"
+ /* d += a0 * a4 */
+ "movq %%r10,%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* d+= (a1*2) * a3 */
+ "leaq (%%r11,%%r11,1),%%rax\n"
+ "mulq %%r13\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* d += a2 * a2 */
+ "movq %%r12,%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* d += c * R */
+ "movq %%r8,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* t4 = d & M (%%rsi) */
+ "movq %%rbx,%%rsi\n"
+ "andq %%r15,%%rsi\n"
+ /* d >>= 52 */
+ "shrdq $52,%%rcx,%%rbx\n"
+ "xorq %%rcx,%%rcx\n"
+ /* tx = t4 >> 48 (tmp3) */
+ "movq %%rsi,%%rax\n"
+ "shrq $48,%%rax\n"
+ "movq %%rax,%q3\n"
+ /* t4 &= (M >> 4) (tmp2) */
+ "movq $0xffffffffffff,%%rax\n"
+ "andq %%rax,%%rsi\n"
+ "movq %%rsi,%q2\n"
+ /* c = a0 * a0 */
+ "movq %%r10,%%rax\n"
+ "mulq %%r10\n"
+ "movq %%rax,%%r8\n"
+ "movq %%rdx,%%r9\n"
+ /* d += a1 * a4 */
+ "movq %%r11,%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* d += (a2*2) * a3 */
+ "leaq (%%r12,%%r12,1),%%rax\n"
+ "mulq %%r13\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* u0 = d & M (%%rsi) */
+ "movq %%rbx,%%rsi\n"
+ "andq %%r15,%%rsi\n"
+ /* d >>= 52 */
+ "shrdq $52,%%rcx,%%rbx\n"
+ "xorq %%rcx,%%rcx\n"
+ /* u0 = (u0 << 4) | tx (%%rsi) */
+ "shlq $4,%%rsi\n"
+ "movq %q3,%%rax\n"
+ "orq %%rax,%%rsi\n"
+ /* c += u0 * (R >> 4) */
+ "movq $0x1000003d1,%%rax\n"
+ "mulq %%rsi\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* r[0] = c & M */
+ "movq %%r8,%%rax\n"
+ "andq %%r15,%%rax\n"
+ "movq %%rax,0(%%rdi)\n"
+ /* c >>= 52 */
+ "shrdq $52,%%r9,%%r8\n"
+ "xorq %%r9,%%r9\n"
+ /* a0 *= 2 */
+ "addq %%r10,%%r10\n"
+ /* c += a0 * a1 */
+ "movq %%r10,%%rax\n"
+ "mulq %%r11\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* d += a2 * a4 */
+ "movq %%r12,%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* d += a3 * a3 */
+ "movq %%r13,%%rax\n"
+ "mulq %%r13\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* c += (d & M) * R */
+ "movq %%rbx,%%rax\n"
+ "andq %%r15,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* d >>= 52 */
+ "shrdq $52,%%rcx,%%rbx\n"
+ "xorq %%rcx,%%rcx\n"
+ /* r[1] = c & M */
+ "movq %%r8,%%rax\n"
+ "andq %%r15,%%rax\n"
+ "movq %%rax,8(%%rdi)\n"
+ /* c >>= 52 */
+ "shrdq $52,%%r9,%%r8\n"
+ "xorq %%r9,%%r9\n"
+ /* c += a0 * a2 (last use of %%r10) */
+ "movq %%r10,%%rax\n"
+ "mulq %%r12\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* fetch t3 (%%r10, overwrites a0),t4 (%%rsi) */
+ "movq %q2,%%rsi\n"
+ "movq %q1,%%r10\n"
+ /* c += a1 * a1 */
+ "movq %%r11,%%rax\n"
+ "mulq %%r11\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* d += a3 * a4 */
+ "movq %%r13,%%rax\n"
+ "mulq %%r14\n"
+ "addq %%rax,%%rbx\n"
+ "adcq %%rdx,%%rcx\n"
+ /* c += (d & M) * R */
+ "movq %%rbx,%%rax\n"
+ "andq %%r15,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* d >>= 52 (%%rbx only) */
+ "shrdq $52,%%rcx,%%rbx\n"
+ /* r[2] = c & M */
+ "movq %%r8,%%rax\n"
+ "andq %%r15,%%rax\n"
+ "movq %%rax,16(%%rdi)\n"
+ /* c >>= 52 */
+ "shrdq $52,%%r9,%%r8\n"
+ "xorq %%r9,%%r9\n"
+ /* c += t3 */
+ "addq %%r10,%%r8\n"
+ /* c += d * R */
+ "movq %%rbx,%%rax\n"
+ "movq $0x1000003d10,%%rdx\n"
+ "mulq %%rdx\n"
+ "addq %%rax,%%r8\n"
+ "adcq %%rdx,%%r9\n"
+ /* r[3] = c & M */
+ "movq %%r8,%%rax\n"
+ "andq %%r15,%%rax\n"
+ "movq %%rax,24(%%rdi)\n"
+ /* c >>= 52 (%%r8 only) */
+ "shrdq $52,%%r9,%%r8\n"
+ /* c += t4 (%%r8 only) */
+ "addq %%rsi,%%r8\n"
+ /* r[4] = c */
+ "movq %%r8,32(%%rdi)\n"
+: "+S"(a), "=m"(tmp1), "=m"(tmp2), "=m"(tmp3)
+: "D"(r)
+: "%rax", "%rbx", "%rcx", "%rdx", "%r8", "%r9", "%r10", "%r11", "%r12", "%r13", "%r14", "%r15", "cc", "memory"
+);
+}
#endif
diff --git a/src/secp256k1/src/field_5x52_impl.h b/src/secp256k1/src/field_5x52_impl.h
index 75b210eaf6..63176d6de4 100644
--- a/src/secp256k1/src/field_5x52_impl.h
+++ b/src/secp256k1/src/field_5x52_impl.h
@@ -102,6 +102,50 @@ static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
#endif
}
+static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
+ uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
+
+ /* Reduce t4 at the start so there will be at most a single carry from the first pass */
+ uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
+ uint64_t m;
+
+ /* The first pass ensures the magnitude is 1, ... */
+ t0 += x * 0x1000003D1ULL;
+ t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
+ t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
+ t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
+ t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;
+
+ /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t4 >> 49 == 0);
+
+ /* At most a single final reduction is needed; check if the value is >= the field characteristic */
+ x = (t4 >> 48) | ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
+ & (t0 >= 0xFFFFEFFFFFC2FULL));
+
+ if (x) {
+ t0 += 0x1000003D1ULL;
+ t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
+ t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
+ t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
+ t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
+
+ /* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
+ VERIFY_CHECK(t4 >> 48 == x);
+
+ /* Mask off the possible multiple of 2^256 from the final reduction */
+ t4 &= 0x0FFFFFFFFFFFFULL;
+ }
+
+ r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
+
+#ifdef VERIFY
+ r->magnitude = 1;
+ r->normalized = 1;
+ secp256k1_fe_verify(r);
+#endif
+}
+
SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a) {
r->n[0] = a;
r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
@@ -255,7 +299,7 @@ static void secp256k1_fe_mul(secp256k1_fe_t *r, const secp256k1_fe_t *a, const s
secp256k1_fe_verify(b);
VERIFY_CHECK(r != b);
#endif
- secp256k1_fe_mul_inner(a->n, b->n, r->n);
+ secp256k1_fe_mul_inner(r->n, a->n, b->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
@@ -268,7 +312,7 @@ static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
VERIFY_CHECK(a->magnitude <= 8);
secp256k1_fe_verify(a);
#endif
- secp256k1_fe_sqr_inner(a->n, r->n);
+ secp256k1_fe_sqr_inner(r->n, a->n);
#ifdef VERIFY
r->magnitude = 1;
r->normalized = 0;
diff --git a/src/secp256k1/src/field_5x52_int128_impl.h b/src/secp256k1/src/field_5x52_int128_impl.h
index e552fb4319..ec631833cf 100644
--- a/src/secp256k1/src/field_5x52_int128_impl.h
+++ b/src/secp256k1/src/field_5x52_int128_impl.h
@@ -15,7 +15,7 @@
#define VERIFY_BITS(x, n) do { } while(0)
#endif
-SECP256K1_INLINE static void secp256k1_fe_mul_inner(const uint64_t *a, const uint64_t * SECP256K1_RESTRICT b, uint64_t *r) {
+SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint64_t *r, const uint64_t *a, const uint64_t * SECP256K1_RESTRICT b) {
VERIFY_BITS(a[0], 56);
VERIFY_BITS(a[1], 56);
VERIFY_BITS(a[2], 56);
@@ -152,7 +152,7 @@ SECP256K1_INLINE static void secp256k1_fe_mul_inner(const uint64_t *a, const uin
/* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
}
-SECP256K1_INLINE static void secp256k1_fe_sqr_inner(const uint64_t *a, uint64_t *r) {
+SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint64_t *r, const uint64_t *a) {
VERIFY_BITS(a[0], 56);
VERIFY_BITS(a[1], 56);
VERIFY_BITS(a[2], 56);
diff --git a/src/secp256k1/src/field_gmp_impl.h b/src/secp256k1/src/field_gmp_impl.h
index 8af7dd68f8..73a55c4f00 100644
--- a/src/secp256k1/src/field_gmp_impl.h
+++ b/src/secp256k1/src/field_gmp_impl.h
@@ -46,6 +46,10 @@ static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
mpn_sub(r->n, r->n, FIELD_LIMBS, secp256k1_field_p, FIELD_LIMBS);
}
+static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
+ secp256k1_fe_normalize(r);
+}
+
SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a) {
r->n[0] = a;
for (int i=1; i<FIELD_LIMBS+1; i++)
diff --git a/src/secp256k1/src/field_impl.h b/src/secp256k1/src/field_impl.h
index 4d25e53715..24d3104ed1 100644
--- a/src/secp256k1/src/field_impl.h
+++ b/src/secp256k1/src/field_impl.h
@@ -66,7 +66,7 @@ static int secp256k1_fe_set_hex(secp256k1_fe_t *r, const char *a, int alen) {
return secp256k1_fe_set_b32(r, tmp);
}
-static int secp256k1_fe_sqrt(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
+static int secp256k1_fe_sqrt_var(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
/** The binary representation of (p + 1)/4 has 3 blocks of 1s, with lengths in
* { 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block:
@@ -132,7 +132,7 @@ static int secp256k1_fe_sqrt(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
secp256k1_fe_sqr(&t1, r);
secp256k1_fe_negate(&t1, &t1, 1);
secp256k1_fe_add(&t1, a);
- secp256k1_fe_normalize(&t1);
+ secp256k1_fe_normalize_var(&t1);
return secp256k1_fe_is_zero(&t1);
}
@@ -206,7 +206,7 @@ static void secp256k1_fe_inv_var(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
#elif defined(USE_FIELD_INV_NUM)
unsigned char b[32];
secp256k1_fe_t c = *a;
- secp256k1_fe_normalize(&c);
+ secp256k1_fe_normalize_var(&c);
secp256k1_fe_get_b32(b, &c);
secp256k1_num_t n;
secp256k1_num_set_bin(&n, b, 32);
@@ -218,30 +218,6 @@ static void secp256k1_fe_inv_var(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
#endif
}
-static void secp256k1_fe_inv_all(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
- if (len < 1)
- return;
-
- VERIFY_CHECK((r + len <= a) || (a + len <= r));
-
- r[0] = a[0];
-
- size_t i = 0;
- while (++i < len) {
- secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
- }
-
- secp256k1_fe_t u; secp256k1_fe_inv(&u, &r[--i]);
-
- while (i > 0) {
- int j = i--;
- secp256k1_fe_mul(&r[j], &r[i], &u);
- secp256k1_fe_mul(&u, &u, &a[j]);
- }
-
- r[0] = u;
-}
-
static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
if (len < 1)
return;
@@ -277,7 +253,7 @@ static void secp256k1_fe_start(void) {
#endif
if (secp256k1_fe_consts == NULL) {
secp256k1_fe_inner_start();
- secp256k1_fe_consts_t *ret = (secp256k1_fe_consts_t*)malloc(sizeof(secp256k1_fe_consts_t));
+ secp256k1_fe_consts_t *ret = (secp256k1_fe_consts_t*)checked_malloc(sizeof(secp256k1_fe_consts_t));
#ifndef USE_NUM_NONE
secp256k1_num_set_bin(&ret->p, secp256k1_fe_consts_p, sizeof(secp256k1_fe_consts_p));
#endif
diff --git a/src/secp256k1/src/group.h b/src/secp256k1/src/group.h
index 0f14bd25f3..ecfebcdc0c 100644
--- a/src/secp256k1/src/group.h
+++ b/src/secp256k1/src/group.h
@@ -51,15 +51,16 @@ static void secp256k1_ge_set_xy(secp256k1_ge_t *r, const secp256k1_fe_t *x, cons
/** Set a group element (affine) equal to the point with the given X coordinate, and given oddness
* for Y. Return value indicates whether the result is valid. */
-static int secp256k1_ge_set_xo(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd);
+static int secp256k1_ge_set_xo_var(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd);
/** Check whether a group element is the point at infinity. */
static int secp256k1_ge_is_infinity(const secp256k1_ge_t *a);
/** Check whether a group element is valid (i.e., on the curve). */
-static int secp256k1_ge_is_valid(const secp256k1_ge_t *a);
+static int secp256k1_ge_is_valid_var(const secp256k1_ge_t *a);
static void secp256k1_ge_neg(secp256k1_ge_t *r, const secp256k1_ge_t *a);
+static void secp256k1_ge_neg_var(secp256k1_ge_t *r, const secp256k1_ge_t *a);
/** Get a hex representation of a point. *rlen will be overwritten with the real length. */
static void secp256k1_ge_get_hex(char *r, int *rlen, const secp256k1_ge_t *a);
@@ -84,7 +85,7 @@ static void secp256k1_gej_set_ge(secp256k1_gej_t *r, const secp256k1_ge_t *a);
static void secp256k1_gej_get_x_var(secp256k1_fe_t *r, const secp256k1_gej_t *a);
/** Set r equal to the inverse of a (i.e., mirrored around the X axis) */
-static void secp256k1_gej_neg(secp256k1_gej_t *r, const secp256k1_gej_t *a);
+static void secp256k1_gej_neg_var(secp256k1_gej_t *r, const secp256k1_gej_t *a);
/** Check whether a group element is the point at infinity. */
static int secp256k1_gej_is_infinity(const secp256k1_gej_t *a);
diff --git a/src/secp256k1/src/group_impl.h b/src/secp256k1/src/group_impl.h
index cbd0d8c4fc..1ab5d5fe7b 100644
--- a/src/secp256k1/src/group_impl.h
+++ b/src/secp256k1/src/group_impl.h
@@ -28,13 +28,17 @@ static int secp256k1_ge_is_infinity(const secp256k1_ge_t *a) {
}
static void secp256k1_ge_neg(secp256k1_ge_t *r, const secp256k1_ge_t *a) {
- r->infinity = a->infinity;
- r->x = a->x;
- r->y = a->y;
+ *r = *a;
secp256k1_fe_normalize(&r->y);
secp256k1_fe_negate(&r->y, &r->y, 1);
}
+static void secp256k1_ge_neg_var(secp256k1_ge_t *r, const secp256k1_ge_t *a) {
+ *r = *a;
+ secp256k1_fe_normalize_var(&r->y);
+ secp256k1_fe_negate(&r->y, &r->y, 1);
+}
+
static void secp256k1_ge_get_hex(char *r, int *rlen, const secp256k1_ge_t *a) {
char cx[65]; int lx=65;
char cy[65]; int ly=65;
@@ -85,15 +89,16 @@ static void secp256k1_ge_set_gej_var(secp256k1_ge_t *r, secp256k1_gej_t *a) {
static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge_t r[len], const secp256k1_gej_t a[len]) {
size_t count = 0;
- secp256k1_fe_t az[len];
+ secp256k1_fe_t *az = checked_malloc(sizeof(secp256k1_fe_t) * len);
for (size_t i=0; i<len; i++) {
if (!a[i].infinity) {
az[count++] = a[i].z;
}
}
- secp256k1_fe_t azi[count];
+ secp256k1_fe_t *azi = checked_malloc(sizeof(secp256k1_fe_t) * count);
secp256k1_fe_inv_all_var(count, azi, az);
+ free(az);
count = 0;
for (size_t i=0; i<len; i++) {
@@ -106,6 +111,7 @@ static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge_t r[len], cons
secp256k1_fe_mul(&r[i].y, &a[i].y, &zi3);
}
}
+ free(azi);
}
static void secp256k1_gej_set_infinity(secp256k1_gej_t *r) {
@@ -135,16 +141,16 @@ static void secp256k1_ge_clear(secp256k1_ge_t *r) {
secp256k1_fe_clear(&r->y);
}
-static int secp256k1_ge_set_xo(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd) {
+static int secp256k1_ge_set_xo_var(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd) {
r->x = *x;
secp256k1_fe_t x2; secp256k1_fe_sqr(&x2, x);
secp256k1_fe_t x3; secp256k1_fe_mul(&x3, x, &x2);
r->infinity = 0;
secp256k1_fe_t c; secp256k1_fe_set_int(&c, 7);
secp256k1_fe_add(&c, &x3);
- if (!secp256k1_fe_sqrt(&r->y, &c))
+ if (!secp256k1_fe_sqrt_var(&r->y, &c))
return 0;
- secp256k1_fe_normalize(&r->y);
+ secp256k1_fe_normalize_var(&r->y);
if (secp256k1_fe_is_odd(&r->y) != odd)
secp256k1_fe_negate(&r->y, &r->y, 1);
return 1;
@@ -162,12 +168,12 @@ static void secp256k1_gej_get_x_var(secp256k1_fe_t *r, const secp256k1_gej_t *a)
secp256k1_fe_mul(r, &a->x, &zi2);
}
-static void secp256k1_gej_neg(secp256k1_gej_t *r, const secp256k1_gej_t *a) {
+static void secp256k1_gej_neg_var(secp256k1_gej_t *r, const secp256k1_gej_t *a) {
r->infinity = a->infinity;
r->x = a->x;
r->y = a->y;
r->z = a->z;
- secp256k1_fe_normalize(&r->y);
+ secp256k1_fe_normalize_var(&r->y);
secp256k1_fe_negate(&r->y, &r->y, 1);
}
@@ -175,7 +181,7 @@ static int secp256k1_gej_is_infinity(const secp256k1_gej_t *a) {
return a->infinity;
}
-static int secp256k1_gej_is_valid(const secp256k1_gej_t *a) {
+static int secp256k1_gej_is_valid_var(const secp256k1_gej_t *a) {
if (a->infinity)
return 0;
/** y^2 = x^3 + 7
@@ -189,12 +195,12 @@ static int secp256k1_gej_is_valid(const secp256k1_gej_t *a) {
secp256k1_fe_t z6; secp256k1_fe_sqr(&z6, &z2); secp256k1_fe_mul(&z6, &z6, &z2);
secp256k1_fe_mul_int(&z6, 7);
secp256k1_fe_add(&x3, &z6);
- secp256k1_fe_normalize(&y2);
- secp256k1_fe_normalize(&x3);
+ secp256k1_fe_normalize_var(&y2);
+ secp256k1_fe_normalize_var(&x3);
return secp256k1_fe_equal(&y2, &x3);
}
-static int secp256k1_ge_is_valid(const secp256k1_ge_t *a) {
+static int secp256k1_ge_is_valid_var(const secp256k1_ge_t *a) {
if (a->infinity)
return 0;
/* y^2 = x^3 + 7 */
@@ -202,8 +208,8 @@ static int secp256k1_ge_is_valid(const secp256k1_ge_t *a) {
secp256k1_fe_t x3; secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
secp256k1_fe_t c; secp256k1_fe_set_int(&c, 7);
secp256k1_fe_add(&x3, &c);
- secp256k1_fe_normalize(&y2);
- secp256k1_fe_normalize(&x3);
+ secp256k1_fe_normalize_var(&y2);
+ secp256k1_fe_normalize_var(&x3);
return secp256k1_fe_equal(&y2, &x3);
}
@@ -255,11 +261,11 @@ static void secp256k1_gej_add_var(secp256k1_gej_t *r, const secp256k1_gej_t *a,
secp256k1_fe_t u2; secp256k1_fe_mul(&u2, &b->x, &z12);
secp256k1_fe_t s1; secp256k1_fe_mul(&s1, &a->y, &z22); secp256k1_fe_mul(&s1, &s1, &b->z);
secp256k1_fe_t s2; secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
- secp256k1_fe_normalize(&u1);
- secp256k1_fe_normalize(&u2);
+ secp256k1_fe_normalize_var(&u1);
+ secp256k1_fe_normalize_var(&u2);
if (secp256k1_fe_equal(&u1, &u2)) {
- secp256k1_fe_normalize(&s1);
- secp256k1_fe_normalize(&s2);
+ secp256k1_fe_normalize_var(&s1);
+ secp256k1_fe_normalize_var(&s2);
if (secp256k1_fe_equal(&s1, &s2)) {
secp256k1_gej_double_var(r, a);
} else {
@@ -294,15 +300,14 @@ static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *
}
r->infinity = 0;
secp256k1_fe_t z12; secp256k1_fe_sqr(&z12, &a->z);
- secp256k1_fe_t u1 = a->x; secp256k1_fe_normalize(&u1);
+ secp256k1_fe_t u1 = a->x;
secp256k1_fe_t u2; secp256k1_fe_mul(&u2, &b->x, &z12);
- secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize(&s1);
+ secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize_var(&s1);
secp256k1_fe_t s2; secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
- secp256k1_fe_normalize(&u1);
- secp256k1_fe_normalize(&u2);
+ secp256k1_fe_normalize_var(&u1);
+ secp256k1_fe_normalize_var(&u2);
if (secp256k1_fe_equal(&u1, &u2)) {
- secp256k1_fe_normalize(&s1);
- secp256k1_fe_normalize(&s2);
+ secp256k1_fe_normalize_var(&s2);
if (secp256k1_fe_equal(&s1, &s2)) {
secp256k1_gej_double_var(r, a);
} else {
@@ -434,7 +439,7 @@ static void secp256k1_ge_start(void) {
};
#endif
if (secp256k1_ge_consts == NULL) {
- secp256k1_ge_consts_t *ret = (secp256k1_ge_consts_t*)malloc(sizeof(secp256k1_ge_consts_t));
+ secp256k1_ge_consts_t *ret = (secp256k1_ge_consts_t*)checked_malloc(sizeof(secp256k1_ge_consts_t));
#ifdef USE_ENDOMORPHISM
VERIFY_CHECK(secp256k1_fe_set_b32(&ret->beta, secp256k1_ge_consts_beta));
#endif
diff --git a/src/secp256k1/src/scalar_impl.h b/src/secp256k1/src/scalar_impl.h
index 7fc159df77..4408cce2d8 100644
--- a/src/secp256k1/src/scalar_impl.h
+++ b/src/secp256k1/src/scalar_impl.h
@@ -40,7 +40,7 @@ static void secp256k1_scalar_start(void) {
return;
/* Allocate. */
- secp256k1_scalar_consts_t *ret = (secp256k1_scalar_consts_t*)malloc(sizeof(secp256k1_scalar_consts_t));
+ secp256k1_scalar_consts_t *ret = (secp256k1_scalar_consts_t*)checked_malloc(sizeof(secp256k1_scalar_consts_t));
#ifndef USE_NUM_NONE
static const unsigned char secp256k1_scalar_consts_order[] = {
diff --git a/src/secp256k1/src/secp256k1.c b/src/secp256k1/src/secp256k1.c
index 20fc27df74..0328db88fc 100644
--- a/src/secp256k1/src/secp256k1.c
+++ b/src/secp256k1/src/secp256k1.c
@@ -40,15 +40,12 @@ void secp256k1_stop(void) {
secp256k1_fe_stop();
}
-int secp256k1_ecdsa_verify(const unsigned char *msg, int msglen, const unsigned char *sig, int siglen, const unsigned char *pubkey, int pubkeylen) {
+int secp256k1_ecdsa_verify(const unsigned char *msg32, const unsigned char *sig, int siglen, const unsigned char *pubkey, int pubkeylen) {
DEBUG_CHECK(secp256k1_ecmult_consts != NULL);
- DEBUG_CHECK(msg != NULL);
- DEBUG_CHECK(msglen <= 32);
+ DEBUG_CHECK(msg32 != NULL);
DEBUG_CHECK(sig != NULL);
DEBUG_CHECK(pubkey != NULL);
- unsigned char msg32[32] = {0};
- memcpy(msg32 + 32 - msglen, msg, msglen);
int ret = -3;
secp256k1_scalar_t m;
secp256k1_ecdsa_sig_t s;
@@ -72,10 +69,9 @@ end:
return ret;
}
-int secp256k1_ecdsa_sign(const unsigned char *message, int messagelen, unsigned char *signature, int *signaturelen, const unsigned char *seckey, const unsigned char *nonce) {
+int secp256k1_ecdsa_sign(const unsigned char *msg32, unsigned char *signature, int *signaturelen, const unsigned char *seckey, const unsigned char *nonce) {
DEBUG_CHECK(secp256k1_ecmult_gen_consts != NULL);
- DEBUG_CHECK(message != NULL);
- DEBUG_CHECK(messagelen <= 32);
+ DEBUG_CHECK(msg32 != NULL);
DEBUG_CHECK(signature != NULL);
DEBUG_CHECK(signaturelen != NULL);
DEBUG_CHECK(seckey != NULL);
@@ -85,12 +81,7 @@ int secp256k1_ecdsa_sign(const unsigned char *message, int messagelen, unsigned
secp256k1_scalar_set_b32(&sec, seckey, NULL);
int overflow = 0;
secp256k1_scalar_set_b32(&non, nonce, &overflow);
- {
- unsigned char c[32] = {0};
- memcpy(c + 32 - messagelen, message, messagelen);
- secp256k1_scalar_set_b32(&msg, c, NULL);
- memset(c, 0, 32);
- }
+ secp256k1_scalar_set_b32(&msg, msg32, NULL);
int ret = !secp256k1_scalar_is_zero(&non) && !overflow;
secp256k1_ecdsa_sig_t sig;
if (ret) {
@@ -105,10 +96,9 @@ int secp256k1_ecdsa_sign(const unsigned char *message, int messagelen, unsigned
return ret;
}
-int secp256k1_ecdsa_sign_compact(const unsigned char *message, int messagelen, unsigned char *sig64, const unsigned char *seckey, const unsigned char *nonce, int *recid) {
+int secp256k1_ecdsa_sign_compact(const unsigned char *msg32, unsigned char *sig64, const unsigned char *seckey, const unsigned char *nonce, int *recid) {
DEBUG_CHECK(secp256k1_ecmult_gen_consts != NULL);
- DEBUG_CHECK(message != NULL);
- DEBUG_CHECK(messagelen <= 32);
+ DEBUG_CHECK(msg32 != NULL);
DEBUG_CHECK(sig64 != NULL);
DEBUG_CHECK(seckey != NULL);
DEBUG_CHECK(nonce != NULL);
@@ -117,12 +107,7 @@ int secp256k1_ecdsa_sign_compact(const unsigned char *message, int messagelen, u
secp256k1_scalar_set_b32(&sec, seckey, NULL);
int overflow = 0;
secp256k1_scalar_set_b32(&non, nonce, &overflow);
- {
- unsigned char c[32] = {0};
- memcpy(c + 32 - messagelen, message, messagelen);
- secp256k1_scalar_set_b32(&msg, c, NULL);
- memset(c, 0, 32);
- }
+ secp256k1_scalar_set_b32(&msg, msg32, NULL);
int ret = !secp256k1_scalar_is_zero(&non) && !overflow;
secp256k1_ecdsa_sig_t sig;
if (ret) {
@@ -138,18 +123,15 @@ int secp256k1_ecdsa_sign_compact(const unsigned char *message, int messagelen, u
return ret;
}
-int secp256k1_ecdsa_recover_compact(const unsigned char *msg, int msglen, const unsigned char *sig64, unsigned char *pubkey, int *pubkeylen, int compressed, int recid) {
+int secp256k1_ecdsa_recover_compact(const unsigned char *msg32, const unsigned char *sig64, unsigned char *pubkey, int *pubkeylen, int compressed, int recid) {
DEBUG_CHECK(secp256k1_ecmult_consts != NULL);
- DEBUG_CHECK(msg != NULL);
- DEBUG_CHECK(msglen <= 32);
+ DEBUG_CHECK(msg32 != NULL);
DEBUG_CHECK(sig64 != NULL);
DEBUG_CHECK(pubkey != NULL);
DEBUG_CHECK(pubkeylen != NULL);
DEBUG_CHECK(recid >= 0 && recid <= 3);
int ret = 0;
- unsigned char msg32[32] = {0};
- memcpy(msg32 + 32 - msglen, msg, msglen);
secp256k1_scalar_t m;
secp256k1_ecdsa_sig_t sig;
int overflow = 0;
diff --git a/src/secp256k1/src/tests.c b/src/secp256k1/src/tests.c
index 78cdd67f27..7ebb19ff99 100644
--- a/src/secp256k1/src/tests.c
+++ b/src/secp256k1/src/tests.c
@@ -11,6 +11,8 @@
#include <stdio.h>
#include <stdlib.h>
+#include <time.h>
+
#include "secp256k1.c"
#include "testrand_impl.h"
@@ -46,7 +48,7 @@ void random_group_element_test(secp256k1_ge_t *ge) {
secp256k1_fe_t fe;
do {
random_field_element_test(&fe);
- if (secp256k1_ge_set_xo(ge, &fe, secp256k1_rand32() & 1))
+ if (secp256k1_ge_set_xo_var(ge, &fe, secp256k1_rand32() & 1))
break;
} while(1);
}
@@ -400,6 +402,30 @@ void scalar_test(void) {
CHECK(secp256k1_scalar_eq(&r1, &r2));
}
+ {
+ /* Test multiplicative identity. */
+ secp256k1_scalar_t r1, v1;
+ secp256k1_scalar_set_int(&v1,1);
+ secp256k1_scalar_mul(&r1, &s1, &v1);
+ CHECK(secp256k1_scalar_eq(&r1, &s1));
+ }
+
+ {
+ /* Test additive identity. */
+ secp256k1_scalar_t r1, v0;
+ secp256k1_scalar_set_int(&v0,0);
+ secp256k1_scalar_add(&r1, &s1, &v0);
+ CHECK(secp256k1_scalar_eq(&r1, &s1));
+ }
+
+ {
+ /* Test zero product property. */
+ secp256k1_scalar_t r1, v0;
+ secp256k1_scalar_set_int(&v0,0);
+ secp256k1_scalar_mul(&r1, &s1, &v0);
+ CHECK(secp256k1_scalar_eq(&r1, &v0));
+ }
+
}
void run_scalar_tests(void) {
@@ -411,9 +437,12 @@ void run_scalar_tests(void) {
/* (-1)+1 should be zero. */
secp256k1_scalar_t s, o;
secp256k1_scalar_set_int(&s, 1);
+ CHECK(secp256k1_scalar_is_one(&s));
secp256k1_scalar_negate(&o, &s);
secp256k1_scalar_add(&o, &o, &s);
CHECK(secp256k1_scalar_is_zero(&o));
+ secp256k1_scalar_negate(&o, &o);
+ CHECK(secp256k1_scalar_is_zero(&o));
}
#ifndef USE_NUM_NONE
@@ -459,14 +488,14 @@ void random_fe_non_zero(secp256k1_fe_t *nz) {
void random_fe_non_square(secp256k1_fe_t *ns) {
random_fe_non_zero(ns);
secp256k1_fe_t r;
- if (secp256k1_fe_sqrt(&r, ns)) {
+ if (secp256k1_fe_sqrt_var(&r, ns)) {
secp256k1_fe_negate(ns, ns, 1);
}
}
int check_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
secp256k1_fe_t an = *a; secp256k1_fe_normalize(&an);
- secp256k1_fe_t bn = *b; secp256k1_fe_normalize(&bn);
+ secp256k1_fe_t bn = *b; secp256k1_fe_normalize_var(&bn);
return secp256k1_fe_equal(&an, &bn);
}
@@ -476,6 +505,55 @@ int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
return check_fe_equal(&x, &one);
}
+void run_field_misc(void) {
+ const unsigned char f32_5[32] = {
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x05,
+ };
+ secp256k1_fe_t x;
+ secp256k1_fe_t y;
+ secp256k1_fe_t z;
+ secp256k1_fe_t q;
+ secp256k1_fe_t fe5;
+ CHECK(secp256k1_fe_set_b32(&fe5, f32_5));
+ for (int i=0; i<5*count; i++) {
+ random_fe(&x);
+ random_fe_non_zero(&y);
+ /* Test the fe equality and comparison operations. */
+ CHECK(secp256k1_fe_cmp_var(&x, &x) == 0);
+ CHECK(secp256k1_fe_equal(&x, &x));
+ z = x;
+ secp256k1_fe_add(&z,&y);
+ secp256k1_fe_normalize(&z);
+ /* Test the conditional move. */
+ secp256k1_fe_cmov(&z, &x, 0);
+ CHECK(secp256k1_fe_equal(&x, &z) == 0);
+ CHECK(secp256k1_fe_cmp_var(&x, &z) != 0);
+ secp256k1_fe_cmov(&y, &x, 1);
+ CHECK(secp256k1_fe_equal(&x, &y));
+ /* Test that mul_int, mul, and add agree. */
+ secp256k1_fe_add(&y, &x);
+ secp256k1_fe_add(&y, &x);
+ z = x;
+ secp256k1_fe_mul_int(&z, 3);
+ CHECK(check_fe_equal(&y, &z));
+ secp256k1_fe_add(&y, &x);
+ secp256k1_fe_add(&z, &x);
+ CHECK(check_fe_equal(&z, &y));
+ z = x;
+ secp256k1_fe_mul_int(&z, 5);
+ secp256k1_fe_mul(&q, &x, &fe5);
+ CHECK(check_fe_equal(&z, &q));
+ secp256k1_fe_negate(&x, &x, 1);
+ secp256k1_fe_add(&z, &x);
+ secp256k1_fe_add(&q, &x);
+ CHECK(check_fe_equal(&y, &z));
+ CHECK(check_fe_equal(&q, &y));
+ }
+}
+
void run_field_inv(void) {
secp256k1_fe_t x, xi, xii;
for (int i=0; i<10*count; i++) {
@@ -498,23 +576,6 @@ void run_field_inv_var(void) {
}
}
-void run_field_inv_all(void) {
- secp256k1_fe_t x[16], xi[16], xii[16];
- /* Check it's safe to call for 0 elements */
- secp256k1_fe_inv_all(0, xi, x);
- for (int i=0; i<count; i++) {
- size_t len = (secp256k1_rand32() & 15) + 1;
- for (size_t j=0; j<len; j++)
- random_fe_non_zero(&x[j]);
- secp256k1_fe_inv_all(len, xi, x);
- for (size_t j=0; j<len; j++)
- CHECK(check_fe_inverse(&x[j], &xi[j]));
- secp256k1_fe_inv_all(len, xii, xi);
- for (size_t j=0; j<len; j++)
- CHECK(check_fe_equal(&x[j], &xii[j]));
- }
-}
-
void run_field_inv_all_var(void) {
secp256k1_fe_t x[16], xi[16], xii[16];
/* Check it's safe to call for 0 elements */
@@ -549,7 +610,7 @@ void run_sqr(void) {
void test_sqrt(const secp256k1_fe_t *a, const secp256k1_fe_t *k) {
secp256k1_fe_t r1, r2;
- int v = secp256k1_fe_sqrt(&r1, a);
+ int v = secp256k1_fe_sqrt_var(&r1, a);
CHECK((v == 0) == (k == NULL));
if (k != NULL) {
@@ -769,6 +830,7 @@ void run_ecmult_chain(void) {
}
void test_point_times_order(const secp256k1_gej_t *point) {
+ unsigned char pub[65];
/* X * (point + G) + (order-X) * (pointer + G) = 0 */
secp256k1_scalar_t x;
random_scalar_order_test(&x);
@@ -779,27 +841,36 @@ void test_point_times_order(const secp256k1_gej_t *point) {
secp256k1_ecmult(&res2, point, &nx, &nx); /* calc res2 = (order - x) * point + (order - x) * G; */
secp256k1_gej_add_var(&res1, &res1, &res2);
CHECK(secp256k1_gej_is_infinity(&res1));
- CHECK(secp256k1_gej_is_valid(&res1) == 0);
+ CHECK(secp256k1_gej_is_valid_var(&res1) == 0);
secp256k1_ge_t res3;
secp256k1_ge_set_gej(&res3, &res1);
CHECK(secp256k1_ge_is_infinity(&res3));
- CHECK(secp256k1_ge_is_valid(&res3) == 0);
+ CHECK(secp256k1_ge_is_valid_var(&res3) == 0);
+ int psize = 65;
+ CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 0) == 0);
+ psize = 65;
+ CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
}
void run_point_times_order(void) {
secp256k1_fe_t x; VERIFY_CHECK(secp256k1_fe_set_hex(&x, "02", 2));
for (int i=0; i<500; i++) {
secp256k1_ge_t p;
- if (secp256k1_ge_set_xo(&p, &x, 1)) {
- CHECK(secp256k1_ge_is_valid(&p));
+ if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
+ CHECK(secp256k1_ge_is_valid_var(&p));
secp256k1_gej_t j;
secp256k1_gej_set_ge(&j, &p);
- CHECK(secp256k1_gej_is_valid(&j));
+ CHECK(secp256k1_gej_is_valid_var(&j));
test_point_times_order(&j);
}
secp256k1_fe_sqr(&x, &x);
}
- char c[65]; int cl=65;
+ char c[65];
+ int cl = 1;
+ c[1] = 123;
+ secp256k1_fe_get_hex(c, &cl, &x); /* Check that fe_get_hex handles a too short input. */
+ CHECK(c[1] == 123);
+ cl = 65;
secp256k1_fe_get_hex(c, &cl, &x);
CHECK(strcmp(c, "7603CB59B0EF6C63FE6084792A0C378CDB3233A80F8A9A09A877DEAD31B38C45") == 0);
}
@@ -894,7 +965,10 @@ void test_ecdsa_end_to_end(void) {
/* Construct and verify corresponding public key. */
CHECK(secp256k1_ec_seckey_verify(privkey) == 1);
unsigned char pubkey[65]; int pubkeylen = 65;
- CHECK(secp256k1_ec_pubkey_create(pubkey, &pubkeylen, privkey, secp256k1_rand32() % 2) == 1);
+ CHECK(secp256k1_ec_pubkey_create(pubkey, &pubkeylen, privkey, (secp256k1_rand32() & 3) != 0) == 1);
+ if (secp256k1_rand32() & 1) {
+ CHECK(secp256k1_ec_pubkey_decompress(pubkey, &pubkeylen));
+ }
CHECK(secp256k1_ec_pubkey_verify(pubkey, pubkeylen));
/* Verify private key import and export. */
@@ -935,38 +1009,96 @@ void test_ecdsa_end_to_end(void) {
while(1) {
unsigned char rnd[32];
secp256k1_rand256_test(rnd);
- if (secp256k1_ecdsa_sign(message, 32, signature, &signaturelen, privkey, rnd) == 1) {
+ if (secp256k1_ecdsa_sign(message, signature, &signaturelen, privkey, rnd) == 1) {
break;
}
}
/* Verify. */
- CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) == 1);
+ CHECK(secp256k1_ecdsa_verify(message, signature, signaturelen, pubkey, pubkeylen) == 1);
/* Destroy signature and verify again. */
signature[signaturelen - 1 - secp256k1_rand32() % 20] += 1 + (secp256k1_rand32() % 255);
- CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) != 1);
+ CHECK(secp256k1_ecdsa_verify(message, signature, signaturelen, pubkey, pubkeylen) != 1);
/* Compact sign. */
unsigned char csignature[64]; int recid = 0;
while(1) {
unsigned char rnd[32];
secp256k1_rand256_test(rnd);
- if (secp256k1_ecdsa_sign_compact(message, 32, csignature, privkey, rnd, &recid) == 1) {
+ if (secp256k1_ecdsa_sign_compact(message, csignature, privkey, rnd, &recid) == 1) {
break;
}
}
/* Recover. */
unsigned char recpubkey[65]; int recpubkeylen = 0;
- CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
+ CHECK(secp256k1_ecdsa_recover_compact(message, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
CHECK(recpubkeylen == pubkeylen);
CHECK(memcmp(pubkey, recpubkey, pubkeylen) == 0);
/* Destroy signature and verify again. */
csignature[secp256k1_rand32() % 64] += 1 + (secp256k1_rand32() % 255);
- CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) != 1 ||
+ CHECK(secp256k1_ecdsa_recover_compact(message, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) != 1 ||
memcmp(pubkey, recpubkey, pubkeylen) != 0);
CHECK(recpubkeylen == pubkeylen);
}
+void test_random_pubkeys(void) {
+ unsigned char in[65];
+ /* Generate some randomly sized pubkeys. */
+ uint32_t r = secp256k1_rand32();
+ int len = (r & 3) == 0 ? 65 : 33;
+ r>>=2;
+ if ((r & 3) == 0) len = (r & 252) >> 3;
+ r>>=8;
+ if (len == 65) {
+ in[0] = (r & 2) ? 4 : (r & 1? 6 : 7);
+ } else {
+ in[0] = (r & 1) ? 2 : 3;
+ }
+ r>>=2;
+ if ((r & 7) == 0) in[0] = (r & 2040) >> 3;
+ r>>=11;
+ if (len > 1) secp256k1_rand256(&in[1]);
+ if (len > 33) secp256k1_rand256(&in[33]);
+ secp256k1_ge_t elem;
+ secp256k1_ge_t elem2;
+ if (secp256k1_eckey_pubkey_parse(&elem, in, len)) {
+ unsigned char out[65];
+ unsigned char firstb;
+ int res;
+ int size = len;
+ firstb = in[0];
+ /* If the pubkey can be parsed, it should round-trip... */
+ CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
+ CHECK(size == len);
+ CHECK(memcmp(&in[1], &out[1], len-1) == 0);
+ /* ... except for the type of hybrid inputs. */
+ if ((in[0] != 6) && (in[0] != 7)) CHECK(in[0] == out[0]);
+ size = 65;
+ CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
+ CHECK(size == 65);
+ CHECK(secp256k1_eckey_pubkey_parse(&elem2, in, size));
+ CHECK(ge_equals_ge(&elem,&elem2));
+ /* Check that the X9.62 hybrid type is checked. */
+ in[0] = (r & 1) ? 6 : 7;
+ res = secp256k1_eckey_pubkey_parse(&elem2, in, size);
+ if (firstb == 2 || firstb == 3) {
+ if (in[0] == firstb + 4) CHECK(res);
+ else CHECK(!res);
+ }
+ if (res) {
+ CHECK(ge_equals_ge(&elem,&elem2));
+ CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
+ CHECK(memcmp(&in[1], &out[1], 64) == 0);
+ }
+ }
+}
+
+void run_random_pubkeys(void) {
+ for (int i=0; i<10*count; i++) {
+ test_random_pubkeys();
+ }
+}
+
void run_ecdsa_end_to_end(void) {
for (int i=0; i<64*count; i++) {
test_ecdsa_end_to_end();
@@ -995,10 +1127,10 @@ void test_ecdsa_edge_cases(void) {
};
unsigned char pubkey[65];
int pubkeylen = 65;
- CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 0));
- CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 1));
- CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 2));
- CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 3));
+ CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 0));
+ CHECK(secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 1));
+ CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 2));
+ CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 3));
/* signature (r,s) = (4,4), which can be recovered with all 4 recids. */
const unsigned char sigb64[64] = {
@@ -1016,6 +1148,36 @@ void test_ecdsa_edge_cases(void) {
for (int recid = 0; recid < 4; recid++) {
/* (4,4) encoded in DER. */
unsigned char sigbder[8] = {0x30, 0x06, 0x02, 0x01, 0x04, 0x02, 0x01, 0x04};
+ unsigned char sigcder_zr[7] = {0x30, 0x05, 0x02, 0x00, 0x02, 0x01, 0x01};
+ unsigned char sigcder_zs[7] = {0x30, 0x05, 0x02, 0x01, 0x01, 0x02, 0x00};
+ unsigned char sigbderalt1[39] = {
+ 0x30, 0x25, 0x02, 0x20, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
+ };
+ unsigned char sigbderalt2[39] = {
+ 0x30, 0x25, 0x02, 0x01, 0x04, 0x02, 0x20, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
+ };
+ unsigned char sigbderalt3[40] = {
+ 0x30, 0x26, 0x02, 0x21, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
+ };
+ unsigned char sigbderalt4[40] = {
+ 0x30, 0x26, 0x02, 0x01, 0x04, 0x02, 0x21, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
+ };
/* (order + r,4) encoded in DER. */
unsigned char sigbderlong[40] = {
0x30, 0x26, 0x02, 0x21, 0x00, 0xFF, 0xFF, 0xFF,
@@ -1024,18 +1186,45 @@ void test_ecdsa_edge_cases(void) {
0xE6, 0xAF, 0x48, 0xA0, 0x3B, 0xBF, 0xD2, 0x5E,
0x8C, 0xD0, 0x36, 0x41, 0x45, 0x02, 0x01, 0x04
};
- CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigb64, pubkeyb, &pubkeyblen, 1, recid));
- CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 1);
+ CHECK(secp256k1_ecdsa_recover_compact(msg32, sigb64, pubkeyb, &pubkeyblen, 1, recid));
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 1);
for (int recid2 = 0; recid2 < 4; recid2++) {
unsigned char pubkey2b[33];
int pubkey2blen = 33;
- CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigb64, pubkey2b, &pubkey2blen, 1, recid2));
+ CHECK(secp256k1_ecdsa_recover_compact(msg32, sigb64, pubkey2b, &pubkey2blen, 1, recid2));
/* Verifying with (order + r,4) should always fail. */
- CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderlong, sizeof(sigbderlong), pubkey2b, pubkey2blen) != 1);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbderlong, sizeof(sigbderlong), pubkey2b, pubkey2blen) != 1);
}
+ /* DER parsing tests. */
+ /* Zero length r/s. */
+ CHECK(secp256k1_ecdsa_verify(msg32, sigcder_zr, sizeof(sigcder_zr), pubkeyb, pubkeyblen) == -2);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigcder_zs, sizeof(sigcder_zs), pubkeyb, pubkeyblen) == -2);
+ /* Leading zeros. */
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt1, sizeof(sigbderalt1), pubkeyb, pubkeyblen) == 1);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt2, sizeof(sigbderalt2), pubkeyb, pubkeyblen) == 1);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == 1);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == 1);
+ sigbderalt3[4] = 1;
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == -2);
+ sigbderalt4[7] = 1;
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == -2);
/* Damage signature. */
sigbder[7]++;
- CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 0);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 0);
+ sigbder[7]--;
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbder, 6, pubkeyb, pubkeyblen) == -2);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder)-1, pubkeyb, pubkeyblen) == -2);
+ for(int i = 0; i<8; i++) {
+ unsigned char orig = sigbder[i];
+ /*Try every single-byte change.*/
+ for (int c=0; c<256; c++) {
+ if (c == orig ) continue;
+ sigbder[i] = c;
+ CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) ==
+ (i==4 || i==7) ? 0 : -2 );
+ }
+ sigbder[i] = orig;
+ }
}
/* Test the case where ECDSA recomputes a point that is infinity. */
@@ -1069,18 +1258,60 @@ void test_ecdsa_edge_cases(void) {
};
unsigned char pubkeyc[65];
int pubkeyclen = 65;
- CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigc64, pubkeyc, &pubkeyclen, 0, 0) == 1);
- CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 1);
+ CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyc, &pubkeyclen, 0, 0) == 1);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 1);
sigcder[4] = 0;
sigc64[31] = 0;
- CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
- CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
+ CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
sigcder[4] = 1;
sigcder[7] = 0;
sigc64[31] = 1;
sigc64[63] = 0;
- CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
- CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
+ CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
+ CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
+ }
+
+ /*Signature where s would be zero.*/
+ {
+ const unsigned char nonce[32] = {
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
+ };
+ const unsigned char key[32] = {
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
+ };
+ unsigned char msg[32] = {
+ 0x86, 0x41, 0x99, 0x81, 0x06, 0x23, 0x44, 0x53,
+ 0xaa, 0x5f, 0x9d, 0x6a, 0x31, 0x78, 0xf4, 0xf7,
+ 0xb8, 0x12, 0xe0, 0x0b, 0x81, 0x7a, 0x77, 0x62,
+ 0x65, 0xdf, 0xdd, 0x31, 0xb9, 0x3e, 0x29, 0xa9,
+ };
+ unsigned char sig[72];
+ int siglen = 72;
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce) == 0);
+ msg[31] = 0xaa;
+ siglen = 72;
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce) == 1);
+ }
+
+ /* Privkey export where pubkey is the point at infinity. */
+ {
+ unsigned char privkey[300];
+ unsigned char seckey[32] = {
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
+ 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
+ 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41,
+ };
+ int outlen = 300;
+ CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 0));
+ CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 1));
}
}
@@ -1185,8 +1416,8 @@ int main(int argc, char **argv) {
/* field tests */
run_field_inv();
run_field_inv_var();
- run_field_inv_all();
run_field_inv_all_var();
+ run_field_misc();
run_sqr();
run_sqrt();
@@ -1199,6 +1430,7 @@ int main(int argc, char **argv) {
run_ecmult_chain();
/* ecdsa tests */
+ run_random_pubkeys();
run_ecdsa_sign_verify();
run_ecdsa_end_to_end();
run_ecdsa_edge_cases();
diff --git a/src/secp256k1/src/util.h b/src/secp256k1/src/util.h
index 08b23a9d38..c3a8f3a42b 100644
--- a/src/secp256k1/src/util.h
+++ b/src/secp256k1/src/util.h
@@ -61,6 +61,12 @@
#define VERIFY_CHECK(cond) do { (void)(cond); } while(0)
#endif
+static inline void *checked_malloc(size_t size) {
+ void *ret = malloc(size);
+ CHECK(ret != NULL);
+ return ret;
+}
+
/* Macro for restrict, when available and not in a VERIFY build. */
#if defined(SECP256K1_BUILD) && defined(VERIFY)
# define SECP256K1_RESTRICT