diff --git a/src/secp256k1/.travis.yml b/src/secp256k1/.travis.yml index b574a58b5..c65d7b9cb 100644 --- a/src/secp256k1/.travis.yml +++ b/src/secp256k1/.travis.yml @@ -1,131 +1,130 @@ language: c os: - linux - osx dist: bionic # Valgrind currently supports upto macOS 10.13, the latest xcode of that version is 10.1 osx_image: xcode10.1 addons: apt: packages: - gcc-multilib - libc6-dbg:i386 - libgmp-dev - libgmp-dev:i386 - libtool-bin - ninja-build - valgrind homebrew: packages: - cmake - gcc@9 - gmp - ninja - valgrind update: true install: - if [ "${TRAVIS_OS_NAME}" = "linux" ] && [ "${TRAVIS_CPU_ARCH}" = "amd64" ]; then ./travis/install_cmake.sh; fi cache: directories: - /opt/cmake compiler: - clang - gcc env: global: - - FIELD=auto + - WIDEMUL=auto - BIGNUM=gmp - - SCALAR=auto - ENDOMORPHISM=no - STATICPRECOMPUTATION=yes - ECMULTGENPRECISION=auto - ASM=no - AUTOTOOLS_TARGET=check - CMAKE_TARGET=check-secp256k1 - AUTOTOOLS_EXTRA_FLAGS= - CMAKE_EXTRA_FLAGS= - HOST= - ECDH=no - RECOVERY=no - SCHNORR=yes - EXPERIMENTAL=no - JNI=no - OPENSSL_TESTS=auto - MULTISET=no - CTIMETEST=yes - BENCH=yes - ITERS=2 jobs: - - SCALAR=32bit RECOVERY=yes - - SCALAR=32bit FIELD=32bit ECDH=yes EXPERIMENTAL=yes MULTISET=yes - - SCALAR=64bit - - FIELD=64bit RECOVERY=yes - - FIELD=64bit ENDOMORPHISM=yes - - FIELD=64bit ENDOMORPHISM=yes ECDH=yes EXPERIMENTAL=yes MULTISET=yes - - FIELD=64bit ASM=x86_64 - - FIELD=64bit ENDOMORPHISM=yes ASM=x86_64 - - FIELD=32bit ENDOMORPHISM=yes + - WIDEMUL=int64 RECOVERY=yes + - WIDEMUL=int64 ECDH=yes EXPERIMENTAL=yes MULTISET=yes + - WIDEMUL=int64 ENDOMORPHISM=yes + - WIDEMUL=int128 + - WIDEMUL=int128 RECOVERY=yes + - WIDEMUL=int128 ENDOMORPHISM=yes + - WIDEMUL=int128 ENDOMORPHISM=yes ECDH=yes EXPERIMENTAL=yes MULTISET=yes + - WIDEMUL=int128 ASM=x86_64 + - WIDEMUL=int128 ENDOMORPHISM=yes ASM=x86_64 - BIGNUM=no - BIGNUM=no ENDOMORPHISM=yes RECOVERY=yes EXPERIMENTAL=yes MULTISET=yes - BIGNUM=no STATICPRECOMPUTATION=no - AUTOTOOLS_TARGET=distcheck CMAKE_TARGET=install CTIMETEST= BENCH= - AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DDETERMINISTIC CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DDETERMINISTIC - AUTOTOOLS_EXTRA_FLAGS=CFLAGS=-O0 CMAKE_EXTRA_FLAGS=-DCMAKE_BUILD_TYPE=Debug CTIMETEST= - AUTOTOOLS_TARGET=check-java CMAKE_TARGET=check-secp256k1-java JNI=yes ECDH=yes EXPERIMENTAL=yes CTIMETEST= BENCH= - ECMULTGENPRECISION=2 - ECMULTGENPRECISION=8 - VALGRIND=yes BIGNUM=no ENDOMORPHISM=yes ASM=x86_64 EXPERIMENTAL=yes ECDH=yes RECOVERY=yes OPENSSL_TESTS=no MULTISET=yes AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND AUTOTOOLS_TARGET= CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND CMAKE_TARGET="secp256k1-tests secp256k1-exhaustive_tests" # The same as above but without endomorphism. - VALGRIND=yes BIGNUM=no ASM=x86_64 EXPERIMENTAL=yes ECDH=yes RECOVERY=yes OPENSSL_TESTS=no MULTISET=yes AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND AUTOTOOLS_TARGET= CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND CMAKE_TARGET="secp256k1-tests secp256k1-exhaustive_tests" - SCHNORR=no jobs: fast_finish: true include: - compiler: clang os: linux env: HOST=i686-linux-gnu ENDOMORPHISM=yes OPENSSL_TESTS=no - compiler: clang os: linux env: HOST=i686-linux-gnu BIGNUM=no OPENSSL_TESTS=no - compiler: gcc os: linux env: HOST=i686-linux-gnu ENDOMORPHISM=yes BIGNUM=no OPENSSL_TESTS=no - compiler: gcc os: linux env: HOST=i686-linux-gnu OPENSSL_TESTS=no # S390x build (big endian system) - dist: focal compiler: gcc env: HOST=s390x-unknown-linux-gnu OPENSSL_TESTS=no ECDH=yes RECOVERY=yes EXPERIMENTAL=yes MULTISET=yes CTIMETEST= arch: s390x addons: apt: packages: - cmake - libgmp-dev - libtool-bin - ninja-build before_script: # This limits the iterations in the benchmarks below to ITER iterations. - export SECP256K1_BENCH_ITERS="$ITERS" # travis auto terminates jobs that go for 10 minutes without printing to stdout, # but travis_wait doesn't work well with forking programs like valgrind # (https://docs.travis-ci.com/user/common-build-problems/#build-times-out-because-no-output-was-received https://github.com/bitcoin-core/secp256k1/pull/750#issuecomment-623476860) script: - function keep_alive() { while true; do echo -en "\a"; sleep 60; done } - keep_alive & - ./travis/build_autotools.sh - ./travis/build_cmake.sh - kill %keep_alive after_script: - valgrind --version diff --git a/src/secp256k1/CMakeLists.txt b/src/secp256k1/CMakeLists.txt index c8c793786..f81728a48 100644 --- a/src/secp256k1/CMakeLists.txt +++ b/src/secp256k1/CMakeLists.txt @@ -1,430 +1,380 @@ # Copyright (c) 2017 The Bitcoin developers cmake_minimum_required(VERSION 3.16) project(secp256k1 LANGUAGES C VERSION 0.1.0) # Add path for custom modules when building as a standalone project list(APPEND CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake/modules) # Default to RelWithDebInfo configuration if(NOT CMAKE_BUILD_TYPE) set(CMAKE_BUILD_TYPE RelWithDebInfo CACHE STRING "Select the configuration for the build" FORCE) set(__NO_USER_CMAKE_BUILD_TYPE ON CACHE BOOL "True if the user didn't set a build type on the command line") endif() option(SECP256K1_ENABLE_COVERAGE "Enable coverage" OFF) option(SECP256K1_ENABLE_BRANCH_COVERAGE "Enable branch coverage" OFF) include(AddCompilerFlags) if(SECP256K1_ENABLE_COVERAGE) include(Coverage) enable_coverage(${SECP256K1_ENABLE_BRANCH_COVERAGE}) exclude_from_coverage("${CMAKE_CURRENT_SOURCE_DIR}/src/bench") # If no build type is manually defined, override the optimization level. # Otherwise, alert the user than the coverage result might be useless. if(__NO_USER_CMAKE_BUILD_TYPE) set_c_optimization_level(0) else() message(WARNING "It is advised to not enforce CMAKE_BUILD_TYPE to get the best coverage results") endif() set(COVERAGE 1) endif() # libsecp256k1 use a different set of flags. add_c_compiler_flags( -pedantic -Wall -Wextra -Wcast-align -Wshadow -Wno-unused-function -Wno-overlength-strings -std=c89 -Wnested-externs -Wstrict-prototypes -Wno-long-long ) # Default visibility is hidden on all targets. set(CMAKE_C_VISIBILITY_PRESET hidden) include_directories( . src # For the config ${CMAKE_CURRENT_BINARY_DIR}/src ) # The library add_library(secp256k1 src/secp256k1.c) target_include_directories(secp256k1 PUBLIC include) set(SECP256K1_PUBLIC_HEADERS include/secp256k1.h include/secp256k1_preallocated.h ) option(SECP256K1_ENABLE_BIGNUM "Use the GMP bignum implementation" OFF) if(SECP256K1_ENABLE_BIGNUM) # We need to link in GMP find_package(GMP REQUIRED) target_link_libraries(secp256k1 GMP::gmp) set(USE_NUM_GMP 1) set(USE_FIELD_INV_NUM 1) set(USE_SCALAR_INV_NUM 1) else() set(USE_NUM_NONE 1) set(USE_FIELD_INV_BUILTIN 1) set(USE_SCALAR_INV_BUILTIN 1) endif() # Guess the target architecture, within the ones with supported ASM. # First check if the CMAKE_C_COMPILER_TARGET is set (should be when # cross compiling), then CMAKE_SYSTEM_PROCESSOR as a fallback if meaningful # (this is not the case for ARM as the content is highly non standard). if(CMAKE_C_COMPILER_TARGET MATCHES "x86_64" OR CMAKE_SYSTEM_PROCESSOR MATCHES "x86_64") set(SECP256K1_ASM_BUILD_TARGET "x86_64") set(SECP256K1_DEFAULT_USE_ASM ON) elseif(CMAKE_C_COMPILER_TARGET MATCHES "arm-linux-gnueabihf") set(SECP256K1_ASM_BUILD_TARGET "arm-linux-gnueabihf") set(SECP256K1_DEFAULT_USE_ASM ON) endif() # Enable ASM by default only if we are building for a compatible target. # The user can still enable/disable it manually if needed. option(SECP256K1_USE_ASM "Use assembly" ${SECP256K1_DEFAULT_USE_ASM}) if(SECP256K1_USE_ASM) macro(unsupported_asm_error) message(FATAL_ERROR "Assembly is enabled, but not supported for your target architecture." "Re-run cmake with -DSECP256K1_USE_ASM=OFF to disable ASM support." ) endmacro() if(SECP256K1_ASM_BUILD_TARGET MATCHES "x86_64") # We check if amd64 asm is supported. check_c_source_compiles(" #include int main() { uint64_t a = 11, tmp; __asm__ __volatile__(\"movq \$0x100000000,%1; mulq %%rsi\" : \"+a\"(a) : \"S\"(tmp) : \"cc\", \"%rdx\"); return 0; } " USE_ASM_X86_64) if(NOT USE_ASM_X86_64) unsupported_asm_error() endif() elseif(SECP256K1_ASM_BUILD_TARGET MATCHES "arm-linux-gnueabihf") enable_language(ASM) set(USE_EXTERNAL_ASM 1) add_library(secp256k1_common src/asm/field_10x26_arm.s) target_link_libraries(secp256k1 secp256k1_common) else() unsupported_asm_error() endif() endif() -# We make sure __int128 is defined -include(CheckTypeSize) -check_type_size(__int128 SIZEOF___INT128) -if(SIZEOF___INT128 EQUAL 16) - set(HAVE___INT128 1) -else() - # If we do not support __int128, we should be falling back - # on 32bits implementations for field and scalar. -endif() - -# Select the finite field implementation to use. -# This can be autodetected or forced by setting USE_FIELD to 32bit or 64bit. -# See the truth table below: -# +----------------------------------------------------------------------------------------------------------------------+ -# | USE_FIELD=64bit | USE_FIELD=32bit | HAVE___INT128 | USE_ASM_X86_64 | USE_FIELD_5X52 | USE_FIELD_10x26 | Config error | -# +----------------------------------------------------------------------------------------------------------------------+ -# | 0 | 0 | 0 | 0 | 0 | 1 | 0 | -# | 0 | 0 | 0 | 1 | 1 | 0 | 0 | -# | 0 | 0 | 1 | 0 | 1 | 0 | 0 | -# | 0 | 0 | 1 | 1 | 1 | 0 | 0 | -# | 0 | 1 | 0 | 0 | 0 | 1 | 0 | -# | 0 | 1 | 0 | 1 | 0 | 1 | 0 | -# | 0 | 1 | 1 | 0 | 0 | 1 | 0 | -# | 0 | 1 | 1 | 1 | 0 | 1 | 0 | -# | 1 | 0 | 0 | 0 | 0 | 0 | 1 | -# | 1 | 0 | 0 | 1 | 1 | 0 | 0 | -# | 1 | 0 | 1 | 0 | 1 | 0 | 0 | -# | 1 | 0 | 1 | 1 | 1 | 0 | 0 | -# +----------------------------------------------------------------------------------------------------------------------+ -set(USE_FIELD "" CACHE STRING "Force the finite field implementation to use (can be 32bit or 64bit)") -if(USE_FIELD STREQUAL "64bit" AND NOT (HAVE___INT128 OR USE_ASM_X86_64)) - message(SEND_ERROR "64 finite field requested but the compiler does not support __int128 or inline assembly") -elseif(NOT USE_FIELD STREQUAL "32bit" AND (HAVE___INT128 OR USE_ASM_X86_64)) - set(USE_FIELD_5X52 1) -else() - set(USE_FIELD_10X26 1) -endif() - -# Select the scalar implementation to use. -# This can be autodetected or forced by setting USE_SCALAR to 32bit or 64bit. -# See the truth table below: -# +--------------------------------------------------------------------------------------------------------+ -# | USE_SCALAR=64bit | USE_SCALAR=32bit | HAVE___INT128 | USE_SCALAR_4X64 | USE_SCALAR_8X32 | Config error | -# +--------------------------------------------------------------------------------------------------------+ -# | 0 | 0 | 0 | 0 | 1 | 0 | -# | 0 | 0 | 1 | 1 | 0 | 0 | -# | 0 | 1 | 0 | 0 | 1 | 0 | -# | 0 | 1 | 1 | 0 | 1 | 0 | -# | 1 | 0 | 0 | 0 | 0 | 1 | -# | 1 | 0 | 1 | 1 | 0 | 0 | -# +--------------------------------------------------------------------------------------------------------+ -set(USE_SCALAR "" CACHE STRING "Force the scalar implementation to use (can be 32bit or 64bit)") -if(USE_SCALAR STREQUAL "64bit" AND NOT HAVE___INT128) - message(SEND_ERROR "64 scalar requested but the compiler does not support __int128") -elseif(NOT USE_SCALAR STREQUAL "32bit" AND HAVE___INT128) - set(USE_SCALAR_4X64 1) -else() - set(USE_SCALAR_8X32 1) +set(SECP256K1_TEST_OVERRIDE_WIDE_MULTIPLY "" CACHE STRING "Test-only override of the (autodetected by the C code) \"widemul\" setting (can be int64 or int128)") +if(SECP256K1_TEST_OVERRIDE_WIDE_MULTIPLY STREQUAL "int128") + message(STATUS "Force the use of the (unsigned) __int128 based wide multiplication implementation") + target_compile_definitions(secp256k1 PUBLIC USE_FORCE_WIDEMUL_INT128=1) +elseif(SECP256K1_TEST_OVERRIDE_WIDE_MULTIPLY STREQUAL "int64") + message(STATUS "Force the use of the (u)int64_t based wide multiplication implementation") + target_compile_definitions(secp256k1 PUBLIC USE_FORCE_WIDEMUL_INT64=1) endif() option(SECP256K1_BUILD_TEST "Build secp256k1's unit tests" ON) include(CMakeDependentOption) cmake_dependent_option( SECP256K1_BUILD_OPENSSL_TESTS "Build the OpenSSL tests" ON SECP256K1_BUILD_TEST ON ) if(SECP256K1_BUILD_OPENSSL_TESTS) include(BrewHelper) find_brew_prefix(OPENSSL_ROOT_DIR openssl) find_package(OpenSSL COMPONENTS Crypto) if(NOT OpenSSL_FOUND) message(FATAL_ERROR "OpenSSL is not found, but is required for some tests. You can disable them by passing -DSECP256K1_BUILD_OPENSSL_TESTS=OFF." ) endif() set(ENABLE_OPENSSL_TESTS 1) endif() # Executable internal to secp256k1 need to have the HAVE_CONFIG_H define set. # For convenience, we wrap this into a function. function(link_secp256k1_internal NAME) target_link_libraries(${NAME} secp256k1) target_compile_definitions(${NAME} PRIVATE HAVE_CONFIG_H SECP256K1_BUILD) if(SECP256K1_BUILD_OPENSSL_TESTS) target_link_libraries(${NAME} OpenSSL::Crypto) endif() endfunction(link_secp256k1_internal) include(InstallationHelper) # Phony target to build benchmarks add_custom_target(bench-secp256k1) function(add_secp256k1_bench NAME) set(EXECUTABLE_NAME "${NAME}-bench") add_executable(${EXECUTABLE_NAME} ${ARGN}) link_secp256k1_internal(${EXECUTABLE_NAME}) set(BENCH_NAME "bench-secp256k1-${NAME}") add_custom_target(${BENCH_NAME} COMMENT "Benchmarking libsecp256k1 ${NAME}" COMMAND ${EXECUTABLE_NAME} USES_TERMINAL ) add_dependencies(bench-secp256k1 ${BENCH_NAME}) install_target("${EXECUTABLE_NAME}" COMPONENT secp256k1-bench EXCLUDE_FROM_ALL ) endfunction(add_secp256k1_bench) # ECDH module option(SECP256K1_ENABLE_MODULE_ECDH "Build libsecp256k1's ECDH module" OFF) if(SECP256K1_ENABLE_MODULE_ECDH) set(ENABLE_MODULE_ECDH 1) add_secp256k1_bench(ecdh src/bench_ecdh.c) list(APPEND SECP256K1_PUBLIC_HEADERS include/secp256k1_ecdh.h) endif() # MultiSet module option(SECP256K1_ENABLE_MODULE_MULTISET "Build libsecp256k1's MULTISET module" OFF) if(SECP256K1_ENABLE_MODULE_MULTISET) set(ENABLE_MODULE_MULTISET 1) add_secp256k1_bench(multiset src/bench_multiset.c) list(APPEND SECP256K1_PUBLIC_HEADERS include/secp256k1_multiset.h) endif() # Recovery module option(SECP256K1_ENABLE_MODULE_RECOVERY "Build libsecp256k1's recovery module" ON) if(SECP256K1_ENABLE_MODULE_RECOVERY) set(ENABLE_MODULE_RECOVERY 1) add_secp256k1_bench(recover src/bench_recover.c) list(APPEND SECP256K1_PUBLIC_HEADERS include/secp256k1_recovery.h) endif() # Schnorr module option(SECP256K1_ENABLE_MODULE_SCHNORR "Build libsecp256k1's Schnorr module" ON) if(SECP256K1_ENABLE_MODULE_SCHNORR) set(ENABLE_MODULE_SCHNORR 1) list(APPEND SECP256K1_PUBLIC_HEADERS include/secp256k1_schnorr.h) endif() # External default callbacks option(SECP256K1_ENABLE_EXTERNAL_DEFAULT_CALLBACKS "Enable external default callbacks" OFF) if(SECP256K1_ENABLE_EXTERNAL_DEFAULT_CALLBACKS) set(USE_EXTERNAL_DEFAULT_CALLBACKS 1) endif() # Endomorphism option(SECP256K1_ENABLE_ENDOMORPHISM "Enable endomorphism" OFF) if(SECP256K1_ENABLE_ENDOMORPHISM) set(USE_ENDOMORPHISM 1) endif() # Make the emult window size customizable. set(SECP256K1_ECMULT_WINDOW_SIZE 15 CACHE STRING "Window size for ecmult precomputation for verification, specified as integer in range [2..24].") if(${SECP256K1_ECMULT_WINDOW_SIZE} LESS 2 OR ${SECP256K1_ECMULT_WINDOW_SIZE} GREATER 24) message(FATAL_ERROR "SECP256K1_ECMULT_WINDOW_SIZE must be an integer in range [2..24]") endif() set(SECP256K1_ECMULT_GEN_PRECISION 4 CACHE STRING "Precision bits to tune the precomputed table size for signing.") set(VALID_PRECISIONS 2 4 8) if(NOT ${SECP256K1_ECMULT_GEN_PRECISION} IN_LIST VALID_PRECISIONS) message(FATAL_ERROR "SECP256K1_ECMULT_GEN_PRECISION not 2, 4, 8") endif() # Static precomputation for elliptic curve multiplication option(SECP256K1_ECMULT_STATIC_PRECOMPUTATION "Precompute libsecp256k1's elliptic curve multiplication tables" ON) if(SECP256K1_ECMULT_STATIC_PRECOMPUTATION) set(USE_ECMULT_STATIC_PRECOMPUTATION 1) include(NativeExecutable) native_add_cmake_flags( "-DSECP256K1_ECMULT_WINDOW_SIZE=${SECP256K1_ECMULT_WINDOW_SIZE}" "-DSECP256K1_ECMULT_GEN_PRECISION=${SECP256K1_ECMULT_GEN_PRECISION}" "-DSECP256K1_USE_ASM=OFF" + "-DSECP256K1_TEST_OVERRIDE_WIDE_MULTIPLY=${SECP256K1_TEST_OVERRIDE_WIDE_MULTIPLY}" ) add_native_executable(gen_context src/gen_context.c) add_custom_command( OUTPUT src/ecmult_static_context.h COMMAND gen_context ) target_sources(secp256k1 PRIVATE src/ecmult_static_context.h) endif() # If this project is not the top level project, then don't install by default get_directory_property(SECP256K1_PARENT_DIRECTORY PARENT_DIRECTORY) if(SECP256K1_PARENT_DIRECTORY) set(SECP256K1_INSTALL_EXCLUDE_FROM_ALL EXCLUDE_FROM_ALL) endif() if(BUILD_SHARED_LIBS) install_shared_library(secp256k1 PUBLIC_HEADER ${SECP256K1_PUBLIC_HEADERS} ${SECP256K1_INSTALL_EXCLUDE_FROM_ALL} ) else() set_property(TARGET secp256k1 PROPERTY PUBLIC_HEADER ${SECP256K1_PUBLIC_HEADERS}) install_target(secp256k1 ${SECP256K1_INSTALL_EXCLUDE_FROM_ALL}) endif() # Generate the config configure_file(src/libsecp256k1-config.h.cmake.in src/libsecp256k1-config.h ESCAPE_QUOTES) target_compile_definitions(secp256k1 PRIVATE HAVE_CONFIG_H SECP256K1_BUILD) # Build the Java binding option(SECP256K1_ENABLE_JNI "Enable the Java Native Interface binding" OFF) if(SECP256K1_ENABLE_JNI) if(NOT SECP256K1_ENABLE_MODULE_ECDH) message(FATAL_ERROR "The secp256k1 JNI support requires ECDH. Try again with -DSECP256K1_ENABLE_MODULE_ECDH=ON.") endif() find_package(Java REQUIRED) find_package(JNI REQUIRED) include(UseJava) add_library(secp256k1_jni SHARED src/java/org_bitcoin_NativeSecp256k1.c src/java/org_bitcoin_Secp256k1Context.c ) install_shared_library(secp256k1_jni ${SECP256K1_INSTALL_EXCLUDE_FROM_ALL}) target_include_directories(secp256k1_jni PUBLIC ${JNI_INCLUDE_DIRS}) # As per CMake documentation: the POSITION_INDEPENDENT_CODE property is set # when a target is created. It defaults to True for SHARED or MODULE library # targets and False otherwise. # The secp256ki_jni library being shared, the property is set and it will # build with PIC enabled. But the secp256k1 dependency might not have the # property set, so it's associated source files won't be built with PIC # enabled. That would cause the linker to fail. # Forcing the property for the secp256k1 library fixes the issue. set_target_properties(secp256k1 PROPERTIES POSITION_INDEPENDENT_CODE ON) link_secp256k1_internal(secp256k1_jni) endif() # Tests if(SECP256K1_BUILD_TEST) include(TestSuite) create_test_suite(secp256k1) function(create_secp256k1_test NAME FILES) add_test_to_suite(secp256k1 ${NAME} EXCLUDE_FROM_ALL ${FILES}) link_secp256k1_internal(${NAME}) endfunction() create_secp256k1_test(secp256k1-tests src/tests.c) create_secp256k1_test(secp256k1-exhaustive_tests src/tests_exhaustive.c) # This should not be enabled at the same time as coverage is. # The VERIFY failure branch is not expected to be reached, so it would make # coverage appear lower if set. if(NOT SECP256K1_ENABLE_COVERAGE) target_compile_definitions(secp256k1-tests PRIVATE VERIFY) target_compile_definitions(secp256k1-exhaustive_tests PRIVATE VERIFY) endif() if(SECP256K1_ENABLE_JNI) set(SECP256k1_JNI_TEST_JAR "secp256k1-jni-test") set(CMAKE_JNI_TARGET TRUE) add_jar(secp256k1-jni-test-jar SOURCES src/java/org/bitcoin/NativeSecp256k1.java src/java/org/bitcoin/NativeSecp256k1Test.java src/java/org/bitcoin/NativeSecp256k1Util.java src/java/org/bitcoin/Secp256k1Context.java ENTRY_POINT org/bitcoin/NativeSecp256k1Test OUTPUT_NAME "${SECP256k1_JNI_TEST_JAR}" ) add_dependencies(secp256k1-jni-test-jar secp256k1_jni) add_custom_target(check-secp256k1-java COMMAND "${Java_JAVA_EXECUTABLE}" "-Djava.library.path=${CMAKE_CURRENT_BINARY_DIR}" "-jar" "${SECP256k1_JNI_TEST_JAR}.jar" WORKING_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}" ) add_dependencies(check-secp256k1-java secp256k1-jni-test-jar) add_dependencies(check-secp256k1 check-secp256k1-java) endif() endif(SECP256K1_BUILD_TEST) # Benchmarks add_secp256k1_bench(verify src/bench_verify.c) add_secp256k1_bench(sign src/bench_sign.c) add_secp256k1_bench(internal src/bench_internal.c) add_secp256k1_bench(ecmult src/bench_ecmult.c) diff --git a/src/secp256k1/build-aux/m4/bitcoin_secp.m4 b/src/secp256k1/build-aux/m4/bitcoin_secp.m4 index 1b2b71e6a..57595f449 100644 --- a/src/secp256k1/build-aux/m4/bitcoin_secp.m4 +++ b/src/secp256k1/build-aux/m4/bitcoin_secp.m4 @@ -1,71 +1,66 @@ -dnl libsecp25k1 helper checks -AC_DEFUN([SECP_INT128_CHECK],[ -has_int128=$ac_cv_type___int128 -]) - dnl escape "$0x" below using the m4 quadrigaph @S|@, and escape it again with a \ for the shell. AC_DEFUN([SECP_64BIT_ASM_CHECK],[ AC_MSG_CHECKING(for x86_64 assembly availability) AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[ #include ]],[[ uint64_t a = 11, tmp; __asm__ __volatile__("movq \@S|@0x100000000,%1; mulq %%rsi" : "+a"(a) : "S"(tmp) : "cc", "%rdx"); ]])],[has_64bit_asm=yes],[has_64bit_asm=no]) AC_MSG_RESULT([$has_64bit_asm]) ]) dnl AC_DEFUN([SECP_OPENSSL_CHECK],[ has_libcrypto=no m4_ifdef([PKG_CHECK_MODULES],[ PKG_CHECK_MODULES([CRYPTO], [libcrypto], [has_libcrypto=yes],[has_libcrypto=no]) if test x"$has_libcrypto" = x"yes"; then TEMP_LIBS="$LIBS" LIBS="$LIBS $CRYPTO_LIBS" AC_CHECK_LIB(crypto, main,[AC_DEFINE(HAVE_LIBCRYPTO,1,[Define this symbol if libcrypto is installed])],[has_libcrypto=no]) LIBS="$TEMP_LIBS" fi ]) if test x$has_libcrypto = xno; then AC_CHECK_HEADER(openssl/crypto.h,[ AC_CHECK_LIB(crypto, main,[ has_libcrypto=yes CRYPTO_LIBS=-lcrypto AC_DEFINE(HAVE_LIBCRYPTO,1,[Define this symbol if libcrypto is installed]) ]) ]) LIBS= fi if test x"$has_libcrypto" = x"yes" && test x"$has_openssl_ec" = x; then AC_MSG_CHECKING(for EC functions in libcrypto) CPPFLAGS_TEMP="$CPPFLAGS" CPPFLAGS="$CRYPTO_CPPFLAGS $CPPFLAGS" AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[ #include #include #include ]],[[ EC_KEY *eckey = EC_KEY_new_by_curve_name(NID_secp256k1); ECDSA_sign(0, NULL, 0, NULL, NULL, eckey); ECDSA_verify(0, NULL, 0, NULL, 0, eckey); EC_KEY_free(eckey); ECDSA_SIG *sig_openssl; sig_openssl = ECDSA_SIG_new(); ECDSA_SIG_free(sig_openssl); ]])],[has_openssl_ec=yes],[has_openssl_ec=no]) AC_MSG_RESULT([$has_openssl_ec]) CPPFLAGS="$CPPFLAGS_TEMP" fi ]) dnl AC_DEFUN([SECP_GMP_CHECK],[ if test x"$has_gmp" != x"yes"; then CPPFLAGS_TEMP="$CPPFLAGS" CPPFLAGS="$GMP_CPPFLAGS $CPPFLAGS" LIBS_TEMP="$LIBS" LIBS="$GMP_LIBS $LIBS" AC_CHECK_HEADER(gmp.h,[AC_CHECK_LIB(gmp, __gmpz_init,[has_gmp=yes; GMP_LIBS="$GMP_LIBS -lgmp"; AC_DEFINE(HAVE_LIBGMP,1,[Define this symbol if libgmp is installed])])]) CPPFLAGS="$CPPFLAGS_TEMP" LIBS="$LIBS_TEMP" fi ]) diff --git a/src/secp256k1/configure.ac b/src/secp256k1/configure.ac index aff11672d..86d9703b9 100644 --- a/src/secp256k1/configure.ac +++ b/src/secp256k1/configure.ac @@ -1,634 +1,564 @@ AC_PREREQ([2.60]) AC_INIT([libsecp256k1],[0.1]) AC_CONFIG_AUX_DIR([build-aux]) AC_CONFIG_MACRO_DIR([build-aux/m4]) 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 subdir-objects]) # Set -g if CFLAGS are not already set, which matches the default autoconf # behavior (see PROG_CC in the Autoconf manual) with the exception that we don't # set -O2 here because we set it in any case (see further down). : ${CFLAGS="-g"} LT_INIT dnl make the compilation flags quiet unless V=1 is used m4_ifdef([AM_SILENT_RULES], [AM_SILENT_RULES([yes])]) PKG_PROG_PKG_CONFIG AC_PATH_TOOL(AR, ar) AC_PATH_TOOL(RANLIB, ranlib) AC_PATH_TOOL(STRIP, strip) AX_PROG_CC_FOR_BUILD AM_PROG_CC_C_O AC_PROG_CC_C89 if test x"$ac_cv_prog_cc_c89" = x"no"; then AC_MSG_ERROR([c89 compiler support required]) fi AM_PROG_AS case $host_os in *darwin*) if test x$cross_compiling != xyes; then AC_PATH_PROG([BREW],brew,) if test x$BREW != x; then dnl These Homebrew packages may be keg-only, meaning that they won't be found dnl in expected paths because they may conflict with system files. Ask dnl Homebrew where each one is located, then adjust paths accordingly. openssl_prefix=`$BREW --prefix openssl 2>/dev/null` gmp_prefix=`$BREW --prefix gmp 2>/dev/null` if test x$openssl_prefix != x; then PKG_CONFIG_PATH="$openssl_prefix/lib/pkgconfig:$PKG_CONFIG_PATH" export PKG_CONFIG_PATH CRYPTO_CPPFLAGS="-I$openssl_prefix/include" fi if test x$gmp_prefix != x; then GMP_CPPFLAGS="-I$gmp_prefix/include" GMP_LIBS="-L$gmp_prefix/lib" fi else AC_PATH_PROG([PORT],port,) dnl if homebrew isn't installed and macports is, add the macports default paths dnl as a last resort. if test x$PORT != x; then CPPFLAGS="$CPPFLAGS -isystem /opt/local/include" LDFLAGS="$LDFLAGS -L/opt/local/lib" fi fi fi ;; esac CFLAGS="-W $CFLAGS" warn_CFLAGS="-std=c89 -pedantic -Wall -Wextra -Wcast-align -Wnested-externs -Wshadow -Wstrict-prototypes -Wno-unused-function -Wno-long-long -Wno-overlength-strings" saved_CFLAGS="$CFLAGS" CFLAGS="$warn_CFLAGS $CFLAGS" AC_MSG_CHECKING([if ${CC} supports ${warn_CFLAGS}]) AC_COMPILE_IFELSE([AC_LANG_SOURCE([[char foo;]])], [ AC_MSG_RESULT([yes]) ], [ AC_MSG_RESULT([no]) CFLAGS="$saved_CFLAGS" ]) saved_CFLAGS="$CFLAGS" CFLAGS="-fvisibility=hidden $CFLAGS" AC_MSG_CHECKING([if ${CC} supports -fvisibility=hidden]) AC_COMPILE_IFELSE([AC_LANG_SOURCE([[char foo;]])], [ AC_MSG_RESULT([yes]) ], [ AC_MSG_RESULT([no]) CFLAGS="$saved_CFLAGS" ]) AC_ARG_ENABLE(benchmark, AS_HELP_STRING([--enable-benchmark],[compile benchmark [default=yes]]), [use_benchmark=$enableval], [use_benchmark=yes]) AC_ARG_ENABLE(coverage, AS_HELP_STRING([--enable-coverage],[enable compiler flags to support kcov coverage analysis [default=no]]), [enable_coverage=$enableval], [enable_coverage=no]) AC_ARG_ENABLE(tests, AS_HELP_STRING([--enable-tests],[compile tests [default=yes]]), [use_tests=$enableval], [use_tests=yes]) AC_ARG_ENABLE(openssl_tests, AS_HELP_STRING([--enable-openssl-tests],[enable OpenSSL tests [default=auto]]), [enable_openssl_tests=$enableval], [enable_openssl_tests=auto]) AC_ARG_ENABLE(experimental, AS_HELP_STRING([--enable-experimental],[allow experimental configure options [default=no]]), [use_experimental=$enableval], [use_experimental=no]) AC_ARG_ENABLE(exhaustive_tests, AS_HELP_STRING([--enable-exhaustive-tests],[compile exhaustive tests [default=yes]]), [use_exhaustive_tests=$enableval], [use_exhaustive_tests=yes]) AC_ARG_ENABLE(endomorphism, AS_HELP_STRING([--enable-endomorphism],[enable endomorphism [default=no]]), [use_endomorphism=$enableval], [use_endomorphism=no]) AC_ARG_ENABLE(ecmult_static_precomputation, AS_HELP_STRING([--enable-ecmult-static-precomputation],[enable precomputed ecmult table for signing [default=auto]]), [use_ecmult_static_precomputation=$enableval], [use_ecmult_static_precomputation=auto]) AC_ARG_ENABLE(module_ecdh, AS_HELP_STRING([--enable-module-ecdh],[enable ECDH shared secret computation (experimental)]), [enable_module_ecdh=$enableval], [enable_module_ecdh=no]) AC_ARG_ENABLE(module_multiset, AS_HELP_STRING([--enable-module-multiset],[enable multiset operations (experimental)]), [enable_module_multiset=$enableval], [enable_module_multiset=no]) AC_ARG_ENABLE(module_recovery, AS_HELP_STRING([--enable-module-recovery],[enable ECDSA pubkey recovery module [default=no]]), [enable_module_recovery=$enableval], [enable_module_recovery=no]) AC_ARG_ENABLE(module_schnorr, AS_HELP_STRING([--enable-module-schnorr],[enable Schnorr signatures module [default=yes]]), [enable_module_schnorr=$enableval], [enable_module_schnorr=yes]) AC_ARG_ENABLE(external_default_callbacks, AS_HELP_STRING([--enable-external-default-callbacks],[enable external default callback functions [default=no]]), [use_external_default_callbacks=$enableval], [use_external_default_callbacks=no]) +dnl Test-only override of the (autodetected by the C code) "widemul" setting. +dnl Legal values are int64 (for [u]int64_t), int128 (for [unsigned] __int128), and auto (the default). +AC_ARG_WITH([test-override-wide-multiply], [] ,[set_widemul=$withval], [set_widemul=auto]) + AC_ARG_ENABLE(jni, AS_HELP_STRING([--enable-jni],[enable libsecp256k1_jni [default=no]]), [use_jni=$enableval], [use_jni=no]) -AC_ARG_WITH([field], [AS_HELP_STRING([--with-field=64bit|32bit|auto], -[finite field implementation to use [default=auto]])],[req_field=$withval], [req_field=auto]) - AC_ARG_WITH([bignum], [AS_HELP_STRING([--with-bignum=gmp|no|auto], [bignum implementation to use [default=auto]])],[req_bignum=$withval], [req_bignum=auto]) -AC_ARG_WITH([scalar], [AS_HELP_STRING([--with-scalar=64bit|32bit|auto], -[scalar implementation to use [default=auto]])],[req_scalar=$withval], [req_scalar=auto]) - AC_ARG_WITH([asm], [AS_HELP_STRING([--with-asm=x86_64|arm|no|auto], [assembly optimizations to use (experimental: arm) [default=auto]])],[req_asm=$withval], [req_asm=auto]) AC_ARG_WITH([ecmult-window], [AS_HELP_STRING([--with-ecmult-window=SIZE|auto], [window size for ecmult precomputation for verification, specified as integer in range [2..24].] [Larger values result in possibly better performance at the cost of an exponentially larger precomputed table.] [The table will store 2^(SIZE-2) * 64 bytes of data but can be larger in memory due to platform-specific padding and alignment.] [If the endomorphism optimization is enabled, two tables of this size are used instead of only one.] ["auto" is a reasonable setting for desktop machines (currently 15). [default=auto]] )], [req_ecmult_window=$withval], [req_ecmult_window=auto]) AC_ARG_WITH([ecmult-gen-precision], [AS_HELP_STRING([--with-ecmult-gen-precision=2|4|8|auto], [Precision bits to tune the precomputed table size for signing.] [The size of the table is 32kB for 2 bits, 64kB for 4 bits, 512kB for 8 bits of precision.] [A larger table size usually results in possible faster signing.] ["auto" is a reasonable setting for desktop machines (currently 4). [default=auto]] )], [req_ecmult_gen_precision=$withval], [req_ecmult_gen_precision=auto]) -AC_CHECK_TYPES([__int128]) - AC_ARG_WITH([valgrind], [AS_HELP_STRING([--with-valgrind=yes|no|auto], [Build with extra checks for running inside Valgrind [default=auto]] )], [req_valgrind=$withval], [req_valgrind=auto]) if test x"$req_valgrind" = x"no"; then enable_valgrind=no else AC_CHECK_HEADER([valgrind/memcheck.h], [enable_valgrind=yes], [ if test x"$req_valgrind" = x"yes"; then AC_MSG_ERROR([Valgrind support explicitly requested but valgrind/memcheck.h header not available]) fi enable_valgrind=no ], []) fi AM_CONDITIONAL([VALGRIND_ENABLED],[test "$enable_valgrind" = "yes"]) if test x"$enable_coverage" = x"yes"; then AC_DEFINE(COVERAGE, 1, [Define this symbol to compile out all VERIFY code]) CFLAGS="-O0 --coverage $CFLAGS" LDFLAGS="--coverage $LDFLAGS" else CFLAGS="-O2 $CFLAGS" fi if test x"$use_ecmult_static_precomputation" != x"no"; then # Temporarily switch to an environment for the native compiler save_cross_compiling=$cross_compiling cross_compiling=no SAVE_CC="$CC" CC="$CC_FOR_BUILD" SAVE_CFLAGS="$CFLAGS" CFLAGS="$CFLAGS_FOR_BUILD" SAVE_CPPFLAGS="$CPPFLAGS" CPPFLAGS="$CPPFLAGS_FOR_BUILD" SAVE_LDFLAGS="$LDFLAGS" LDFLAGS="$LDFLAGS_FOR_BUILD" warn_CFLAGS_FOR_BUILD="-Wall -Wextra -Wno-unused-function" saved_CFLAGS="$CFLAGS" CFLAGS="$warn_CFLAGS_FOR_BUILD $CFLAGS" AC_MSG_CHECKING([if native ${CC_FOR_BUILD} supports ${warn_CFLAGS_FOR_BUILD}]) AC_COMPILE_IFELSE([AC_LANG_SOURCE([[char foo;]])], [ AC_MSG_RESULT([yes]) ], [ AC_MSG_RESULT([no]) CFLAGS="$saved_CFLAGS" ]) AC_MSG_CHECKING([for working native compiler: ${CC_FOR_BUILD}]) AC_RUN_IFELSE( [AC_LANG_PROGRAM([], [])], [working_native_cc=yes], [working_native_cc=no],[:]) CFLAGS_FOR_BUILD="$CFLAGS" # Restore the environment cross_compiling=$save_cross_compiling CC="$SAVE_CC" CFLAGS="$SAVE_CFLAGS" CPPFLAGS="$SAVE_CPPFLAGS" LDFLAGS="$SAVE_LDFLAGS" if test x"$working_native_cc" = x"no"; then AC_MSG_RESULT([no]) set_precomp=no m4_define([please_set_for_build], [Please set CC_FOR_BUILD, CFLAGS_FOR_BUILD, CPPFLAGS_FOR_BUILD, and/or LDFLAGS_FOR_BUILD.]) if test x"$use_ecmult_static_precomputation" = x"yes"; then AC_MSG_ERROR([native compiler ${CC_FOR_BUILD} does not produce working binaries. please_set_for_build]) else AC_MSG_WARN([Disabling statically generated ecmult table because the native compiler ${CC_FOR_BUILD} does not produce working binaries. please_set_for_build]) fi else AC_MSG_RESULT([yes]) set_precomp=yes fi else set_precomp=no fi if test x"$req_asm" = x"auto"; then SECP_64BIT_ASM_CHECK if test x"$has_64bit_asm" = x"yes"; then 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 ;; arm) ;; 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 - set_field=32bit - fi -else - set_field=$req_field - case $set_field in - 64bit) - 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) - ;; - *) - AC_MSG_ERROR([invalid field implementation selection]) - ;; - esac -fi - -if test x"$req_scalar" = x"auto"; then - 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 - fi -else - set_scalar=$req_scalar - 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) - ;; - *) - AC_MSG_ERROR([invalid scalar implementation selected]) - ;; - esac -fi - if test x"$req_bignum" = x"auto"; then SECP_GMP_CHECK if test x"$has_gmp" = x"yes"; then set_bignum=gmp fi if test x"$set_bignum" = x; then 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 ;; no) ;; *) AC_MSG_ERROR([invalid bignum implementation selection]) ;; esac fi # select assembly optimization use_external_asm=no case $set_asm in x86_64) AC_DEFINE(USE_ASM_X86_64, 1, [Define this symbol to enable x86_64 assembly optimizations]) ;; arm) use_external_asm=yes ;; no) ;; *) AC_MSG_ERROR([invalid assembly optimizations]) ;; esac -# select field implementation -case $set_field in -64bit) - AC_DEFINE(USE_FIELD_5X52, 1, [Define this symbol to use the FIELD_5X52 implementation]) +# select wide multiplication implementation +case $set_widemul in +int128) + AC_DEFINE(USE_FORCE_WIDEMUL_INT128, 1, [Define this symbol to force the use of the (unsigned) __int128 based wide multiplication implementation]) + ;; +int64) + AC_DEFINE(USE_FORCE_WIDEMUL_INT64, 1, [Define this symbol to force the use of the (u)int64_t based wide multiplication implementation]) ;; -32bit) - AC_DEFINE(USE_FIELD_10X26, 1, [Define this symbol to use the FIELD_10X26 implementation]) +auto) ;; *) - AC_MSG_ERROR([invalid field implementation]) + AC_MSG_ERROR([invalid wide multiplication implementation]) ;; esac # select bignum implementation case $set_bignum in gmp) AC_DEFINE(HAVE_LIBGMP, 1, [Define this symbol if libgmp is installed]) AC_DEFINE(USE_NUM_GMP, 1, [Define this symbol to use the gmp implementation for num]) 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]) ;; 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]) ;; *) AC_MSG_ERROR([invalid bignum implementation]) ;; esac -#select scalar implementation -case $set_scalar in -64bit) - AC_DEFINE(USE_SCALAR_4X64, 1, [Define this symbol to use the 4x64 scalar implementation]) - ;; -32bit) - AC_DEFINE(USE_SCALAR_8X32, 1, [Define this symbol to use the 8x32 scalar implementation]) - ;; -*) - AC_MSG_ERROR([invalid scalar implementation]) - ;; -esac - #set ecmult window size if test x"$req_ecmult_window" = x"auto"; then set_ecmult_window=15 else set_ecmult_window=$req_ecmult_window fi error_window_size=['window size for ecmult precomputation not an integer in range [2..24] or "auto"'] case $set_ecmult_window in ''|*[[!0-9]]*) # no valid integer AC_MSG_ERROR($error_window_size) ;; *) if test "$set_ecmult_window" -lt 2 -o "$set_ecmult_window" -gt 24 ; then # not in range AC_MSG_ERROR($error_window_size) fi AC_DEFINE_UNQUOTED(ECMULT_WINDOW_SIZE, $set_ecmult_window, [Set window size for ecmult precomputation]) ;; esac #set ecmult gen precision if test x"$req_ecmult_gen_precision" = x"auto"; then set_ecmult_gen_precision=4 else set_ecmult_gen_precision=$req_ecmult_gen_precision fi case $set_ecmult_gen_precision in 2|4|8) AC_DEFINE_UNQUOTED(ECMULT_GEN_PREC_BITS, $set_ecmult_gen_precision, [Set ecmult gen precision bits]) ;; *) AC_MSG_ERROR(['ecmult gen precision not 2, 4, 8 or "auto"']) ;; esac if test x"$use_tests" = x"yes"; then SECP_OPENSSL_CHECK if test x"$has_openssl_ec" = x"yes"; then if test x"$enable_openssl_tests" != x"no"; then AC_DEFINE(ENABLE_OPENSSL_TESTS, 1, [Define this symbol if OpenSSL EC functions are available]) SECP_TEST_INCLUDES="$SSL_CFLAGS $CRYPTO_CFLAGS $CRYPTO_CPPFLAGS" SECP_TEST_LIBS="$CRYPTO_LIBS" case $host in *mingw*) SECP_TEST_LIBS="$SECP_TEST_LIBS -lgdi32" ;; esac fi else if test x"$enable_openssl_tests" = x"yes"; then AC_MSG_ERROR([OpenSSL tests requested but OpenSSL with EC support is not available]) fi fi else if test x"$enable_openssl_tests" = x"yes"; then AC_MSG_ERROR([OpenSSL tests requested but tests are not enabled]) fi fi if test x"$use_jni" != x"no"; then AX_JNI_INCLUDE_DIR have_jni_dependencies=yes if test x"$enable_module_ecdh" = x"no"; then have_jni_dependencies=no fi if test "x$JNI_INCLUDE_DIRS" = "x"; then have_jni_dependencies=no fi if test "x$have_jni_dependencies" = "xno"; then if test x"$use_jni" = x"yes"; then AC_MSG_ERROR([jni support explicitly requested but headers/dependencies were not found. Enable ECDH and try again.]) fi AC_MSG_WARN([jni headers/dependencies not found. jni support disabled]) use_jni=no else use_jni=yes for JNI_INCLUDE_DIR in $JNI_INCLUDE_DIRS; do JNI_INCLUDES="$JNI_INCLUDES -I$JNI_INCLUDE_DIR" done fi fi if test x"$set_bignum" = x"gmp"; then SECP_LIBS="$SECP_LIBS $GMP_LIBS" SECP_INCLUDES="$SECP_INCLUDES $GMP_CPPFLAGS" fi if test x"$use_endomorphism" = x"yes"; then AC_DEFINE(USE_ENDOMORPHISM, 1, [Define this symbol to use endomorphism optimization]) fi if test x"$set_precomp" = x"yes"; then AC_DEFINE(USE_ECMULT_STATIC_PRECOMPUTATION, 1, [Define this symbol to use a statically generated ecmult table]) fi if test x"$enable_module_ecdh" = x"yes"; then AC_DEFINE(ENABLE_MODULE_ECDH, 1, [Define this symbol to enable the ECDH module]) fi if test x"$enable_module_multiset" = x"yes"; then AC_DEFINE(ENABLE_MODULE_MULTISET, 1, [Define this symbol to enable the multiset module]) fi if test x"$enable_module_recovery" = x"yes"; then AC_DEFINE(ENABLE_MODULE_RECOVERY, 1, [Define this symbol to enable the ECDSA pubkey recovery module]) fi if test x"$enable_module_schnorr" = x"yes"; then AC_DEFINE(ENABLE_MODULE_SCHNORR, 1, [Define this symbol to enable the Schnorr signature module]) fi if test x"$use_external_asm" = x"yes"; then AC_DEFINE(USE_EXTERNAL_ASM, 1, [Define this symbol if an external (non-inline) assembly implementation is used]) fi if test x"$use_external_default_callbacks" = x"yes"; then AC_DEFINE(USE_EXTERNAL_DEFAULT_CALLBACKS, 1, [Define this symbol if an external implementation of the default callbacks is used]) fi if test x"$enable_experimental" = x"yes"; then AC_MSG_NOTICE([******]) AC_MSG_NOTICE([WARNING: experimental build]) AC_MSG_NOTICE([Experimental features do not have stable APIs or properties, and may not be safe for production use.]) AC_MSG_NOTICE([Building ECDH module: $enable_module_ecdh]) AC_MSG_NOTICE([******]) else if test x"$enable_module_ecdh" = x"yes"; then AC_MSG_ERROR([ECDH module is experimental. Use --enable-experimental to allow.]) fi if test x"$enable_module_multiset" = x"yes"; then AC_MSG_ERROR([Multiset module is experimental. Use --enable-experimental to allow.]) fi if test x"$set_asm" = x"arm"; then AC_MSG_ERROR([ARM assembly optimization is experimental. Use --enable-experimental to allow.]) fi fi AC_CONFIG_HEADERS([src/libsecp256k1-config.h]) AC_CONFIG_FILES([Makefile libsecp256k1.pc]) AC_SUBST(JNI_INCLUDES) AC_SUBST(SECP_INCLUDES) AC_SUBST(SECP_LIBS) AC_SUBST(SECP_TEST_LIBS) AC_SUBST(SECP_TEST_INCLUDES) AM_CONDITIONAL([ENABLE_COVERAGE], [test x"$enable_coverage" = x"yes"]) AM_CONDITIONAL([USE_TESTS], [test x"$use_tests" != x"no"]) AM_CONDITIONAL([USE_EXHAUSTIVE_TESTS], [test x"$use_exhaustive_tests" != x"no"]) AM_CONDITIONAL([USE_BENCHMARK], [test x"$use_benchmark" = x"yes"]) AM_CONDITIONAL([USE_ECMULT_STATIC_PRECOMPUTATION], [test x"$set_precomp" = x"yes"]) AM_CONDITIONAL([ENABLE_MODULE_ECDH], [test x"$enable_module_ecdh" = x"yes"]) AM_CONDITIONAL([ENABLE_MODULE_MULTISET], [test x"$enable_module_multiset" = x"yes"]) AM_CONDITIONAL([ENABLE_MODULE_RECOVERY], [test x"$enable_module_recovery" = x"yes"]) AM_CONDITIONAL([ENABLE_MODULE_SCHNORR], [test x"$enable_module_schnorr" = x"yes"]) AM_CONDITIONAL([USE_JNI], [test x"$use_jni" = x"yes"]) AM_CONDITIONAL([USE_EXTERNAL_ASM], [test x"$use_external_asm" = x"yes"]) AM_CONDITIONAL([USE_ASM_ARM], [test x"$set_asm" = x"arm"]) dnl make sure nothing new is exported so that we don't break the cache PKGCONFIG_PATH_TEMP="$PKG_CONFIG_PATH" unset PKG_CONFIG_PATH PKG_CONFIG_PATH="$PKGCONFIG_PATH_TEMP" AC_OUTPUT echo echo "Build Options:" echo " with endomorphism = $use_endomorphism" echo " with ecmult precomp = $set_precomp" echo " with external callbacks = $use_external_default_callbacks" echo " with jni = $use_jni" echo " with benchmarks = $use_benchmark" echo " with coverage = $enable_coverage" echo " module ecdh = $enable_module_ecdh" echo " module recovery = $enable_module_recovery" echo " module multiset = $enable_module_multiset" echo " module schnorr = $enable_module_schnorr" echo echo " asm = $set_asm" echo " bignum = $set_bignum" -echo " field = $set_field" -echo " scalar = $set_scalar" echo " ecmult window size = $set_ecmult_window" echo " ecmult gen prec. bits = $set_ecmult_gen_precision" +dnl Hide test-only options unless they're used. +if test x"$set_widemul" != xauto; then +echo " wide multiplication = $set_widemul" +fi echo echo " valgrind = $enable_valgrind" echo " CC = $CC" echo " CFLAGS = $CFLAGS" echo " CPPFLAGS = $CPPFLAGS" echo " LDFLAGS = $LDFLAGS" echo diff --git a/src/secp256k1/src/basic-config.h b/src/secp256k1/src/basic-config.h index b5ccd8398..83dbe6f25 100644 --- a/src/secp256k1/src/basic-config.h +++ b/src/secp256k1/src/basic-config.h @@ -1,39 +1,35 @@ /********************************************************************** * 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_BASIC_CONFIG_H #define SECP256K1_BASIC_CONFIG_H #ifdef USE_BASIC_CONFIG #undef USE_ASM_X86_64 #undef USE_ECMULT_STATIC_PRECOMPUTATION #undef USE_ENDOMORPHISM #undef USE_EXTERNAL_ASM #undef USE_EXTERNAL_DEFAULT_CALLBACKS -#undef USE_FIELD_10X26 -#undef USE_FIELD_5X52 #undef USE_FIELD_INV_BUILTIN #undef USE_FIELD_INV_NUM #undef USE_NUM_GMP #undef USE_NUM_NONE -#undef USE_SCALAR_4X64 -#undef USE_SCALAR_8X32 #undef USE_SCALAR_INV_BUILTIN #undef USE_SCALAR_INV_NUM +#undef USE_FORCE_WIDEMUL_INT64 +#undef USE_FORCE_WIDEMUL_INT128 #undef ECMULT_WINDOW_SIZE -#undef HAVE___INT128 /* used in util.h */ #define USE_NUM_NONE 1 #define USE_FIELD_INV_BUILTIN 1 #define USE_SCALAR_INV_BUILTIN 1 -#define USE_FIELD_10X26 1 -#define USE_SCALAR_8X32 1 +#define USE_WIDEMUL_64 1 #define ECMULT_WINDOW_SIZE 15 #endif /* USE_BASIC_CONFIG */ #endif /* SECP256K1_BASIC_CONFIG_H */ diff --git a/src/secp256k1/src/field.h b/src/secp256k1/src/field.h index 7993a1f11..aca1fb72c 100644 --- a/src/secp256k1/src/field.h +++ b/src/secp256k1/src/field.h @@ -1,134 +1,134 @@ /********************************************************************** * 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_H #define SECP256K1_FIELD_H /** Field element module. * * Field elements can be represented in several ways, but code accessing * it (and implementations) need to take certain properties into account: * - Each field element can be normalized or not. * - Each field element has a magnitude, which represents how far away * its representation is away from normalization. Normalized elements * always have a magnitude of 1, but a magnitude of 1 doesn't imply * normality. */ #if defined HAVE_CONFIG_H #include "libsecp256k1-config.h" #endif -#if defined(USE_FIELD_10X26) -#include "field_10x26.h" -#elif defined(USE_FIELD_5X52) +#include "util.h" + +#if defined(SECP256K1_WIDEMUL_INT128) #include "field_5x52.h" +#elif defined(SECP256K1_WIDEMUL_INT64) +#include "field_10x26.h" #else -#error "Please select field implementation" +#error "Please select wide multiplication implementation" #endif -#include "util.h" - /** Normalize a field element. This brings the field element to a canonical representation, reduces * its magnitude to 1, and reduces it modulo field size `p`. */ static void secp256k1_fe_normalize(secp256k1_fe *r); /** Weakly normalize a field element: reduce its magnitude to 1, but don't fully normalize. */ static void secp256k1_fe_normalize_weak(secp256k1_fe *r); /** Normalize a field element, without constant-time guarantee. */ static void secp256k1_fe_normalize_var(secp256k1_fe *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 *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 *r); /** Set a field element equal to a small integer. Resulting field element is normalized. */ static void secp256k1_fe_set_int(secp256k1_fe *r, int a); /** Sets a field element equal to zero, initializing all fields. */ static void secp256k1_fe_clear(secp256k1_fe *a); /** Verify whether a field element is zero. Requires the input to be normalized. */ static int secp256k1_fe_is_zero(const secp256k1_fe *a); /** Check the "oddness" of a field element. Requires the input to be normalized. */ static int secp256k1_fe_is_odd(const secp256k1_fe *a); /** Compare two field elements. Requires magnitude-1 inputs. */ static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b); /** Same as secp256k1_fe_equal, but may be variable time. */ static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b); /** Compare two field elements. Requires both inputs to be normalized */ static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b); /** Set a field element equal to 32-byte big endian value. If successful, the resulting field element is normalized. */ static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a); /** 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 *a); /** Set a field element equal to the additive inverse of another. Takes a maximum magnitude of the input * as an argument. The magnitude of the output is one higher. */ static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m); /** Multiplies the passed field element with a small integer constant. Multiplies the magnitude by that * small integer. */ static void secp256k1_fe_mul_int(secp256k1_fe *r, int a); /** Adds a field element to another. The result has the sum of the inputs' magnitudes as magnitude. */ static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a); /** Sets a field element to be the product of two others. Requires the inputs' magnitudes to be at most 8. * The output magnitude is 1 (but not guaranteed to be normalized). */ static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b); /** Sets a field element to be the square of another. Requires the input's magnitude to be at most 8. * The output magnitude is 1 (but not guaranteed to be normalized). */ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a); /** If a has a square root, it is computed in r and 1 is returned. If a does not * have a square root, the root of its negation is computed and 0 is returned. * The input's magnitude can be at most 8. The output magnitude is 1 (but not * guaranteed to be normalized). The result in r will always be a square * itself. */ static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a); /** Checks whether a field element is a quadratic residue. */ static int secp256k1_fe_is_quad_var(const secp256k1_fe *a); /** Sets a field element to be the (modular) inverse of another. Requires the input's magnitude to be * at most 8. The output magnitude is 1 (but not guaranteed to be normalized). */ static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a); /** Potentially faster version of secp256k1_fe_inv, without constant-time guarantee. */ static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a); /** Calculate the (modular) inverses of a batch of field elements. Requires the inputs' magnitudes to be * at most 8. The output magnitudes are 1 (but not guaranteed to be normalized). The inputs and * outputs must not overlap in memory. */ static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len); /** Convert a field element to the storage type. */ static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a); /** Convert a field element back from the storage type. */ static void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a); /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ static void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag); /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag); #endif /* SECP256K1_FIELD_H */ diff --git a/src/secp256k1/src/field_5x52.h b/src/secp256k1/src/field_5x52.h index fc5bfe357..6a068484c 100644 --- a/src/secp256k1/src/field_5x52.h +++ b/src/secp256k1/src/field_5x52.h @@ -1,49 +1,55 @@ /********************************************************************** * 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_H #define SECP256K1_FIELD_REPR_H #include typedef struct { /* X = sum(i=0..4, n[i]*2^(i*52)) mod p * where p = 2^256 - 0x1000003D1 */ uint64_t n[5]; #ifdef VERIFY int magnitude; int normalized; #endif } secp256k1_fe; /* Unpacks a constant into a overlapping multi-limbed FE element. */ #define SECP256K1_FE_CONST_INNER(d7, d6, d5, d4, d3, d2, d1, d0) { \ (d0) | (((uint64_t)(d1) & 0xFFFFFUL) << 32), \ ((uint64_t)(d1) >> 20) | (((uint64_t)(d2)) << 12) | (((uint64_t)(d3) & 0xFFUL) << 44), \ ((uint64_t)(d3) >> 8) | (((uint64_t)(d4) & 0xFFFFFFFUL) << 24), \ ((uint64_t)(d4) >> 28) | (((uint64_t)(d5)) << 4) | (((uint64_t)(d6) & 0xFFFFUL) << 36), \ ((uint64_t)(d6) >> 16) | (((uint64_t)(d7)) << 16) \ } #ifdef VERIFY #define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)), 1, 1} #else #define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0))} #endif typedef struct { uint64_t n[4]; } secp256k1_fe_storage; #define SECP256K1_FE_STORAGE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {{ \ (d0) | (((uint64_t)(d1)) << 32), \ (d2) | (((uint64_t)(d3)) << 32), \ (d4) | (((uint64_t)(d5)) << 32), \ (d6) | (((uint64_t)(d7)) << 32) \ }} +#define SECP256K1_FE_STORAGE_CONST_GET(d) \ + (uint32_t)(d.n[3] >> 32), (uint32_t)d.n[3], \ + (uint32_t)(d.n[2] >> 32), (uint32_t)d.n[2], \ + (uint32_t)(d.n[1] >> 32), (uint32_t)d.n[1], \ + (uint32_t)(d.n[0] >> 32), (uint32_t)d.n[0] + #endif /* SECP256K1_FIELD_REPR_H */ diff --git a/src/secp256k1/src/field_impl.h b/src/secp256k1/src/field_impl.h index 485921a60..18e4d2f30 100644 --- a/src/secp256k1/src/field_impl.h +++ b/src/secp256k1/src/field_impl.h @@ -1,320 +1,320 @@ /********************************************************************** * 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_IMPL_H #define SECP256K1_FIELD_IMPL_H #if defined HAVE_CONFIG_H #include "libsecp256k1-config.h" #endif #include "util.h" #include "num.h" -#if defined(USE_FIELD_10X26) -#include "field_10x26_impl.h" -#elif defined(USE_FIELD_5X52) +#if defined(SECP256K1_WIDEMUL_INT128) #include "field_5x52_impl.h" +#elif defined(SECP256K1_WIDEMUL_INT64) +#include "field_10x26_impl.h" #else -#error "Please select field implementation" +#error "Please select wide multiplication implementation" #endif SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) { secp256k1_fe na; secp256k1_fe_negate(&na, a, 1); secp256k1_fe_add(&na, b); return secp256k1_fe_normalizes_to_zero(&na); } SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b) { secp256k1_fe 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(secp256k1_fe *r, const secp256k1_fe *a) { /** Given that p is congruent to 3 mod 4, we can compute the square root of * a mod p as the (p+1)/4'th power of a. * * As (p+1)/4 is an even number, it will have the same result for a and for * (-a). Only one of these two numbers actually has a square root however, * so we test at the end by squaring and comparing to the input. * Also because (p+1)/4 is an even number, the computed square root is * itself always a square (a ** ((p+1)/4) is the square of a ** ((p+1)/8)). */ secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1; int j; VERIFY_CHECK(r != a); /** The binary representation of (p + 1)/4 has 3 blocks of 1s, with lengths in * { 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block: * 1, [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223] */ secp256k1_fe_sqr(&x2, a); secp256k1_fe_mul(&x2, &x2, a); secp256k1_fe_sqr(&x3, &x2); secp256k1_fe_mul(&x3, &x3, a); x6 = x3; for (j=0; j<3; j++) { secp256k1_fe_sqr(&x6, &x6); } secp256k1_fe_mul(&x6, &x6, &x3); x9 = x6; for (j=0; j<3; j++) { secp256k1_fe_sqr(&x9, &x9); } secp256k1_fe_mul(&x9, &x9, &x3); x11 = x9; for (j=0; j<2; j++) { secp256k1_fe_sqr(&x11, &x11); } secp256k1_fe_mul(&x11, &x11, &x2); x22 = x11; for (j=0; j<11; j++) { secp256k1_fe_sqr(&x22, &x22); } secp256k1_fe_mul(&x22, &x22, &x11); x44 = x22; for (j=0; j<22; j++) { secp256k1_fe_sqr(&x44, &x44); } secp256k1_fe_mul(&x44, &x44, &x22); x88 = x44; for (j=0; j<44; j++) { secp256k1_fe_sqr(&x88, &x88); } secp256k1_fe_mul(&x88, &x88, &x44); x176 = x88; for (j=0; j<88; j++) { secp256k1_fe_sqr(&x176, &x176); } secp256k1_fe_mul(&x176, &x176, &x88); x220 = x176; for (j=0; j<44; j++) { secp256k1_fe_sqr(&x220, &x220); } secp256k1_fe_mul(&x220, &x220, &x44); x223 = x220; for (j=0; j<3; j++) { secp256k1_fe_sqr(&x223, &x223); } secp256k1_fe_mul(&x223, &x223, &x3); /* The final result is then assembled using a sliding window over the blocks. */ t1 = x223; for (j=0; j<23; j++) { secp256k1_fe_sqr(&t1, &t1); } secp256k1_fe_mul(&t1, &t1, &x22); for (j=0; j<6; j++) { secp256k1_fe_sqr(&t1, &t1); } secp256k1_fe_mul(&t1, &t1, &x2); secp256k1_fe_sqr(&t1, &t1); secp256k1_fe_sqr(r, &t1); /* Check that a square root was actually calculated */ secp256k1_fe_sqr(&t1, r); return secp256k1_fe_equal(&t1, a); } static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a) { secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1; int j; /** The binary representation of (p - 2) has 5 blocks of 1s, with lengths in * { 1, 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block: * [1], [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223] */ secp256k1_fe_sqr(&x2, a); secp256k1_fe_mul(&x2, &x2, a); secp256k1_fe_sqr(&x3, &x2); secp256k1_fe_mul(&x3, &x3, a); x6 = x3; for (j=0; j<3; j++) { secp256k1_fe_sqr(&x6, &x6); } secp256k1_fe_mul(&x6, &x6, &x3); x9 = x6; for (j=0; j<3; j++) { secp256k1_fe_sqr(&x9, &x9); } secp256k1_fe_mul(&x9, &x9, &x3); x11 = x9; for (j=0; j<2; j++) { secp256k1_fe_sqr(&x11, &x11); } secp256k1_fe_mul(&x11, &x11, &x2); x22 = x11; for (j=0; j<11; j++) { secp256k1_fe_sqr(&x22, &x22); } secp256k1_fe_mul(&x22, &x22, &x11); x44 = x22; for (j=0; j<22; j++) { secp256k1_fe_sqr(&x44, &x44); } secp256k1_fe_mul(&x44, &x44, &x22); x88 = x44; for (j=0; j<44; j++) { secp256k1_fe_sqr(&x88, &x88); } secp256k1_fe_mul(&x88, &x88, &x44); x176 = x88; for (j=0; j<88; j++) { secp256k1_fe_sqr(&x176, &x176); } secp256k1_fe_mul(&x176, &x176, &x88); x220 = x176; for (j=0; j<44; j++) { secp256k1_fe_sqr(&x220, &x220); } secp256k1_fe_mul(&x220, &x220, &x44); x223 = x220; for (j=0; j<3; j++) { secp256k1_fe_sqr(&x223, &x223); } secp256k1_fe_mul(&x223, &x223, &x3); /* The final result is then assembled using a sliding window over the blocks. */ t1 = x223; for (j=0; j<23; j++) { secp256k1_fe_sqr(&t1, &t1); } secp256k1_fe_mul(&t1, &t1, &x22); for (j=0; j<5; j++) { secp256k1_fe_sqr(&t1, &t1); } secp256k1_fe_mul(&t1, &t1, a); for (j=0; j<3; j++) { secp256k1_fe_sqr(&t1, &t1); } secp256k1_fe_mul(&t1, &t1, &x2); for (j=0; j<2; j++) { secp256k1_fe_sqr(&t1, &t1); } secp256k1_fe_mul(r, a, &t1); } static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a) { #if defined(USE_FIELD_INV_BUILTIN) secp256k1_fe_inv(r, a); #elif defined(USE_FIELD_INV_NUM) secp256k1_num n, m; static const secp256k1_fe negone = SECP256K1_FE_CONST( 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 0xFFFFFC2EUL ); /* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */ static const unsigned char prime[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,0xFE,0xFF,0xFF,0xFC,0x2F }; unsigned char b[32]; int res; secp256k1_fe c = *a; secp256k1_fe_normalize_var(&c); secp256k1_fe_get_b32(b, &c); secp256k1_num_set_bin(&n, b, 32); secp256k1_num_set_bin(&m, prime, 32); secp256k1_num_mod_inverse(&n, &n, &m); secp256k1_num_get_bin(b, 32, &n); res = secp256k1_fe_set_b32(r, b); (void)res; VERIFY_CHECK(res); /* Verify the result is the (unique) valid inverse using non-GMP code. */ secp256k1_fe_mul(&c, &c, r); secp256k1_fe_add(&c, &negone); CHECK(secp256k1_fe_normalizes_to_zero_var(&c)); #else #error "Please select field inverse implementation" #endif } static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len) { secp256k1_fe u; size_t i; if (len < 1) { return; } VERIFY_CHECK((r + len <= a) || (a + len <= r)); r[0] = a[0]; i = 0; while (++i < len) { secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]); } secp256k1_fe_inv_var(&u, &r[--i]); while (i > 0) { size_t j = i--; secp256k1_fe_mul(&r[j], &r[i], &u); secp256k1_fe_mul(&u, &u, &a[j]); } r[0] = u; } static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) { #ifndef USE_NUM_NONE unsigned char b[32]; secp256k1_num n; secp256k1_num m; /* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */ static const unsigned char prime[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,0xFE,0xFF,0xFF,0xFC,0x2F }; secp256k1_fe c = *a; secp256k1_fe_normalize_var(&c); secp256k1_fe_get_b32(b, &c); secp256k1_num_set_bin(&n, b, 32); secp256k1_num_set_bin(&m, prime, 32); return secp256k1_num_jacobi(&n, &m) >= 0; #else secp256k1_fe r; return secp256k1_fe_sqrt(&r, a); #endif } static const secp256k1_fe secp256k1_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1); #endif /* SECP256K1_FIELD_IMPL_H */ diff --git a/src/secp256k1/src/scalar.h b/src/secp256k1/src/scalar.h index 2a7470352..95d3e326c 100644 --- a/src/secp256k1/src/scalar.h +++ b/src/secp256k1/src/scalar.h @@ -1,117 +1,118 @@ /********************************************************************** * 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_SCALAR_H #define SECP256K1_SCALAR_H #include "num.h" +#include "util.h" #if defined HAVE_CONFIG_H #include "libsecp256k1-config.h" #endif #if defined(EXHAUSTIVE_TEST_ORDER) #include "scalar_low.h" -#elif defined(USE_SCALAR_4X64) +#elif defined(SECP256K1_WIDEMUL_INT128) #include "scalar_4x64.h" -#elif defined(USE_SCALAR_8X32) +#elif defined(SECP256K1_WIDEMUL_INT64) #include "scalar_8x32.h" #else -#error "Please select scalar implementation" +#error "Please select wide multiplication implementation" #endif /** Clear a scalar to prevent the leak of sensitive data. */ static void secp256k1_scalar_clear(secp256k1_scalar *r); /** Access bits from a scalar. All requested bits must belong to the same 32-bit limb. */ static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count); /** Access bits from a scalar. Not constant time. */ static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count); /** Set a scalar from a big endian byte array. The scalar will be reduced modulo group order `n`. * In: bin: pointer to a 32-byte array. * Out: r: scalar to be set. * overflow: non-zero if the scalar was bigger or equal to `n` before reduction, zero otherwise (can be NULL). */ static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow); /** Set a scalar from a big endian byte array and returns 1 if it is a valid * seckey and 0 otherwise. */ static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin); /** Set a scalar to an unsigned integer. */ static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v); /** Convert a scalar to a byte array. */ static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a); /** Add two scalars together (modulo the group order). Returns whether it overflowed. */ static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b); /** Conditionally add a power of two to a scalar. The result is not allowed to overflow. */ static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag); /** Multiply two scalars (modulo the group order). */ static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b); /** Shift a scalar right by some amount strictly between 0 and 16, returning * the low bits that were shifted off */ static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n); /** Compute the square of a scalar (modulo the group order). */ static void secp256k1_scalar_sqr(secp256k1_scalar *r, const secp256k1_scalar *a); /** Compute the inverse of a scalar (modulo the group order). */ static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *a); /** Compute the inverse of a scalar (modulo the group order), without constant-time guarantee. */ static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *a); /** Compute the complement of a scalar (modulo the group order). */ static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a); /** Check whether a scalar equals zero. */ static int secp256k1_scalar_is_zero(const secp256k1_scalar *a); /** Check whether a scalar equals one. */ static int secp256k1_scalar_is_one(const secp256k1_scalar *a); /** Check whether a scalar, considered as an nonnegative integer, is even. */ static int secp256k1_scalar_is_even(const secp256k1_scalar *a); /** Check whether a scalar is higher than the group order divided by 2. */ static int secp256k1_scalar_is_high(const secp256k1_scalar *a); /** Conditionally negate a number, in constant time. * Returns -1 if the number was negated, 1 otherwise */ static int secp256k1_scalar_cond_negate(secp256k1_scalar *a, int flag); #ifndef USE_NUM_NONE /** Convert a scalar to a number. */ static void secp256k1_scalar_get_num(secp256k1_num *r, const secp256k1_scalar *a); /** Get the order of the group as a number. */ static void secp256k1_scalar_order_get_num(secp256k1_num *r); #endif /** Compare two scalars. */ static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b); #ifdef USE_ENDOMORPHISM /** Find r1 and r2 such that r1+r2*2^128 = a. */ static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a); /** Find r1 and r2 such that r1+r2*lambda = a, and r1 and r2 are maximum 128 bits long (see secp256k1_gej_mul_lambda). */ static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a); #endif /** Multiply a and b (without taking the modulus!), divide by 2**shift, and round to the nearest integer. Shift must be at least 256. */ static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b, unsigned int shift); /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ static void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag); #endif /* SECP256K1_SCALAR_H */ diff --git a/src/secp256k1/src/scalar_impl.h b/src/secp256k1/src/scalar_impl.h index 70cd73db0..2ec04b1ae 100644 --- a/src/secp256k1/src/scalar_impl.h +++ b/src/secp256k1/src/scalar_impl.h @@ -1,342 +1,342 @@ /********************************************************************** * 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_SCALAR_IMPL_H #define SECP256K1_SCALAR_IMPL_H #include "scalar.h" #include "util.h" #if defined HAVE_CONFIG_H #include "libsecp256k1-config.h" #endif #if defined(EXHAUSTIVE_TEST_ORDER) #include "scalar_low_impl.h" -#elif defined(USE_SCALAR_4X64) +#elif defined(SECP256K1_WIDEMUL_INT128) #include "scalar_4x64_impl.h" -#elif defined(USE_SCALAR_8X32) +#elif defined(SECP256K1_WIDEMUL_INT64) #include "scalar_8x32_impl.h" #else -#error "Please select scalar implementation" +#error "Please select wide multiplication implementation" #endif static const secp256k1_scalar secp256k1_scalar_one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); static const secp256k1_scalar secp256k1_scalar_zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); #ifndef USE_NUM_NONE static void secp256k1_scalar_get_num(secp256k1_num *r, const secp256k1_scalar *a) { unsigned char c[32]; secp256k1_scalar_get_b32(c, a); secp256k1_num_set_bin(r, c, 32); } /** secp256k1 curve order, see secp256k1_ecdsa_const_order_as_fe in ecdsa_impl.h */ static void secp256k1_scalar_order_get_num(secp256k1_num *r) { #if defined(EXHAUSTIVE_TEST_ORDER) static const unsigned char order[32] = { 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,EXHAUSTIVE_TEST_ORDER }; #else static const unsigned char order[32] = { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE, 0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B, 0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41 }; #endif secp256k1_num_set_bin(r, order, 32); } #endif static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin) { int overflow; secp256k1_scalar_set_b32(r, bin, &overflow); return (!overflow) & (!secp256k1_scalar_is_zero(r)); } static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) { #if defined(EXHAUSTIVE_TEST_ORDER) int i; *r = 0; for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) if ((i * *x) % EXHAUSTIVE_TEST_ORDER == 1) *r = i; /* If this VERIFY_CHECK triggers we were given a noninvertible scalar (and thus * have a composite group order; fix it in exhaustive_tests.c). */ VERIFY_CHECK(*r != 0); } #else secp256k1_scalar *t; int i; /* First compute xN as x ^ (2^N - 1) for some values of N, * and uM as x ^ M for some values of M. */ secp256k1_scalar x2, x3, x6, x8, x14, x28, x56, x112, x126; secp256k1_scalar u2, u5, u9, u11, u13; secp256k1_scalar_sqr(&u2, x); secp256k1_scalar_mul(&x2, &u2, x); secp256k1_scalar_mul(&u5, &u2, &x2); secp256k1_scalar_mul(&x3, &u5, &u2); secp256k1_scalar_mul(&u9, &x3, &u2); secp256k1_scalar_mul(&u11, &u9, &u2); secp256k1_scalar_mul(&u13, &u11, &u2); secp256k1_scalar_sqr(&x6, &u13); secp256k1_scalar_sqr(&x6, &x6); secp256k1_scalar_mul(&x6, &x6, &u11); secp256k1_scalar_sqr(&x8, &x6); secp256k1_scalar_sqr(&x8, &x8); secp256k1_scalar_mul(&x8, &x8, &x2); secp256k1_scalar_sqr(&x14, &x8); for (i = 0; i < 5; i++) { secp256k1_scalar_sqr(&x14, &x14); } secp256k1_scalar_mul(&x14, &x14, &x6); secp256k1_scalar_sqr(&x28, &x14); for (i = 0; i < 13; i++) { secp256k1_scalar_sqr(&x28, &x28); } secp256k1_scalar_mul(&x28, &x28, &x14); secp256k1_scalar_sqr(&x56, &x28); for (i = 0; i < 27; i++) { secp256k1_scalar_sqr(&x56, &x56); } secp256k1_scalar_mul(&x56, &x56, &x28); secp256k1_scalar_sqr(&x112, &x56); for (i = 0; i < 55; i++) { secp256k1_scalar_sqr(&x112, &x112); } secp256k1_scalar_mul(&x112, &x112, &x56); secp256k1_scalar_sqr(&x126, &x112); for (i = 0; i < 13; i++) { secp256k1_scalar_sqr(&x126, &x126); } secp256k1_scalar_mul(&x126, &x126, &x14); /* Then accumulate the final result (t starts at x126). */ t = &x126; for (i = 0; i < 3; i++) { secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u5); /* 101 */ for (i = 0; i < 4; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x3); /* 111 */ for (i = 0; i < 4; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u5); /* 101 */ for (i = 0; i < 5; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u11); /* 1011 */ for (i = 0; i < 4; i++) { secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u11); /* 1011 */ for (i = 0; i < 4; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x3); /* 111 */ for (i = 0; i < 5; i++) { /* 00 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x3); /* 111 */ for (i = 0; i < 6; i++) { /* 00 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u13); /* 1101 */ for (i = 0; i < 4; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u5); /* 101 */ for (i = 0; i < 3; i++) { secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x3); /* 111 */ for (i = 0; i < 5; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u9); /* 1001 */ for (i = 0; i < 6; i++) { /* 000 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u5); /* 101 */ for (i = 0; i < 10; i++) { /* 0000000 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x3); /* 111 */ for (i = 0; i < 4; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x3); /* 111 */ for (i = 0; i < 9; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x8); /* 11111111 */ for (i = 0; i < 5; i++) { /* 0 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u9); /* 1001 */ for (i = 0; i < 6; i++) { /* 00 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u11); /* 1011 */ for (i = 0; i < 4; i++) { secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u13); /* 1101 */ for (i = 0; i < 5; i++) { secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &x2); /* 11 */ for (i = 0; i < 6; i++) { /* 00 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u13); /* 1101 */ for (i = 0; i < 10; i++) { /* 000000 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u13); /* 1101 */ for (i = 0; i < 4; i++) { secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, &u9); /* 1001 */ for (i = 0; i < 6; i++) { /* 00000 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(t, t, x); /* 1 */ for (i = 0; i < 8; i++) { /* 00 */ secp256k1_scalar_sqr(t, t); } secp256k1_scalar_mul(r, t, &x6); /* 111111 */ } SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) { return !(a->d[0] & 1); } #endif static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) { #if defined(USE_SCALAR_INV_BUILTIN) secp256k1_scalar_inverse(r, x); #elif defined(USE_SCALAR_INV_NUM) unsigned char b[32]; secp256k1_num n, m; secp256k1_scalar t = *x; secp256k1_scalar_get_b32(b, &t); secp256k1_num_set_bin(&n, b, 32); secp256k1_scalar_order_get_num(&m); secp256k1_num_mod_inverse(&n, &n, &m); secp256k1_num_get_bin(b, 32, &n); secp256k1_scalar_set_b32(r, b, NULL); /* Verify that the inverse was computed correctly, without GMP code. */ secp256k1_scalar_mul(&t, &t, r); CHECK(secp256k1_scalar_is_one(&t)); #else #error "Please select scalar inverse implementation" #endif } #ifdef USE_ENDOMORPHISM #if defined(EXHAUSTIVE_TEST_ORDER) /** * Find k1 and k2 given k, such that k1 + k2 * lambda == k mod n; unlike in the * full case we don't bother making k1 and k2 be small, we just want them to be * nontrivial to get full test coverage for the exhaustive tests. We therefore * (arbitrarily) set k2 = k + 5 and k1 = k - k2 * lambda. */ static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) { *r2 = (*a + 5) % EXHAUSTIVE_TEST_ORDER; *r1 = (*a + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER; } #else /** * The Secp256k1 curve has an endomorphism, where lambda * (x, y) = (beta * x, y), where * lambda is {0x53,0x63,0xad,0x4c,0xc0,0x5c,0x30,0xe0,0xa5,0x26,0x1c,0x02,0x88,0x12,0x64,0x5a, * 0x12,0x2e,0x22,0xea,0x20,0x81,0x66,0x78,0xdf,0x02,0x96,0x7c,0x1b,0x23,0xbd,0x72} * * "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone) gives an algorithm * (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1 * and k2 have a small size. * It relies on constants a1, b1, a2, b2. These constants for the value of lambda above are: * * - a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15} * - b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3} * - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8} * - b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15} * * The algorithm then computes c1 = round(b1 * k / n) and c2 = round(b2 * k / n), and gives * k1 = k - (c1*a1 + c2*a2) and k2 = -(c1*b1 + c2*b2). Instead, we use modular arithmetic, and * compute k1 as k - k2 * lambda, avoiding the need for constants a1 and a2. * * g1, g2 are precomputed constants used to replace division with a rounded multiplication * when decomposing the scalar for an endomorphism-based point multiplication. * * The possibility of using precomputed estimates is mentioned in "Guide to Elliptic Curve * Cryptography" (Hankerson, Menezes, Vanstone) in section 3.5. * * The derivation is described in the paper "Efficient Software Implementation of Public-Key * Cryptography on Sensor Networks Using the MSP430X Microcontroller" (Gouvea, Oliveira, Lopez), * Section 4.3 (here we use a somewhat higher-precision estimate): * d = a1*b2 - b1*a2 * g1 = round((2^272)*b2/d) * g2 = round((2^272)*b1/d) * * (Note that 'd' is also equal to the curve order here because [a1,b1] and [a2,b2] are found * as outputs of the Extended Euclidean Algorithm on inputs 'order' and 'lambda'). * * The function below splits a in r1 and r2, such that r1 + lambda * r2 == a (mod order). */ static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) { secp256k1_scalar c1, c2; static const secp256k1_scalar minus_lambda = SECP256K1_SCALAR_CONST( 0xAC9C52B3UL, 0x3FA3CF1FUL, 0x5AD9E3FDUL, 0x77ED9BA4UL, 0xA880B9FCUL, 0x8EC739C2UL, 0xE0CFC810UL, 0xB51283CFUL ); static const secp256k1_scalar minus_b1 = SECP256K1_SCALAR_CONST( 0x00000000UL, 0x00000000UL, 0x00000000UL, 0x00000000UL, 0xE4437ED6UL, 0x010E8828UL, 0x6F547FA9UL, 0x0ABFE4C3UL ); static const secp256k1_scalar minus_b2 = SECP256K1_SCALAR_CONST( 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 0x8A280AC5UL, 0x0774346DUL, 0xD765CDA8UL, 0x3DB1562CUL ); static const secp256k1_scalar g1 = SECP256K1_SCALAR_CONST( 0x00000000UL, 0x00000000UL, 0x00000000UL, 0x00003086UL, 0xD221A7D4UL, 0x6BCDE86CUL, 0x90E49284UL, 0xEB153DABUL ); static const secp256k1_scalar g2 = SECP256K1_SCALAR_CONST( 0x00000000UL, 0x00000000UL, 0x00000000UL, 0x0000E443UL, 0x7ED6010EUL, 0x88286F54UL, 0x7FA90ABFUL, 0xE4C42212UL ); VERIFY_CHECK(r1 != a); VERIFY_CHECK(r2 != a); /* these _var calls are constant time since the shift amount is constant */ secp256k1_scalar_mul_shift_var(&c1, a, &g1, 272); secp256k1_scalar_mul_shift_var(&c2, a, &g2, 272); secp256k1_scalar_mul(&c1, &c1, &minus_b1); secp256k1_scalar_mul(&c2, &c2, &minus_b2); secp256k1_scalar_add(r2, &c1, &c2); secp256k1_scalar_mul(r1, r2, &minus_lambda); secp256k1_scalar_add(r1, r1, a); } #endif #endif #endif /* SECP256K1_SCALAR_IMPL_H */ diff --git a/src/secp256k1/src/util.h b/src/secp256k1/src/util.h index 510544b99..eb4db4faf 100644 --- a/src/secp256k1/src/util.h +++ b/src/secp256k1/src/util.h @@ -1,230 +1,243 @@ /********************************************************************** * 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_UTIL_H #define SECP256K1_UTIL_H #if defined HAVE_CONFIG_H #include "libsecp256k1-config.h" #endif #include #include #include #include typedef struct { void (*fn)(const char *text, void* data); const void* data; } secp256k1_callback; static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback * const cb, const char * const text) { cb->fn(text, (void*)cb->data); } #ifdef DETERMINISTIC #define TEST_FAILURE(msg) do { \ fprintf(stderr, "%s\n", msg); \ abort(); \ } while(0); #else #define TEST_FAILURE(msg) do { \ fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, msg); \ abort(); \ } while(0) #endif #if SECP256K1_GNUC_PREREQ(3, 0) #define EXPECT(x,c) __builtin_expect((x),(c)) #else #define EXPECT(x,c) (x) #endif #ifdef DETERMINISTIC #define CHECK(cond) do { \ if (EXPECT(!(cond), 0)) { \ TEST_FAILURE("test condition failed"); \ } \ } while(0) #else #define CHECK(cond) do { \ if (EXPECT(!(cond), 0)) { \ TEST_FAILURE("test condition failed: " #cond); \ } \ } while(0) #endif /* Like assert(), but when VERIFY is defined, and side-effect safe. */ #if defined(COVERAGE) #define VERIFY_CHECK(check) #define VERIFY_SETUP(stmt) #elif defined(VERIFY) #define VERIFY_CHECK CHECK #define VERIFY_SETUP(stmt) do { stmt; } while(0) #else #define VERIFY_CHECK(cond) do { (void)(cond); } while(0) #define VERIFY_SETUP(stmt) #endif /* Define `VG_UNDEF` and `VG_CHECK` when VALGRIND is defined */ #if !defined(VG_CHECK) # if defined(VALGRIND) # include # define VG_UNDEF(x,y) VALGRIND_MAKE_MEM_UNDEFINED((x),(y)) # define VG_CHECK(x,y) VALGRIND_CHECK_MEM_IS_DEFINED((x),(y)) # else # define VG_UNDEF(x,y) # define VG_CHECK(x,y) # endif #endif /* Like `VG_CHECK` but on VERIFY only */ #if defined(VERIFY) #define VG_CHECK_VERIFY(x,y) VG_CHECK((x), (y)) #else #define VG_CHECK_VERIFY(x,y) #endif static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_t size) { void *ret = malloc(size); if (ret == NULL) { secp256k1_callback_call(cb, "Out of memory"); } return ret; } static SECP256K1_INLINE void *checked_realloc(const secp256k1_callback* cb, void *ptr, size_t size) { void *ret = realloc(ptr, size); if (ret == NULL) { secp256k1_callback_call(cb, "Out of memory"); } return ret; } #if defined(__BIGGEST_ALIGNMENT__) #define ALIGNMENT __BIGGEST_ALIGNMENT__ #else /* Using 16 bytes alignment because common architectures never have alignment * requirements above 8 for any of the types we care about. In addition we * leave some room because currently we don't care about a few bytes. */ #define ALIGNMENT 16 #endif #define ROUND_TO_ALIGN(size) (((size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT) /* Assume there is a contiguous memory object with bounds [base, base + max_size) * of which the memory range [base, *prealloc_ptr) is already allocated for usage, * where *prealloc_ptr is an aligned pointer. In that setting, this functions * reserves the subobject [*prealloc_ptr, *prealloc_ptr + alloc_size) of * alloc_size bytes by increasing *prealloc_ptr accordingly, taking into account * alignment requirements. * * The function returns an aligned pointer to the newly allocated subobject. * * This is useful for manual memory management: if we're simply given a block * [base, base + max_size), the caller can use this function to allocate memory * in this block and keep track of the current allocation state with *prealloc_ptr. * * It is VERIFY_CHECKed that there is enough space left in the memory object and * *prealloc_ptr is aligned relative to base. */ static SECP256K1_INLINE void *manual_alloc(void** prealloc_ptr, size_t alloc_size, void* base, size_t max_size) { size_t aligned_alloc_size = ROUND_TO_ALIGN(alloc_size); void* ret; VERIFY_CHECK(prealloc_ptr != NULL); VERIFY_CHECK(*prealloc_ptr != NULL); VERIFY_CHECK(base != NULL); VERIFY_CHECK((unsigned char*)*prealloc_ptr >= (unsigned char*)base); VERIFY_CHECK(((unsigned char*)*prealloc_ptr - (unsigned char*)base) % ALIGNMENT == 0); VERIFY_CHECK((unsigned char*)*prealloc_ptr - (unsigned char*)base + aligned_alloc_size <= max_size); ret = *prealloc_ptr; *((unsigned char**)prealloc_ptr) += aligned_alloc_size; return ret; } /* Macro for restrict, when available and not in a VERIFY build. */ #if defined(SECP256K1_BUILD) && defined(VERIFY) # define SECP256K1_RESTRICT #else # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) ) # if SECP256K1_GNUC_PREREQ(3,0) # define SECP256K1_RESTRICT __restrict__ # elif (defined(_MSC_VER) && _MSC_VER >= 1400) # define SECP256K1_RESTRICT __restrict # else # define SECP256K1_RESTRICT # endif # else # define SECP256K1_RESTRICT restrict # endif #endif #if defined(_WIN32) # define I64FORMAT "I64d" # define I64uFORMAT "I64u" #else # define I64FORMAT "lld" # define I64uFORMAT "llu" #endif -#if defined(HAVE___INT128) -# if defined(__GNUC__) -# define SECP256K1_GNUC_EXT __extension__ -# else -# define SECP256K1_GNUC_EXT -# endif -SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t; +#if defined(__GNUC__) +# define SECP256K1_GNUC_EXT __extension__ +#else +# define SECP256K1_GNUC_EXT #endif #if defined(__BYTE_ORDER__) # if defined(__ORDER_LITTLE_ENDIAN__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && !defined(SECP256K1_LITTLE_ENDIAN) # define SECP256K1_LITTLE_ENDIAN # elif defined(__ORDER_BIG_ENDIAN__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && !defined(SECP256K1_BIG_ENDIAN) # define SECP256K1_BIG_ENDIAN # endif #endif #if defined(_MSC_VER) && defined(_WIN32) && !defined(SECP256K1_LITTLE_ENDIAN) # define SECP256K1_LITTLE_ENDIAN #endif #if defined(SECP256K1_LITTLE_ENDIAN) == defined(SECP256K1_BIG_ENDIAN) # error Please make sure that either SECP256K1_LITTLE_ENDIAN or SECP256K1_BIG_ENDIAN is set, see src/util.h. #endif /* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */ static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) { unsigned char *p = (unsigned char *)s; /* Access flag with a volatile-qualified lvalue. This prevents clang from figuring out (after inlining) that flag can take only be 0 or 1, which leads to variable time code. */ volatile int vflag = flag; unsigned char mask = -(unsigned char) vflag; while (len) { *p &= ~mask; p++; len--; } } /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized and non-negative.*/ static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) { unsigned int mask0, mask1, r_masked, a_masked; /* Access flag with a volatile-qualified lvalue. This prevents clang from figuring out (after inlining) that flag can take only be 0 or 1, which leads to variable time code. */ volatile int vflag = flag; /* Casting a negative int to unsigned and back to int is implementation defined behavior */ VERIFY_CHECK(*r >= 0 && *a >= 0); mask0 = (unsigned int)vflag + ~0u; mask1 = ~mask0; r_masked = ((unsigned int)*r & mask0); a_masked = ((unsigned int)*a & mask1); *r = (int)(r_masked | a_masked); } +/* If USE_FORCE_WIDEMUL_{INT128,INT64} is set, use that wide multiplication implementation. + * Otherwise use the presence of __SIZEOF_INT128__ to decide. + */ +#if defined(USE_FORCE_WIDEMUL_INT128) +# define SECP256K1_WIDEMUL_INT128 1 +#elif defined(USE_FORCE_WIDEMUL_INT64) +# define SECP256K1_WIDEMUL_INT64 1 +#elif defined(__SIZEOF_INT128__) +# define SECP256K1_WIDEMUL_INT128 1 +#else +# define SECP256K1_WIDEMUL_INT64 1 +#endif +#if defined(SECP256K1_WIDEMUL_INT128) +SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t; +#endif + #endif /* SECP256K1_UTIL_H */ diff --git a/src/secp256k1/travis/build_autotools.sh b/src/secp256k1/travis/build_autotools.sh index 3f5da8db6..099383abc 100755 --- a/src/secp256k1/travis/build_autotools.sh +++ b/src/secp256k1/travis/build_autotools.sh @@ -1,99 +1,98 @@ #!/usr/bin/env bash export LC_ALL=C set -ex # FIXME The java tests will fail on macOS with autotools due to the # libsepc256k1_jni library referencing the libsecp256k1 library with an absolute # path. This needs to be rewritten with install_name_tool to use relative paths # via the @variables supported by the macOS loader. if [ "$TRAVIS_OS_NAME" = "osx" ] && [ "$JNI" = "yes" ] then echo "Skipping the java tests built with autotools on OSX" exit 0 fi if [ -n "$HOST" ]; then USE_HOST="--host=$HOST" fi if [ "x$HOST" = "xi686-linux-gnu" ]; then CC="$CC -m32" fi if [ "$TRAVIS_OS_NAME" = "osx" ] && [ "$TRAVIS_COMPILER" = "gcc" ] then CC="gcc-9" fi $CC --version ./autogen.sh mkdir buildautotools pushd buildautotools ../configure \ --enable-experimental=$EXPERIMENTAL \ --enable-endomorphism=$ENDOMORPHISM \ - --with-field=$FIELD \ + --with-test-override-wide-multiply=$WIDEMUL \ --with-bignum=$BIGNUM \ --with-asm=$ASM \ - --with-scalar=$SCALAR \ --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION \ --with-ecmult-gen-precision=$ECMULTGENPRECISION \ --enable-module-ecdh=$ECDH \ --enable-module-multiset=$MULTISET \ --enable-module-recovery=$RECOVERY \ --enable-module-schnorr=$SCHNORR \ --enable-jni=$JNI \ --enable-openssl-tests=$OPENSSL_TESTS \ $AUTOTOOLS_EXTRA_FLAGS \ $USE_HOST print_logs() { cat tests.log || : cat exhaustive_tests.log || : cat valgrind_ctime_test.log || : cat bench.log || : } trap 'print_logs' ERR make -j2 $AUTOTOOLS_TARGET if [ -n "$VALGRIND" ]; then # the `--error-exitcode` is required to make the test fail if valgrind found # errors, otherwise it'll return 0 # (http://valgrind.org/docs/manual/manual-core.html) valgrind --error-exitcode=42 ./tests 16 valgrind --error-exitcode=42 ./exhaustive_tests fi if [ -n "$BENCH" ]; then if [ -n "$VALGRIND" ]; then # Using the local `libtool` because on macOS the system's libtool has # nothing to do with GNU libtool EXEC='./libtool --mode=execute valgrind --error-exitcode=42'; else EXEC= ; fi $EXEC ./bench_ecmult >> bench.log 2>&1 $EXEC ./bench_internal >> bench.log 2>&1 $EXEC ./bench_sign >> bench.log 2>&1 $EXEC ./bench_verify >> bench.log 2>&1 if [ "$RECOVERY" == "yes" ]; then $EXEC ./bench_recover >> bench.log 2>&1 fi if [ "$ECDH" == "yes" ]; then $EXEC ./bench_ecdh >> bench.log 2>&1 fi if [ "$MULTISET" == "yes" ]; then $EXEC ./bench_multiset >> bench.log 2>&1 fi fi if [ -n "$CTIMETEST" ]; then ./libtool --mode=execute valgrind --error-exitcode=42 ./valgrind_ctime_test > valgrind_ctime_test.log 2>&1 fi popd diff --git a/src/secp256k1/travis/build_cmake.sh b/src/secp256k1/travis/build_cmake.sh index d923e5579..ab43c9d22 100755 --- a/src/secp256k1/travis/build_cmake.sh +++ b/src/secp256k1/travis/build_cmake.sh @@ -1,61 +1,60 @@ #!/usr/bin/env bash export LC_ALL=C set -ex if [ "x$HOST" = "xi686-linux-gnu" ]; then CMAKE_EXTRA_FLAGS="$CMAKE_EXTRA_FLAGS -DCMAKE_C_FLAGS=-m32" fi if [ "$TRAVIS_OS_NAME" = "osx" ] && [ "$TRAVIS_COMPILER" = "gcc" ] then CMAKE_EXTRA_FLAGS="$CMAKE_EXTRA_FLAGS -DCMAKE_C_COMPILER=gcc-9" fi # "auto" is not a valid value for SECP256K1_ECMULT_GEN_PRECISION with cmake. # In this case we use the default value instead by not setting the cache # variable on the cmake command line. if [ "x$ECMULTGENPRECISION" != "xauto" ]; then ECMULT_GEN_PRECISION_ARG="-DSECP256K1_ECMULT_GEN_PRECISION=$ECMULTGENPRECISION" fi mkdir -p buildcmake/install pushd buildcmake # Use the cmake version installed via the install_cmake.sh script on linux amd64 if [ "$TRAVIS_OS_NAME" = "linux" ] && [ "${TRAVIS_CPU_ARCH}" = "amd64" ] then CMAKE_COMMAND=/opt/cmake/bin/cmake else CMAKE_COMMAND=cmake fi ${CMAKE_COMMAND} --version ${CMAKE_COMMAND} -GNinja .. \ -DCMAKE_INSTALL_PREFIX=install \ -DSECP256K1_BUILD_OPENSSL_TESTS=$OPENSSL_TESTS \ -DSECP256K1_ECMULT_STATIC_PRECOMPUTATION=$STATICPRECOMPUTATION \ -DSECP256K1_ENABLE_MODULE_ECDH=$ECDH \ -DSECP256K1_ENABLE_MODULE_MULTISET=$MULTISET \ -DSECP256K1_ENABLE_MODULE_RECOVERY=$RECOVERY \ -DSECP256K1_ENABLE_MODULE_SCHNORR=$SCHNORR \ -DSECP256K1_ENABLE_JNI=$JNI \ -DSECP256K1_ENABLE_ENDOMORPHISM=$ENDOMORPHISM \ -DSECP256K1_ENABLE_BIGNUM=$BIGNUM \ -DSECP256K1_USE_ASM=$ASM \ - -DUSE_FIELD=$FIELD \ - -DUSE_SCALAR=$SCALAR \ + -DSECP256K1_TEST_OVERRIDE_WIDE_MULTIPLY=$WIDEMUL \ $ECMULT_GEN_PRECISION_ARG \ $CMAKE_EXTRA_FLAGS ninja $CMAKE_TARGET if [ -n "$VALGRIND" ]; then # the `--error-exitcode` is required to make the test fail if valgrind found # errors, otherwise it'll return 0 # (http://valgrind.org/docs/manual/manual-core.html) valgrind --error-exitcode=42 ./secp256k1-tests 16 valgrind --error-exitcode=42 ./secp256k1-exhaustive_tests fi popd