Peter Dettman [Tue, 4 Nov 2014 12:16:55 +0000 (19:16 +0700)]
Effective affine addition in EC multiplication
* Make secp256k1_gej_add_var and secp256k1_gej_double return the
Z ratio to go from a.z to r.z.
* Use these Z ratios to speed up batch point conversion to affine
coordinates, and to speed up batch conversion of points to a
common Z coordinate.
* Add a point addition function that takes a point with a known
Z inverse.
* Due to secp256k1's endomorphism, all additions in the EC
multiplication code can work on affine coordinate (with an
implicit common Z coordinate), correcting the Z coordinate of
the result afterwards.
Refactoring by Pieter Wuille:
* Move more global-z logic into the group code.
* Separate code for computing the odd multiples from the code to bring it
to either storage or globalz format.
* Rename functions.
* Make all addition operations return Z ratios, and test them.
* Make the zr table format compatible with future batch chaining
(the first entry in zr becomes the ratio between the input and the
first output).
Original idea and code by Peter Dettman.
Pieter Wuille [Wed, 22 Apr 2015 19:54:10 +0000 (12:54 -0700)]
Merge pull request #245
c146b4a Add bench_internal to gitignore. (Gregory Maxwell)
9c4fb23 Add a secp256k1_fe_cmov unit test. (Gregory Maxwell)
Pieter Wuille [Wed, 22 Apr 2015 19:32:58 +0000 (12:32 -0700)]
Merge pull request #190
d227579 Add scalar blinding and a secp256k1_context_randomize() call. (Gregory Maxwell)
Gregory Maxwell [Wed, 15 Apr 2015 21:35:50 +0000 (21:35 +0000)]
Add scalar blinding and a secp256k1_context_randomize() call.
This computes (n-b)G + bG with random value b, in place of nG in
ecmult_gen() for signing.
This is intended to reduce exposure to potential power/EMI sidechannels
during signing and pubkey generation by blinding the secret value with
another value which is hopefully unknown to the attacker.
It may not be very helpful if the attacker is able to observe the setup
or if even the scalar addition has an unacceptable leak, but it has low
overhead in any case and the security should be purely additive on top
of the existing defenses against sidechannels.
Gregory Maxwell [Wed, 22 Apr 2015 19:11:19 +0000 (19:11 +0000)]
Add bench_internal to gitignore.
Gregory Maxwell [Wed, 22 Apr 2015 19:07:31 +0000 (19:07 +0000)]
Add a secp256k1_fe_cmov unit test.
(Also add my name to the top of tests.c: I wrote a bunch of that
and update the copyright dates)
Pieter Wuille [Wed, 22 Apr 2015 09:46:20 +0000 (02:46 -0700)]
Merge pull request #243
bb0ea50 Replace set/add with cmov in secp256k1_gej_add_ge. (Gregory Maxwell)
Pieter Wuille [Wed, 22 Apr 2015 09:28:05 +0000 (02:28 -0700)]
Merge pull request #244
2d2707a travis: test i686 builds with gmp (Cory Fields)
cf7f702 travis: update to new build infrastructure (Cory Fields)
Cory Fields [Wed, 22 Apr 2015 04:42:19 +0000 (00:42 -0400)]
travis: test i686 builds with gmp
Test with and without endomorphism.
Cory Fields [Wed, 22 Apr 2015 00:21:00 +0000 (20:21 -0400)]
travis: update to new build infrastructure
See here:
http://blog.travis-ci.com/2014-12-17-faster-builds-with-container-based-infrastructure/
These changes remove our use of sudo so that we can move to the container-based
builds. This yields quicker builds and less reliance on the old infrastructure.
Gregory Maxwell [Wed, 22 Apr 2015 00:20:54 +0000 (00:20 +0000)]
Replace set/add with cmov in secp256k1_gej_add_ge.
Use a conditional move of the same kind we use for the affine points
in the storage type instead of multiplying with the infinity flag
and adding. This results in fewer constructions to worry about for
sidechannel behavior.
It also might be faster: It doesn't appear to benchmark as slower for
me at least; but I think the CMOV is faster than the mul_int + add,
but slower than the set+add; making it a wash.
Pieter Wuille [Sun, 19 Apr 2015 18:32:09 +0000 (11:32 -0700)]
Merge pull request #241
5c2a4fa Fix memory leak in context unit test (Andrew Poelstra)
Andrew Poelstra [Thu, 16 Apr 2015 20:56:04 +0000 (15:56 -0500)]
Fix memory leak in context unit test
Before fix, `valgrind ./tests 1` outputs
==21959== in use at exit: 2,228,288 bytes in 8 blocks
after:
==23974== in use at exit: 0 bytes in 0 blocks
Pieter Wuille [Tue, 14 Apr 2015 08:02:50 +0000 (01:02 -0700)]
Merge pull request #239
93226a5 secp256k1.c: Add missing DEBUG_CHECKs for sufficiently capable contexts (Andrew Poelstra)
Andrew Poelstra [Tue, 14 Apr 2015 02:51:38 +0000 (21:51 -0500)]
secp256k1.c: Add missing DEBUG_CHECKs for sufficiently capable contexts
Pieter Wuille [Sun, 12 Apr 2015 15:39:45 +0000 (08:39 -0700)]
Merge pull request #237
6066bb6 Fix typo: avg -> max (Pieter Wuille)
Pieter Wuille [Sun, 12 Apr 2015 13:17:24 +0000 (06:17 -0700)]
Fix typo: avg -> max
Pieter Wuille [Sun, 12 Apr 2015 09:05:23 +0000 (02:05 -0700)]
Merge pull request #236
d899b5b Expose ability to deep-copy a context (Andrew Poelstra)
Andrew Poelstra [Sat, 11 Apr 2015 19:06:54 +0000 (14:06 -0500)]
Expose ability to deep-copy a context
Pieter Wuille [Sat, 11 Apr 2015 08:01:32 +0000 (01:01 -0700)]
Merge pull request #208
a9b6595 [API BREAK] Introduce explicit contexts (Pieter Wuille)
Pieter Wuille [Wed, 4 Feb 2015 01:27:00 +0000 (17:27 -0800)]
[API BREAK] Introduce explicit contexts
Pieter Wuille [Fri, 10 Apr 2015 08:20:23 +0000 (01:20 -0700)]
Merge pull request #233
6534ee1 initialize variable (Cory Fields)
Pieter Wuille [Fri, 10 Apr 2015 08:08:52 +0000 (01:08 -0700)]
Merge pull request #234
4450e24 Add a comment about the avoidance of secret data in array indexes. (Gregory Maxwell)
Pieter Wuille [Fri, 10 Apr 2015 08:06:51 +0000 (01:06 -0700)]
Merge pull request #235
5098f62 Improve documentation formatting consistency (Daniel Cousens)
Daniel Cousens [Fri, 10 Apr 2015 06:33:33 +0000 (16:33 +1000)]
Improve documentation formatting consistency
Gregory Maxwell [Mon, 6 Apr 2015 03:48:08 +0000 (03:48 +0000)]
Add a comment about the avoidance of secret data in array indexes.
People elsewhere still seem to be writing crypto code making this
mistake, so it must not be that well known.
Cory Fields [Fri, 3 Apr 2015 21:16:09 +0000 (17:16 -0400)]
initialize variable
Pieter Wuille [Sun, 29 Mar 2015 21:31:45 +0000 (14:31 -0700)]
Merge pull request #232
c01df1a Avoid some implicit type conversions to make C++ compilers happy. (Gregory Maxwell)
Gregory Maxwell [Sat, 28 Mar 2015 02:20:36 +0000 (02:20 +0000)]
Avoid some implicit type conversions to make C++ compilers happy.
Pieter Wuille [Sat, 28 Mar 2015 00:46:29 +0000 (17:46 -0700)]
Merge pull request #231
33270bf Add a couple comments pointing to particular sections of RFC6979. (Gregory Maxwell)
Gregory Maxwell [Sat, 28 Mar 2015 00:43:15 +0000 (00:43 +0000)]
Add a couple comments pointing to particular sections of RFC6979.
Pieter Wuille [Fri, 27 Mar 2015 23:58:04 +0000 (16:58 -0700)]
Merge pull request #230
2632019 Brace all the if/for/while. (Gregory Maxwell)
Gregory Maxwell [Fri, 27 Mar 2015 23:14:17 +0000 (23:14 +0000)]
Brace all the if/for/while.
Unbraced statements spanning multiple lines has been shown in many
projects to contribute to the introduction of bugs and a failure
to catch them in review, especially for maintenance on infrequently
modified code.
Most, but not all, of the existing practice in the codebase were not
cases that I would have expected to eventually result in bugs but
applying it as a rule makes it easier for other people to safely
contribute.
I'm not aware of any such evidence for the case with the statement
on a single line, but some people strongly prefer to never do that
and the opposite rule of "_always_ use a single line for single
statement blocks" isn't a reasonable rule for formatting reasons.
Might as well brace all these too, since that's more universally
acceptable.
[In any case, I seem to have introduced the vast majority of the
single-line form (as they're my preference where they fit).]
This also removes a broken test which is no longer needed.
Pieter Wuille [Fri, 27 Mar 2015 20:49:45 +0000 (13:49 -0700)]
Merge pull request #229
efc571c Add simple testcases for signing with rfc6979 extra entropy. (Gregory Maxwell)
1573a10 Add ability to pass extra entropy to rfc6979 (Pieter Wuille)
Gregory Maxwell [Fri, 27 Mar 2015 11:55:17 +0000 (11:55 +0000)]
Add simple testcases for signing with rfc6979 extra entropy.
Pieter Wuille [Fri, 20 Mar 2015 16:19:38 +0000 (09:19 -0700)]
Add ability to pass extra entropy to rfc6979
Suggested by Greg Maxwell.
Pieter Wuille [Mon, 16 Mar 2015 10:29:29 +0000 (03:29 -0700)]
Merge pull request #228
27bc131 Silence some warnings from pedantic static analysis tools, improve compatibility with C++. (Gregory Maxwell)
Pieter Wuille [Mon, 16 Mar 2015 10:24:12 +0000 (03:24 -0700)]
Merge pull request #218
0065a8f Eliminate multiple-returns from secp256k1.c. (Gregory Maxwell)
354ffa3 Make secp256k1_ec_pubkey_create reject oversized secrets. (Gregory Maxwell)
Gregory Maxwell [Tue, 17 Feb 2015 09:01:48 +0000 (01:01 -0800)]
Eliminate multiple-returns from secp256k1.c.
Goto, multiple returns, continue, and/or multiple breaks in a
loop are often used to build complex or non-local control
flow in software.
(They're all basically the same thing, and anyone axiomatically
opposing goto and not the rest is probably cargo-culting from
the title of Dijkstra's essay without thinking hard about it.)
Personally, I think the current use of these constructs in the
code base is fine: no where are we using them to create control-
flow that couldn't easily be described in plain English, which
is hard to read or reason about, or which looks like a trap for
future developers.
Some, however, prefer a more rules based approach to software
quality. In particular, MISRA forbids all of these constructs,
and for good experience based reasons. Rules also have the
benefit of being machine checkable and surviving individual
developers.
(To be fair-- MISRA also has a process for accommodating code that
breaks the rules for good reason).
I think that in general we should also try to satisfy the rules-
based measures of software quality, except where there is an
objective reason not do: a measurable performance difference,
logic that turns to spaghetti, etc.
Changing out all the multiple returns in secp256k1.c appears to
be basically neutral: Some parts become slightly less clear,
some parts slightly more.
Gregory Maxwell [Tue, 17 Feb 2015 08:10:12 +0000 (00:10 -0800)]
Make secp256k1_ec_pubkey_create reject oversized secrets.
Gregory Maxwell [Mon, 26 Jan 2015 05:26:09 +0000 (05:26 +0000)]
Silence some warnings from pedantic static analysis tools, improve compatibility with C++.
C doesn't include the null in an array initilized from a
string literal if it doesn't fit, in C++ this is invalid.
The vararray style prototypes and init+calc also changed in
this commit are not C89 enough for some tools.
Pieter Wuille [Mon, 2 Mar 2015 10:44:45 +0000 (02:44 -0800)]
Merge pull request #221
443cd4b Get rid of hex format and some binary conversions (Pieter Wuille)
Pieter Wuille [Tue, 24 Feb 2015 10:38:27 +0000 (02:38 -0800)]
Merge pull request #215
8956111 use 128-bit hex seed (Pieter Wuille)
02efd06 Use RFC6979 for test PRNGs (Pieter Wuille)
Pieter Wuille [Tue, 24 Feb 2015 10:37:06 +0000 (02:37 -0800)]
Merge pull request #222
7c3771d Disable overlength-strings warnings. (evoskuil)
Pieter Wuille [Tue, 24 Feb 2015 10:22:46 +0000 (02:22 -0800)]
Merge pull request #216
ae55e85 Use faster byteswapping and avoid alignment-increasing casts. (Pieter Wuille)
evoskuil [Mon, 23 Feb 2015 22:12:25 +0000 (14:12 -0800)]
Disable overlength-strings warnings.
Pieter Wuille [Sat, 14 Feb 2015 23:30:58 +0000 (15:30 -0800)]
use 128-bit hex seed
Pieter Wuille [Fri, 13 Feb 2015 23:56:08 +0000 (15:56 -0800)]
Use RFC6979 for test PRNGs
Pieter Wuille [Sun, 22 Feb 2015 13:54:56 +0000 (05:54 -0800)]
Use faster byteswapping and avoid alignment-increasing casts.
Pieter Wuille [Mon, 23 Feb 2015 12:17:37 +0000 (04:17 -0800)]
Get rid of hex format and some binary conversions
Pieter Wuille [Mon, 16 Feb 2015 19:28:42 +0000 (11:28 -0800)]
Merge #214: Improve signing API documentation & specification
8030d7c Improve signing API documentation & specification (Pieter Wuille)
Pieter Wuille [Fri, 13 Feb 2015 02:00:50 +0000 (18:00 -0800)]
Improve signing API documentation & specification
Pieter Wuille [Fri, 13 Feb 2015 18:41:03 +0000 (10:41 -0800)]
Merge #213: Removed gotos, which are hard to trace and maintain.
11690d3 Removed gotos, which are hard to trace and maintain. (Iang)
Iang [Sat, 8 Nov 2014 18:19:10 +0000 (18:19 +0000)]
Removed gotos, which are hard to trace and maintain.
Pieter Wuille [Fri, 13 Feb 2015 01:05:18 +0000 (17:05 -0800)]
Merge pull request #205
6cc8425 Include a comment on secp256k1_ecdsa_sign explaining low-s. (Gregory Maxwell)
Pieter Wuille [Fri, 13 Feb 2015 00:26:40 +0000 (16:26 -0800)]
Merge pull request #206
34b898d Additional comments for the testing PRNG and a seeding fix. (Gregory Maxwell)
6efd6e7 Some comments explaining some of the constants in the code. (Gregory Maxwell)
Pieter Wuille [Sat, 7 Feb 2015 02:21:30 +0000 (18:21 -0800)]
Merge pull request #161
ffccfd2 x86_64 assembly optimization for scalar_4x64 (Pieter Wuille)
Gregory Maxwell [Mon, 2 Feb 2015 06:46:04 +0000 (06:46 +0000)]
Additional comments for the testing PRNG and a seeding fix.
Rw has additional short-cycle inputs because 2^32/0x464fffff >= 2.
Gregory Maxwell [Mon, 2 Feb 2015 01:47:23 +0000 (01:47 +0000)]
Some comments explaining some of the constants in the code.
Pieter Wuille [Fri, 12 Dec 2014 15:55:02 +0000 (16:55 +0100)]
x86_64 assembly optimization for scalar_4x64
Pieter Wuille [Tue, 3 Feb 2015 04:57:33 +0000 (20:57 -0800)]
Merge pull request #207
039723d Benchmarks for all internal operations (Pieter Wuille)
Pieter Wuille [Sat, 31 Jan 2015 20:12:10 +0000 (16:12 -0400)]
Benchmarks for all internal operations
Gregory Maxwell [Mon, 2 Feb 2015 02:16:29 +0000 (02:16 +0000)]
Include a comment on secp256k1_ecdsa_sign explaining low-s.
This was suggested by DavidEGrayson.
Pieter Wuille [Thu, 29 Jan 2015 04:37:34 +0000 (00:37 -0400)]
Merge pull request #203
d61e899 Add group operation counts (Pieter Wuille)
Pieter Wuille [Tue, 27 Jan 2015 16:05:50 +0000 (12:05 -0400)]
Add group operation counts
Pieter Wuille [Mon, 26 Jan 2015 05:18:17 +0000 (01:18 -0400)]
Merge pull request #202
b5bbce6 Some readme updates, e.g. removal of the GMP field. (Gregory Maxwell)
Gregory Maxwell [Mon, 26 Jan 2015 04:12:24 +0000 (04:12 +0000)]
Some readme updates, e.g. removal of the GMP field.
Pieter Wuille [Sun, 25 Jan 2015 18:22:23 +0000 (14:22 -0400)]
Merge pull request #201
f735446 Convert the rest of the codebase to C89. (Gregory Maxwell)
Pieter Wuille [Sun, 25 Jan 2015 17:59:17 +0000 (13:59 -0400)]
Merge pull request #200
bf2e1ac Convert tests to C89. (also fixes a use of bare "inline" in field) (Gregory Maxwell)
Gregory Maxwell [Sun, 25 Jan 2015 17:32:08 +0000 (17:32 +0000)]
Convert the rest of the codebase to C89.
Update build system to enforce -std=c89 -pedantic.
Gregory Maxwell [Sun, 25 Jan 2015 15:47:04 +0000 (15:47 +0000)]
Convert tests to C89. (also fixes a use of bare "inline" in field)
Pieter Wuille [Sun, 25 Jan 2015 13:13:31 +0000 (09:13 -0400)]
Merge pull request #199
fcc48c4 Remove the non-storage cmov (Pieter Wuille)
55422b6 Switch ecmult_gen to use storage types (Pieter Wuille)
41f8455 Use group element storage type in EC multiplications (Pieter Wuille)
e68d720 Add group element storage type (Pieter Wuille)
ff889f7 Field storage type (Pieter Wuille)
Pieter Wuille [Sun, 25 Jan 2015 05:37:25 +0000 (01:37 -0400)]
Merge pull request #197
4be8d6f Centralize the definition of uint128_t and use it uniformly. (Gregory Maxwell)
d9543c9 Switch scalar code to C89. (Gregory Maxwell)
Gregory Maxwell [Sun, 25 Jan 2015 03:41:59 +0000 (03:41 +0000)]
Centralize the definition of uint128_t and use it uniformly.
This needs to be renamed along with the other _t types, because _t
is reserved. But that will be done later.
Gregory Maxwell [Sun, 25 Jan 2015 02:54:48 +0000 (02:54 +0000)]
Switch scalar code to C89.
Pieter Wuille [Sun, 25 Jan 2015 04:56:22 +0000 (00:56 -0400)]
Remove the non-storage cmov
Pieter Wuille [Sun, 25 Jan 2015 04:46:31 +0000 (00:46 -0400)]
Switch ecmult_gen to use storage types
Pieter Wuille [Sun, 25 Jan 2015 04:32:22 +0000 (00:32 -0400)]
Use group element storage type in EC multiplications
Pieter Wuille [Sun, 25 Jan 2015 04:31:56 +0000 (00:31 -0400)]
Add group element storage type
Pieter Wuille [Sun, 25 Jan 2015 03:04:48 +0000 (23:04 -0400)]
Field storage type
Pieter Wuille [Sun, 25 Jan 2015 02:14:42 +0000 (22:14 -0400)]
Merge pull request #196
0768bd5 Get rid of variable-length hex string conversions (Pieter Wuille)
Pieter Wuille [Sun, 25 Jan 2015 01:52:48 +0000 (21:52 -0400)]
Get rid of variable-length hex string conversions
Pieter Wuille [Sun, 25 Jan 2015 01:35:02 +0000 (21:35 -0400)]
Merge pull request #195
792bcdb Covert several more files to C89. (Gregory Maxwell)
Gregory Maxwell [Sat, 24 Jan 2015 23:34:09 +0000 (23:34 +0000)]
Covert several more files to C89.
Pieter Wuille [Sat, 24 Jan 2015 22:50:56 +0000 (18:50 -0400)]
Merge pull request #193
25b35c7 Convert field code to strict C89 (+ long long, +__int128) (Gregory Maxwell)
3627437 C89 nits and dead code removal. (Gregory Maxwell)
Pieter Wuille [Sat, 24 Jan 2015 19:26:09 +0000 (15:26 -0400)]
Merge pull request #194
402878a fix ifdef/ifndef (mb300sd)
mb300sd [Fri, 23 Jan 2015 22:09:50 +0000 (17:09 -0500)]
fix ifdef/ifndef
Gregory Maxwell [Fri, 23 Jan 2015 05:48:27 +0000 (05:48 +0000)]
Convert field code to strict C89 (+ long long, +__int128)
This makes the software more portable to embedded systems
and static analysis tools.
Sadly, it can't result in identical binaries because C99 mixed
declarations seem to make GCC emit superfluous stack-pointer
updates. The compiler is also somewhat dependent on the
declaration order.
Gregory Maxwell [Fri, 23 Jan 2015 04:17:12 +0000 (04:17 +0000)]
C89 nits and dead code removal.
Pieter Wuille [Fri, 23 Jan 2015 04:10:39 +0000 (23:10 -0500)]
Merge pull request #191
4732d26 Convert the field/group/ecdsa constant initialization to static consts (Pieter Wuille)
19f3e76 Remove unused secp256k1_fe_inner_{start, stop} functions (Pieter Wuille)
f1ebfe3 Convert the scalar constant initialization to static consts (Pieter Wuille)
Pieter Wuille [Wed, 21 Jan 2015 22:38:17 +0000 (17:38 -0500)]
Convert the field/group/ecdsa constant initialization to static consts
Pieter Wuille [Wed, 21 Jan 2015 22:50:16 +0000 (17:50 -0500)]
Remove unused secp256k1_fe_inner_{start, stop} functions
Pieter Wuille [Wed, 21 Jan 2015 22:20:43 +0000 (17:20 -0500)]
Convert the scalar constant initialization to static consts
Pieter Wuille [Mon, 5 Jan 2015 14:04:21 +0000 (15:04 +0100)]
Merge pull request #178
941e221 Add tests for handling of the nonce function in signing. (Gregory Maxwell)
Gregory Maxwell [Mon, 5 Jan 2015 01:26:51 +0000 (17:26 -0800)]
Add tests for handling of the nonce function in signing.
Pieter Wuille [Sun, 4 Jan 2015 14:23:03 +0000 (15:23 +0100)]
Merge pull request #177
7688e34 Add magnitude limits to secp256k1_fe_verify to ensure that it's own tests function correctly. (Gregory Maxwell)
70ae0d2 Use secp256k1_fe_equal_var in secp256k1_fe_sqrt_var. (Gregory Maxwell)
Gregory Maxwell [Fri, 2 Jan 2015 15:52:27 +0000 (07:52 -0800)]
Add magnitude limits to secp256k1_fe_verify to ensure that it's own tests function correctly.
Pieter Wuille [Fri, 2 Jan 2015 15:28:09 +0000 (16:28 +0100)]
Merge pull request #176
9ab9335 Add a reference consistency test to ge_tests. (Pieter Wuille)
60571c6 Rework group tests (Pieter Wuille)
Gregory Maxwell [Wed, 31 Dec 2014 13:56:00 +0000 (05:56 -0800)]
Use secp256k1_fe_equal_var in secp256k1_fe_sqrt_var.
In theory this should be faster, since secp256k1_fe_equal_var is able to
shortcut the normalization. On x86_64 the improvement appears to be in
the noise for me. At least it makes the code cleaner.
Pieter Wuille [Mon, 29 Dec 2014 16:51:24 +0000 (17:51 +0100)]
Merge pull request #175
d26e26f Avoid constructing an invalid signature with probability 1:2^256. (Gregory Maxwell)
This page took 0.067438 seconds and 4 git commands to generate.