I've been staring at this problem for a while and I decided that it's too important to make a conclusion on instinct alone. So I'm hoping there's some real mathematical types here that can help with this ECDSA problem.

Consider a system where you need lots of ECDSA public-private keypairs. Assume you can generate random numbers reliably, so there's no security-problem with generating new private keys. The problem is I'd like to backup my keypairs, but I'm constantly making new ones, requiring constant backups.

Instead, I want to generate two 256-bit random numbers, the first one is my first private key a, and generate my first public key

where G is your generator point on the curve of order n. The other number is used as a "chain-code," c. Using the chain-code, I can calulate the next pub-priv keypair by doing:Code:PrivKeyA = a PubKeyA = a*G

First of all, I can now backup only PrivateKeyA and chain-code c, once, and I'll never need to backup again. Second, you'll notice that the new public key can be computed by another party (perhaps myself, on another computer), withCode:PrivKeyB = c*a PubKeyB = c*a*G = c*PubKeyAonlythe previous public key and the chain-code!

But, I'm aware of the problems with signing messages using ECDSA without using a different random number for each signature. I'm afraid there might be a similar problem here, but I can't find it, which meansI don't know.

So now put yourself in the place of an attacker. Consder both cases, in one case you have the chain-code, in the other case you don't (so all the powers of c look the same). You have the following information:

And you've seen signatures from each of these public keys.Code:PubKeyA = a * G PubKeyB = c * a * G PubKeyC = c^2 * a * G PubKeyD = c^3 * a * G ... etc

Code:msg zA, Sig: rA = (kA*G)_x, sA = inv(kA)*(zA + rA*a) msg zB, Sig: rB = (kB*G)_x, sB = inv(kB)*(zB + rB*a*c) msg zC, Sig: rC = (kC*G)_x, sC = inv(kC)*(zC + rC*a*c^2) msg zD, Sig: rD = (kD*G)_x, sD = inv(kD)*(zD + rD*a*c^3) ... etcYour goal is to calculate the private key, a

Alternatively, if instead of using a single number c as the chain code, I use the first 128 bits for "c", and use the next 128-bits to represent a constant "offset" value. So my next pair would be:

It's probably a tad faster anyway, since the multiplier c is smaller, and offset*G can be precomputed.Code:PrivKeyB = (c*a+offset)*G PubKeyB = c*PubKey + offset*G

Obviously, I know a bit about the math, but I haven't really spent a lot of time digging into any of the EC-type algorithms. Any help is appreciated!

Tweet This+ 1 thisPost To Linkedin