ECC - ctfnote.com

Elliptic Curve
An elliptic curve is a plane curve defined by an equation of the form:
y2=x3+ax+by^{2}=x^{3}+ax+by2=x3+ax+b
after a linear change of variables (aaa
 and bbb
 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:
​
Δ=−16(4a3+27b2)\Delta =-16(4a^{3}+27b^{2})Δ=−16(4a3+27b2)
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=(xP,yP)P = (x_P,y_P)P=(xP​,yP​)
, then P+(xP,xP+yP)=OP + (x_P, x_P+y_P) = OP+(xP​,xP​+yP​)=O
. In other word, −P=(xP,xP+yP)-P = (x_P, x_P+y_P)−P=(xP​,xP​+yP​)
.
Implementation
In this challenge we are given P=(8045,6936)P = (8045, 6936)P=(8045,6936)
, hence Q=−P=(8045,(8045+6936)mod  9739)=(8045,2803)Q = -P = (8045, (8045 + 6936) \mod 9739) = (8045, 2803)Q=−P=(8045,(8045+6936)mod9739)=(8045,2803)
​
Point Addition
Algorithm
1.If P=OP = OP=O
, then P+Q=QP + Q = QP+Q=Q
.
2.Otherwise, if Q=OQ = OQ=O
, then P+Q=PP + Q = PP+Q=P
.
3.Otherwise, write P=(x1,y1)P = (x_1, y_1)P=(x1​,y1​)
 and Q=(x2,y2)Q = (x_2, y_2)Q=(x2​,y2​)
.
4.If x1=x2x_1 = x_2x1​=x2​
 and y1=−y2y_1 = −y_2y1​=−y2​
, then P+Q=OP + Q = OP+Q=O
.
5.Otherwise:
if P≠QP \neq QP=Q
: λ=(y2−y1)/(x2−x1)\lambda = (y_2 - y_1) / (x_2 - x_1)λ=(y2​−y1​)/(x2​−x1​)
​
if P=QP = QP=Q
: λ=(3x12+a)/2y1\lambda = (3x_1^2 + a) / 2y_1λ=(3x12​+a)/2y1​
​
6.​x3=λ2−x1−x2x_3 = \lambda_2 − x_1 − x2x3​=λ2​−x1​−x2
 and y3=λ(x1−x3)−y1y_3 = \lambda(x_1 − x_3) − y_1y3​=λ(x1​−x3​)−y1​
​
7.​P+Q=(x3,y3)P + Q = (x_3, y_3)P+Q=(x3​,y3​)
​
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
#--------Addition--------#
15
​
16
def point_addition(P, Q):
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
# print(point_addition(X, Y))
56
# print(point_addition(X, X))
57
​
58
# S = P + P + Q + R
59
S = point_addition(point_addition(point_addition(P, P), Q), R)
60
print(S)
Copied!
Scalar Multiplication
Algorithm
Input: PPP
 in E(Fp)E(F_p)E(Fp​)
 and an integer n>0n > 0n>0
.
1.Set Q=PQ = PQ=P
 and R=OR = OR=O
.
2.Loop while n>0n > 0n>0
.
If n≡1mod  2n \equiv 1 \mod 2n≡1mod2
, set R=R+QR = R + QR=R+Q
.
Set Q=2QQ = 2QQ=2Q
 and n=⌊n/2⌋n = \left\lfloor n/2 \right\rfloorn=⌊n/2⌋
.
If n>0n > 0n>0
, continue with loop at Step 2.
3.Return the point RRR
, which equals nPnPnP
.
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
def point_addition(P, Q):
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!
Curves and Logs
Algorithm
1.Alice and Bob agree on a curve EEE
, a prime ppp
 and a generator point GGG
.
2.Alice generates a secret random integer nAn_AnA​
 and calculates QA=nAGQ_A = n_AGQA​=nA​G
.
3.Bob generates a secret random integer nBn_BnB​
 and calculates QB=nBGQ_B = n_BGQB​=nB​G
.
4.Alice sends Bob QAQ_AQA​
, and Bob sends Alice $Q_B$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculatenA/B n{A/B}nA/B
 in reasonable time.
5.Alice then calculates nAQBn_AQ_BnA​QB​
, and Bob calculates nBQAn_BQ_AnB​QA​
.
Due to the associativity of scalar multiplication, S=nAQB=nBQAS = n_AQ_B = n_BQ_AS=nA​QB​=nB​QA​
. Alice and Bob can use SSS
 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
def point_addition(P, Q):
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

Low Private Exponent

Next - Crypto

Digital Signature

Last modified 1mo ago

Copy link

Contents

Elliptic Curve

Arithmetics on Elliptic Curves

Point Negation

Point Addition

Scalar Multiplication