[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 |

## Sample

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 [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)

Other methods include the Icard method [2] and Elligator [3].

## Reference

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

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

[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.