Simple Hash to ECC[Hashing Home][Home]
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\)):
|
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: (10,34)
We can check with \(10^3+7 \pmod {149}\) and which is equal to 113. In Python we can check with:
>>> print (34**2) % 149 113
and closest to \(x=11\):
Elliptic curve is: y^2=x^3+7 Finding elliptic point closes to: 11 Prime number: 149 Closest point is: 12 29
We can check with \(12^3+7 \pmod {149}\) and which is equal to 96. In Python we can check with:
>>> print (34**2) % 149 96
And here is \(p=2^{255}-19\) for the closet point to \(x=15\):
Elliptic curve is: y^2=x^3+7 Finding elliptic point closes to: 15 Prime number: 57896044618658097711785492504343953926634992332820282019728792003956564819949 Closest point is (18, 44896790295197716018270078918719734963186459585283064676699513485587012850919)
We can check with \(19^3+7 \pmod {57896044618658097711785492504343953926634992332820282019728792003956564819949}\) and which is equal to 5839. In Python we can check with:
>>> print (44896790295197716018270078918719734963186459585283064676699513485587012850919**2) % 57896044618658097711785492504343953926634992332820282019728792003956564819949 5839
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 libnum import sys p=101 x=1 if (len(sys.argv)>1): x=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) y_2=x**3+7 print("Elliptic curve is:\t\ty^2=x^3+7") print("Finding elliptic point closes to:\t",x) print("Prime number:\t\t\t",p) while (True): if (libnum.has_sqrtmod(y_2,{p:1} )): y=next(libnum.sqrtmod(y_2,{p:1})) break x=x+1 y_2=x**3+7 print("Closest point is:\t\t",x,y)
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.