ctfnote.com
Search
⌃K

ECC

Elliptic Curve Cryptography

Elliptic Curve

An elliptic curve is a plane curve defined by an equation of the form:
y2=x3+ax+by^{2}=x^{3}+ax+b
after a linear change of variables (
aa
 and
bb
 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})
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

Point Negation

Algorithm

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

Implementation

In this challenge we are given
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)
​

Point Addition

Algorithm

  1. 1.
    If
    P=OP = O
    , then
    P+Q=QP + Q = Q
    .
  2. 2.
    Otherwise, if
    Q=OQ = O
    , then
    P+Q=PP + Q = P
    .
  3. 3.
    Otherwise, write
    P=(x1,y1)P = (x_1, y_1)
     and
    Q=(x2,y2)Q = (x_2, y_2)
    .
  4. 4.
    If
    x1=x2x_1 = x_2
     and
    y1=−y2y_1 = −y_2
    , then
    P+Q=OP + Q = O
    .
  5. 5.
    Otherwise:
    • if
      P≠QP \neq Q
      :
      λ=(y2−y1)/(x2−x1)\lambda = (y_2 - y_1) / (x_2 - x_1)
      ​
    • if
      P=QP = Q
      :
      λ=(3x12+a)/2y1\lambda = (3x_1^2 + a) / 2y_1
      ​
  6. 6.
    ​
    x3=λ2−x1−x2x_3 = \lambda_2 − x_1 − x2
     and
    y3=λ(x1−x3)−y1y_3 = \lambda(x_1 − x_3) − y_1
    ​
  7. 7.
    ​
    P+Q=(x3,y3)P + Q = (x_3, y_3)
    ​

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:
PP
 in
E(Fp)E(F_p)
 and an integer
n>0n > 0
.
  1. 1.
    Set
    Q=PQ = P
     and
    R=OR = O
    .
  2. 2.
    Loop while
    n>0n > 0
    .
    • If
      n≡1mod  2n \equiv 1 \mod 2
      , set
      R=R+QR = R + Q
      .
    • Set
      Q=2QQ = 2Q
       and
      n=⌊n/2⌋n = \left\lfloor n/2 \right\rfloor
      .
    • If
      n>0n > 0
      , continue with loop at Step 2.
  3. 3.
    Return the point
    RR
    , which equals
    nPnP
    .

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

  1. 1.
    Alice and Bob agree on a curve
    EE
    , a prime
    pp
     and a generator point
    GG
    .
  2. 2.
    Alice generates a secret random integer
    nAn_A
     and calculates
    QA=nAGQ_A = n_AG
    .
  3. 3.
    Bob generates a secret random integer
    nBn_B
     and calculates
    QB=nBGQ_B = n_BG
    .
  4. 4.
    Alice sends Bob
    QAQ_A
    , and Bob sends Alice $$Q_B$$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate
    nA/B n{A/B}
     in reasonable time.
  5. 5.
    Alice then calculates
    nAQBn_AQ_B
    , and Bob calculates
    nBQAn_BQ_A
    .
Due to the associativity of scalar multiplication,
S=nAQB=nBQAS = n_AQ_B = n_BQ_A
. Alice and Bob can use
SS
 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

Elliptic curve
Wikipedia
Elliptic curve - Wikipedia
ECC2 (200) · Hackademia Writeups
picoCTF 2017 ECC 2 - 200 (Cryptography) Writeup
Previous
Low Private Exponent
Next - Cryptography
Digital Signature
Last modified 1yr ago