Image for post
Image for post

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.

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

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store