7

Is it possibly to test if an Ed25519 public key is valid without having access to the private key, a signed message or anything except the public key?

"Valid" as in "Not just 32 random bytes".

I'm assuming not every random combination of bits would be possible to generate as a public key.

Peter Mortensen
  • 877
  • 5
  • 10
Martijn
  • 205
  • 1
  • 7

1 Answers1

8

Yes. In order for the public key to be valid (i.e. not just 32 random bytes), the point must be on the curve. You can test if the point is on the curve by plugging the x and y values into the equation of the curve, and solving the equation 'over the field', to see if the equation checks.

For example, the equation for the secp256k1 curve is:

 y^2 = x^3 + 7

and the field characteristic (p) is:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

So, to check if a point is on the curve, you would plug the x and y values of the point into the following equation, and test if it checks:

(y^2 - x^3 - 7) % p == 0

The following point is on the secp256k1 curve:

(0x5633454c810b6e3c881e35f904a6215f1825e46429a54061d1b7448be1b4285e, 0xd1016a4e4b8c6d3a2220e76c8cd66d0ad8e42c1ea84109fef12fa601b5dd09b8)

But, the following point is not:

(0x2d09f894eff47eba35ae4eda6ecfe71fb8263b84c092249e820ba5e6e73c0da3, 0x19ece9e391ce286cbb1907c38359dd4c086e5540fc82593731a2f893ef1bedef)

Here is a short Python script that can be used to test whether a point is on the curve.

def isoncurve(x, y):
    # For secp256k1
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
    return (y * y - x * x * x - 7) % p == 0

#returns True
x=0x5633454c810b6e3c881e35f904a6215f1825e46429a54061d1b7448be1b4285e
y=0xd1016a4e4b8c6d3a2220e76c8cd66d0ad8e42c1ea84109fef12fa601b5dd09b8
print (hex(x) + ',' + hex(y) + ' is on secp256k1 curve: ' + str(isoncurve(x, y)))

# Returns False
x=0x2d09f894eff47eba35ae4eda6ecfe71fb8263b84c092249e820ba5e6e73c0da3
y=0x19ece9e391ce286cbb1907c38359dd4c086e5540fc82593731a2f893ef1bedef
print (hex(x) + ',' + hex(y) + ' is on secp256k1 curve: ' + str(isoncurve(x, y)))
Peter Mortensen
  • 877
  • 5
  • 10
mti2935
  • 19,868
  • 2
  • 45
  • 64
  • 1
    Do you know of a practical way to feed a public key to a program and retrieve a result? Ideally with existing tools? Curious to know as I don't think I'd be able to implement this. – Pedro Jun 11 '20 at 14:29
  • 1
    Hi @Pedro. I edited my answer to include a short python script that can be used to test whether a point is on a curve. – mti2935 Jun 11 '20 at 15:01
  • 2
    Awesome, but this script is only for telling if it is a point on the secp256k1 curve, right? I suppose we could replace the modulo equation with the appropriate one for another curve. Because for ed25519, I believe it is using a *different* elliptic curve than secp256k1. – auspicious99 Jun 11 '20 at 15:14
  • @auspicious99 Yes, that's correct. I just used secp256k1 as an example. For other curves, you would have to modify the equation and the value for p in the function. You can find these at https://safecurves.cr.yp.to/equation.html and https://safecurves.cr.yp.to/field.html. I believe ed25519 is actually an EC digital signature algorithm, not an EC curve. – mti2935 Jun 11 '20 at 15:20
  • 1
    @mti2935 cool, thanks, something fun to try this weekend :-) – auspicious99 Jun 11 '20 at 15:22
  • 1
    @auspicious99 sounds like a fun time. Check out https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/ and https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdhe.py for more cool stuff that you can do with EC curves and points using python. – mti2935 Jun 11 '20 at 16:03
  • What is the probability of a false negative (for a correct key)? What is the probability of a false positive (for a corrupt key)? Are they both 0%? – Peter Mortensen Jun 11 '20 at 19:26
  • @PeterMortensen Normally, an EC public key is the product of the private key (which is a 32-byte randomly choosen integer) and the generator point (which is standard). It's possible that the given point may be a point on the curve, but not a multiple of the generator point. So in this case, the given point would not be a valid public key. But, there would be no way of checking this, without knowledge of the private key. The best you can do, given a point that is purported to be a public key, is to check that the point is on the curve. – mti2935 Jun 11 '20 at 20:58