[Back] Several methods involve taking a random value and then matching it to a point on an elliptic curve. The curve used is \(y^2 = x^3+7\) and we use a given prime number (\(p\)):
Simple Hash to ECC
We can implement the 'Try-and-Increment' method, and where we basically increment a value until we find a matching (x,y) point.
An example is:
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^3+7 \pmod 149\) and which is equal to 1. In Python we can check with:
>>> print (26**3 + 7) % 149 1
And another one:
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^3+7 \pmod 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 , 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) if (len(sys.argv)>2): p=int(sys.argv) 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)
Other methods include the Icard method  and Elligator .
 Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. J. Cryptology, 17(4):297–319, 2004
 Icart, Thomas. "How to hash into elliptic curves." Advances in Cryptology-CRYPTO 2009. Springer, Berlin, Heidelberg, 2009. 303–316.
 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.