Search content
Sort by
Showing 18 of 18 results by Yves Cuicui
This just to finalize this topic.
Because P=9xu+7, if a cubic root exists it can be computed by r1=a^((P+2)/9).
The other two solutions are:
r2=0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c . r1
r3=0x1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c555554e9 . r1
Then it is easy to see that -7 has no cubic root because ((-7)^((P+2)/9))^3 <> -7
Then there is no points with y=0
my 2 cents
Thanks to you all
Because P=9xu+7, if a cubic root exists it can be computed by r1=a^((P+2)/9).
The other two solutions are:
r2=0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c . r1
r3=0x1c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c71c555554e9 . r1
Then it is easy to see that -7 has no cubic root because ((-7)^((P+2)/9))^3 <> -7
Then there is no points with y=0
my 2 cents
Thanks to you all
K=secret-key is no more a special value than K=11 (or 12 or 13 or any other specific value)
Agreed, but the difference is that to recognize values k=11, 12 ... you need a lookup table on the r value that does not worth it! Checking r=Qx is at no cost!Once again this thread has nothing to do with RNG.
It is just a special case, very easy to detect, more or less as probable (or improbable) as other tests that are performed in the signing process.
So why not?
It is just a special case, very easy to detect, more or less as probable (or improbable) as other tests that are performed in the signing process.
So why not?
the way for the attacker to check if you actually did the mistake, is by computing: d = z(s-r)-1
No just to see if r equals the x coordinate of the public key.
Quote
You're describing how to carry out one particular attack that succeeds with probability 2^{-n}
I know this will succeed with a {very low}^N probability, but this is of the same order as checking r<>0 or s<>0 (for example, r=0 only for the two points with x=N).Quote
For example, with OpenSSL it would force you to add your own K generation conversion to R and Rinv
I am not aware of the OpenSSL modules. I imagine this test could be integrated in it.Quote
You might as well just deny K=11, since if they used 11 (or any other specific value) and you know it you could recover the private key too.
Are you kidding me? Using k=d is made obvious by the fact that r=Qx. Using 11 or whatever cannot be guessed.The subject is not that RNG are broken or bugged or ... I just want to draw attention to a situation on which nobody thinks
When a signature is generated, there are a number of things to check, for example, the parameter k must be between 1 and N-1, the r and s signature must not be null etc ...
There is another condition (I have never seen), even if the probability is extremely low: k must not be equal to the private key d.
If k is equal to d, the private key can be calculated by d = z(s-r)-1 (z is the reduced message hash)!
This case is very easy to detect. Indeed, if k == d, r is the x coordinate of the public key!
Although this case is very unlikely, it costs nothing to add this test in the module signature;
Here is an example:
Public key
Q: "0x02f24fb983ba6825277b09fabbf60afe833ebf03f0bb808cab04ccbfb81593d835" (compressed)
Message Hash
z: "0x8d29467f53b7a412dc54de9a8eeb8960821d191568f5e22f64806326a5e11f20"
Signature
r: "0xf24fb983ba6825277b09fabbf60afe833ebf03f0bb808cab04ccbfb81593d835"
s: "0x24f080f53a8384be1e3263aeabc48df6569286f29a7141baf43d8723988eb558"
You can effectively see that r==Qx. This indicates that k==d!
It is then easy to get the private key "0x26439421bbfcf3c81d8ab8cda150d6e2e280d1656e70d8e49e18acf5ae0f11df" and compute Q from it to be convinced that this is the correct value.
There is another condition (I have never seen), even if the probability is extremely low: k must not be equal to the private key d.
If k is equal to d, the private key can be calculated by d = z(s-r)-1 (z is the reduced message hash)!
This case is very easy to detect. Indeed, if k == d, r is the x coordinate of the public key!
Although this case is very unlikely, it costs nothing to add this test in the module signature;
Here is an example:
Public key
Q: "0x02f24fb983ba6825277b09fabbf60afe833ebf03f0bb808cab04ccbfb81593d835" (compressed)
Message Hash
z: "0x8d29467f53b7a412dc54de9a8eeb8960821d191568f5e22f64806326a5e11f20"
Signature
r: "0xf24fb983ba6825277b09fabbf60afe833ebf03f0bb808cab04ccbfb81593d835"
s: "0x24f080f53a8384be1e3263aeabc48df6569286f29a7141baf43d8723988eb558"
You can effectively see that r==Qx. This indicates that k==d!
It is then easy to get the private key "0x26439421bbfcf3c81d8ab8cda150d6e2e280d1656e70d8e49e18acf5ae0f11df" and compute Q from it to be convinced that this is the correct value.
In my opinion, before going further, we must request the opinion of security experts.
I am not an expert, but introducing a new relation in the set of the DSA equations is just a weakening of the security.
I am not an expert, but introducing a new relation in the set of the DSA equations is just a weakening of the security.
Anyway, this is not an information we can rely on.
I notice many blocks pretending to be version 2 but showing bad height encode values
See
http://blockexplorer.com/block/00000000000005d024e86337ca13439b7f3dbd5e1a005b1dbe510150d45b6e98 is block 200433 and pretends to be 436591499
http://blockexplorer.com/block/00000000000003c6947e260dc80d6ab426771a7ba9d8d5fb58ff66a0db26c361 is block 199914and pretends to be 436591499
May be such blocks must not be accepted by the network as the BIP34 is now enforced?
I notice many blocks pretending to be version 2 but showing bad height encode values
See
http://blockexplorer.com/block/00000000000005d024e86337ca13439b7f3dbd5e1a005b1dbe510150d45b6e98 is block 200433 and pretends to be 436591499
http://blockexplorer.com/block/00000000000003c6947e260dc80d6ab426771a7ba9d8d5fb58ff66a0db26c361 is block 199914and pretends to be 436591499
May be such blocks must not be accepted by the network as the BIP34 is now enforced?
Thanks for these ideas. I will dig in.
As N is odd and all points are duals (x,y) and (x,-y), there is at least one point (x,0), so you must get one.
Quote
I used the code listed here to solve your particular example. It returns None, so probably there isn't an x that solves the equation when y is 0.
As N is odd and all points are duals (x,y) and (x,-y), there is at least one point (x,0), so you must get one.
Given the x coordinate of a point on the EC curve, it's easy to compute one of the y coordinate.
But, given y, how can we get x? In particular does someone know a solution to x^3+7 = 0 on the secp256k1 curve?
Thanks
But, given y, how can we get x? In particular does someone know a solution to x^3+7 = 0 on the secp256k1 curve?
Thanks
The Bitcoin protocol changes from time to time and it is not easy to know what is the latest version and what are the changes.
BIP and the change log of the official client are a good source, but it is difficult thing to navigate because the life cycle is different.
Unless I am mistaken the latest version is 70001? Right?
Is there a change log available for the Bitcoin protocol?
BIP and the change log of the official client are a good source, but it is difficult thing to navigate because the life cycle is different.
Unless I am mistaken the latest version is 70001? Right?
Is there a change log available for the Bitcoin protocol?