Am 28.04.2015 um 04:11 schrieb JF Jobidon: > OK Thanks again > > I just realize that there are 2 points with x = 17: > 7 * G = (17,9) > and > 24*g = (17,20) > And for the exemple in http://www.royalforkblog.com/2014/09/04/ecc/ > the point I was looking for is (17,9)!!! > > My goal is to verify a signature in a bitcoin transaction. > I need a public Key which is a point on the elliptic curve: > pubKeyPoint = privateKey * G = (X, Y) > where G is the generator point. > In a transaction we can find X and Y but sometimes only X. > Same for the ramdom number. In order to sign a transaction > the user pick a random number RN and compute RN * G = (RNx, RNy). > Only RNx is given in a transaction. In order to verify the validity of > a signature, > I must find Y and RNy. I don't see other way to do it. > In this case p is very large: is there a non-negligible risk of collision > like (17,9) and (17,20) ? I'd say the probability of such a collision is in fact 1. With the algorithm I gave you you'll get a positive and a negative square-root for the y-coordinates. (17,20) would correspond to the positive square root. (17,9) would correspond to the negative square root (-20 = 29-20 = 9 (mod 29)). You can do the exact same thing with basically any field-element, so you'll (always) get two non-negative square roots and hence get a "collision". In order to find the correct point you'll need an extra bit of information (telling you whether to use positive or negative square root) which might be encoded in a clever way, so the documentation for Bitcoin for this.
BR JPM > -- > -- > You received this message because you are subscribed to the "Crypto++ > Users" Google Group. > To unsubscribe, send an email to > [email protected]. > More information about Crypto++ and this group is available at > http://www.cryptopp.com. > --- > You received this message because you are subscribed to the Google > Groups "Crypto++ Users" group. > To unsubscribe from this group and stop receiving emails from it, send > an email to [email protected] > <mailto:[email protected]>. > For more options, visit https://groups.google.com/d/optout. -- -- You received this message because you are subscribed to the "Crypto++ Users" Google Group. To unsubscribe, send an email to [email protected]. More information about Crypto++ and this group is available at http://www.cryptopp.com. --- You received this message because you are subscribed to the Google Groups "Crypto++ Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
smime.p7s
Description: S/MIME Cryptographic Signature
