ECC
Elliptic Curve Cryptography

# Elliptic Curve

An elliptic curve is a plane curve defined by an equation of the form:
$y^{2}=x^{3}+ax+b$
after a linear change of variables (
$a$
and
$b$
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:
$\Delta =-16(4a^{3}+27b^{2})$
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:
Graphs of curves y^2 = x^3 − x and y^2 = x^3 − x + 1

# Arithmetics on Elliptic Curves

CryptoHack – Elliptic Curves challenges
CryptoHack
Elliptic Curves - CryptoHack

## Point Negation

### Algorithm

The rule is: if
$P = (x_P,y_P)$
, then
$P + (x_P, x_P+y_P) = O$
. In other word,
$-P = (x_P, x_P+y_P)$
.

### Implementation

In this challenge we are given
$P = (8045, 6936)$
, hence
$Q = -P = (8045, (8045 + 6936) \mod 9739) = (8045, 2803)$

### Algorithm

1. 1.
If
$P = O$
, then
$P + Q = Q$
.
2. 2.
Otherwise, if
$Q = O$
, then
$P + Q = P$
.
3. 3.
Otherwise, write
$P = (x_1, y_1)$
and
$Q = (x_2, y_2)$
.
4. 4.
If
$x_1 = x_2$
and
$y_1 = −y_2$
, then
$P + Q = O$
.
5. 5.
Otherwise:
• if
$P \neq Q$
:
$\lambda = (y_2 - y_1) / (x_2 - x_1)$
• if
$P = Q$
:
$\lambda = (3x_1^2 + a) / 2y_1$
6. 6.
$x_3 = \lambda_2 − x_1 − x2$
and
$y_3 = \lambda(x_1 − x_3) − y_1$
7. 7.
$P + Q = (x_3, y_3)$

### Implementation

1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse
3
4
#--------Data--------#
5
6
a = 497
7
b = 1768
8
p = 9739
9
10
P = (493, 5564)
11
Q = (1539, 4742)
12
R = (4403,5202)
13
14
15
16
17
# Define zero
18
O = (0, 0)
19
20
# If P = O, then P + Q = Q
21
if P == O:
22
return Q
23
# If Q = O, then P + Q = P
24
if Q == O:
25
return P
26
27
# Otherwise, write P = (x1, y1) and Q = (x2, y2)
28
x1, y1 = P[0], P[1]
29
x2, y2 = Q[0], Q[1]
30
31
# If x1 = x2 and y1 = -y2, then P + Q = O
32
if x1 == x2 and y1 == -y2:
33
return O
34
35
# Otherwise, if P ≠ Q: λ = (y2 - y1) / (x2 - x1)
36
if P != Q:
37
lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
38
# If P = Q: λ = (3 * x1**2 + a) / 2 * y1
39
else:
40
lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p
41
42
# x3 = λ**2 - x1 - x2, y3 = λ *( x1 - x3) - y1
43
x3 = (lam**2 - x1 - x2) % p
44
y3 = (lam * (x1 - x3) - y1) % p
45
46
# P + Q = (x3, y3)
47
summation = (x3, y3)
48
49
return summation
50
51
#--------Testing--------#
52
53
# X = (5274, 2841)
54
# Y = (8669, 740)
55
56
57
58
# S = P + P + Q + R
59
60
print(S)
Copied!

## Scalar Multiplication

### Algorithm

Input:
$P$
in
$E(F_p)$
and an integer
$n > 0$
.
1. 1.
Set
$Q = P$
and
$R = O$
.
2. 2.
Loop while
$n > 0$
.
• If
$n \equiv 1 \mod 2$
, set
$R = R + Q$
.
• Set
$Q = 2Q$
and
$n = \left\lfloor n/2 \right\rfloor$
.
• If
$n > 0$
, continue with loop at Step 2.
3. 3.
Return the point
$R$
, which equals
$nP$
.

### Implementation

1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse
3
4
#--------Data--------#
5
6
a = 497
7
b = 1768
8
p = 9739
9
10
P = (2339, 2213)
11
12
#--------Functions--------#
13
14
15
# Define zero
16
O = (0, 0)
17
18
# If P = O, then P + Q = Q
19
if P == O:
20
return Q
21
# If Q = O, then P + Q = P
22
if Q == O:
23
return P
24
25
# Otherwise, write P = (x1, y1) and Q = (x2, y2)
26
x1, y1 = P[0], P[1]
27
x2, y2 = Q[0], Q[1]
28
29
# If x1 = x2 and y1 = -y2, then P + Q = O
30
if x1 == x2 and y1 == -y2:
31
return O
32
33
# Otherwise, if P ≠ Q: λ = (y2 - y1) / (x2 - x1)
34
if P != Q:
35
lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
36
# If P = Q: λ = (3 * x1**2 + a) / 2 * y1
37
else:
38
lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p
39
40
# x3 = λ**2 - x1 - x2, y3 = λ *( x1 - x3) - y1
41
x3 = (lam**2 - x1 - x2) % p
42
y3 = (lam * (x1 - x3) - y1) % p
43
44
# P + Q = (x3, y3)
45
summation = (x3, y3)
46
47
return summation
48
49
def scalar_multiplication(n, P):
50
# Define zero
51
O = (0, 0)
52
# Set Q = P and R = O
53
Q, R = P, O
54
55
while n > 0:
56
# If n ≡ 1 mod 2, set R = R + Q
57
if n % 2 == 1:
58
R = point_addition(R, Q)
59
# Set Q = 2 Q and n = ⌊n/2⌋.
60
Q = point_addition(Q, Q)
61
n //= 2
62
63
return R
64
65
#--------Testing--------#
66
67
# X = (5323, 5438)
68
# print(scalar_multiplication(1337, X))
69
70
# Q = 7863 P
71
print(scalar_multiplication(7863, P))
Copied!

## Algorithm

1. 1.
Alice and Bob agree on a curve
$E$
, a prime
$p$
and a generator point
$G$
.
2. 2.
Alice generates a secret random integer
$n_A$
and calculates
$Q_A = n_AG$
.
3. 3.
Bob generates a secret random integer
$n_B$
and calculates
$Q_B = n_BG$
.
4. 4.
Alice sends Bob
$Q_A$
, and Bob sends Alice $Q_B$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate
$n{A/B}$
in reasonable time.
5. 5.
Alice then calculates
$n_AQ_B$
, and Bob calculates
$n_BQ_A$
.
Due to the associativity of scalar multiplication,
$S = n_AQ_B = n_BQ_A$
. Alice and Bob can use
$S$
as their shared secret.

## Implementation

1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse
3
from hashlib import sha1
4
5
#--------Data--------#
6
7
a = 497
8
b = 1768
9
p = 9739
10
11
G = (1804,5368)
12
Q_A = (815, 3190)
13
n_B = 1829
14
15
#--------Functions--------#
16
17
18
# Define zero
19
O = (0, 0)
20
21
# If P = O, then P + Q = Q
22
if P == O:
23
return Q
24
# If Q = O, then P + Q = P
25
if Q == O:
26
return P
27
28
# Otherwise, write P = (x1, y1) and Q = (x2, y2)
29
x1, y1 = P[0], P[1]
30
x2, y2 = Q[0], Q[1]
31
32
# If x1 = x2 and y1 = -y2, then P + Q = O
33
if x1 == x2 and y1 == -y2:
34
return O
35
36
# Otherwise, if P ≠ Q: λ = (y2 - y1) / (x2 - x1)
37
if P != Q:
38
lam = ((y2 - y1) * inverse(x2 - x1, p)) % p
39
# If P = Q: λ = (3 * x1**2 + a) / 2 * y1
40
else:
41
lam = ((3 * x1**2 + a) * inverse(2 * y1, p)) % p
42
43
# x3 = λ**2 - x1 - x2, y3 = λ *( x1 - x3) - y1
44
x3 = (lam**2 - x1 - x2) % p
45
y3 = (lam * (x1 - x3) - y1) % p
46
47
# P + Q = (x3, y3)
48
summation = (x3, y3)
49
50
return summation
51
52
def scalar_multiplication(n, P):
53
# Define zero
54
O = (0, 0)
55
# Set Q = P and R = O
56
Q, R = P, O
57
58
# Loop while n > 0
59
while n > 0:
60
# If n ≡ 1 mod 2, set R = R + Q
61
if n % 2 == 1:
62
R = point_addition(R, Q)
63
# Set Q = 2 Q and n = ⌊n/2⌋.
64
Q = point_addition(Q, Q)
65
n //= 2
66
67
return R
68
69
#--------ECDH--------#
70
71
S = scalar_multiplication(n_B, Q_A)
72
key = sha1(str(S[0]).encode()).hexdigest()
73
74
print(key)
Copied!

# Lab

CryptoHack – Elliptic Curves challenges
CryptoHack
Elliptic Curves - CryptoHack

# Reference

Elliptic curve
Wikipedia
Elliptic curve - Wikipedia
ECC2 (200) · Hackademia Writeups
picoCTF 2017 ECC 2 - 200 (Cryptography) Writeup