aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2015-01-06 00:28:47 +0100
committerPieter Wuille <pieter.wuille@gmail.com>2015-01-06 00:28:47 +0100
commit7873633b5752621548b8d38fc175f5a5f2f1e5d6 (patch)
tree3b675a638355f8ccad0474900fed0bffcda8e62a
parentecae2acb06d44509425a9cdad38ed9a5bce15cbe (diff)
Squashed 'src/secp256k1/' changes from bccaf86..50cc6ab
50cc6ab Merge pull request #178 941e221 Add tests for handling of the nonce function in signing. 10c81ff Merge pull request #177 7688e34 Add magnitude limits to secp256k1_fe_verify to ensure that it's own tests function correctly. 4ee4f7a Merge pull request #176 70ae0d2 Use secp256k1_fe_equal_var in secp256k1_fe_sqrt_var. 7767b4d Merge pull request #175 9ab9335 Add a reference consistency test to ge_tests. 60571c6 Rework group tests d26e26f Avoid constructing an invalid signature with probability 1:2^256. b450c34 Merge pull request #163 d57cae9 Merge pull request #154 49ee0db Add _normalizes_to_zero_var variant eed599d Add _fe_normalizes_to_zero method d7174ed Weak normalization for secp256k1_fe_equal 0295f0a weak normalization bbd5ba7 Use rfc6979 as default nonce generation function b37fbc2 Implement SHA256 / HMAC-SHA256 / RFC6979. c6e7f4e [API BREAK] Use a nonce-generation function instead of a nonce cf0c48b Merge pull request #169 603c33b Make signing fail if a too small buffer is passed. 6d16606 Merge pull request #168 7277fd7 Remove GMP field implementation e99c4c4 Merge pull request #123 13278f6 Add explanation about how inversion can be avoided ce7eb6f Optimize verification: avoid field inverse a098f78 Merge pull request #160 38acd01 Merge pull request #165 6a59012 Make git ignore bench_recover when configured with benchmark enabled 1ba4a60 Configure options reorganization 3c0f246 Merge pull request #157 808dd9b Merge pull request #156 8dc75e9 Merge pull request #158 28ade27 build: nuke bashisms 5190079 build: use subdir-objects for automake 8336040 build: disable benchmark by default git-subtree-dir: src/secp256k1 git-subtree-split: 50cc6ab0625efda6dddf1dc86c1e2671f069b0d8
Diffstat
-rw-r--r--.gitignore1
-rw-r--r--.travis.yml14
-rw-r--r--Makefile.am4
-rw-r--r--build-aux/m4/bitcoin_secp.m420
-rw-r--r--configure.ac113
-rw-r--r--include/secp256k1.h51
-rw-r--r--src/bench_sign.c5
-rw-r--r--src/bench_verify.c4
-rw-r--r--src/ecdsa_impl.h59
-rw-r--r--src/ecmult_gen_impl.h2
-rw-r--r--src/ecmult_impl.h4
-rw-r--r--src/field.h19
-rw-r--r--src/field_10x26_impl.h111
-rw-r--r--src/field_5x52_impl.h96
-rw-r--r--src/field_gmp.h18
-rw-r--r--src/field_gmp_impl.h184
-rw-r--r--src/field_impl.h16
-rw-r--r--src/group.h7
-rw-r--r--src/group_impl.h66
-rw-r--r--src/hash.h41
-rw-r--r--src/hash_impl.h291
-rw-r--r--src/secp256k1.c73
-rw-r--r--src/tests.c502
23 files changed, 1172 insertions, 529 deletions
diff --git a/.gitignore b/.gitignore
index f0a54077a5..b9f7d243ec 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,6 +1,7 @@
bench_inv
bench_sign
bench_verify
+bench_recover
tests
*.exe
*.so
diff --git a/.travis.yml b/.travis.yml
index 28cd61dbc9..40f8dae23f 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -4,24 +4,22 @@ compiler:
- gcc
install:
- sudo apt-get install -qq libssl-dev
- - if [ "$BIGNUM" = "gmp" -o "$BIGNUM" = "auto" -o "$FIELD" = "gmp" ]; then sudo apt-get install --no-install-recommends --no-upgrade -qq libgmp-dev; fi
+ - if [ "$BIGNUM" = "gmp" -o "$BIGNUM" = "auto" ]; 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= HOST= EXTRAPACKAGES=
+ - FIELD=auto BIGNUM=auto SCALAR=auto ENDOMORPHISM=no ASM=no BUILD=check EXTRAFLAGS= HOST= EXTRAPACKAGES=
matrix:
- SCALAR=32bit
- SCALAR=64bit
- - FIELD=gmp
- - FIELD=gmp ENDOMORPHISM=yes
- - FIELD=64bit_asm
- - FIELD=64bit_asm ENDOMORPHISM=yes
- FIELD=64bit
- FIELD=64bit ENDOMORPHISM=yes
+ - FIELD=64bit ASM=x86_64
+ - FIELD=64bit ENDOMORPHISM=yes ASM=x86_64
- FIELD=32bit
- FIELD=32bit ENDOMORPHISM=yes
- - BIGNUM=none
- - BIGNUM=none ENDOMORPHISM=yes
+ - BIGNUM=no
+ - BIGNUM=no ENDOMORPHISM=yes
- BUILD=distcheck
- EXTRAFLAGS=CFLAGS=-DDETERMINISTIC
- HOST=i686-linux-gnu EXTRAPACKAGES="gcc-multilib"
diff --git a/Makefile.am b/Makefile.am
index 390d2c9ffa..985c172eba 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -33,8 +33,8 @@ noinst_HEADERS += src/java/org_bitcoin_NativeSecp256k1.h
noinst_HEADERS += src/util.h
noinst_HEADERS += src/testrand.h
noinst_HEADERS += src/testrand_impl.h
-noinst_HEADERS += src/field_gmp.h
-noinst_HEADERS += src/field_gmp_impl.h
+noinst_HEADERS += src/hash.h
+noinst_HEADERS += src/hash_impl.h
noinst_HEADERS += src/field.h
noinst_HEADERS += src/field_impl.h
noinst_HEADERS += src/bench.h
diff --git a/build-aux/m4/bitcoin_secp.m4 b/build-aux/m4/bitcoin_secp.m4
index 1373478c9c..4a398d6c93 100644
--- a/build-aux/m4/bitcoin_secp.m4
+++ b/build-aux/m4/bitcoin_secp.m4
@@ -1,12 +1,6 @@
dnl libsecp25k1 helper checks
AC_DEFUN([SECP_INT128_CHECK],[
has_int128=$ac_cv_type___int128
-if test x"$has_int128" != x"yes" && test x"$set_field" = x"64bit"; then
- AC_MSG_ERROR([$set_field field support explicitly requested but is not compatible with this host])
-fi
-if test x"$has_int128" != x"yes" && test x"$set_scalar" = x"64bit"; then
- AC_MSG_ERROR([$set_scalar scalar support explicitly requested but is not compatible with this host])
-fi
])
dnl
@@ -18,11 +12,6 @@ AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[
__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
])
dnl
@@ -43,7 +32,7 @@ else
)])
LIBS=
fi
-if test x"$has_libcrypto" == x"yes" && test x"$has_openssl_ec" = x; then
+if test x"$has_libcrypto" = x"yes" && test x"$has_openssl_ec" = x; then
AC_MSG_CHECKING(for EC functions in libcrypto)
AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[
#include <openssl/ec.h>
@@ -69,11 +58,4 @@ if test x"$has_gmp" != x"yes"; then
CPPFLAGS="$CPPFLAGS_TEMP"
LIBS="$LIBS_TEMP"
fi
-if test x"$set_field" = x"gmp" && test x"$has_gmp" != x"yes"; then
- AC_MSG_ERROR([$set_field field support explicitly requested but libgmp was not found])
-fi
-if test x"$set_bignum" = x"gmp" && test x"$has_gmp" != x"yes"; then
- AC_MSG_ERROR([$set_bignum field support explicitly requested but libgmp was not found])
-fi
])
-
diff --git a/configure.ac b/configure.ac
index 40e121e806..f691156ff7 100644
--- a/configure.ac
+++ b/configure.ac
@@ -6,7 +6,7 @@ AC_CANONICAL_HOST
AH_TOP([#ifndef LIBSECP256K1_CONFIG_H])
AH_TOP([#define LIBSECP256K1_CONFIG_H])
AH_BOTTOM([#endif //LIBSECP256K1_CONFIG_H])
-AM_INIT_AUTOMAKE([foreign])
+AM_INIT_AUTOMAKE([foreign subdir-objects])
LT_INIT
dnl make the compilation flags quiet unless V=1 is used
@@ -23,7 +23,7 @@ if test "x$CFLAGS" = "x"; then
fi
AC_PROG_CC_C99
-if test x"$ac_cv_prog_cc_c99" == x"no"; then
+if test x"$ac_cv_prog_cc_c99" = x"no"; then
AC_MSG_ERROR([c99 compiler support required])
fi
@@ -82,9 +82,9 @@ AC_COMPILE_IFELSE([AC_LANG_SOURCE([[char foo;]])],
AC_ARG_ENABLE(benchmark,
- AS_HELP_STRING([--enable-benchmark],[compile benchmark (default is yes)]),
+ AS_HELP_STRING([--enable-benchmark],[compile benchmark (default is no)]),
[use_benchmark=$enableval],
- [use_benchmark=yes])
+ [use_benchmark=no])
AC_ARG_ENABLE(tests,
AS_HELP_STRING([--enable-tests],[compile tests (default is yes)]),
@@ -96,15 +96,18 @@ AC_ARG_ENABLE(endomorphism,
[use_endomorphism=$enableval],
[use_endomorphism=no])
-AC_ARG_WITH([field], [AS_HELP_STRING([--with-field=gmp|64bit|64bit_asm|32bit|auto],
+AC_ARG_WITH([field], [AS_HELP_STRING([--with-field=64bit|32bit|auto],
[Specify Field Implementation. Default is auto])],[req_field=$withval], [req_field=auto])
-AC_ARG_WITH([bignum], [AS_HELP_STRING([--with-bignum=gmp|none|auto],
+AC_ARG_WITH([bignum], [AS_HELP_STRING([--with-bignum=gmp|no|auto],
[Specify Bignum Implementation. Default is auto])],[req_bignum=$withval], [req_bignum=auto])
AC_ARG_WITH([scalar], [AS_HELP_STRING([--with-scalar=64bit|32bit|auto],
[Specify scalar implementation. Default is auto])],[req_scalar=$withval], [req_scalar=auto])
+AC_ARG_WITH([asm], [AS_HELP_STRING([--with-asm=x86_64|no|auto]
+[Specify assembly optimizations to use. Default is auto])],[req_asm=$withval], [req_asm=auto])
+
AC_CHECK_TYPES([__int128])
AC_MSG_CHECKING([for __builtin_expect])
@@ -113,40 +116,54 @@ AC_COMPILE_IFELSE([AC_LANG_SOURCE([[void myfunc() {__builtin_expect(0,0);}]])],
[ AC_MSG_RESULT([no])
])
-if test x"$req_field" = x"auto"; then
+if test x"$req_asm" = x"auto"; then
SECP_64BIT_ASM_CHECK
if test x"$has_64bit_asm" = x"yes"; then
- set_field=64bit_asm
+ set_asm=x86_64
+ fi
+ if test x"$set_asm" = x; then
+ set_asm=no
fi
+else
+ set_asm=$req_asm
+ case $set_asm in
+ x86_64)
+ SECP_64BIT_ASM_CHECK
+ if test x"$has_64bit_asm" != x"yes"; then
+ AC_MSG_ERROR([x86_64 assembly optimization requested but not available])
+ fi
+ ;;
+ no)
+ ;;
+ *)
+ AC_MSG_ERROR([invalid assembly optimization selection])
+ ;;
+ esac
+fi
+if test x"$req_field" = x"auto"; then
+ if test x"set_asm" = x"x86_64"; then
+ set_field=64bit
+ fi
if test x"$set_field" = x; then
SECP_INT128_CHECK
if test x"$has_int128" = x"yes"; then
set_field=64bit
fi
fi
-
- if test x"$set_field" = x; then
- SECP_GMP_CHECK
- if test x"$has_gmp" = x"yes"; then
- set_field=gmp
- fi
- fi
-
if test x"$set_field" = x; then
set_field=32bit
fi
else
set_field=$req_field
case $set_field in
- 64bit_asm)
- SECP_64BIT_ASM_CHECK
- ;;
64bit)
- SECP_INT128_CHECK
- ;;
- gmp)
- SECP_GMP_CHECK
+ if test x"$set_asm" != x"x86_64"; then
+ SECP_INT128_CHECK
+ if test x"$has_int128" != x"yes"; then
+ AC_MSG_ERROR([64bit field explicitly requested but neither __int128 support or x86_64 assembly available])
+ fi
+ fi
;;
32bit)
;;
@@ -157,11 +174,9 @@ else
fi
if test x"$req_scalar" = x"auto"; then
- if test x"$set_scalar" = x; then
- SECP_INT128_CHECK
- if test x"$has_int128" = x"yes"; then
- set_scalar=64bit
- fi
+ SECP_INT128_CHECK
+ if test x"$has_int128" = x"yes"; then
+ set_scalar=64bit
fi
if test x"$set_scalar" = x; then
set_scalar=32bit
@@ -171,6 +186,9 @@ else
case $set_scalar in
64bit)
SECP_INT128_CHECK
+ if test x"$has_int128" != x"yes"; then
+ AC_MSG_ERROR([64bit scalar explicitly requested but __int128 support not available])
+ fi
;;
32bit)
;;
@@ -187,15 +205,18 @@ if test x"$req_bignum" = x"auto"; then
fi
if test x"$set_bignum" = x; then
- set_bignum=none
+ set_bignum=no
fi
else
set_bignum=$req_bignum
case $set_bignum in
gmp)
SECP_GMP_CHECK
+ if test x"$has_gmp" != x"yes"; then
+ AC_MSG_ERROR([gmp bignum explicitly requested but libgmp not available])
+ fi
;;
- none)
+ no)
;;
*)
AC_MSG_ERROR([invalid bignum implementation selection])
@@ -203,20 +224,23 @@ else
esac
fi
+# select assembly optimization
+case $set_asm in
+x86_64)
+ AC_DEFINE(USE_ASM_X86_64, 1, [Define this symbol to enable x86_64 assembly optimizations])
+ ;;
+no)
+ ;;
+*)
+ AC_MSG_ERROR([invalid assembly optimizations])
+ ;;
+esac
+
# select field implementation
case $set_field in
-64bit_asm)
- AC_DEFINE(USE_FIELD_5X52_ASM, 1, [Define this symbol to use the assembly version for the 5x52 field implementation])
- AC_DEFINE(USE_FIELD_5X52, 1, [Define this symbol to use the FIELD_5X52 implementation])
- ;;
64bit)
- AC_DEFINE(USE_FIELD_5X52_INT128, 1, [Define this symbol to use the __int128 version for the 5x52 field implementation])
AC_DEFINE(USE_FIELD_5X52, 1, [Define this symbol to use the FIELD_5X52 implementation])
;;
-gmp)
- AC_DEFINE(HAVE_LIBGMP,1,[Define this symbol if libgmp is installed])
- AC_DEFINE(USE_FIELD_GMP, 1, [Define this symbol to use the FIELD_GMP implementation])
- ;;
32bit)
AC_DEFINE(USE_FIELD_10X26, 1, [Define this symbol to use the FIELD_10X26 implementation])
;;
@@ -233,7 +257,7 @@ gmp)
AC_DEFINE(USE_FIELD_INV_NUM, 1, [Define this symbol to use the num-based field inverse implementation])
AC_DEFINE(USE_SCALAR_INV_NUM, 1, [Define this symbol to use the num-based scalar inverse implementation])
;;
-none)
+no)
AC_DEFINE(USE_NUM_NONE, 1, [Define this symbol to use no num implementation])
AC_DEFINE(USE_FIELD_INV_BUILTIN, 1, [Define this symbol to use the native field inverse implementation])
AC_DEFINE(USE_SCALAR_INV_BUILTIN, 1, [Define this symbol to use the native scalar inverse implementation])
@@ -258,7 +282,7 @@ esac
if test x"$use_tests" = x"yes"; then
SECP_OPENSSL_CHECK
- if test x"$has_openssl_ec" == x"yes"; then
+ if test x"$has_openssl_ec" = x"yes"; then
AC_DEFINE(ENABLE_OPENSSL_TESTS, 1, [Define this symbol if OpenSSL EC functions are available])
SECP_TEST_INCLUDES="$SSL_CFLAGS $CRYPTO_CFLAGS"
SECP_TEST_LIBS="$CRYPTO_LIBS"
@@ -272,7 +296,7 @@ if test x"$use_tests" = x"yes"; then
fi
fi
-if test x"$set_field" = x"gmp" || test x"$set_bignum" = x"gmp"; then
+if test x"$set_bignum" = x"gmp"; then
SECP_LIBS="$SECP_LIBS $GMP_LIBS"
SECP_INCLUDES="$SECP_INCLUDES $GMP_CPPFLAGS"
fi
@@ -281,9 +305,11 @@ if test x"$use_endomorphism" = x"yes"; then
AC_DEFINE(USE_ENDOMORPHISM, 1, [Define this symbol to use endomorphism optimization])
fi
+AC_MSG_NOTICE([Using assembly optimizations: $set_asm])
AC_MSG_NOTICE([Using field implementation: $set_field])
AC_MSG_NOTICE([Using bignum implementation: $set_bignum])
AC_MSG_NOTICE([Using scalar implementation: $set_scalar])
+AC_MSG_NOTICE([Using endomorphism optimizations: $use_endomorphism])
AC_CONFIG_HEADERS([src/libsecp256k1-config.h])
AC_CONFIG_FILES([Makefile libsecp256k1.pc])
@@ -291,9 +317,8 @@ AC_SUBST(SECP_INCLUDES)
AC_SUBST(SECP_LIBS)
AC_SUBST(SECP_TEST_LIBS)
AC_SUBST(SECP_TEST_INCLUDES)
-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"])
+AM_CONDITIONAL([USE_BENCHMARK], [test x"$use_benchmark" = x"yes"])
dnl make sure nothing new is exported so that we don't break the cache
PKGCONFIG_PATH_TEMP="$PKG_CONFIG_PATH"
diff --git a/include/secp256k1.h b/include/secp256k1.h
index dca7ca00e7..cfdae31eaf 100644
--- a/include/secp256k1.h
+++ b/include/secp256k1.h
@@ -77,42 +77,73 @@ SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_verify(
int pubkeylen
) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(4);
+/** A pointer to a function to deterministically generate a nonce.
+ * Returns: 1 if a nonce was succesfully generated. 0 will cause signing to fail.
+ * In: msg32: the 32-byte message hash being verified (will not be NULL)
+ * key32: pointer to a 32-byte secret key (will not be NULL)
+ * attempt: how many iterations we have tried to find a nonce.
+ * This will almost always be 0, but different attempt values
+ * are required to result in a different nonce.
+ * data: Arbitrary data pointer that is passed through.
+ * Out: nonce32: pointer to a 32-byte array to be filled by the function.
+ * Except for test cases, this function should compute some cryptographic hash of
+ * the message, the key and the attempt.
+ */
+typedef int (*secp256k1_nonce_function_t)(
+ unsigned char *nonce32,
+ const unsigned char *msg32,
+ const unsigned char *key32,
+ unsigned int attempt,
+ const void *data
+);
+
+/** An implementation of RFC6979 (using HMAC-SHA256) as nonce generation function. */
+extern const secp256k1_nonce_function_t secp256k1_nonce_function_rfc6979;
+
+/** A default safe nonce generation function (currently equal to secp256k1_nonce_function_rfc6979). */
+extern const secp256k1_nonce_function_t secp256k1_nonce_function_default;
+
+
/** Create an ECDSA signature.
* Returns: 1: signature created
- * 0: nonce invalid, try another one
+ * 0: the nonce generation function failed
* 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)
+ * noncefp:pointer to a nonce generation function. If NULL, secp256k1_nonce_function_default is used
+ * ndata: pointer to arbitrary data used by the nonce generation function (can be NULL)
* Out: sig: pointer to an array where the signature will be placed (cannot be NULL)
* In/Out: siglen: pointer to an int with the length of sig, which will be updated
* to contain the actual signature length (<=72).
* Requires starting using SECP256K1_START_SIGN.
*/
-SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_sign(
+int secp256k1_ecdsa_sign(
const unsigned char *msg32,
unsigned char *sig,
int *siglen,
const unsigned char *seckey,
- const unsigned char *nonce
-) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
+ secp256k1_nonce_function_t noncefp,
+ const void *ndata
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
/** Create a compact ECDSA signature (64 byte + recovery id).
* Returns: 1: signature created
- * 0: nonce invalid, try another one
+ * 0: the nonce generation function failed
* 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)
+ * noncefp:pointer to a nonce generation function. If NULL, secp256k1_nonce_function_default is used
+ * ndata: pointer to arbitrary data used by the nonce generation function (can be NULL)
* Out: sig: pointer to a 64-byte array where the signature will be placed (cannot be NULL)
* recid: pointer to an int, which will be updated to contain the recovery id (can be NULL)
* Requires starting using SECP256K1_START_SIGN.
*/
-SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_sign_compact(
+int secp256k1_ecdsa_sign_compact(
const unsigned char *msg32,
unsigned char *sig64,
const unsigned char *seckey,
- const unsigned char *nonce,
+ secp256k1_nonce_function_t noncefp,
+ const void *ndata,
int *recid
-) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
/** Recover an ECDSA public key from a compact signature.
* Returns: 1: public key successfully recovered (which guarantees a correct signature).
diff --git a/src/bench_sign.c b/src/bench_sign.c
index 66e71e1ac4..2276f00b9a 100644
--- a/src/bench_sign.c
+++ b/src/bench_sign.c
@@ -10,7 +10,6 @@
typedef struct {
unsigned char msg[32];
- unsigned char nonce[32];
unsigned char key[32];
} bench_sign_t;
@@ -18,7 +17,6 @@ static void bench_sign_setup(void* arg) {
bench_sign_t *data = (bench_sign_t*)arg;
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;
}
@@ -28,9 +26,8 @@ static void bench_sign(void* arg) {
unsigned char sig[64];
for (int i=0; i<20000; i++) {
int recid = 0;
- CHECK(secp256k1_ecdsa_sign_compact(data->msg, sig, data->key, data->nonce, &recid));
+ CHECK(secp256k1_ecdsa_sign_compact(data->msg, sig, data->key, NULL, NULL, &recid));
for (int j = 0; j < 32; j++) {
- 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. */
}
diff --git a/src/bench_verify.c b/src/bench_verify.c
index b123c4087d..a58ca84347 100644
--- a/src/bench_verify.c
+++ b/src/bench_verify.c
@@ -14,7 +14,6 @@
typedef struct {
unsigned char msg[32];
unsigned char key[32];
- unsigned char nonce[32];
unsigned char sig[72];
int siglen;
unsigned char pubkey[33];
@@ -42,9 +41,8 @@ int main(void) {
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));
+ secp256k1_ecdsa_sign(data.msg, data.sig, &data.siglen, data.key, NULL, NULL);
data.pubkeylen = 33;
CHECK(secp256k1_ec_pubkey_create(data.pubkey, &data.pubkeylen, data.key, 1));
diff --git a/src/ecdsa_impl.h b/src/ecdsa_impl.h
index 8825d05fed..674650c1e9 100644
--- a/src/ecdsa_impl.h
+++ b/src/ecdsa_impl.h
@@ -109,25 +109,53 @@ static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, int *size, const se
return 1;
}
-static int secp256k1_ecdsa_sig_recompute(secp256k1_scalar_t *r2, const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
+static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
if (secp256k1_scalar_is_zero(&sig->r) || secp256k1_scalar_is_zero(&sig->s))
return 0;
- int ret = 0;
secp256k1_scalar_t sn, u1, u2;
secp256k1_scalar_inverse_var(&sn, &sig->s);
secp256k1_scalar_mul(&u1, &sn, message);
secp256k1_scalar_mul(&u2, &sn, &sig->r);
secp256k1_gej_t pubkeyj; secp256k1_gej_set_ge(&pubkeyj, pubkey);
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_var(&xr);
- unsigned char xrb[32]; secp256k1_fe_get_b32(xrb, &xr);
- secp256k1_scalar_set_b32(r2, xrb, NULL);
- ret = 1;
+ if (secp256k1_gej_is_infinity(&pr)) {
+ return 0;
+ }
+ unsigned char c[32];
+ secp256k1_scalar_get_b32(c, &sig->r);
+ secp256k1_fe_t xr;
+ secp256k1_fe_set_b32(&xr, c);
+
+ // We now have the recomputed R point in pr, and its claimed x coordinate (modulo n)
+ // in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p),
+ // compute the remainder modulo n, and compare it to xr. However:
+ //
+ // xr == X(pr) mod n
+ // <=> exists h. (xr + h * n < p && xr + h * n == X(pr))
+ // [Since 2 * n > p, h can only be 0 or 1]
+ // <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr))
+ // [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p]
+ // <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p)
+ // [Multiplying both sides of the equations by pr.z^2 mod p]
+ // <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)
+ //
+ // Thus, we can avoid the inversion, but we have to check both cases separately.
+ // secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.
+ if (secp256k1_gej_eq_x_var(&xr, &pr)) {
+ // xr.x == xr * xr.z^2 mod p, so the signature is valid.
+ return 1;
+ }
+ if (secp256k1_fe_cmp_var(&xr, &secp256k1_ecdsa_consts->p_minus_order) >= 0) {
+ // xr + p >= n, so we can skip testing the second case.
+ return 0;
+ }
+ secp256k1_fe_add(&xr, &secp256k1_ecdsa_consts->order_as_fe);
+ if (secp256k1_gej_eq_x_var(&xr, &pr)) {
+ // (xr + n) * pr.z^2 mod p == pr.x, so the signature is valid.
+ return 1;
}
- return ret;
+ return 0;
}
static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message, int recid) {
@@ -159,13 +187,6 @@ static int secp256k1_ecdsa_sig_recover(const secp256k1_ecdsa_sig_t *sig, secp256
return !secp256k1_gej_is_infinity(&qj);
}
-static int secp256k1_ecdsa_sig_verify(const secp256k1_ecdsa_sig_t *sig, const secp256k1_ge_t *pubkey, const secp256k1_scalar_t *message) {
- secp256k1_scalar_t r2;
- int ret = 0;
- ret = secp256k1_ecdsa_sig_recompute(&r2, sig, pubkey, message) && secp256k1_scalar_eq(&sig->r, &r2);
- return ret;
-}
-
static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *seckey, const secp256k1_scalar_t *message, const secp256k1_scalar_t *nonce, int *recid) {
secp256k1_gej_t rp;
secp256k1_ecmult_gen(&rp, nonce);
@@ -177,6 +198,12 @@ static int secp256k1_ecdsa_sig_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_
secp256k1_fe_get_b32(b, &r.x);
int overflow = 0;
secp256k1_scalar_set_b32(&sig->r, b, &overflow);
+ if (secp256k1_scalar_is_zero(&sig->r)) {
+ /* P.x = order is on the curve, so technically sig->r could end up zero, which would be an invalid signature. */
+ secp256k1_gej_clear(&rp);
+ secp256k1_ge_clear(&r);
+ return 0;
+ }
if (recid)
*recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
secp256k1_scalar_t n;
diff --git a/src/ecmult_gen_impl.h b/src/ecmult_gen_impl.h
index 5a5b16ce14..48436316e1 100644
--- a/src/ecmult_gen_impl.h
+++ b/src/ecmult_gen_impl.h
@@ -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_var(&numsbase, &numsbase);
+ secp256k1_gej_neg(&numsbase, &numsbase);
secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej);
}
}
diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h
index 6536771046..345cfae733 100644
--- a/src/ecmult_impl.h
+++ b/src/ecmult_impl.h
@@ -70,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_var)
-#define ECMULT_TABLE_GET_GE(r,pre,n,w) ECMULT_TABLE_GET((r),(pre),(n),(w),secp256k1_ge_neg_var)
+#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)
typedef struct {
/* For accelerating the computation of a*P + b*G: */
diff --git a/src/field.h b/src/field.h
index 53aa29e13f..14e2b813c1 100644
--- a/src/field.h
+++ b/src/field.h
@@ -22,9 +22,7 @@
#include "libsecp256k1-config.h"
#endif
-#if defined(USE_FIELD_GMP)
-#include "field_gmp.h"
-#elif defined(USE_FIELD_10X26)
+#if defined(USE_FIELD_10X26)
#include "field_10x26.h"
#elif defined(USE_FIELD_5X52)
#include "field_5x52.h"
@@ -50,9 +48,20 @@ static void secp256k1_fe_stop(void);
/** Normalize a field element. */
static void secp256k1_fe_normalize(secp256k1_fe_t *r);
+/** Weakly normalize a field element: reduce it magnitude to 1, but don't fully normalize. */
+static void secp256k1_fe_normalize_weak(secp256k1_fe_t *r);
+
/** Normalize a field element, without constant-time guarantee. */
static void secp256k1_fe_normalize_var(secp256k1_fe_t *r);
+/** Verify whether a field element represents zero i.e. would normalize to a zero value. The field
+ * implementation may optionally normalize the input, but this should not be relied upon. */
+static int secp256k1_fe_normalizes_to_zero(secp256k1_fe_t *r);
+
+/** Verify whether a field element represents zero i.e. would normalize to a zero value. The field
+ * implementation may optionally normalize the input, but this should not be relied upon. */
+static int secp256k1_fe_normalizes_to_zero_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);
@@ -62,8 +71,8 @@ static int secp256k1_fe_is_zero(const secp256k1_fe_t *a);
/** Check the "oddness" of a field element. Requires the input to be normalized. */
static int secp256k1_fe_is_odd(const secp256k1_fe_t *a);
-/** Compare two field elements. Requires both inputs to be normalized */
-static int secp256k1_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b);
+/** Compare two field elements. Requires magnitude-1 inputs. */
+static int secp256k1_fe_equal_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b);
/** Compare two field elements. Requires both inputs to be normalized */
static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b);
diff --git a/src/field_10x26_impl.h b/src/field_10x26_impl.h
index d20229cda6..9ef60a807a 100644
--- a/src/field_10x26_impl.h
+++ b/src/field_10x26_impl.h
@@ -31,6 +31,7 @@ static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
r &= (d[8] <= 0x3FFFFFFUL * m);
r &= (d[9] <= 0x03FFFFFUL * m);
r &= (a->magnitude >= 0);
+ r &= (a->magnitude <= 32);
if (a->normalized) {
r &= (a->magnitude <= 1);
if (r && (d[9] == 0x03FFFFFUL)) {
@@ -103,6 +104,37 @@ static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
#endif
}
+static void secp256k1_fe_normalize_weak(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;
+
+ /* 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;
+ 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;
+
+ /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t9 >> 23 == 0);
+
+ 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;
+ secp256k1_fe_verify(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];
@@ -159,6 +191,73 @@ static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
#endif
}
+static int secp256k1_fe_normalizes_to_zero(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;
+
+ /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
+ uint32_t z0, z1;
+
+ /* The first pass ensures the magnitude is 1, ... */
+ t0 += x * 0x3D1UL; t1 += (x << 6);
+ t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL; z0 = t0; z1 = t0 ^ 0x3D0UL;
+ t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL; z0 |= t1; z1 &= t1 ^ 0x40UL;
+ t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; z0 |= t2; z1 &= t2;
+ t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; z0 |= t3; z1 &= t3;
+ t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; z0 |= t4; z1 &= t4;
+ t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; z0 |= t5; z1 &= t5;
+ t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; z0 |= t6; z1 &= t6;
+ t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; z0 |= t7; z1 &= t7;
+ t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; z0 |= t8; z1 &= t8;
+ z0 |= t9; z1 &= t9 ^ 0x3C00000UL;
+
+ /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t9 >> 23 == 0);
+
+ return (z0 == 0) | (z1 == 0x3FFFFFFUL);
+}
+
+static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe_t *r) {
+ uint32_t t0 = r->n[0], 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;
+
+ /* The first pass ensures the magnitude is 1, ... */
+ t0 += x * 0x3D1UL;
+
+ /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
+ uint32_t z0 = t0 & 0x3FFFFFFUL, z1 = z0 ^ 0x3D0UL;
+
+ /* Fast return path should catch the majority of cases */
+ if ((z0 != 0UL) & (z1 != 0x3FFFFFFUL))
+ return 0;
+
+ uint32_t 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 &= 0x03FFFFFUL;
+ t1 += (x << 6);
+
+ t1 += (t0 >> 26); t0 = z0;
+ t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL; z0 |= t1; z1 &= t1 ^ 0x40UL;
+ t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; z0 |= t2; z1 &= t2;
+ t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; z0 |= t3; z1 &= t3;
+ t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; z0 |= t4; z1 &= t4;
+ t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; z0 |= t5; z1 &= t5;
+ t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; z0 |= t6; z1 &= t6;
+ t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; z0 |= t7; z1 &= t7;
+ t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; z0 |= t8; z1 &= t8;
+ z0 |= t9; z1 &= t9 ^ 0x3C00000UL;
+
+ /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t9 >> 23 == 0);
+
+ return (z0 == 0) | (z1 == 0x3FFFFFFUL);
+}
+
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;
@@ -196,18 +295,6 @@ SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe_t *a) {
}
}
-SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
-#ifdef VERIFY
- VERIFY_CHECK(a->normalized);
- VERIFY_CHECK(b->normalized);
- secp256k1_fe_verify(a);
- secp256k1_fe_verify(b);
-#endif
- const uint32_t *t = a->n, *u = b->n;
- return ((t[0]^u[0]) | (t[1]^u[1]) | (t[2]^u[2]) | (t[3]^u[3]) | (t[4]^u[4])
- | (t[5]^u[5]) | (t[6]^u[6]) | (t[7]^u[7]) | (t[8]^u[8]) | (t[9]^u[9])) == 0;
-}
-
static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
diff --git a/src/field_5x52_impl.h b/src/field_5x52_impl.h
index 63176d6de4..4db9e6f5ff 100644
--- a/src/field_5x52_impl.h
+++ b/src/field_5x52_impl.h
@@ -16,12 +16,10 @@
#include "num.h"
#include "field.h"
-#if defined(USE_FIELD_5X52_ASM)
+#if defined(USE_ASM_X86_64)
#include "field_5x52_asm_impl.h"
-#elif defined(USE_FIELD_5X52_INT128)
-#include "field_5x52_int128_impl.h"
#else
-#error "Please select field_5x52 implementation"
+#include "field_5x52_int128_impl.h"
#endif
/** Implements arithmetic modulo FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F,
@@ -45,6 +43,7 @@ static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
r &= (d[3] <= 0xFFFFFFFFFFFFFULL * m);
r &= (d[4] <= 0x0FFFFFFFFFFFFULL * m);
r &= (a->magnitude >= 0);
+ r &= (a->magnitude <= 2048);
if (a->normalized) {
r &= (a->magnitude <= 1);
if (r && (d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
@@ -102,6 +101,30 @@ static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
#endif
}
+static void secp256k1_fe_normalize_weak(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;
+
+ /* The first pass ensures the magnitude is 1, ... */
+ t0 += x * 0x1000003D1ULL;
+ t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
+ t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
+ t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
+ t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
+
+ /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t4 >> 49 == 0);
+
+ 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;
+ secp256k1_fe_verify(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];
@@ -146,6 +169,60 @@ static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
#endif
}
+static int secp256k1_fe_normalizes_to_zero(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;
+
+ /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
+ uint64_t z0, z1;
+
+ /* The first pass ensures the magnitude is 1, ... */
+ t0 += x * 0x1000003D1ULL;
+ t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL; z0 = t0; z1 = t0 ^ 0x1000003D0ULL;
+ t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
+ t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
+ t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
+ z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;
+
+ /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t4 >> 49 == 0);
+
+ return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
+}
+
+static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe_t *r) {
+ uint64_t t0 = r->n[0], 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;
+
+ /* The first pass ensures the magnitude is 1, ... */
+ t0 += x * 0x1000003D1ULL;
+
+ /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
+ uint64_t z0 = t0 & 0xFFFFFFFFFFFFFULL, z1 = z0 ^ 0x1000003D0ULL;
+
+ /* Fast return path should catch the majority of cases */
+ if ((z0 != 0ULL) & (z1 != 0xFFFFFFFFFFFFFULL))
+ return 0;
+
+ uint64_t t1 = r->n[1], t2 = r->n[2], t3 = r->n[3];
+ t4 &= 0x0FFFFFFFFFFFFULL;
+
+ t1 += (t0 >> 52); t0 = z0;
+ t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
+ t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
+ t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
+ z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;
+
+ /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
+ VERIFY_CHECK(t4 >> 49 == 0);
+
+ return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
+}
+
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;
@@ -183,17 +260,6 @@ SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe_t *a) {
}
}
-SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
-#ifdef VERIFY
- VERIFY_CHECK(a->normalized);
- VERIFY_CHECK(b->normalized);
- secp256k1_fe_verify(a);
- secp256k1_fe_verify(b);
-#endif
- const uint64_t *t = a->n, *u = b->n;
- return ((t[0]^u[0]) | (t[1]^u[1]) | (t[2]^u[2]) | (t[3]^u[3]) | (t[4]^u[4])) == 0;
-}
-
static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
#ifdef VERIFY
VERIFY_CHECK(a->normalized);
diff --git a/src/field_gmp.h b/src/field_gmp.h
deleted file mode 100644
index b390fd9de8..0000000000
--- a/src/field_gmp.h
+++ /dev/null
@@ -1,18 +0,0 @@
-/**********************************************************************
- * Copyright (c) 2013, 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_FIELD_REPR_
-#define _SECP256K1_FIELD_REPR_
-
-#include <gmp.h>
-
-#define FIELD_LIMBS ((256 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
-
-typedef struct {
- mp_limb_t n[FIELD_LIMBS+1];
-} secp256k1_fe_t;
-
-#endif
diff --git a/src/field_gmp_impl.h b/src/field_gmp_impl.h
deleted file mode 100644
index 73a55c4f00..0000000000
--- a/src/field_gmp_impl.h
+++ /dev/null
@@ -1,184 +0,0 @@
-/**********************************************************************
- * Copyright (c) 2013, 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_FIELD_REPR_IMPL_H_
-#define _SECP256K1_FIELD_REPR_IMPL_H_
-
-#include <stdio.h>
-#include <string.h>
-#include "num.h"
-#include "field.h"
-
-static mp_limb_t secp256k1_field_p[FIELD_LIMBS];
-static mp_limb_t secp256k1_field_pc[(33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS];
-
-static void secp256k1_fe_inner_start(void) {
- for (int i=0; i<(33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS; i++)
- secp256k1_field_pc[i] = 0;
- secp256k1_field_pc[0] += 0x3D1UL;
- secp256k1_field_pc[32/GMP_NUMB_BITS] += (((mp_limb_t)1) << (32 % GMP_NUMB_BITS));
- for (int i=0; i<FIELD_LIMBS; i++) {
- secp256k1_field_p[i] = 0;
- }
- mpn_sub(secp256k1_field_p, secp256k1_field_p, FIELD_LIMBS, secp256k1_field_pc, (33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS);
-}
-
-static void secp256k1_fe_inner_stop(void) {
-}
-
-static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
- if (r->n[FIELD_LIMBS] != 0) {
-#if (GMP_NUMB_BITS >= 40)
- mp_limb_t carry = mpn_add_1(r->n, r->n, FIELD_LIMBS, 0x1000003D1ULL * r->n[FIELD_LIMBS]);
- mpn_add_1(r->n, r->n, FIELD_LIMBS, 0x1000003D1ULL * carry);
-#else
- mp_limb_t carry = mpn_add_1(r->n, r->n, FIELD_LIMBS, 0x3D1UL * r->n[FIELD_LIMBS]) +
- mpn_add_1(r->n+(32/GMP_NUMB_BITS), r->n+(32/GMP_NUMB_BITS), FIELD_LIMBS-(32/GMP_NUMB_BITS), r->n[FIELD_LIMBS] << (32 % GMP_NUMB_BITS));
- mpn_add_1(r->n, r->n, FIELD_LIMBS, 0x3D1UL * carry);
- mpn_add_1(r->n+(32/GMP_NUMB_BITS), r->n+(32/GMP_NUMB_BITS), FIELD_LIMBS-(32/GMP_NUMB_BITS), carry << (32%GMP_NUMB_BITS));
-#endif
- r->n[FIELD_LIMBS] = 0;
- }
- if (mpn_cmp(r->n, secp256k1_field_p, FIELD_LIMBS) >= 0)
- 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++)
- r->n[i] = 0;
-}
-
-SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe_t *r) {
- for (int i=0; i<FIELD_LIMBS+1; i++)
- r->n[i] = 0;
-}
-
-SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe_t *a) {
- int ret = 1;
- for (int i=0; i<FIELD_LIMBS+1; i++)
- ret &= (a->n[i] == 0);
- return ret;
-}
-
-SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe_t *a) {
- return a->n[0] & 1;
-}
-
-SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
- int ret = 1;
- for (int i=0; i<FIELD_LIMBS+1; i++)
- ret &= (a->n[i] == b->n[i]);
- return ret;
-}
-
-SECP256K1_INLINE static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
- for (int i=FIELD_LIMBS; i>=0; i--) {
- if (a->n[i] > b->n[i]) return 1;
- if (a->n[i] < b->n[i]) return -1;
- }
- return 0;
-}
-
-static int secp256k1_fe_set_b32(secp256k1_fe_t *r, const unsigned char *a) {
- for (int i=0; i<FIELD_LIMBS+1; i++)
- r->n[i] = 0;
- for (int i=0; i<256; i++) {
- int limb = i/GMP_NUMB_BITS;
- int shift = i%GMP_NUMB_BITS;
- r->n[limb] |= (mp_limb_t)((a[31-i/8] >> (i%8)) & 0x1) << shift;
- }
- return (mpn_cmp(r->n, secp256k1_field_p, FIELD_LIMBS) < 0);
-}
-
-/** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
-static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe_t *a) {
- for (int i=0; i<32; i++) {
- int c = 0;
- for (int j=0; j<8; j++) {
- int limb = (8*i+j)/GMP_NUMB_BITS;
- int shift = (8*i+j)%GMP_NUMB_BITS;
- c |= ((a->n[limb] >> shift) & 0x1) << j;
- }
- r[31-i] = c;
- }
-}
-
-SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe_t *r, const secp256k1_fe_t *a, int m) {
- (void)m;
- *r = *a;
- secp256k1_fe_normalize(r);
- for (int i=0; i<FIELD_LIMBS; i++)
- r->n[i] = ~(r->n[i]);
-#if (GMP_NUMB_BITS >= 33)
- mpn_sub_1(r->n, r->n, FIELD_LIMBS, 0x1000003D0ULL);
-#else
- mpn_sub_1(r->n, r->n, FIELD_LIMBS, 0x3D0UL);
- mpn_sub_1(r->n+(32/GMP_NUMB_BITS), r->n+(32/GMP_NUMB_BITS), FIELD_LIMBS-(32/GMP_NUMB_BITS), 0x1UL << (32%GMP_NUMB_BITS));
-#endif
-}
-
-SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe_t *r, int a) {
- mpn_mul_1(r->n, r->n, FIELD_LIMBS+1, a);
-}
-
-SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
- mpn_add(r->n, r->n, FIELD_LIMBS+1, a->n, FIELD_LIMBS+1);
-}
-
-static void secp256k1_fe_reduce(secp256k1_fe_t *r, mp_limb_t *tmp) {
- /** <A1 A2 A3 A4> <B1 B2 B3 B4>
- * B1 B2 B3 B4
- * + C * A1 A2 A3 A4
- * + A1 A2 A3 A4
- */
-
-#if (GMP_NUMB_BITS >= 33)
- mp_limb_t o = mpn_addmul_1(tmp, tmp+FIELD_LIMBS, FIELD_LIMBS, 0x1000003D1ULL);
-#else
- mp_limb_t o = mpn_addmul_1(tmp, tmp+FIELD_LIMBS, FIELD_LIMBS, 0x3D1UL) +
- mpn_addmul_1(tmp+(32/GMP_NUMB_BITS), tmp+FIELD_LIMBS, FIELD_LIMBS-(32/GMP_NUMB_BITS), 0x1UL << (32%GMP_NUMB_BITS));
-#endif
- mp_limb_t q[1+(33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS];
- q[(33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS] = mpn_mul_1(q, secp256k1_field_pc, (33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS, o);
-#if (GMP_NUMB_BITS <= 32)
- mp_limb_t o2 = tmp[2*FIELD_LIMBS-(32/GMP_NUMB_BITS)] << (32%GMP_NUMB_BITS);
- q[(33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS] += mpn_addmul_1(q, secp256k1_field_pc, (33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS, o2);
-#endif
- r->n[FIELD_LIMBS] = mpn_add(r->n, tmp, FIELD_LIMBS, q, 1+(33+GMP_NUMB_BITS-1)/GMP_NUMB_BITS);
-}
-
-static void secp256k1_fe_mul(secp256k1_fe_t *r, const secp256k1_fe_t *a, const secp256k1_fe_t * SECP256K1_RESTRICT b) {
- VERIFY_CHECK(r != b);
- secp256k1_fe_t ac = *a;
- secp256k1_fe_t bc = *b;
- secp256k1_fe_normalize(&ac);
- secp256k1_fe_normalize(&bc);
- mp_limb_t tmp[2*FIELD_LIMBS];
- mpn_mul_n(tmp, ac.n, bc.n, FIELD_LIMBS);
- secp256k1_fe_reduce(r, tmp);
-}
-
-static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
- secp256k1_fe_t ac = *a;
- secp256k1_fe_normalize(&ac);
- mp_limb_t tmp[2*FIELD_LIMBS];
- mpn_sqr(tmp, ac.n, FIELD_LIMBS);
- secp256k1_fe_reduce(r, tmp);
-}
-
-static void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int flag) {
- mp_limb_t mask0 = flag + ~((mp_limb_t)0), mask1 = ~mask0;
- for (int i = 0; i <= FIELD_LIMBS; i++) {
- r->n[i] = (r->n[i] & mask0) | (a->n[i] & mask1);
- }
-}
-
-#endif
diff --git a/src/field_impl.h b/src/field_impl.h
index 24d3104ed1..4e2c24aa15 100644
--- a/src/field_impl.h
+++ b/src/field_impl.h
@@ -13,9 +13,7 @@
#include "util.h"
-#if defined(USE_FIELD_GMP)
-#include "field_gmp_impl.h"
-#elif defined(USE_FIELD_10X26)
+#if defined(USE_FIELD_10X26)
#include "field_10x26_impl.h"
#elif defined(USE_FIELD_5X52)
#include "field_5x52_impl.h"
@@ -66,6 +64,13 @@ static int secp256k1_fe_set_hex(secp256k1_fe_t *r, const char *a, int alen) {
return secp256k1_fe_set_b32(r, tmp);
}
+SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
+ secp256k1_fe_t na;
+ secp256k1_fe_negate(&na, a, 1);
+ secp256k1_fe_add(&na, b);
+ return secp256k1_fe_normalizes_to_zero_var(&na);
+}
+
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
@@ -130,10 +135,7 @@ static int secp256k1_fe_sqrt_var(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
/* Check that a square root was actually calculated */
secp256k1_fe_sqr(&t1, r);
- secp256k1_fe_negate(&t1, &t1, 1);
- secp256k1_fe_add(&t1, a);
- secp256k1_fe_normalize_var(&t1);
- return secp256k1_fe_is_zero(&t1);
+ return secp256k1_fe_equal_var(&t1, a);
}
static void secp256k1_fe_inv(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
diff --git a/src/group.h b/src/group.h
index ecfebcdc0c..6dea6bb5ac 100644
--- a/src/group.h
+++ b/src/group.h
@@ -60,7 +60,6 @@ static int secp256k1_ge_is_infinity(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);
@@ -81,11 +80,11 @@ static void secp256k1_gej_set_xy(secp256k1_gej_t *r, const secp256k1_fe_t *x, co
/** Set a group element (jacobian) equal to another which is given in affine coordinates. */
static void secp256k1_gej_set_ge(secp256k1_gej_t *r, const secp256k1_ge_t *a);
-/** Get the X coordinate of a group element (jacobian). */
-static void secp256k1_gej_get_x_var(secp256k1_fe_t *r, const secp256k1_gej_t *a);
+/** Compare the X coordinate of a group element (jacobian). */
+static int secp256k1_gej_eq_x_var(const secp256k1_fe_t *x, 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_var(secp256k1_gej_t *r, const secp256k1_gej_t *a);
+static void secp256k1_gej_neg(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/group_impl.h b/src/group_impl.h
index 1ab5d5fe7b..fef06df289 100644
--- a/src/group_impl.h
+++ b/src/group_impl.h
@@ -29,13 +29,7 @@ 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 = *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_normalize_weak(&r->y);
secp256k1_fe_negate(&r->y, &r->y, 1);
}
@@ -163,17 +157,19 @@ static void secp256k1_gej_set_ge(secp256k1_gej_t *r, const secp256k1_ge_t *a) {
secp256k1_fe_set_int(&r->z, 1);
}
-static void secp256k1_gej_get_x_var(secp256k1_fe_t *r, const secp256k1_gej_t *a) {
- secp256k1_fe_t zi2; secp256k1_fe_inv_var(&zi2, &a->z); secp256k1_fe_sqr(&zi2, &zi2);
- secp256k1_fe_mul(r, &a->x, &zi2);
+static int secp256k1_gej_eq_x_var(const secp256k1_fe_t *x, const secp256k1_gej_t *a) {
+ VERIFY_CHECK(!a->infinity);
+ secp256k1_fe_t r; secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
+ secp256k1_fe_t r2 = a->x; secp256k1_fe_normalize_weak(&r2);
+ return secp256k1_fe_equal_var(&r, &r2);
}
-static void secp256k1_gej_neg_var(secp256k1_gej_t *r, const secp256k1_gej_t *a) {
+static void secp256k1_gej_neg(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_var(&r->y);
+ secp256k1_fe_normalize_weak(&r->y);
secp256k1_fe_negate(&r->y, &r->y, 1);
}
@@ -195,9 +191,8 @@ static int secp256k1_gej_is_valid_var(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_var(&y2);
- secp256k1_fe_normalize_var(&x3);
- return secp256k1_fe_equal(&y2, &x3);
+ secp256k1_fe_normalize_weak(&x3);
+ return secp256k1_fe_equal_var(&y2, &x3);
}
static int secp256k1_ge_is_valid_var(const secp256k1_ge_t *a) {
@@ -208,9 +203,8 @@ static int secp256k1_ge_is_valid_var(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_var(&y2);
- secp256k1_fe_normalize_var(&x3);
- return secp256k1_fe_equal(&y2, &x3);
+ secp256k1_fe_normalize_weak(&x3);
+ return secp256k1_fe_equal_var(&y2, &x3);
}
static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *a) {
@@ -261,20 +255,16 @@ 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_var(&u1);
- secp256k1_fe_normalize_var(&u2);
- if (secp256k1_fe_equal(&u1, &u2)) {
- secp256k1_fe_normalize_var(&s1);
- secp256k1_fe_normalize_var(&s2);
- if (secp256k1_fe_equal(&s1, &s2)) {
+ secp256k1_fe_t h; secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
+ secp256k1_fe_t i; secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
+ if (secp256k1_fe_normalizes_to_zero_var(&h)) {
+ if (secp256k1_fe_normalizes_to_zero_var(&i)) {
secp256k1_gej_double_var(r, a);
} else {
r->infinity = 1;
}
return;
}
- secp256k1_fe_t h; secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
- secp256k1_fe_t i; secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
secp256k1_fe_t i2; secp256k1_fe_sqr(&i2, &i);
secp256k1_fe_t h2; secp256k1_fe_sqr(&h2, &h);
secp256k1_fe_t h3; secp256k1_fe_mul(&h3, &h, &h2);
@@ -300,23 +290,20 @@ 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_t u1 = a->x; secp256k1_fe_normalize_weak(&u1);
secp256k1_fe_t u2; secp256k1_fe_mul(&u2, &b->x, &z12);
- secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize_var(&s1);
+ secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize_weak(&s1);
secp256k1_fe_t s2; secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
- secp256k1_fe_normalize_var(&u1);
- secp256k1_fe_normalize_var(&u2);
- if (secp256k1_fe_equal(&u1, &u2)) {
- secp256k1_fe_normalize_var(&s2);
- if (secp256k1_fe_equal(&s1, &s2)) {
+ secp256k1_fe_t h; secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
+ secp256k1_fe_t i; secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
+ if (secp256k1_fe_normalizes_to_zero_var(&h)) {
+ if (secp256k1_fe_normalizes_to_zero_var(&i)) {
secp256k1_gej_double_var(r, a);
} else {
r->infinity = 1;
}
return;
}
- secp256k1_fe_t h; secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
- secp256k1_fe_t i; secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
secp256k1_fe_t i2; secp256k1_fe_sqr(&i2, &i);
secp256k1_fe_t h2; secp256k1_fe_sqr(&h2, &h);
secp256k1_fe_t h3; secp256k1_fe_mul(&h3, &h, &h2);
@@ -355,9 +342,9 @@ static void secp256k1_gej_add_ge(secp256k1_gej_t *r, const secp256k1_gej_t *a, c
*/
secp256k1_fe_t zz; secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */
- secp256k1_fe_t u1 = a->x; secp256k1_fe_normalize(&u1); /* u1 = U1 = X1*Z2^2 (1) */
+ secp256k1_fe_t u1 = a->x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */
secp256k1_fe_t u2; secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */
- secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize(&s1); /* s1 = S1 = Y1*Z2^3 (1) */
+ secp256k1_fe_t s1 = a->y; secp256k1_fe_normalize_weak(&s1); /* s1 = S1 = Y1*Z2^3 (1) */
secp256k1_fe_t s2; secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z2^2 (1) */
secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */
secp256k1_fe_t z = a->z; /* z = Z = Z1*Z2 (8) */
@@ -371,8 +358,7 @@ static void secp256k1_gej_add_ge(secp256k1_gej_t *r, const secp256k1_gej_t *a, c
secp256k1_fe_add(&rr, &t); /* rr = R = T^2-U1*U2 (3) */
secp256k1_fe_sqr(&t, &rr); /* t = R^2 (1) */
secp256k1_fe_mul(&r->z, &m, &z); /* r->z = M*Z (1) */
- secp256k1_fe_normalize(&r->z);
- int infinity = secp256k1_fe_is_zero(&r->z) * (1 - a->infinity);
+ int infinity = secp256k1_fe_normalizes_to_zero(&r->z) * (1 - a->infinity);
secp256k1_fe_mul_int(&r->z, 2 * (1 - a->infinity)); /* r->z = Z3 = 2*M*Z (2) */
r->x = t; /* r->x = R^2 (1) */
secp256k1_fe_negate(&q, &q, 1); /* q = -Q (2) */
@@ -384,7 +370,7 @@ static void secp256k1_gej_add_ge(secp256k1_gej_t *r, const secp256k1_gej_t *a, c
secp256k1_fe_mul(&t, &t, &rr); /* t = R*(2*R^2-3*Q) (1) */
secp256k1_fe_add(&t, &n); /* t = R*(2*R^2-3*Q)+M^4 (2) */
secp256k1_fe_negate(&r->y, &t, 2); /* r->y = R*(3*Q-2*R^2)-M^4 (3) */
- secp256k1_fe_normalize(&r->y);
+ secp256k1_fe_normalize_weak(&r->y);
secp256k1_fe_mul_int(&r->x, 4 * (1 - a->infinity)); /* r->x = X3 = 4*(R^2-Q) */
secp256k1_fe_mul_int(&r->y, 4 * (1 - a->infinity)); /* r->y = Y3 = 4*R*(3*Q-2*R^2)-4*M^4 (4) */
diff --git a/src/hash.h b/src/hash.h
new file mode 100644
index 0000000000..d1e65b968a
--- /dev/null
+++ b/src/hash.h
@@ -0,0 +1,41 @@
+/**********************************************************************
+ * 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_HASH_
+#define _SECP256K1_HASH_
+
+#include <stdlib.h>
+#include <stdint.h>
+
+typedef struct {
+ uint32_t s[32];
+ unsigned char buf[64];
+ size_t bytes;
+} secp256k1_sha256_t;
+
+static void secp256k1_sha256_initialize(secp256k1_sha256_t *hash);
+static void secp256k1_sha256_write(secp256k1_sha256_t *hash, const unsigned char *data, size_t size);
+static void secp256k1_sha256_finalize(secp256k1_sha256_t *hash, unsigned char *out32);
+
+typedef struct {
+ secp256k1_sha256_t inner, outer;
+} secp256k1_hmac_sha256_t;
+
+static void secp256k1_hmac_sha256_initialize(secp256k1_hmac_sha256_t *hash, const unsigned char *key, size_t size);
+static void secp256k1_hmac_sha256_write(secp256k1_hmac_sha256_t *hash, const unsigned char *data, size_t size);
+static void secp256k1_hmac_sha256_finalize(secp256k1_hmac_sha256_t *hash, unsigned char *out32);
+
+typedef struct {
+ unsigned char v[32];
+ unsigned char k[32];
+ int retry;
+} secp256k1_rfc6979_hmac_sha256_t;
+
+static void secp256k1_rfc6979_hmac_sha256_initialize(secp256k1_rfc6979_hmac_sha256_t *rng, const unsigned char *key, size_t keylen, const unsigned char *msg, size_t msglen);
+static void secp256k1_rfc6979_hmac_sha256_generate(secp256k1_rfc6979_hmac_sha256_t *rng, unsigned char *out, size_t outlen);
+static void secp256k1_rfc6979_hmac_sha256_finalize(secp256k1_rfc6979_hmac_sha256_t *rng);
+
+#endif
diff --git a/src/hash_impl.h b/src/hash_impl.h
new file mode 100644
index 0000000000..f35c5f7a82
--- /dev/null
+++ b/src/hash_impl.h
@@ -0,0 +1,291 @@
+/**********************************************************************
+ * 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_HASH_IMPL_H_
+#define _SECP256K1_HASH_IMPL_H_
+
+#include "hash.h"
+
+#include <stdlib.h>
+#include <stdint.h>
+
+#define Ch(x,y,z) ((z) ^ ((x) & ((y) ^ (z))))
+#define Maj(x,y,z) (((x) & (y)) | ((z) & ((x) | (y))))
+#define Sigma0(x) (((x) >> 2 | (x) << 30) ^ ((x) >> 13 | (x) << 19) ^ ((x) >> 22 | (x) << 10))
+#define Sigma1(x) (((x) >> 6 | (x) << 26) ^ ((x) >> 11 | (x) << 21) ^ ((x) >> 25 | (x) << 7))
+#define sigma0(x) (((x) >> 7 | (x) << 25) ^ ((x) >> 18 | (x) << 14) ^ ((x) >> 3))
+#define sigma1(x) (((x) >> 17 | (x) << 15) ^ ((x) >> 19 | (x) << 13) ^ ((x) >> 10))
+
+#define Round(a,b,c,d,e,f,g,h,k,w) do { \
+ uint32_t t1 = (h) + Sigma1(e) + Ch((e), (f), (g)) + (k) + (w); \
+ uint32_t t2 = Sigma0(a) + Maj((a), (b), (c)); \
+ (d) += t1; \
+ (h) = t1 + t2; \
+} while(0)
+
+#define ReadBE32(p) (((uint32_t)((p)[0])) << 24 | ((uint32_t)((p)[1])) << 16 | ((uint32_t)((p)[2])) << 8 | ((uint32_t)((p)[3])))
+#define WriteBE32(p, v) do { (p)[0] = (v) >> 24; (p)[1] = (v) >> 16; (p)[2] = (v) >> 8; (p)[3] = (v); } while(0)
+
+static void secp256k1_sha256_initialize(secp256k1_sha256_t *hash) {
+ hash->s[0] = 0x6a09e667ul;
+ hash->s[1] = 0xbb67ae85ul;
+ hash->s[2] = 0x3c6ef372ul;
+ hash->s[3] = 0xa54ff53aul;
+ hash->s[4] = 0x510e527ful;
+ hash->s[5] = 0x9b05688cul;
+ hash->s[6] = 0x1f83d9abul;
+ hash->s[7] = 0x5be0cd19ul;
+ hash->bytes = 0;
+}
+
+/** Perform one SHA-256 transformation, processing a 64-byte chunk. */
+static void secp256k1_sha256_transform(uint32_t* s, const unsigned char* chunk) {
+ uint32_t a = s[0], b = s[1], c = s[2], d = s[3], e = s[4], f = s[5], g = s[6], h = s[7];
+ uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15;
+
+ Round(a, b, c, d, e, f, g, h, 0x428a2f98, w0 = ReadBE32(chunk + 0));
+ Round(h, a, b, c, d, e, f, g, 0x71374491, w1 = ReadBE32(chunk + 4));
+ Round(g, h, a, b, c, d, e, f, 0xb5c0fbcf, w2 = ReadBE32(chunk + 8));
+ Round(f, g, h, a, b, c, d, e, 0xe9b5dba5, w3 = ReadBE32(chunk + 12));
+ Round(e, f, g, h, a, b, c, d, 0x3956c25b, w4 = ReadBE32(chunk + 16));
+ Round(d, e, f, g, h, a, b, c, 0x59f111f1, w5 = ReadBE32(chunk + 20));
+ Round(c, d, e, f, g, h, a, b, 0x923f82a4, w6 = ReadBE32(chunk + 24));
+ Round(b, c, d, e, f, g, h, a, 0xab1c5ed5, w7 = ReadBE32(chunk + 28));
+ Round(a, b, c, d, e, f, g, h, 0xd807aa98, w8 = ReadBE32(chunk + 32));
+ Round(h, a, b, c, d, e, f, g, 0x12835b01, w9 = ReadBE32(chunk + 36));
+ Round(g, h, a, b, c, d, e, f, 0x243185be, w10 = ReadBE32(chunk + 40));
+ Round(f, g, h, a, b, c, d, e, 0x550c7dc3, w11 = ReadBE32(chunk + 44));
+ Round(e, f, g, h, a, b, c, d, 0x72be5d74, w12 = ReadBE32(chunk + 48));
+ Round(d, e, f, g, h, a, b, c, 0x80deb1fe, w13 = ReadBE32(chunk + 52));
+ Round(c, d, e, f, g, h, a, b, 0x9bdc06a7, w14 = ReadBE32(chunk + 56));
+ Round(b, c, d, e, f, g, h, a, 0xc19bf174, w15 = ReadBE32(chunk + 60));
+
+ Round(a, b, c, d, e, f, g, h, 0xe49b69c1, w0 += sigma1(w14) + w9 + sigma0(w1));
+ Round(h, a, b, c, d, e, f, g, 0xefbe4786, w1 += sigma1(w15) + w10 + sigma0(w2));
+ Round(g, h, a, b, c, d, e, f, 0x0fc19dc6, w2 += sigma1(w0) + w11 + sigma0(w3));
+ Round(f, g, h, a, b, c, d, e, 0x240ca1cc, w3 += sigma1(w1) + w12 + sigma0(w4));
+ Round(e, f, g, h, a, b, c, d, 0x2de92c6f, w4 += sigma1(w2) + w13 + sigma0(w5));
+ Round(d, e, f, g, h, a, b, c, 0x4a7484aa, w5 += sigma1(w3) + w14 + sigma0(w6));
+ Round(c, d, e, f, g, h, a, b, 0x5cb0a9dc, w6 += sigma1(w4) + w15 + sigma0(w7));
+ Round(b, c, d, e, f, g, h, a, 0x76f988da, w7 += sigma1(w5) + w0 + sigma0(w8));
+ Round(a, b, c, d, e, f, g, h, 0x983e5152, w8 += sigma1(w6) + w1 + sigma0(w9));
+ Round(h, a, b, c, d, e, f, g, 0xa831c66d, w9 += sigma1(w7) + w2 + sigma0(w10));
+ Round(g, h, a, b, c, d, e, f, 0xb00327c8, w10 += sigma1(w8) + w3 + sigma0(w11));
+ Round(f, g, h, a, b, c, d, e, 0xbf597fc7, w11 += sigma1(w9) + w4 + sigma0(w12));
+ Round(e, f, g, h, a, b, c, d, 0xc6e00bf3, w12 += sigma1(w10) + w5 + sigma0(w13));
+ Round(d, e, f, g, h, a, b, c, 0xd5a79147, w13 += sigma1(w11) + w6 + sigma0(w14));
+ Round(c, d, e, f, g, h, a, b, 0x06ca6351, w14 += sigma1(w12) + w7 + sigma0(w15));
+ Round(b, c, d, e, f, g, h, a, 0x14292967, w15 += sigma1(w13) + w8 + sigma0(w0));
+
+ Round(a, b, c, d, e, f, g, h, 0x27b70a85, w0 += sigma1(w14) + w9 + sigma0(w1));
+ Round(h, a, b, c, d, e, f, g, 0x2e1b2138, w1 += sigma1(w15) + w10 + sigma0(w2));
+ Round(g, h, a, b, c, d, e, f, 0x4d2c6dfc, w2 += sigma1(w0) + w11 + sigma0(w3));
+ Round(f, g, h, a, b, c, d, e, 0x53380d13, w3 += sigma1(w1) + w12 + sigma0(w4));
+ Round(e, f, g, h, a, b, c, d, 0x650a7354, w4 += sigma1(w2) + w13 + sigma0(w5));
+ Round(d, e, f, g, h, a, b, c, 0x766a0abb, w5 += sigma1(w3) + w14 + sigma0(w6));
+ Round(c, d, e, f, g, h, a, b, 0x81c2c92e, w6 += sigma1(w4) + w15 + sigma0(w7));
+ Round(b, c, d, e, f, g, h, a, 0x92722c85, w7 += sigma1(w5) + w0 + sigma0(w8));
+ Round(a, b, c, d, e, f, g, h, 0xa2bfe8a1, w8 += sigma1(w6) + w1 + sigma0(w9));
+ Round(h, a, b, c, d, e, f, g, 0xa81a664b, w9 += sigma1(w7) + w2 + sigma0(w10));
+ Round(g, h, a, b, c, d, e, f, 0xc24b8b70, w10 += sigma1(w8) + w3 + sigma0(w11));
+ Round(f, g, h, a, b, c, d, e, 0xc76c51a3, w11 += sigma1(w9) + w4 + sigma0(w12));
+ Round(e, f, g, h, a, b, c, d, 0xd192e819, w12 += sigma1(w10) + w5 + sigma0(w13));
+ Round(d, e, f, g, h, a, b, c, 0xd6990624, w13 += sigma1(w11) + w6 + sigma0(w14));
+ Round(c, d, e, f, g, h, a, b, 0xf40e3585, w14 += sigma1(w12) + w7 + sigma0(w15));
+ Round(b, c, d, e, f, g, h, a, 0x106aa070, w15 += sigma1(w13) + w8 + sigma0(w0));
+
+ Round(a, b, c, d, e, f, g, h, 0x19a4c116, w0 += sigma1(w14) + w9 + sigma0(w1));
+ Round(h, a, b, c, d, e, f, g, 0x1e376c08, w1 += sigma1(w15) + w10 + sigma0(w2));
+ Round(g, h, a, b, c, d, e, f, 0x2748774c, w2 += sigma1(w0) + w11 + sigma0(w3));
+ Round(f, g, h, a, b, c, d, e, 0x34b0bcb5, w3 += sigma1(w1) + w12 + sigma0(w4));
+ Round(e, f, g, h, a, b, c, d, 0x391c0cb3, w4 += sigma1(w2) + w13 + sigma0(w5));
+ Round(d, e, f, g, h, a, b, c, 0x4ed8aa4a, w5 += sigma1(w3) + w14 + sigma0(w6));
+ Round(c, d, e, f, g, h, a, b, 0x5b9cca4f, w6 += sigma1(w4) + w15 + sigma0(w7));
+ Round(b, c, d, e, f, g, h, a, 0x682e6ff3, w7 += sigma1(w5) + w0 + sigma0(w8));
+ Round(a, b, c, d, e, f, g, h, 0x748f82ee, w8 += sigma1(w6) + w1 + sigma0(w9));
+ Round(h, a, b, c, d, e, f, g, 0x78a5636f, w9 += sigma1(w7) + w2 + sigma0(w10));
+ Round(g, h, a, b, c, d, e, f, 0x84c87814, w10 += sigma1(w8) + w3 + sigma0(w11));
+ Round(f, g, h, a, b, c, d, e, 0x8cc70208, w11 += sigma1(w9) + w4 + sigma0(w12));
+ Round(e, f, g, h, a, b, c, d, 0x90befffa, w12 += sigma1(w10) + w5 + sigma0(w13));
+ Round(d, e, f, g, h, a, b, c, 0xa4506ceb, w13 += sigma1(w11) + w6 + sigma0(w14));
+ Round(c, d, e, f, g, h, a, b, 0xbef9a3f7, w14 + sigma1(w12) + w7 + sigma0(w15));
+ Round(b, c, d, e, f, g, h, a, 0xc67178f2, w15 + sigma1(w13) + w8 + sigma0(w0));
+
+ s[0] += a;
+ s[1] += b;
+ s[2] += c;
+ s[3] += d;
+ s[4] += e;
+ s[5] += f;
+ s[6] += g;
+ s[7] += h;
+}
+
+static void secp256k1_sha256_write(secp256k1_sha256_t *hash, const unsigned char *data, size_t len) {
+ const unsigned char* end = data + len;
+ size_t bufsize = hash->bytes % 64;
+ if (bufsize && bufsize + len >= 64) {
+ // Fill the buffer, and process it.
+ memcpy(hash->buf + bufsize, data, 64 - bufsize);
+ hash->bytes += 64 - bufsize;
+ data += 64 - bufsize;
+ secp256k1_sha256_transform(hash->s, hash->buf);
+ bufsize = 0;
+ }
+ while (end >= data + 64) {
+ // Process full chunks directly from the source.
+ secp256k1_sha256_transform(hash->s, data);
+ hash->bytes += 64;
+ data += 64;
+ }
+ if (end > data) {
+ // Fill the buffer with what remains.
+ memcpy(hash->buf + bufsize, data, end - data);
+ hash->bytes += end - data;
+ }
+}
+
+static void secp256k1_sha256_finalize(secp256k1_sha256_t *hash, unsigned char *out32) {
+ static const unsigned char pad[64] = {0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+ unsigned char sizedesc[8];
+ WriteBE32(sizedesc, hash->bytes >> 29);
+ WriteBE32(sizedesc + 4, hash->bytes << 3);
+ secp256k1_sha256_write(hash, pad, 1 + ((119 - (hash->bytes % 64)) % 64));
+ secp256k1_sha256_write(hash, sizedesc, 8);
+ WriteBE32(out32, hash->s[0]);
+ hash->s[0] = 0;
+ WriteBE32(out32 + 4, hash->s[1]);
+ hash->s[1] = 0;
+ WriteBE32(out32 + 8, hash->s[2]);
+ hash->s[2] = 0;
+ WriteBE32(out32 + 12, hash->s[3]);
+ hash->s[3] = 0;
+ WriteBE32(out32 + 16, hash->s[4]);
+ hash->s[4] = 0;
+ WriteBE32(out32 + 20, hash->s[5]);
+ hash->s[5] = 0;
+ WriteBE32(out32 + 24, hash->s[6]);
+ hash->s[6] = 0;
+ WriteBE32(out32 + 28, hash->s[7]);
+ hash->s[7] = 0;
+}
+
+static void secp256k1_hmac_sha256_initialize(secp256k1_hmac_sha256_t *hash, const unsigned char *key, size_t keylen) {
+ unsigned char rkey[64];
+ if (keylen <= 64) {
+ memcpy(rkey, key, keylen);
+ memset(rkey + keylen, 0, 64 - keylen);
+ } else {
+ secp256k1_sha256_t sha256;
+ secp256k1_sha256_initialize(&sha256);
+ secp256k1_sha256_write(&sha256, key, keylen);
+ secp256k1_sha256_finalize(&sha256, rkey);
+ memset(rkey + 32, 0, 32);
+ }
+
+ secp256k1_sha256_initialize(&hash->outer);
+ for (int n = 0; n < 64; n++)
+ rkey[n] ^= 0x5c;
+ secp256k1_sha256_write(&hash->outer, rkey, 64);
+
+ secp256k1_sha256_initialize(&hash->inner);
+ for (int n = 0; n < 64; n++)
+ rkey[n] ^= 0x5c ^ 0x36;
+ secp256k1_sha256_write(&hash->inner, rkey, 64);
+ memset(rkey, 0, 64);
+}
+
+static void secp256k1_hmac_sha256_write(secp256k1_hmac_sha256_t *hash, const unsigned char *data, size_t size) {
+ secp256k1_sha256_write(&hash->inner, data, size);
+}
+
+static void secp256k1_hmac_sha256_finalize(secp256k1_hmac_sha256_t *hash, unsigned char *out32) {
+ unsigned char temp[32];
+ secp256k1_sha256_finalize(&hash->inner, temp);
+ secp256k1_sha256_write(&hash->outer, temp, 32);
+ memset(temp, 0, 32);
+ secp256k1_sha256_finalize(&hash->outer, out32);
+}
+
+
+static void secp256k1_rfc6979_hmac_sha256_initialize(secp256k1_rfc6979_hmac_sha256_t *rng, const unsigned char *key, size_t keylen, const unsigned char *msg, size_t msglen) {
+ static const unsigned char zero[1] = {0x00};
+ static const unsigned char one[1] = {0x01};
+
+ memset(rng->v, 0x01, 32);
+ memset(rng->k, 0x00, 32);
+
+ secp256k1_hmac_sha256_t hmac;
+ secp256k1_hmac_sha256_initialize(&hmac, rng->k, 32);
+ secp256k1_hmac_sha256_write(&hmac, rng->v, 32);
+ secp256k1_hmac_sha256_write(&hmac, zero, 1);
+ secp256k1_hmac_sha256_write(&hmac, key, keylen);
+ secp256k1_hmac_sha256_write(&hmac, msg, msglen);
+ secp256k1_hmac_sha256_finalize(&hmac, rng->k);
+ secp256k1_hmac_sha256_initialize(&hmac, rng->k, 32);
+ secp256k1_hmac_sha256_write(&hmac, rng->v, 32);
+ secp256k1_hmac_sha256_finalize(&hmac, rng->v);
+
+ secp256k1_hmac_sha256_initialize(&hmac, rng->k, 32);
+ secp256k1_hmac_sha256_write(&hmac, rng->v, 32);
+ secp256k1_hmac_sha256_write(&hmac, one, 1);
+ secp256k1_hmac_sha256_write(&hmac, key, keylen);
+ secp256k1_hmac_sha256_write(&hmac, msg, msglen);
+ secp256k1_hmac_sha256_finalize(&hmac, rng->k);
+ secp256k1_hmac_sha256_initialize(&hmac, rng->k, 32);
+ secp256k1_hmac_sha256_write(&hmac, rng->v, 32);
+ secp256k1_hmac_sha256_finalize(&hmac, rng->v);
+ rng->retry = 0;
+}
+
+static void secp256k1_rfc6979_hmac_sha256_generate(secp256k1_rfc6979_hmac_sha256_t *rng, unsigned char *out, size_t outlen) {
+ static const unsigned char zero[1] = {0x00};
+ if (rng->retry) {
+ secp256k1_hmac_sha256_t hmac;
+ secp256k1_hmac_sha256_initialize(&hmac, rng->k, 32);
+ secp256k1_hmac_sha256_write(&hmac, rng->v, 32);
+ secp256k1_hmac_sha256_write(&hmac, zero, 1);
+ secp256k1_hmac_sha256_finalize(&hmac, rng->k);
+ secp256k1_hmac_sha256_initialize(&hmac, rng->k, 32);
+ secp256k1_hmac_sha256_write(&hmac, rng->v, 32);
+ secp256k1_hmac_sha256_finalize(&hmac, rng->v);
+ }
+
+ while (outlen > 0) {
+ secp256k1_hmac_sha256_t hmac;
+ secp256k1_hmac_sha256_initialize(&hmac, rng->k, 32);
+ secp256k1_hmac_sha256_write(&hmac, rng->v, 32);
+ secp256k1_hmac_sha256_finalize(&hmac, rng->v);
+ int now = outlen;
+ if (now > 32) {
+ now = 32;
+ }
+ memcpy(out, rng->v, now);
+ out += now;
+ outlen -= now;
+ }
+
+ rng->retry = 1;
+}
+
+static void secp256k1_rfc6979_hmac_sha256_finalize(secp256k1_rfc6979_hmac_sha256_t *rng) {
+ memset(rng->k, 0, 32);
+ memset(rng->v, 0, 32);
+ rng->retry = 0;
+}
+
+
+#undef Round
+#undef sigma0
+#undef sigma1
+#undef Sigma0
+#undef Sigma1
+#undef Ch
+#undef Maj
+#undef ReadBE32
+#undef WriteBE32
+
+#endif
diff --git a/src/secp256k1.c b/src/secp256k1.c
index 0328db88fc..58bcd8d009 100644
--- a/src/secp256k1.c
+++ b/src/secp256k1.c
@@ -17,6 +17,7 @@
#include "ecmult_gen_impl.h"
#include "ecdsa_impl.h"
#include "eckey_impl.h"
+#include "hash_impl.h"
void secp256k1_start(unsigned int flags) {
secp256k1_fe_start();
@@ -69,26 +70,54 @@ end:
return ret;
}
-int secp256k1_ecdsa_sign(const unsigned char *msg32, unsigned char *signature, int *signaturelen, const unsigned char *seckey, const unsigned char *nonce) {
+static int nonce_function_rfc6979(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
+ (void)data;
+ secp256k1_rfc6979_hmac_sha256_t rng;
+ secp256k1_rfc6979_hmac_sha256_initialize(&rng, key32, 32, msg32, 32);
+ for (unsigned int i = 0; i <= counter; i++) {
+ secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
+ }
+ secp256k1_rfc6979_hmac_sha256_finalize(&rng);
+ return 1;
+}
+
+const secp256k1_nonce_function_t secp256k1_nonce_function_rfc6979 = nonce_function_rfc6979;
+const secp256k1_nonce_function_t secp256k1_nonce_function_default = nonce_function_rfc6979;
+
+int secp256k1_ecdsa_sign(const unsigned char *msg32, unsigned char *signature, int *signaturelen, const unsigned char *seckey, secp256k1_nonce_function_t noncefp, const void* noncedata) {
DEBUG_CHECK(secp256k1_ecmult_gen_consts != NULL);
DEBUG_CHECK(msg32 != NULL);
DEBUG_CHECK(signature != NULL);
DEBUG_CHECK(signaturelen != NULL);
DEBUG_CHECK(seckey != NULL);
- DEBUG_CHECK(nonce != NULL);
+ if (noncefp == NULL) {
+ noncefp = secp256k1_nonce_function_default;
+ }
secp256k1_scalar_t sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, NULL);
- int overflow = 0;
- secp256k1_scalar_set_b32(&non, nonce, &overflow);
secp256k1_scalar_set_b32(&msg, msg32, NULL);
- int ret = !secp256k1_scalar_is_zero(&non) && !overflow;
+ int overflow = 0;
+ int ret = 0;
+ unsigned int count = 0;
secp256k1_ecdsa_sig_t sig;
- if (ret) {
- ret = secp256k1_ecdsa_sig_sign(&sig, &sec, &msg, &non, NULL);
+ while (1) {
+ unsigned char nonce32[32];
+ ret = noncefp(nonce32, msg32, seckey, count, noncedata);
+ if (!ret) {
+ break;
+ }
+ secp256k1_scalar_set_b32(&non, nonce32, &overflow);
+ memset(nonce32, 0, 32);
+ if (!secp256k1_scalar_is_zero(&non) && !overflow) {
+ if (secp256k1_ecdsa_sig_sign(&sig, &sec, &msg, &non, NULL)) {
+ break;
+ }
+ }
+ count++;
}
if (ret) {
- secp256k1_ecdsa_sig_serialize(signature, signaturelen, &sig);
+ ret = secp256k1_ecdsa_sig_serialize(signature, signaturelen, &sig);
}
secp256k1_scalar_clear(&msg);
secp256k1_scalar_clear(&non);
@@ -96,22 +125,36 @@ int secp256k1_ecdsa_sign(const unsigned char *msg32, unsigned char *signature, i
return ret;
}
-int secp256k1_ecdsa_sign_compact(const unsigned char *msg32, 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, secp256k1_nonce_function_t noncefp, const void* noncedata, int *recid) {
DEBUG_CHECK(secp256k1_ecmult_gen_consts != NULL);
DEBUG_CHECK(msg32 != NULL);
DEBUG_CHECK(sig64 != NULL);
DEBUG_CHECK(seckey != NULL);
- DEBUG_CHECK(nonce != NULL);
+ if (noncefp == NULL) {
+ noncefp = secp256k1_nonce_function_default;
+ }
secp256k1_scalar_t sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, NULL);
- int overflow = 0;
- secp256k1_scalar_set_b32(&non, nonce, &overflow);
secp256k1_scalar_set_b32(&msg, msg32, NULL);
- int ret = !secp256k1_scalar_is_zero(&non) && !overflow;
+ int overflow = 0;
+ int ret = 0;
+ unsigned int count = 0;
secp256k1_ecdsa_sig_t sig;
- if (ret) {
- ret = secp256k1_ecdsa_sig_sign(&sig, &sec, &msg, &non, recid);
+ while (1) {
+ unsigned char nonce32[32];
+ ret = noncefp(nonce32, msg32, seckey, count, noncedata);
+ if (!ret) {
+ break;
+ }
+ secp256k1_scalar_set_b32(&non, nonce32, &overflow);
+ memset(nonce32, 0, 32);
+ if (!secp256k1_scalar_is_zero(&non) && !overflow) {
+ if (secp256k1_ecdsa_sig_sign(&sig, &sec, &msg, &non, recid)) {
+ break;
+ }
+ }
+ count++;
}
if (ret) {
secp256k1_scalar_get_b32(sig64, &sig.r);
diff --git a/src/tests.c b/src/tests.c
index 7ebb19ff99..cff32f1d06 100644
--- a/src/tests.c
+++ b/src/tests.c
@@ -36,12 +36,19 @@ void random_field_element_test(secp256k1_fe_t *fe) {
}
void random_field_element_magnitude(secp256k1_fe_t *fe) {
+ int n = secp256k1_rand32() % 9;
secp256k1_fe_normalize(fe);
- int n = secp256k1_rand32() % 4;
- for (int i = 0; i < n; i++) {
- secp256k1_fe_negate(fe, fe, 1 + 2*i);
- secp256k1_fe_negate(fe, fe, 2 + 2*i);
+ if (n == 0) {
+ return;
}
+ secp256k1_fe_t zero;
+ secp256k1_fe_clear(&zero);
+ secp256k1_fe_negate(&zero, &zero, 0);
+ secp256k1_fe_mul_int(&zero, n - 1);
+ secp256k1_fe_add(fe, &zero);
+#ifdef VERIFY
+ CHECK(fe->magnitude == n);
+#endif
}
void random_group_element_test(secp256k1_ge_t *ge) {
@@ -91,6 +98,121 @@ void random_scalar_order(secp256k1_scalar_t *num) {
} while(1);
}
+/***** HASH TESTS *****/
+
+void run_sha256_tests(void) {
+ static const char *inputs[8] = {
+ "", "abc", "message digest", "secure hash algorithm", "SHA256 is considered to be safe",
+ "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
+ "For this sample, this 63-byte string will be used as input data",
+ "This is exactly 64 bytes long, not counting the terminating byte"
+ };
+ static const unsigned char outputs[8][32] = {
+ {0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55},
+ {0xba, 0x78, 0x16, 0xbf, 0x8f, 0x01, 0xcf, 0xea, 0x41, 0x41, 0x40, 0xde, 0x5d, 0xae, 0x22, 0x23, 0xb0, 0x03, 0x61, 0xa3, 0x96, 0x17, 0x7a, 0x9c, 0xb4, 0x10, 0xff, 0x61, 0xf2, 0x00, 0x15, 0xad},
+ {0xf7, 0x84, 0x6f, 0x55, 0xcf, 0x23, 0xe1, 0x4e, 0xeb, 0xea, 0xb5, 0xb4, 0xe1, 0x55, 0x0c, 0xad, 0x5b, 0x50, 0x9e, 0x33, 0x48, 0xfb, 0xc4, 0xef, 0xa3, 0xa1, 0x41, 0x3d, 0x39, 0x3c, 0xb6, 0x50},
+ {0xf3, 0x0c, 0xeb, 0x2b, 0xb2, 0x82, 0x9e, 0x79, 0xe4, 0xca, 0x97, 0x53, 0xd3, 0x5a, 0x8e, 0xcc, 0x00, 0x26, 0x2d, 0x16, 0x4c, 0xc0, 0x77, 0x08, 0x02, 0x95, 0x38, 0x1c, 0xbd, 0x64, 0x3f, 0x0d},
+ {0x68, 0x19, 0xd9, 0x15, 0xc7, 0x3f, 0x4d, 0x1e, 0x77, 0xe4, 0xe1, 0xb5, 0x2d, 0x1f, 0xa0, 0xf9, 0xcf, 0x9b, 0xea, 0xea, 0xd3, 0x93, 0x9f, 0x15, 0x87, 0x4b, 0xd9, 0x88, 0xe2, 0xa2, 0x36, 0x30},
+ {0x24, 0x8d, 0x6a, 0x61, 0xd2, 0x06, 0x38, 0xb8, 0xe5, 0xc0, 0x26, 0x93, 0x0c, 0x3e, 0x60, 0x39, 0xa3, 0x3c, 0xe4, 0x59, 0x64, 0xff, 0x21, 0x67, 0xf6, 0xec, 0xed, 0xd4, 0x19, 0xdb, 0x06, 0xc1},
+ {0xf0, 0x8a, 0x78, 0xcb, 0xba, 0xee, 0x08, 0x2b, 0x05, 0x2a, 0xe0, 0x70, 0x8f, 0x32, 0xfa, 0x1e, 0x50, 0xc5, 0xc4, 0x21, 0xaa, 0x77, 0x2b, 0xa5, 0xdb, 0xb4, 0x06, 0xa2, 0xea, 0x6b, 0xe3, 0x42},
+ {0xab, 0x64, 0xef, 0xf7, 0xe8, 0x8e, 0x2e, 0x46, 0x16, 0x5e, 0x29, 0xf2, 0xbc, 0xe4, 0x18, 0x26, 0xbd, 0x4c, 0x7b, 0x35, 0x52, 0xf6, 0xb3, 0x82, 0xa9, 0xe7, 0xd3, 0xaf, 0x47, 0xc2, 0x45, 0xf8}
+ };
+ for (int i = 0; i < 8; i++) {
+ secp256k1_sha256_t hasher;
+ secp256k1_sha256_initialize(&hasher);
+ secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
+ unsigned char out[32];
+ secp256k1_sha256_finalize(&hasher, out);
+ CHECK(memcmp(out, outputs[i], 32) == 0);
+ if (strlen(inputs[i]) > 0) {
+ secp256k1_sha256_initialize(&hasher);
+ int split = secp256k1_rand32() % strlen(inputs[i]);
+ secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
+ secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
+ secp256k1_sha256_finalize(&hasher, out);
+ CHECK(memcmp(out, outputs[i], 32) == 0);
+ }
+ }
+}
+
+void run_hmac_sha256_tests(void) {
+ static const char *keys[6] = {
+ "\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b",
+ "\x4a\x65\x66\x65",
+ "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
+ "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19",
+ "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
+ "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa"
+ };
+ static const char *inputs[6] = {
+ "\x48\x69\x20\x54\x68\x65\x72\x65",
+ "\x77\x68\x61\x74\x20\x64\x6f\x20\x79\x61\x20\x77\x61\x6e\x74\x20\x66\x6f\x72\x20\x6e\x6f\x74\x68\x69\x6e\x67\x3f",
+ "\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd",
+ "\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd",
+ "\x54\x65\x73\x74\x20\x55\x73\x69\x6e\x67\x20\x4c\x61\x72\x67\x65\x72\x20\x54\x68\x61\x6e\x20\x42\x6c\x6f\x63\x6b\x2d\x53\x69\x7a\x65\x20\x4b\x65\x79\x20\x2d\x20\x48\x61\x73\x68\x20\x4b\x65\x79\x20\x46\x69\x72\x73\x74",
+ "\x54\x68\x69\x73\x20\x69\x73\x20\x61\x20\x74\x65\x73\x74\x20\x75\x73\x69\x6e\x67\x20\x61\x20\x6c\x61\x72\x67\x65\x72\x20\x74\x68\x61\x6e\x20\x62\x6c\x6f\x63\x6b\x2d\x73\x69\x7a\x65\x20\x6b\x65\x79\x20\x61\x6e\x64\x20\x61\x20\x6c\x61\x72\x67\x65\x72\x20\x74\x68\x61\x6e\x20\x62\x6c\x6f\x63\x6b\x2d\x73\x69\x7a\x65\x20\x64\x61\x74\x61\x2e\x20\x54\x68\x65\x20\x6b\x65\x79\x20\x6e\x65\x65\x64\x73\x20\x74\x6f\x20\x62\x65\x20\x68\x61\x73\x68\x65\x64\x20\x62\x65\x66\x6f\x72\x65\x20\x62\x65\x69\x6e\x67\x20\x75\x73\x65\x64\x20\x62\x79\x20\x74\x68\x65\x20\x48\x4d\x41\x43\x20\x61\x6c\x67\x6f\x72\x69\x74\x68\x6d\x2e"
+ };
+ static const unsigned char outputs[6][32] = {
+ {0xb0, 0x34, 0x4c, 0x61, 0xd8, 0xdb, 0x38, 0x53, 0x5c, 0xa8, 0xaf, 0xce, 0xaf, 0x0b, 0xf1, 0x2b, 0x88, 0x1d, 0xc2, 0x00, 0xc9, 0x83, 0x3d, 0xa7, 0x26, 0xe9, 0x37, 0x6c, 0x2e, 0x32, 0xcf, 0xf7},
+ {0x5b, 0xdc, 0xc1, 0x46, 0xbf, 0x60, 0x75, 0x4e, 0x6a, 0x04, 0x24, 0x26, 0x08, 0x95, 0x75, 0xc7, 0x5a, 0x00, 0x3f, 0x08, 0x9d, 0x27, 0x39, 0x83, 0x9d, 0xec, 0x58, 0xb9, 0x64, 0xec, 0x38, 0x43},
+ {0x77, 0x3e, 0xa9, 0x1e, 0x36, 0x80, 0x0e, 0x46, 0x85, 0x4d, 0xb8, 0xeb, 0xd0, 0x91, 0x81, 0xa7, 0x29, 0x59, 0x09, 0x8b, 0x3e, 0xf8, 0xc1, 0x22, 0xd9, 0x63, 0x55, 0x14, 0xce, 0xd5, 0x65, 0xfe},
+ {0x82, 0x55, 0x8a, 0x38, 0x9a, 0x44, 0x3c, 0x0e, 0xa4, 0xcc, 0x81, 0x98, 0x99, 0xf2, 0x08, 0x3a, 0x85, 0xf0, 0xfa, 0xa3, 0xe5, 0x78, 0xf8, 0x07, 0x7a, 0x2e, 0x3f, 0xf4, 0x67, 0x29, 0x66, 0x5b},
+ {0x60, 0xe4, 0x31, 0x59, 0x1e, 0xe0, 0xb6, 0x7f, 0x0d, 0x8a, 0x26, 0xaa, 0xcb, 0xf5, 0xb7, 0x7f, 0x8e, 0x0b, 0xc6, 0x21, 0x37, 0x28, 0xc5, 0x14, 0x05, 0x46, 0x04, 0x0f, 0x0e, 0xe3, 0x7f, 0x54},
+ {0x9b, 0x09, 0xff, 0xa7, 0x1b, 0x94, 0x2f, 0xcb, 0x27, 0x63, 0x5f, 0xbc, 0xd5, 0xb0, 0xe9, 0x44, 0xbf, 0xdc, 0x63, 0x64, 0x4f, 0x07, 0x13, 0x93, 0x8a, 0x7f, 0x51, 0x53, 0x5c, 0x3a, 0x35, 0xe2}
+ };
+ for (int i = 0; i < 6; i++) {
+ secp256k1_hmac_sha256_t hasher;
+ secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
+ secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
+ unsigned char out[32];
+ secp256k1_hmac_sha256_finalize(&hasher, out);
+ CHECK(memcmp(out, outputs[i], 32) == 0);
+ if (strlen(inputs[i]) > 0) {
+ secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
+ int split = secp256k1_rand32() % strlen(inputs[i]);
+ secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
+ secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
+ secp256k1_hmac_sha256_finalize(&hasher, out);
+ CHECK(memcmp(out, outputs[i], 32) == 0);
+ }
+ }
+}
+
+void run_rfc6979_hmac_sha256_tests(void) {
+ static const unsigned char key1[32] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x00};
+ static const unsigned char msg1[32] = {0x4b, 0xf5, 0x12, 0x2f, 0x34, 0x45, 0x54, 0xc5, 0x3b, 0xde, 0x2e, 0xbb, 0x8c, 0xd2, 0xb7, 0xe3, 0xd1, 0x60, 0x0a, 0xd6, 0x31, 0xc3, 0x85, 0xa5, 0xd7, 0xcc, 0xe2, 0x3c, 0x77, 0x85, 0x45, 0x9a};
+ static const unsigned char out1[3][32] = {
+ {0x4f, 0xe2, 0x95, 0x25, 0xb2, 0x08, 0x68, 0x09, 0x15, 0x9a, 0xcd, 0xf0, 0x50, 0x6e, 0xfb, 0x86, 0xb0, 0xec, 0x93, 0x2c, 0x7b, 0xa4, 0x42, 0x56, 0xab, 0x32, 0x1e, 0x42, 0x1e, 0x67, 0xe9, 0xfb},
+ {0x2b, 0xf0, 0xff, 0xf1, 0xd3, 0xc3, 0x78, 0xa2, 0x2d, 0xc5, 0xde, 0x1d, 0x85, 0x65, 0x22, 0x32, 0x5c, 0x65, 0xb5, 0x04, 0x49, 0x1a, 0x0c, 0xbd, 0x01, 0xcb, 0x8f, 0x3a, 0xa6, 0x7f, 0xfd, 0x4a},
+ {0xf5, 0x28, 0xb4, 0x10, 0xcb, 0x54, 0x1f, 0x77, 0x00, 0x0d, 0x7a, 0xfb, 0x6c, 0x5b, 0x53, 0xc5, 0xc4, 0x71, 0xea, 0xb4, 0x3e, 0x46, 0x6d, 0x9a, 0xc5, 0x19, 0x0c, 0x39, 0xc8, 0x2f, 0xd8, 0x2e}
+ };
+
+ static const unsigned char key2[32] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
+ static const unsigned char msg2[32] = {0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55};
+ static const unsigned char out2[3][32] = {
+ {0x9c, 0x23, 0x6c, 0x16, 0x5b, 0x82, 0xae, 0x0c, 0xd5, 0x90, 0x65, 0x9e, 0x10, 0x0b, 0x6b, 0xab, 0x30, 0x36, 0xe7, 0xba, 0x8b, 0x06, 0x74, 0x9b, 0xaf, 0x69, 0x81, 0xe1, 0x6f, 0x1a, 0x2b, 0x95},
+ {0xdf, 0x47, 0x10, 0x61, 0x62, 0x5b, 0xc0, 0xea, 0x14, 0xb6, 0x82, 0xfe, 0xee, 0x2c, 0x9c, 0x02, 0xf2, 0x35, 0xda, 0x04, 0x20, 0x4c, 0x1d, 0x62, 0xa1, 0x53, 0x6c, 0x6e, 0x17, 0xae, 0xd7, 0xa9},
+ {0x75, 0x97, 0x88, 0x7c, 0xbd, 0x76, 0x32, 0x1f, 0x32, 0xe3, 0x04, 0x40, 0x67, 0x9a, 0x22, 0xcf, 0x7f, 0x8d, 0x9d, 0x2e, 0xac, 0x39, 0x0e, 0x58, 0x1f, 0xea, 0x09, 0x1c, 0xe2, 0x02, 0xba, 0x94}
+ };
+
+ secp256k1_rfc6979_hmac_sha256_t rng;
+ unsigned char out[32];
+
+ secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 32, msg1, 32);
+ for (int i = 0; i < 3; i++) {
+ secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
+ CHECK(memcmp(out, out1[i], 32) == 0);
+ }
+ secp256k1_rfc6979_hmac_sha256_finalize(&rng);
+
+ secp256k1_rfc6979_hmac_sha256_initialize(&rng, key2, 32, msg2, 32);
+ for (int i = 0; i < 3; i++) {
+ secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
+ CHECK(memcmp(out, out2[i], 32) == 0);
+ }
+ secp256k1_rfc6979_hmac_sha256_finalize(&rng);
+}
+
/***** NUM TESTS *****/
#ifndef USE_NUM_NONE
@@ -494,9 +616,9 @@ void random_fe_non_square(secp256k1_fe_t *ns) {
}
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 an = *a; secp256k1_fe_normalize_weak(&an);
secp256k1_fe_t bn = *b; secp256k1_fe_normalize_var(&bn);
- return secp256k1_fe_equal(&an, &bn);
+ return secp256k1_fe_equal_var(&an, &bn);
}
int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
@@ -523,16 +645,16 @@ void run_field_misc(void) {
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));
+ CHECK(secp256k1_fe_equal_var(&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_equal_var(&x, &z) == 0);
CHECK(secp256k1_fe_cmp_var(&x, &z) != 0);
secp256k1_fe_cmov(&y, &x, 1);
- CHECK(secp256k1_fe_equal(&x, &y));
+ CHECK(secp256k1_fe_equal_var(&x, &y));
/* Test that mul_int, mul, and add agree. */
secp256k1_fe_add(&y, &x);
secp256k1_fe_add(&y, &x);
@@ -656,108 +778,148 @@ void run_sqrt(void) {
/***** GROUP TESTS *****/
-int ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
- if (a->infinity && b->infinity)
- return 1;
- return check_fe_equal(&a->x, &b->x) && check_fe_equal(&a->y, &b->y);
+void ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
+ CHECK(a->infinity == b->infinity);
+ if (a->infinity)
+ return;
+ CHECK(secp256k1_fe_equal_var(&a->x, &b->x));
+ CHECK(secp256k1_fe_equal_var(&b->y, &b->y));
}
void ge_equals_gej(const secp256k1_ge_t *a, const secp256k1_gej_t *b) {
- secp256k1_ge_t bb;
- secp256k1_gej_t bj = *b;
- secp256k1_ge_set_gej_var(&bb, &bj);
- CHECK(ge_equals_ge(a, &bb));
-}
-
-void gej_equals_gej(const secp256k1_gej_t *a, const secp256k1_gej_t *b) {
- secp256k1_ge_t aa, bb;
- secp256k1_gej_t aj = *a, bj = *b;
- secp256k1_ge_set_gej_var(&aa, &aj);
- secp256k1_ge_set_gej_var(&bb, &bj);
- CHECK(ge_equals_ge(&aa, &bb));
+ CHECK(a->infinity == b->infinity);
+ if (a->infinity)
+ return;
+ /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */
+ secp256k1_fe_t z2s;
+ secp256k1_fe_sqr(&z2s, &b->z);
+ secp256k1_fe_t u1, u2, s1, s2;
+ secp256k1_fe_mul(&u1, &a->x, &z2s);
+ u2 = b->x; secp256k1_fe_normalize_weak(&u2);
+ secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z);
+ s2 = b->y; secp256k1_fe_normalize_weak(&s2);
+ CHECK(secp256k1_fe_equal_var(&u1, &u2));
+ CHECK(secp256k1_fe_equal_var(&s1, &s2));
}
void test_ge(void) {
- char ca[135];
- char cb[68];
- int rlen;
- secp256k1_ge_t a, b, i, n;
- random_group_element_test(&a);
- random_group_element_test(&b);
- rlen = sizeof(ca);
- secp256k1_ge_get_hex(ca,&rlen,&a);
- CHECK(rlen > 4 && rlen <= (int)sizeof(ca));
- rlen = sizeof(cb);
- secp256k1_ge_get_hex(cb,&rlen,&b); /* Intentionally undersized buffer. */
- n = a;
- secp256k1_fe_normalize(&a.y);
- secp256k1_fe_negate(&n.y, &a.y, 1);
- secp256k1_ge_set_infinity(&i);
- random_field_element_magnitude(&a.x);
- random_field_element_magnitude(&a.y);
- random_field_element_magnitude(&b.x);
- random_field_element_magnitude(&b.y);
- random_field_element_magnitude(&n.x);
- random_field_element_magnitude(&n.y);
-
- secp256k1_gej_t aj, bj, ij, nj;
- random_group_element_jacobian_test(&aj, &a);
- random_group_element_jacobian_test(&bj, &b);
- secp256k1_gej_set_infinity(&ij);
- random_group_element_jacobian_test(&nj, &n);
- random_field_element_magnitude(&aj.x);
- random_field_element_magnitude(&aj.y);
- random_field_element_magnitude(&aj.z);
- random_field_element_magnitude(&bj.x);
- random_field_element_magnitude(&bj.y);
- random_field_element_magnitude(&bj.z);
- random_field_element_magnitude(&nj.x);
- random_field_element_magnitude(&nj.y);
- random_field_element_magnitude(&nj.z);
-
- /* gej + gej adds */
- secp256k1_gej_t aaj; secp256k1_gej_add_var(&aaj, &aj, &aj);
- secp256k1_gej_t abj; secp256k1_gej_add_var(&abj, &aj, &bj);
- secp256k1_gej_t aij; secp256k1_gej_add_var(&aij, &aj, &ij);
- secp256k1_gej_t anj; secp256k1_gej_add_var(&anj, &aj, &nj);
- secp256k1_gej_t iaj; secp256k1_gej_add_var(&iaj, &ij, &aj);
- secp256k1_gej_t iij; secp256k1_gej_add_var(&iij, &ij, &ij);
-
- /* gej + ge adds */
- secp256k1_gej_t aa; secp256k1_gej_add_ge_var(&aa, &aj, &a);
- secp256k1_gej_t ab; secp256k1_gej_add_ge_var(&ab, &aj, &b);
- secp256k1_gej_t ai; secp256k1_gej_add_ge_var(&ai, &aj, &i);
- secp256k1_gej_t an; secp256k1_gej_add_ge_var(&an, &aj, &n);
- secp256k1_gej_t ia; secp256k1_gej_add_ge_var(&ia, &ij, &a);
- secp256k1_gej_t ii; secp256k1_gej_add_ge_var(&ii, &ij, &i);
-
- /* const gej + ge adds */
- secp256k1_gej_t aac; secp256k1_gej_add_ge(&aac, &aj, &a);
- secp256k1_gej_t abc; secp256k1_gej_add_ge(&abc, &aj, &b);
- secp256k1_gej_t anc; secp256k1_gej_add_ge(&anc, &aj, &n);
- secp256k1_gej_t iac; secp256k1_gej_add_ge(&iac, &ij, &a);
-
- CHECK(secp256k1_gej_is_infinity(&an));
- CHECK(secp256k1_gej_is_infinity(&anj));
- CHECK(secp256k1_gej_is_infinity(&anc));
- gej_equals_gej(&aa, &aaj);
- gej_equals_gej(&aa, &aac);
- gej_equals_gej(&ab, &abj);
- gej_equals_gej(&ab, &abc);
- gej_equals_gej(&an, &anj);
- gej_equals_gej(&an, &anc);
- gej_equals_gej(&ia, &iaj);
- gej_equals_gej(&ai, &aij);
- gej_equals_gej(&ii, &iij);
- ge_equals_gej(&a, &ai);
- ge_equals_gej(&a, &ai);
- ge_equals_gej(&a, &iaj);
- ge_equals_gej(&a, &iaj);
- ge_equals_gej(&a, &iac);
+ int runs = 4;
+ /* Points: (infinity, p1, p1, -p1, -p1, p2, p2, -p2, -p2, p3, p3, -p3, -p3, p4, p4, -p4, -p4).
+ * The second in each pair of identical points uses a random Z coordinate in the Jacobian form.
+ * All magnitudes are randomized.
+ * All 17*17 combinations of points are added to eachother, using all applicable methods.
+ */
+ secp256k1_ge_t *ge = malloc(sizeof(secp256k1_ge_t) * (1 + 4 * runs));
+ secp256k1_gej_t *gej = malloc(sizeof(secp256k1_gej_t) * (1 + 4 * runs));
+ secp256k1_gej_set_infinity(&gej[0]);
+ secp256k1_ge_clear(&ge[0]);
+ secp256k1_ge_set_gej_var(&ge[0], &gej[0]);
+ for (int i = 0; i < runs; i++) {
+ secp256k1_ge_t g;
+ random_group_element_test(&g);
+ ge[1 + 4 * i] = g;
+ ge[2 + 4 * i] = g;
+ secp256k1_ge_neg(&ge[3 + 4 * i], &g);
+ secp256k1_ge_neg(&ge[4 + 4 * i], &g);
+ secp256k1_gej_set_ge(&gej[1 + 4 * i], &ge[1 + 4 * i]);
+ random_group_element_jacobian_test(&gej[2 + 4 * i], &ge[2 + 4 * i]);
+ secp256k1_gej_set_ge(&gej[3 + 4 * i], &ge[3 + 4 * i]);
+ random_group_element_jacobian_test(&gej[4 + 4 * i], &ge[4 + 4 * i]);
+ for (int j = 0; j < 4; j++) {
+ random_field_element_magnitude(&ge[1 + j + 4 * i].x);
+ random_field_element_magnitude(&ge[1 + j + 4 * i].y);
+ random_field_element_magnitude(&gej[1 + j + 4 * i].x);
+ random_field_element_magnitude(&gej[1 + j + 4 * i].y);
+ random_field_element_magnitude(&gej[1 + j + 4 * i].z);
+ }
+ }
+
+ for (int i1 = 0; i1 < 1 + 4 * runs; i1++) {
+ for (int i2 = 0; i2 < 1 + 4 * runs; i2++) {
+ /* Compute reference result using gej + gej (var). */
+ secp256k1_gej_t refj, resj;
+ secp256k1_ge_t ref;
+ secp256k1_gej_add_var(&refj, &gej[i1], &gej[i2]);
+ secp256k1_ge_set_gej_var(&ref, &refj);
+
+ /* Test gej + ge (var). */
+ secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2]);
+ ge_equals_gej(&ref, &resj);
+
+ /* Test gej + ge (const). */
+ if (i2 != 0) {
+ /* secp256k1_gej_add_ge does not support its second argument being infinity. */
+ secp256k1_gej_add_ge(&resj, &gej[i1], &ge[i2]);
+ ge_equals_gej(&ref, &resj);
+ }
+
+ /* Test doubling (var). */
+ if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 == ((i2 + 3)%4)/2)) {
+ /* Normal doubling. */
+ secp256k1_gej_double_var(&resj, &gej[i1]);
+ ge_equals_gej(&ref, &resj);
+ secp256k1_gej_double_var(&resj, &gej[i2]);
+ ge_equals_gej(&ref, &resj);
+ }
+
+ /* Test adding opposites. */
+ if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 != ((i2 + 3)%4)/2)) {
+ CHECK(secp256k1_ge_is_infinity(&ref));
+ }
+
+ /* Test adding infinity. */
+ if (i1 == 0) {
+ CHECK(secp256k1_ge_is_infinity(&ge[i1]));
+ CHECK(secp256k1_gej_is_infinity(&gej[i1]));
+ ge_equals_gej(&ref, &gej[i2]);
+ }
+ if (i2 == 0) {
+ CHECK(secp256k1_ge_is_infinity(&ge[i2]));
+ CHECK(secp256k1_gej_is_infinity(&gej[i2]));
+ ge_equals_gej(&ref, &gej[i1]);
+ }
+ }
+ }
+
+ /* Test adding all points together in random order equals infinity. */
+ {
+ secp256k1_gej_t *gej_shuffled = malloc((4 * runs + 1) * sizeof(secp256k1_gej_t));
+ for (int i = 0; i < 4 * runs + 1; i++) {
+ gej_shuffled[i] = gej[i];
+ }
+ for (int i = 0; i < 4 * runs + 1; i++) {
+ int swap = i + secp256k1_rand32() % (4 * runs + 1 - i);
+ if (swap != i) {
+ secp256k1_gej_t t = gej_shuffled[i];
+ gej_shuffled[i] = gej_shuffled[swap];
+ gej_shuffled[swap] = t;
+ }
+ }
+ secp256k1_gej_t sum;
+ secp256k1_gej_set_infinity(&sum);
+ for (int i = 0; i < 4 * runs + 1; i++) {
+ secp256k1_gej_add_var(&sum, &sum, &gej_shuffled[i]);
+ }
+ CHECK(secp256k1_gej_is_infinity(&sum));
+ free(gej_shuffled);
+ }
+
+ /* Test batch gej -> ge conversion. */
+ {
+ secp256k1_ge_t *ge_set_all = malloc((4 * runs + 1) * sizeof(secp256k1_ge_t));
+ secp256k1_ge_set_all_gej_var(4 * runs + 1, ge_set_all, gej);
+ for (int i = 0; i < 4 * runs + 1; i++) {
+ ge_equals_gej(&ge_set_all[i], &gej[i]);
+ }
+ free(ge_set_all);
+ }
+
+ free(ge);
+ free(gej);
}
void run_ge(void) {
- for (int i = 0; i < 2000*count; i++) {
+ for (int i = 0; i < count * 32; i++) {
test_ge();
}
}
@@ -949,6 +1111,44 @@ void run_ecdsa_sign_verify(void) {
}
}
+/** Dummy nonce generation function that just uses a precomputed nonce, and fails if it is not accepted. Use only for testing. */
+static int precomputed_nonce_function(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
+ (void)msg32;
+ (void)key32;
+ memcpy(nonce32, data, 32);
+ return (counter == 0);
+}
+
+static int nonce_function_test_fail(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
+ /* Dummy nonce generator that has a fatal error on the first counter value. */
+ if (counter == 0) return 0;
+ return nonce_function_rfc6979(nonce32, msg32, key32, counter - 1, data);
+}
+
+static int nonce_function_test_retry(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
+ /* Dummy nonce generator that produces unacceptable nonces for the first several counter values. */
+ if (counter < 3) {
+ memset(nonce32, counter==0 ? 0 : 255, 32);
+ if (counter == 2) nonce32[31]--;
+ return 1;
+ }
+ if (counter < 5) {
+ static const unsigned char order[] = {
+ 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
+ };
+ memcpy(nonce32, order, 32);
+ if (counter == 4) nonce32[31]++;
+ return 1;
+ }
+ /* Retry rate of 6979 is negligible esp. as we only call this in determinstic tests. */
+ /* If someone does fine a case where it retries for secp256k1, we'd like to know. */
+ if (counter > 5) return 0;
+ return nonce_function_rfc6979(nonce32, msg32, key32, counter - 5, data);
+}
+
void test_ecdsa_end_to_end(void) {
unsigned char privkey[32];
unsigned char message[32];
@@ -1006,13 +1206,7 @@ void test_ecdsa_end_to_end(void) {
/* Sign. */
unsigned char signature[72]; int signaturelen = 72;
- while(1) {
- unsigned char rnd[32];
- secp256k1_rand256_test(rnd);
- if (secp256k1_ecdsa_sign(message, signature, &signaturelen, privkey, rnd) == 1) {
- break;
- }
- }
+ CHECK(secp256k1_ecdsa_sign(message, signature, &signaturelen, privkey, NULL, NULL) == 1);
/* Verify. */
CHECK(secp256k1_ecdsa_verify(message, signature, signaturelen, pubkey, pubkeylen) == 1);
/* Destroy signature and verify again. */
@@ -1021,13 +1215,7 @@ void test_ecdsa_end_to_end(void) {
/* 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, csignature, privkey, rnd, &recid) == 1) {
- break;
- }
- }
+ CHECK(secp256k1_ecdsa_sign_compact(message, csignature, privkey, NULL, NULL, &recid) == 1);
/* Recover. */
unsigned char recpubkey[65]; int recpubkeylen = 0;
CHECK(secp256k1_ecdsa_recover_compact(message, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
@@ -1077,7 +1265,7 @@ void test_random_pubkeys(void) {
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));
+ 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);
@@ -1086,7 +1274,7 @@ void test_random_pubkeys(void) {
else CHECK(!res);
}
if (res) {
- CHECK(ge_equals_ge(&elem,&elem2));
+ ge_equals_ge(&elem,&elem2);
CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
CHECK(memcmp(&in[1], &out[1], 64) == 0);
}
@@ -1280,6 +1468,12 @@ void test_ecdsa_edge_cases(void) {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
};
+ static const unsigned char nonce2[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,0x40
+ };
const unsigned char key[32] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
@@ -1294,10 +1488,74 @@ void test_ecdsa_edge_cases(void) {
};
unsigned char sig[72];
int siglen = 72;
- CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce) == 0);
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 0);
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 0);
msg[31] = 0xaa;
siglen = 72;
- CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce) == 1);
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 1);
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 1);
+ siglen = 10;
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) != 1);
+ }
+
+ /* Nonce function corner cases. */
+ {
+ unsigned char key[32];
+ unsigned char msg[32];
+ unsigned char sig[72];
+ memset(key, 0, 32);
+ memset(msg, 0, 32);
+ key[31] = 1;
+ msg[31] = 1;
+ int siglen = 72;
+ int recid;
+ /* Nonce function failure results in signature failure. */
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_fail, NULL) == 0);
+ CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, nonce_function_test_fail, NULL, &recid) == 0);
+ /* The retry loop successfully makes its way to the first good value. */
+ unsigned char sig2[72];
+ int siglen2 = 72;
+ siglen = 72;
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_retry, NULL) == 1);
+ CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, nonce_function_rfc6979, NULL) == 1);
+ CHECK((siglen == siglen2) && (memcmp(sig, sig2, siglen) == 0));
+ int recid2;
+ CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, nonce_function_test_retry, NULL, &recid) == 1);
+ CHECK(secp256k1_ecdsa_sign_compact(msg, sig2, key, nonce_function_rfc6979, NULL, &recid2) == 1);
+ CHECK((recid == recid2) && (memcmp(sig, sig2, 64) == 0));
+ /* The default nonce function is determinstic. */
+ siglen = 72;
+ siglen2 = 72;
+ CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, NULL) == 1);
+ CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, NULL) == 1);
+ CHECK((siglen == siglen2) && (memcmp(sig, sig2, siglen) == 0));
+ CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, NULL, NULL, &recid) == 1);
+ CHECK(secp256k1_ecdsa_sign_compact(msg, sig2, key, NULL, NULL, &recid2) == 1);
+ CHECK((recid == recid2) && (memcmp(sig, sig2, 64) == 0));
+ /* The default nonce function changes output with different messages. */
+ secp256k1_ecdsa_sig_t s[512];
+ for(int i=0; i<256; i++) {
+ siglen2 = 72;
+ msg[0] = i;
+ CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, NULL) == 1);
+ CHECK(secp256k1_ecdsa_sig_parse(&s[i], sig2, siglen2));
+ for (int j=0; j<i; j++) {
+ CHECK(!secp256k1_scalar_eq(&s[i].r, &s[j].r));
+ }
+ }
+ msg[0] = 0;
+ msg[31] = 2;
+ /* The default nonce function changes output with different keys. */
+ for(int i=256; i<512; i++) {
+ siglen2 = 72;
+ key[0] = i - 256;
+ CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, NULL) == 1);
+ CHECK(secp256k1_ecdsa_sig_parse(&s[i], sig2, siglen2));
+ for (int j=0; j<i; j++) {
+ CHECK(!secp256k1_scalar_eq(&s[i].r, &s[j].r));
+ }
+ }
+ key[0] = 0;
}
/* Privkey export where pubkey is the point at infinity. */
@@ -1405,6 +1663,10 @@ int main(int argc, char **argv) {
secp256k1_scalar_start();
secp256k1_ecdsa_start();
+ run_sha256_tests();
+ run_hmac_sha256_tests();
+ run_rfc6979_hmac_sha256_tests();
+
#ifndef USE_NUM_NONE
/* num tests */
run_num_smalltests();
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-11 07:24:38 +0000