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
Code:
PrivKeyA = a
PubKeyA = a*G
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:
PrivKeyB = c*a
PubKeyB = c*a*G = c*PubKeyA
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), with
only the 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 means
I 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:
Code:
PubKeyA = a * G
PubKeyB = c * a * G
PubKeyC = c^2 * a * G
PubKeyD = c^3 * a * G
... etc
And you've seen signatures from each of these public keys.
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)
... etc
Your 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:
Code:
PrivKeyB = (c*a+offset)*G
PubKeyB = c*PubKey + offset*G
It's probably a tad faster anyway, since the multiplier c is smaller, and offset*G can be precomputed.
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!
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
