Bitcoin Forum

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

Hello
Its possible if you know K of that R Or if you know one of private key.

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:

s₁ = (z₁ + x*r)/k
s₂ = (z₂ + x*r)/k

This can be reformatted as:

k = (z₁ - z₂)/(s₁ - s₂)

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:

s₁ = (z₁ + x₁*r)/k
s₂ = (z₂ + x₂*r)/k

Reformat that, and you end up with the following:

k = ((z₁ - z₂) + r(x₁ - x₂))/(s₁ - s₂)

Given that you have two unknowns in this equation (x₁ and x₂), you cannot calculate k.

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!  :-*

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.
 

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.

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.

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.

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.

If you use any HD wallet, then your keys are generated in some deterministic way. That means, in practice, you only have a single key, called master key. Everything is derived from that, which means, all keys are related. If someone will break that single key, then all of them will be also broken. If you want another confirmation, then read that sentence in this context:

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.
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.

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.

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.  ;D

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.  ::)