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 point closes to: 10 Prime number: 149 Closest point is: (10, 115)
We can check with \(10^3+7 \pmod {149}\) and which is equal to \(155 \times 155 \pmod{149}\). In Python we can check with:
>>> print ((10**3 + 7)% 149) 113 >>> print ((115*115)% 149) 113
And another one:
Elliptic curve is: y^2=x^3+7 Finding elliptic point closes to: 10 Prime number: 37 Closest point is: (12, 12)
We can check with \(12^3+7 \pmod {37}\) and which is equal to \(12 \times 12 \pmod{37}\). In Python we can check with
>>> print ((12**3 + 7)% 37) 33 >>> print ((12*12)% 37) 33
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:
import sys import libnum p=53 startval=11 if (len(sys.argv)>1): startval=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) def findit(start,p): x=start while (True): y_2=x**3+7 if (libnum.has_sqrtmod(y_2,{p:1} )): y=next(libnum.sqrtmod(y_2,{p:1})) return(x,y) x=x+1 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.