Matching a Value To An Elliptic Curve Point

Matching a Value To An Elliptic Curve Point

Elliptic Curve Cryptography (ECC) is taking over in the world of cryptography, and you will see it in Tor, Bitcoin, Ethereum, IoT, and in many other places where public key is used. Normally we use ECC to sign for things (with ECDSA) and also to create shared keys (with ECDH). So, if we need to apply a piece of data onto our elliptic curve, how would we match it?

Within ECC, we take a point on the elliptic curve (G) and then can multiply it by a scalar (priv). The public key point is then priv multiplied by G. At the current time, if the scalar (priv) is a large number, it will not be possible to determine the value of priv, even if we know the public key and the G points:

In many applications we will take a value and then hash it. Then we must fit the hashed value onto an elliptic curve point (such as with the Schnorr signature). Obviously we need integer values for the x,y points, so we need to find an x,y point which has integer values for both x and y. So let’s take a common elliptic curve:

y² =x³ +7

and we will define a finite field of p (which is a prime number). All our points will then be between 0 and p-1.

An example is [here]:

Elliptic curve is:		y^2=x^3+7
Finding elliptic closest to:	10
Prime number:			149

Closest point is:		(26, 1)

We can check with 26³+7 (mod 149) and which is equal to 1. In Python we can check with:

>>> print (26**3 + 7) % 149
1

Another example is [here]:

Elliptic curve is:		y^2=x^3+7
Finding elliptic closest to:	10
Prime number:			37

Closest point is:		(17, 6)

We can check with 17³+7 (mod 37) and which is equal to 36 (of which the square root is 6). In Python we can check with:

>>> print (17**3 + 7) % 37
36

The method we have used was defined by Boneh et al in 2004 [1], and uses the ‘Try and Increment’ method. With this the code just increments the x value until we find a value of y which is an integer, and uses a residue value of 0.0001:

import math
import sys

p=101
startval=1

if (len(sys.argv)>1):
	startval=int(sys.argv[1])

if (len(sys.argv)>2):
	p=int(sys.argv[2])

def findit(start,p):
	for x in range(start,p):
		val=((x*x*x) + 7) % p
		res = math.sqrt(val)

		if (abs(res-int(res))<0.0001):
			return(x,int(res))

print "Elliptic curve is:\t\ty^2=x^3+7"
print "Finding elliptic point closes to:\t",startval
print "Prime number:\t\t\t",p
print
print "Closest point is:\t\t",findit(startval,p)

If a real-life example, such as with the P-256 curve, the finite field value is:

p = 115792089210356248762697446949407573530086143415290314195533631308 867097853951

Other methods include the Icard method [2], the Shallue-Woestijne-Ulas method, and the Elligator method [3]. I will outline these in a future article. I’ll also outline the methods with real hash values and a real elliptic curve.

References

[1] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. J. Cryptology, 17(4):297–319, 2004. [Link]

[2] Icart, Thomas. “How to hash into elliptic curves.” Advances in Cryptology-CRYPTO 2009. Springer, Berlin, Heidelberg, 2009. 303–316. [Link]

[3] Bernstein, Daniel J., et al. “Elligator: Elliptic-curve points indistinguishable from uniform random strings.” Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. ACM, 2013.