1
$\begingroup$

If I have a 256bit ECDSA public key how likely is it that the same public key will be generated by another person. Will it take on average 2^256 tries to generate same public key? If I xor the first 32bytes of the public key over the second 32bytes and only have 32bytes is it now 2^128 tries to generate the same 32byte data? Or less? Thanks

$\endgroup$
  • $\begingroup$ Why the heck would you want to XOR the X coordinate over the Y coordinate? $\endgroup$ – Maarten Bodewes Feb 24 '15 at 18:29
  • $\begingroup$ For your understanding: the EC public key consists of a point on the curve ($Q$ or $W$), generated by the scalar used for the private key multiplied with the generator $G$. It is normally represented uncompressed, so it's then 65 bytes (04 for uncompressed point, then $X$, then $Y$). The encoded public key - even without the parameters - is then 1 + twice the key size. 64 bytes is 512 bits, 32 bytes is 256 bits - maybe you are miscalculating? $\endgroup$ – Maarten Bodewes Feb 24 '15 at 18:47
  • $\begingroup$ XORING the the X and Y component is merely to compress the key to later verify it against a full 64 byte key. $\endgroup$ – Harry Feb 25 '15 at 0:45
  • $\begingroup$ What about using point compression? It can be used to compress points. If you just want to verify you could also take a cryptographic hash (and use the leftmost x bits (using 4 bytes as the absolute minimum, 8 bytes should be preferred) $\endgroup$ – Maarten Bodewes Feb 25 '15 at 0:57
3
$\begingroup$

ECC public keys are not random numbers.

They are generated through a scalar multiplication of a random scalar with a known/public point on the curve, called Generator.

The entropy lies entirely in the random scalar. Two public keys will collide if the random scalars collide.

When you say "256bit ECDSA public key" you probably mean that your elliptic curve curve is defined over a finite field whose size is approximatively $2^{256}$. This would explain why you are mentioning a public key of 64 bytes in your question.

Now, in cryptographic secure elliptic curves, that size is closely related to the size of order of the generator, which is actually the size of your random scalar.

Therefore, without knowing the exact curve you are using I can't exactly answer the question. But approximatively the expected probability is: $\frac1{2^{256}}$

This has nothing to do with the encoding, so xoring the key over itself doesn't really make sense to me, or I didn't understand it.

$\endgroup$
-1
$\begingroup$

Well to start of, great question it really got me thinking. unfortunately I cannot give you an exact answer but i can tell you the chances of getting the same public key as someone else is negligible. If the chance would have been anything but negligible the whole system would collapse since and attacker would have just as much chance of getting your key then.

so i don't think you should worry about this, but that is my opinion. also an interesting read is this paper about Key-collisions in (EC)DSA, it is about how there is no algorithm (currently) which can search and create key collisions. Well that's the jest of it anyway. unless the discrete logarithm problem (DLP) gets solved we're safe ;)

I hope this helped.

also check this question and answer on security.stackexhange.com It's for an ssh key but the math is similar and the chances about the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.