Fix build with static ecmult altroot and make dist.
Gen_context was unable to find the required headers without some
autotools fixups. Make dist was also broken without the extra
sources for the host side table builder utility.
5a43124 Save 1 _fe_negate since s1 == -s2 (Peter Dettman) a5d796e Update code comments (Peter Dettman) 7d054cd Refactor to save a _fe_negate (Peter Dettman) b28d02a Refactor to remove a local var (Peter Dettman) 55e7fc3 Perf. improvement in _gej_add_ge (Peter Dettman)
Pieter Wuille [Mon, 29 Jun 2015 16:28:15 +0000 (18:28 +0200)]
Merge pull request #261
7657420 Add tests for adding P+Q with P.x!=Q.x and P.y=-Q.y (Pieter Wuille) 8c5d5f7 tests: Add failing unit test for #257 (bad addition formula) (Andrew Poelstra) 5de4c5d gej_add_ge: fix degenerate case when computing P + (-lambda)P (Andrew Poelstra) bcf2fcf gej_add_ge: rearrange algebra (Andrew Poelstra)
Andrew Poelstra [Tue, 23 Jun 2015 19:41:02 +0000 (12:41 -0700)]
gej_add_ge: fix degenerate case when computing P + (-lambda)P
If two points (x1, y1) and (x2, y2) are given to gej_add_ge with
x1 != x2 but y1 = -y2, the function gives a wrong answer since
this causes it to compute "lambda = 0/0" during an intermediate
step. (Here lambda refers to an auxiallary variable in the point
addition formula, not the cube-root of 1 used by the endomorphism
optimization.)
This commit catches the 0/0 and replaces it with an alternate
expression for lambda, cmov'ing it in place if necessary.
Andrew Poelstra [Tue, 23 Jun 2015 19:35:20 +0000 (12:35 -0700)]
gej_add_ge: rearrange algebra
There is zero functionality or opcount changes here; I need to do
this to make sure both R and M are computed before they are used,
since a future patch will replace either none or both of them.
Also compute r->y directly in terms of r->x, which again will be
used in a future patch.
Andrew Poelstra [Mon, 11 May 2015 14:55:45 +0000 (09:55 -0500)]
Use separate in and out pointers in `secp256k1_ec_pubkey_decompress`
Right now `secp256k1_ec_pubkey_decompress` takes an in/out pointer to
a public key and replaces the input key with its decompressed variant.
This forces users who store compressed keys in small (<65 byte) fixed
size buffers (for example, the Rust bindings do this) to explicitly
and wastefully copy their key to a larger buffer.
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).
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.
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.
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.
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 [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.
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)
projects / secp256k1.git / log