# ELLIPTIC CURVES - CRYPTOHACK
## Background Reading
The flag is the name we give groups with a commutative operation.
`flag: crypto{Abelian}`

## Point Negation
Để $P+Q=0$ thì $Q=-P$ tức là Q sẽ có tọa độ $Q(xP,-yP)$ => Q = (8045, -6936) = (8045, 2803).
`flag: cryto{8045, 2803}`
## Point Addition
Bài yêu cầu tính tổng $S = P + P + Q + R$ trên đường cong Elliptic E:$Y^{2} = X^{3} + 497X + 1768$, p: 9739 và P = (493, 5564), Q = (1539, 4742), R = (4403,5202).
Ta sẽ sử dụng thuật toán:

from Crypto.Util.number import inverse

def PointAdd(P, Q, a, b, p):
    x1 = P[0]
    y1 = P[1]

    x2 = Q[0]
    y2 = Q[1]

    lamda = 0

    if x1 == 0 and y1 == 0:
        return Q
    
    if x2 == 0 and y2 == 0:
        return P
    
    if x1 == x2 and y1 == -y2:
        return [0, 0]
    
    if x1 == x2 and y1 == y2:
        lamda = ((3 * pow(x1, 2) + a) * inverse(2*y1, p))%p
    
    if x1 != x2 and y1 != y2:
        lamda =  ((y2 - y1) * inverse(x2 - x1, p))%p

    x3 = (lamda**2 - x1 - x2)%p
    y3 = (lamda*(x1 - x3) - y1)%p

    return [x3, y3]

a = 497
b = 1768
p = 9739
P = [493, 5564]
Q = [1539, 4742]
R = [4403, 5202]
double_P = PointAdd(P, P, a, b, p)
S1 = PointAdd(double_P, Q, a, b, p)
S2 = PointAdd(S1, R, a, b, p)
print(S2)

`flag: (4215, 2162)`

## Scalar Multiplication
Bài yêu cầu tính $Q(x,y) = 7863P$ trên đường cong Elliptic E:$Y^{2} = X^{3} + 497X + 1768$, p: 9739 và P = (2339, 2213).
Ta sử dụng thuật toán:

from Crypto.Util.number import inverse

def PointAdd(P, Q, a, b, p):
    x1 = P[0]
    y1 = P[1]

    x2 = Q[0]
    y2 = Q[1]

    lamda = 0

    if x1 == 0 and y1 == 0:
        return Q
    
    if x2 == 0 and y2 == 0:
        return P
    
    if x1 == x2 and y1 == -y2:
        return [0, 0]
    
    if x1 == x2 and y1 == y2:
        lamda = ((3 * pow(x1, 2) + a) * inverse(2*y1, p))%p
    
    if x1 != x2 and y1 != y2:
        lamda =  ((y2 - y1) * inverse(x2 - x1, p))%p

    x3 = (lamda**2 - x1 - x2)%p
    y3 = (lamda*(x1 - x3) - y1)%p

    return [x3, y3]

def DAA(P, n, a, b, p):
    Q = P
    R = [0, 0]
    while n > 0:
        if n%2 == 1:
            R = PointAdd(R, Q, a, b, p)
        Q = PointAdd(Q, Q, a, b, p)
        n = n // 2
    
    return R

a = 497
b = 1768
p = 9739
P = [2339, 2213]
n = 7863
print(DAA(P, n, a, b, p))

`flag: crypto{9467, 2742}`

## Curves and Logs
Bài cho đường cong Elliptic E:$Y^{2} = X^{3} + 497X + 1768$, p: 9739, G: (1804,5368) và QA = (815, 3190), nB = 1829.
Bài yêu cầu tính $s(x, y) = nA*Qb = nB * Qa$ và dùng hàm hash SHA1 để tính giá trị của x chính là flag.

from Crypto.Util.number import inverse
from Crypto.Hash import SHA1

def PointAdd(P, Q, a, b, p):
    x1 = P[0]
    y1 = P[1]

    x2 = Q[0]
    y2 = Q[1]

    lamda = 0

    if x1 == 0 and y1 == 0:
        return Q
    
    if x2 == 0 and y2 == 0:
        return P
    
    if x1 == x2 and y1 == -y2:
        return [0, 0]
    
    if x1 == x2 and y1 == y2:
        lamda = ((3 * pow(x1, 2) + a) * inverse(2*y1, p))%p
    
    if x1 != x2 and y1 != y2:
        lamda =  ((y2 - y1) * inverse(x2 - x1, p))%p

    x3 = (lamda**2 - x1 - x2)%p
    y3 = (lamda*(x1 - x3) - y1)%p

    return [x3, y3]

def DAA(P, n, a, b, p):
    Q = P
    R = [0, 0]
    while n > 0:
        if n%2 == 1:
            R = PointAdd(R, Q, a, b, p)
        Q = PointAdd(Q, Q, a, b, p)
        n = n // 2
    
    return R

a = 497
b = 1768
p = 9739
Qa = [815, 3190]
nB = 1829
s = DAA(Qa, nB, a, b, p)
print(s)

`x: 7929`

`flag: crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}`

## Efficient Exchange
Bài cho đường cong Elliptic E:$Y^{2} = X^{3} + 497X + 1768$, p: 9739, G: (1804,5368) và q_x = 4726, nB = 6534 và file code:

def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

shared_secret = ?
iv = ?
ciphertext = ?

print(decrypt_flag(shared_secret, iv, ciphertext))

`'iv': 'cd9da9f1c60925922377ea952afc212c'`
`'encrypted_flag': 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'`
Để tìm được `flag` thì đầu tiên ta cần phải tìm được `s = shared_secret` mà bài chỉ cho q_x nên ta phải tìm `q_y` bằng cách thay `q_x` vào phương trình đường cong Elliptic.
Sau khi thu được $q_y^{2}$, do p = 3 mod 4 nên ta có thể áp dụng thuật toán:
với p = 9739, a = $q_y^{2}$, ta sẽ thu được (y, -y).
Sử dụng thuật toán `double and add` để tìm ra $s(x, y) = n_b * Q_a$. Thay giá trị x vừa tính được vào `shared_secret` và dùng file bài cho để lấy `flag`

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import inverse
import hashlib

def PointAdd(P, Q, a, b, p):
    x1 = P[0]
    y1 = P[1]

    x2 = Q[0]
    y2 = Q[1]

    lamda = 0

    if x1 == 0 and y1 == 0:
        return Q
    
    if x2 == 0 and y2 == 0:
        return P
    
    if x1 == x2 and y1 == -y2:
        return [0, 0]
    
    if x1 == x2 and y1 == y2:
        lamda = ((3 * pow(x1, 2) + a) * inverse(2*y1, p))%p
    
    if x1 != x2 and y1 != y2:
        lamda =  ((y2 - y1) * inverse(x2 - x1, p))%p

    x3 = (lamda**2 - x1 - x2)%p
    y3 = (lamda*(x1 - x3) - y1)%p

    return [x3, y3]

def DAA(P, n, a, b, p):
    Q = P
    R = [0, 0]
    while n > 0:
        if n%2 == 1:
            R = PointAdd(R, Q, a, b, p)
        Q = PointAdd(Q, Q, a, b, p)
        n = n // 2
    
    return R

def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

a = 497
b = 1768
p = 9739
G = [1804,5368]
q_x = 4726
nB = 6534
y2 = (q_x**3 + 497*q_x + 1768)%p
y = (y2**((p + 1)//4))%p
q_y1 = y
q_y2 = -y+p
Qa1 = [q_x, q_y1]
Qa2 = [q_x, q_y2]

s1 = DAA(Qa1, nB, a, b, p)
s2 = DAA(Qa2, nB, a, b, p)

shared_secret1 = s1[0]
shared_secret2 = s2[0]
iv = 'cd9da9f1c60925922377ea952afc212c'
ciphertext = 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'

print(decrypt_flag(shared_secret1, iv, ciphertext))

print(decrypt_flag(shared_secret2, iv, ciphertext))

`flag: crypto{3ff1c1ent_k3y_3xch4ng3}`