I think you made an error in the following:

Should be s2=a*s1 + b, no?

I'm probably overlooking something:

If the ECDSA signature is only for each input of a transaction, and the hash of the transaction is malleable, then what stops a nefarious miner from changing the output script to pay to a different address than the sender intended?

tl;dr: Private key is the scalar coefficient of a EC Point multiplication. If your private key is d, then your public key Q would be:  Q=d*G.


Bitcoin's Elliptic Curve satisfies the equation:  y² = x³ + 7.

Every public key must be a point on the curve, so you can substitute the point's X and Y into the equation to see if it is a valid point.

The addition operation is defined for EC points, so if you know any two points on the curve, then you can "add" them together to get a third point that is also on the curve.  Multiplication is an extension of this, so if you want to multiply a point by some number, then you can add it to itself that many times.  Note that in practice, there are algorithms to make multiplication more efficient than repeated addition.

Private keys are the scalar coefficient used in point multiplication.  There is one special point defined, known as the Generator, that is multiplied by a private key in order to produce a public key.  This is often noted as G, and the point multiplication operation itself is often noted as k*G for a scalar value k. Note that "*" here is not the same as what we think of as multiplication for real numbers.

Gx=79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

It is a common notation to represent scalar values as lowercase letters, and EC Points as uppercase letters when they are mixed in the same equations.

The entire system is contained within a finite field F_p, where p=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F. This means that all scalar operations are performed (mod p), so the largest value needed for the scalar multiplier or the x/y coordinates of the resulting point is a 256-bit number. But, because of this modular math, you quickly lose the relationship between the scalar value k and the resulting point k*G.  

The modular math, plus the complexity of how to represent point addition as an algebraic equation, is what makes point multiplication a one-way function: easy to perform, but extremely difficult to undo. That is, if you know the (x,y) point for k*G, it is currently extremely difficult to determine what k was.  This is the Elliptic Curve Discrete Log Problem, and is the underpinning of security for ECDSA.

Wikipedia entry on Elliptic Curves: http://en.wikipedia.org/wiki/Elliptic_curve
Wikipedia entry on EC Point Multiplication: http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

^^ this. New thread in a forum more appropriate to the research aspect that this thread has taken on would be appreciated.

Is the assumption here is that you can find 2⁴⁰ keypairs all with the same lower 32-bits to use in a rainbow table? I think that task alone is equivalent to O(N).

I'm not a cryptographer, but trying to understand things like the behavior of finite fields and [now] ECDLP are a quirky hobby of mine.

The 32-bit number is just to know when your client has found a potential hit.  It's exactly like a share when mining, where it may not be the solution, but at least shows that you're working towards it. 

In his code (https://github.com/gh2k/rpoints/blob/master/main.cpp), the client starts with a random i*G point, and continuously adds numbers to it (so you're calculating i*G + j*G).  There's logic that attempts to skip around a bit, trying 100 sequential numbers for j, then adding a big random number to it to make a big jump, and then resuming with another 100 sequential numbers attempt. 

All the while, it keeps track of i+j, so that if you find a share, it submits the point's X,Y and the i+j, which is the private key for that point.  The server presumably has the full key's value on it, and it is able to tell if your share was an actual point of interest, or just noise.

What I haven't figured out is what exactly the points of interest are. My first guess was that they're public keys, but spot checking the list against some from the Top 100 list didn't provide any matches for the lower 32-bits of known public key X values.  I also tried some of the unclaimed Satoshi-mined blocks that were paid to a public key, but no hits in the blocks that I checked.  I don't have a full database of known public keys available to query, so my tests were inconclusive.

As far as this code on Github is concerned, EK's intersection diagram has no relevance. I think he provided it to show that given constraints, you can narrow the search scope considerably.  But, I also think his diagram is flawed because it assumes that proximity of EC points correlates with proximity of their scalar multipliers, which I have not been able to observe myself.

Don't confuse the DLP with the ECDLP, though. Similar concepts, but ECDLP doesn't use exponents (it uses EC multiplication instead, which is the operation that is intractable).

Q is public key, n is order of G, set m = sqrt(n)

Baby-step (i) Giant-step (j) is then to find a collision: 

i*G = Q − jm*G

or, in other words, find the sum of two points, i*G + jm*G, that collide with the public key point Q that you're trying to solve. The private key will be i + jm (mod n).

The paradox here is that if someone has broken ECDLP and obtains the keys to the kingdom (BTC and all of the other crypto coins that rely on ECDSA), and they go public with it, then they will assume ownership of nothing because the currency would cease to have any value.  

Does this mean that ECDLP remains unsolved?  Not necessarily.  There are attacks based on randomly finding collisions in the EC space in order to derive unknown variables in the algebraic space (Pollard Rho and Kangaroo come to mind), and a clever person may have figured out ways to make this more efficient, or at least less random in nature.  Hopefully, they remain clever and not seek fame or attention.

In this case, though, I agree that it appears the script on GitHub is being used as a vehicle for a distributed search for the private keys that generate well-known public keys... or similarly, a search for "k" that results in a well-known signature R value (which can then be used to derive the private key for the public key used by that signature).  

I've been studying Bitcoin's use of private/public keys and ECDSA, and I'm a bit confused at the moment about when to use mod(p) vs. mod(n). 

For example, when doing a EC point multiplication (i.e., to compute Q=d*G), are the point coordinates modulo p?  Is anything ever modulo n?

And while on that topic, could someone explain the purpose of p (as in Fp) and n (as in the "order n of the generator point G", but this description is a little lost on me...)? If we never need to use mod(n), then p makes perfect sense as the number of elements in the field, but as soon as mod(n) is used, it seems that there is a range of numbers in Fp that are not used.

Thanks!

I've been studying Bitcoin's ECDSA, and I'm a bit confused at the moment about when to use mod(p) vs. mod(n). 

For example, when doing a EC point multiplication (i.e., to compute Q=d*G), are the point coordinates modulo p?  Is anything ever modulo n?

And while on that topic, could someone explain the purpose of p (as in Fp) and n (as in the "order n of the generator point G", but this description is a little lost on me...)?