Author

Topic: reused or (similar) r values from completely different private keys (Read 298 times)

newbie
Activity: 14
Merit: 1
What if the same private key shares two r values that are (almost) identical to each other? Does this help calculating the private key in any possible way?

Suppose r1 = cabc3692f1f7ba75a8572dc5d270b35bcc00650534f6e5ecd6338e55355454d5
             r2 = cabc3692f1f7ba75a8572dc5d270b35ba54694a2d2302093d8b0a93ed5d83f2c

Here r1 + r2 from the same private key shares only their first 128 bits.



if you mean this, then you are wrong. R value must be the same in 1 wallet address with 2 different transactions. and if you have a script to auto calculate, maybe i can send you the script.  Grin
A few hours ago you were wondering how to use brute force applications, now you are a cryptography expert?

please revise, I ask the use of btcrecover and the correct way of installation.
but the R value script I made myself, even just an R variable is easy. so the R value is not the way to bruteforce.  Roll Eyes
copper member
Activity: 1330
Merit: 899
🖤😏
What if the same private key shares two r values that are (almost) identical to each other? Does this help calculating the private key in any possible way?

Suppose r1 = cabc3692f1f7ba75a8572dc5d270b35bcc00650534f6e5ecd6338e55355454d5
             r2 = cabc3692f1f7ba75a8572dc5d270b35ba54694a2d2302093d8b0a93ed5d83f2c

Here r1 + r2 from the same private key shares only their first 128 bits.



if you mean this, then you are wrong. R value must be the same in 1 wallet address with 2 different transactions. and if you have a script to auto calculate, maybe i can send you the script.  Grin
A few hours ago you were wondering how to use brute force applications, now you are a cryptography expert?
newbie
Activity: 14
Merit: 1
What if the same private key shares two r values that are (almost) identical to each other? Does this help calculating the private key in any possible way?

Suppose r1 = cabc3692f1f7ba75a8572dc5d270b35bcc00650534f6e5ecd6338e55355454d5
             r2 = cabc3692f1f7ba75a8572dc5d270b35ba54694a2d2302093d8b0a93ed5d83f2c

Here r1 + r2 from the same private key shares only their first 128 bits.



if you mean this, then you are wrong. R value must be the same in 1 wallet address with 2 different transactions. and if you have a script to auto calculate, maybe i can send you the script.  Grin
copper member
Activity: 821
Merit: 1992
For example if they are two private keys from a public derivation wallet and you know the chain code you can recover the keys.

Also, the next paragraph about linear equations is quite important: as I described many times, each signature is just a relation between some public key, and signature R-value, that also is in fact some ECDSA point. That means you just have two points, that are connected in a linear way, like in "y=ax+b" function. You have one key under "x", and you can reach another key under "y" by applying "a" and "b" constants, that are publicly known. This equation is true for both cases, for private and public keys. Both sides should be always equal modulo "n", for each and every signature.

The same way of thinking can lead you to another important facts: deterministic wallets are widely used, even in the famous puzzle from 2015, you have some HD wallet.
A few words about the puzzle.  There is no pattern.  It is just consecutive keys from a deterministic wallet (masked with leading 000...0001 to set difficulty).  It is simply a crude measuring instrument, of the cracking strength of the community.
That means, there is some single key, that was used to generate all 256 addresses. Also, it means bruteforcing next keys is not the only way to unlock them. Another method is to pick some HD wallet, go through all steps, and apply more restrictions to the initial key, based on values derived from it. For example, the first key is of course equal to one. But the second key can be two or three. In this puzzle, it is three, that means, around half of the seeds can be rejected.

However, that is not the end of the road. Computers are deterministic, if you know all inputs, you can always reach the same outputs. That means, even if you have some keys from non-HD wallet, then still, you can find some value, that will allow you to deteministically generate all keys. It is all about the size of your inputs, and it is related to exhausting the whole space of possibilities, and applying the proper compression to that. You can see it clearly in neural networks, where you can begin with some data, and you will always reach some model, even if it will be overfitted.

Quote
The same can be applied here: even if the author of the original puzzle used just some single key to derive all addresses, then still, it is technically possible to find another seed, and even another algorithm, that will lead to the same solution. However, practically speaking, I think if we will ever get there, it will be long after breaking all hash functions and ECDSA, where all of those things will be obsolete, and replaced with something else through another soft-fork. But mathematically speaking, I think there exist such solutions.
member
Activity: 143
Merit: 82
Well, sure. If you want to go down that line of reasoning, then by the same logic if you use different but related k values, such as flawed software which simply does k+1 for each new transaction, then you are also at risk.
Indeed, but I raised it because related private keys are extremely common, like every hardware wallet generates them.

Can I ask to elaborate on the notion that "related private keys are extremely common, like every hardware wallet generates them", please? I would appreciate an example and possibly reference to long form article.
staff
Activity: 4284
Merit: 8808
Well, sure. If you want to go down that line of reasoning, then by the same logic if you use different but related k values, such as flawed software which simply does k+1 for each new transaction, then you are also at risk.
Indeed, but I raised it because related private keys are extremely common, like every hardware wallet generates them.
legendary
Activity: 2268
Merit: 18771
Things like linearly related private keys mean that the 'different' private key changes the equation slightly but it doesn't introduce another unknown.
Well, sure. If you want to go down that line of reasoning, then by the same logic if you use different but related k values, such as flawed software which simply does k+1 for each new transaction, then you are also at risk.

What if the same private key shares two r values that are (almost) identical to each other? Does this help calculating the private key in any possible way?
No.

The r value is obtained by taking the x coordinate of the point reached by multiplying the k value with G, the generator point of the secp256k1 curve. It is essentially the same process as using a private key to generate a public key. As with any other public key, two similar r values do not correlate to two similar k values, and vice versa.

If you have two closely related k values then there is a potential risk as discussed above (assuming an attacker knows about the relation), but not with two closely related r values.
member
Activity: 194
Merit: 14
What if the same private key shares two r values that are (almost) identical to each other? Does this help calculating the private key in any possible way?

Suppose r1 = cabc3692f1f7ba75a8572dc5d270b35bcc00650534f6e5ecd6338e55355454d5
             r2 = cabc3692f1f7ba75a8572dc5d270b35ba54694a2d2302093d8b0a93ed5d83f2c

Here r1 + r2 from the same private key shares only their first 128 bits.

staff
Activity: 4284
Merit: 8808
It is only possible when the same private key has reused the same r value.
Not only that, if the private keys have a known relationship then it's also vulnerable. For example if they are two private keys from a public derivation wallet and you know the chain code you can recover the keys.

The right intuition is that each signature is a linear equation in a system of linear equations-- you can solve the whole thing when the number of knows equal the unknowns.   Things like linearly related private keys mean that the 'different' private key changes the equation slightly but it doesn't introduce another unknown.
 
member
Activity: 194
Merit: 14
Dear friend oeleo,

Thank you so much for your answer and the great understandable clarifications! I didn't expect you to merit me too; haha! You didn't have to. I did nothing but asked a question XD

Enjoy your weekend m8!  Kiss
legendary
Activity: 2268
Merit: 18771
Or its only possible when the same private key has done 2 different transaction but used the same r values?
It is only possible when the same private key has reused the same r value.

The equation you are interested in is as follows (all equations mod n):

s = (z + x*r)/k

Where z is the message hash (usually a hash of part of the transaction data) and x is your private key.

Let's say you have two transactions using the same private key and the same k value. You now have following two equations:

s1 = (z1 + x*r)/k
s2 = (z2 + x*r)/k

This can be reformatted as:

k = (z1 - z2)/(s1 - s2)

Given that you know both s values and both z values from the transactions themselves, you can calculate k. Once you know k, you can go back to the initial equation and calculate x, the private key.

If, on the other hand, the private keys (x) are different, then you have the following transactions:

s1 = (z1 + x1*r)/k
s2 = (z2 + x2*r)/k

Reformat that, and you end up with the following:

k = ((z1 - z2) + r(x1 - x2))/(s1 - s2)

Given that you have two unknowns in this equation (x1 and x2), you cannot calculate k.
member
Activity: 69
Merit: 53
Hello
Its possible if you know K of that R Or if you know one of private key.
member
Activity: 194
Merit: 14
Hi,

Suppose i have 2 same r values from different addresses/privatekeys.

Would it be possible to calculate private key for both of the addresses from the same r values?

Or its only possible when the same private key has done 2 different transaction but used the same r values?

I hope my question was clear und understandable
Jump to: