ECC
Elliptic Curve Cryptography
Elliptic Curve
An elliptic curve is a plane curve defined by an equation of the form:
after a linear change of variables ( and are real numbers). This type of equation is called a Weierstrass equation.
The definition of elliptic curve also requires that the curve is non-singular. Geometrically, this means that the graph has no cusps, self-intersections, or isolated points. Algebraically, this holds if and only if the discriminant:
is not equal to zero. (Although the factor โ16 is irrelevant to whether or not the curve is non-singular, this definition of the discriminant is useful in a more advanced study of elliptic curves.)
The (real) graph of a non-singular curve has two components if its discriminant is positive, and one component if it is negative. For example, in the graphs shown in figure below, the discriminant in the first case is 64, and in the second case is โ368:

Arithmetics on Elliptic Curves
Point Negation
Algorithm
The rule is: if , then . In other word, .
Implementation
In this challenge we are given , hence
Point Addition
Algorithm
If , then .
Otherwise, if , then .
Otherwise, write and .
If and , then .
Otherwise:
if :
if :
and
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse
#--------Data--------#
a = 497
b = 1768
p = 9739
P = (493, 5564)
Q = (1539, 4742)
R = (4403,5202)
#--------Addition--------#
def point_addition(P, Q):
# Define zero
O = (0, 0)
# If P = O, then P + Q = Q
if P == O:
return Q
# If Q = O, then P + Q = P
if Q == O:
return P
# Otherwise, write P = (x1, y1) and Q = (x2, y2)
x1, y1 = P[0], P[1]
x2, y2 = Q[0], Q[1]
# If x1 = x2 and y1 = -y2, then P + Q = O
if x1 == x2 and y1 == -y2:
return O
# Otherwise, if P โ Q: ฮป = (y2 - y1) / (x2 - x1)
if P != Q:
lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
# If P = Q: ฮป = (3 * x1**2 + a) / 2 * y1
else:
lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p
# x3 = ฮป**2 - x1 - x2, y3 = ฮป *( x1 - x3) - y1
x3 = (lam**2 - x1 - x2) % p
y3 = (lam * (x1 - x3) - y1) % p
# P + Q = (x3, y3)
summation = (x3, y3)
return summation
#--------Testing--------#
# X = (5274, 2841)
# Y = (8669, 740)
# print(point_addition(X, Y))
# print(point_addition(X, X))
# S = P + P + Q + R
S = point_addition(point_addition(point_addition(P, P), Q), R)
print(S)
Scalar Multiplication
Algorithm
Input: in and an integer .
Set and .
Loop while .
If , set .
Set and .
If , continue with loop at Step 2.
Return the point , which equals .
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse
#--------Data--------#
a = 497
b = 1768
p = 9739
P = (2339, 2213)
#--------Functions--------#
def point_addition(P, Q):
# Define zero
O = (0, 0)
# If P = O, then P + Q = Q
if P == O:
return Q
# If Q = O, then P + Q = P
if Q == O:
return P
# Otherwise, write P = (x1, y1) and Q = (x2, y2)
x1, y1 = P[0], P[1]
x2, y2 = Q[0], Q[1]
# If x1 = x2 and y1 = -y2, then P + Q = O
if x1 == x2 and y1 == -y2:
return O
# Otherwise, if P โ Q: ฮป = (y2 - y1) / (x2 - x1)
if P != Q:
lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
# If P = Q: ฮป = (3 * x1**2 + a) / 2 * y1
else:
lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p
# x3 = ฮป**2 - x1 - x2, y3 = ฮป *( x1 - x3) - y1
x3 = (lam**2 - x1 - x2) % p
y3 = (lam * (x1 - x3) - y1) % p
# P + Q = (x3, y3)
summation = (x3, y3)
return summation
def scalar_multiplication(n, P):
# Define zero
O = (0, 0)
# Set Q = P and R = O
Q, R = P, O
while n > 0:
# If n โก 1 mod 2, set R = R + Q
if n % 2 == 1:
R = point_addition(R, Q)
# Set Q = 2 Q and n = โn/2โ.
Q = point_addition(Q, Q)
n //= 2
return R
#--------Testing--------#
# X = (5323, 5438)
# print(scalar_multiplication(1337, X))
# Q = 7863 P
print(scalar_multiplication(7863, P))
Curves and Logs
Algorithm
Alice and Bob agree on a curve , a prime and a generator point .
Alice generates a secret random integer and calculates .
Bob generates a secret random integer and calculates .
Alice sends Bob , and Bob sends Alice $$Q_B$$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate in reasonable time.
Alice then calculates , and Bob calculates .
Due to the associativity of scalar multiplication, . Alice and Bob can use as their shared secret.
Implementation
#!/usr/bin/env python3
from Crypto.Util.number import inverse
from hashlib import sha1
#--------Data--------#
a = 497
b = 1768
p = 9739
G = (1804,5368)
Q_A = (815, 3190)
n_B = 1829
#--------Functions--------#
def point_addition(P, Q):
# Define zero
O = (0, 0)
# If P = O, then P + Q = Q
if P == O:
return Q
# If Q = O, then P + Q = P
if Q == O:
return P
# Otherwise, write P = (x1, y1) and Q = (x2, y2)
x1, y1 = P[0], P[1]
x2, y2 = Q[0], Q[1]
# If x1 = x2 and y1 = -y2, then P + Q = O
if x1 == x2 and y1 == -y2:
return O
# Otherwise, if P โ Q: ฮป = (y2 - y1) / (x2 - x1)
if P != Q:
lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
# If P = Q: ฮป = (3 * x1**2 + a) / 2 * y1
else:
lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p
# x3 = ฮป**2 - x1 - x2, y3 = ฮป *( x1 - x3) - y1
x3 = (lam**2 - x1 - x2) % p
y3 = (lam * (x1 - x3) - y1) % p
# P + Q = (x3, y3)
summation = (x3, y3)
return summation
def scalar_multiplication(n, P):
# Define zero
O = (0, 0)
# Set Q = P and R = O
Q, R = P, O
# Loop while n > 0
while n > 0:
# If n โก 1 mod 2, set R = R + Q
if n % 2 == 1:
R = point_addition(R, Q)
# Set Q = 2 Q and n = โn/2โ.
Q = point_addition(Q, Q)
n //= 2
return R
#--------ECDH--------#
S = scalar_multiplication(n_B, Q_A)
key = sha1(str(S[0]).encode()).hexdigest()
print(key)
Lab
Reference
Last updated
Was this helpful?