One of the greatest contributions to computer security: Adding Points on an Elliptic Curve
One of the greatest contributions to computer security: Adding Points on an Elliptic Curve
Respecting nP
Beauty is all around us. In nature, and even within the security of our Internet connections. Every single time that you connect to the Internet, there’s a bit of magic that goes on, and it is beautiful in its simplicity, but also in protecting you from others who wish to spy on you.
Your computer generates a random number, and then takes a point on an elliptic curve, and a prime number, and then adds that point to itself, with the number of times that you have generated. Next, you pass that to the server — and who has also done the same thing — and then you take the value received, and then, again, add it to itself by the number your generated. And in the end, both you and the server has the same value. This is now your encryption key, and only you and the server will know it. That is the magic of the ECDH (Elliptic Curve Diffie Hellman) method:
And Elliptic Curve Cryptography (ECC) is also used to create a public key and a private key, and where we can digitally sign for things, and to create your online identity. I will first define the core of ECC:
- If we add two points on the elliptic curve we ALWAYS get another point on the curve.
- We will always get a unique point for a given x value (within the range of prime number N).
- If we have the result of a point addition, it is difficult to find the original points that we added.
At the core is an equation which has the format of y²=x³ +ax + b(mod N), and where N is a prime number. If we take a=0, b=7 and N=37, we get y²=x³ +7 (mod 37). Plotting with real numbers we a beautiful plot of [here]:
In cryptography, we only deal with integers, so we are only interested in values which result in integers for both x and y. But not all the values for x will give us an integer value of y. For example, if x=1, then y²=1 (mod 37), of which there is no possible value for y (as there is no square root for 38 — and its multiples — that will give an integer). But if x=3, we get 3³+7=34, and where 16³ (mod 37) = 34. The graph is here.
For the first 20 points we now have: (3, 16) (4, 16) (5, 13) (6, 1) (8, 1) (9, 12) (12, 12) (13, 13) (16, 12) (17, 6) (18, 17) (19, 13) (22, 6) (23, 1) (24, 17) (30, 16) (32, 17) (35, 6) [here].
With ECC, if we have a point on the curve, and then add another point, we will always get another point on the curve. It is this property that allows ECC to implement cryptography.
So, let’s try one point, and calculate the addition to it with all the other points. If (x1,y1) is not equal to (x2,y2), to two points (x1,y1) and (x2,y2), we use:
Let s=(y1−y2)/(x1−x2)
Then:
x2=s²−x1−x2
y2=s(x1−x2)−y1
If they are the same point (x1,y1), we use:
s=((3*x1²)+a) /(2*y1,p)
x2=(s²–2*x1)
y2=((s(x1-x2))-y1)
Here is a program to implement this [here]:
import sysa=0
b=7
p=37x1=6
x2=8if (len(sys.argv)>1):
x1=int(sys.argv[1])
if (len(sys.argv)>2):
p=int(sys.argv[2])
if (len(sys.argv)>3):
a=int(sys.argv[3])
if (len(sys.argv)>4):
b=int(sys.argv[4])
if (len(sys.argv)>5):
n=int(sys.argv[5])
def modular_sqrt(a, p):
""" Find a quadratic residue (mod p) of 'a'. p
must be an odd prime. Solve the congruence of the form:
x^2 = a (mod p)
And returns x. Note that p - x is also a root. 0 is returned is no square root exists for
these a and p. The Tonelli-Shanks algorithm is used (except
for some simple cases in which the solution
is known from an identity). This algorithm
runs in polynomial time (unless the
generalized Riemann hypothesis is false).
"""
# Simple cases
#
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return p
elif p % 4 == 3:
return pow(a, (p + 1) / 4, p) # Partition p-1 to s * 2^e for an odd s (i.e.
# reduce all the powers of 2 from p-1)
#
s = p - 1
e = 0
while s % 2 == 0:
s /= 2
e += 1 # Find some 'n' with a legendre symbol n|p = -1.
# Shouldn't take long.
#
n = 2
while legendre_symbol(n, p) != -1:
n += 1 # Here be dragons!
# Read the paper "Square roots from 1; 24, 51,
# 10 to Dan Shanks" by Ezra Brown for more
# information
# # x is a guess of the square root that gets better
# with each iteration.
# b is the "fudge factor" - by how much we're off
# with the guess. The invariant x^2 = ab (mod p)
# is maintained throughout the loop.
# g is used for successive powers of n to update
# both a and b
# r is the exponent - decreases with each update
#
x = pow(a, (s + 1) / 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e while True:
t = b
m = 0
for m in xrange(r):
if t == 1:
break
t = pow(t, 2, p) if m == 0:
return x gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
def legendre_symbol(a, p):
""" Compute the Legendre symbol a|p using
Euler's criterion. p is a prime, a is
relatively prime to p (if p divides
a, then a|p = 0) Returns 1 if a has a square root modulo
p, -1 otherwise.
"""
ls = pow(a, (p - 1) / 2, p)
return -1 if ls == p - 1 else lsdef egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)def modinv(a, m):
a=a%p
g, x, y = egcd(a, m)
if g != 1:
print "x-point is not on the curve. Please select another point. No solution for %d (mod %d)" % (a,m)
sys.exit()
else:
return x % mprint "a=",a
print "b=",b
print "p=",pprint "x-point=",x1
z=(x1**3 + a*x1 +b) % p
y1=modular_sqrt(z, p)
if (y1==0):
print "No solution for y1 on curve. Please select another x-point."
sys.exit()for x2 in range(2,p-1):
z=(x2**3 + a*x2 +b) % p
y2=modular_sqrt(z, p)
if (y2!=0 and x1!=x2):
print "P1=(%d,%d)" % (x1,y1),
print "\tP2=(%d,%d)" % (x2,y2), s=(y2-y1)* modinv(x2-x1,p) x3=(s**2-x2-x1) % p y3=((s*(x2-x3)-y2)) % p print "\tP1+P2=(%d,%d)" % (x3,y3)
if (x2>100): sys.exit()
And a sample run for a point (6,1) [here] is:
a= 0
b= 7
p= 37
x-point= 6
P1=(6,1) P2=(3,16) P1+P2=(16,12)
P1=(6,1) P2=(4,16) P1+P2=(0,28)
P1=(6,1) P2=(5,13) P1+P2=(22,6)
P1=(6,1) P2=(6,1) P1+P2=(18,17)
P1=(6,1) P2=(8,1) P1+P2=(23,36)
P1=(6,1) P2=(9,12) P1+P2=(19,13)
P1=(6,1) P2=(12,12) P1+P2=(9,12)
P1=(6,1) P2=(13,13) P1+P2=(30,16)
P1=(6,1) P2=(16,12) P1+P2=(4,16)
P1=(6,1) P2=(17,6) P1+P2=(35,6)
P1=(6,1) P2=(18,17) P1+P2=(23,1)
P1=(6,1) P2=(19,13) P1+P2=(3,16)
P1=(6,1) P2=(22,6) P1+P2=(13,13)
P1=(6,1) P2=(23,1) P1+P2=(8,36)
P1=(6,1) P2=(24,17) P1+P2=(32,17)
P1=(6,1) P2=(30,16) P1+P2=(17,6)
P1=(6,1) P2=(32,17) P1+P2=(32,20)
P1=(6,1) P2=(35,6) P1+P2=(12,12)
In this case we see the 2P is (18,17). We can also see that a point is generated for each addition so that if we add two points on the elliptic curve we always get a point on the curve.
Conclusions
There we go. Take a point on the curve, and add it to itself, and you get another point on the curve. Take two points, too, and add them, and you get another point on the curve. Magic!